Kardinalität (Datenbanken)

Die Kardinalität einer Menge ist die Anzahl der Elemente in dieser Menge. Im Kontext relationaler Datenbanken wird der Terminus häufig verwendet, da eine Datenbanktabelle auch als eine Menge von Zeilen aufgefasst werden kann. Spalten und Zeilen einer Datenbanktabelle können jeweils auch als eine Menge von Attributwerten aufgefasst werden. Die Kardinalität einer Datenbanktabelle (Relation) ist die Anzahl der Zeilen in dieser Tabelle.^[1] Die Kardinalität einer Spalte (Attribut) einer Datenbanktabelle ist die Anzahl der verschiedenen Attributwerte in dieser Spalte.^[2] Man spricht auch von „geringer Kardinalität“ wenn das Verhältnis der Anzahl verschiedener Werte, die in einer Spalte vorkommen, zur Gesamtzeilenzahl der Tabelle gering ist. Aus diesem Grund wird gelegentlich auch abweichend von der eigentlichen Bedeutung des Begriffs Kardinalität dieses Verhältnis als Kardinalität einer Spalte bezeichnet. ^[3]

Siehe auch die von den o. g. Definitionen abweichende Bedeutung von Kardinalität eines Beziehungstyps in der Datenbankmodellierung.

Spaltenkardinalität

Kategorien

Je geringer die Kardinalität der Spalte einer Datenbanktabelle, desto mehr Duplikate oder NULL-Werte gibt es in dieser Spalte. Man unterscheidet drei Kategorien, deren Grenzen fließend sind:

• Hohe Kardinalität: Weisen Spalten mit sehr wenigen Duplikaten oder mit eindeutigen Werten auf. Spalten mit hoher Kardinalität sind beispielsweise solche, die Benutzernamen oder Benutzer-IDs speichern.
• Niedrige Kardinalität: Weisen Spalten auf, deren Werte sehr viele Duplikate haben, beispielsweise solche mit Status-Flags oder Klassifizierungen in wenige Kategorien, wie zum Beispiel die Angabe des Geschlechts.
• Normale Kardinalität: Weisen Spalten auf, die nicht in die beiden oben genannten Kategorien fallen.

Kardinalität und Selektivität

Der Anfrageoptimierer relationaler Datenbanken muss die Selektivität bei Datenbankabfragen abschätzen, um auf die Größe der Zwischenergebnisse schließen und damit einen optimalen Auswertungsplan finden zu können. Dabei spielen Kardinalitäten eine wichtige Rolle.

Im Folgenden dafür ein Beispiel; es sei eine Tabelle KUNDEN mit der Spalte INHALT gegeben, in der 100 Einträge vorhanden sind; ferner wird angenommen, dass für die Attributwerte eine Gleichverteilung vorliegt. Nun werde mit der Abfragesprache SQL folgende Abfrage gestellt:

select *
from   KUNDEN
where  INHALT = X

Für die Selektivität sel dieser Abfrage gilt, wenn das Prädikat INHALT = X zu TRUE evaluiert: $sel= \dfrac{1}{c}$, wobei c der Anzahl der unterschiedlichen Attributwerte in der Spalte INHALT entspricht (jede c-te Zeile qualifiziert sich für die Ergebnismenge). Ferner gilt:

• Ist die Kardinalität der Spalte INHALT hoch, dann ist die Selektivität der Abfrage stark ausgeprägt. Wenn beispielsweise in Spalte INHALT alle Attributwerte verschieden sind (Schlüsseleigenschaft), es also keine Duplikate gibt, dann ist $sel= \dfrac{1}{100}$, sel ist damit ein kleiner Wert. In diesem Fall qualifiziert sich genau eine Zeile für die Ergebnismenge, falls das Prädikat INHALT = X zu TRUE evaluiert.
• Ist die Kardinalität der Spalte INHALT niedrig, dann ist die Selektivität der Abfrage eher schwach ausgeprägt. Wenn beispielsweise nur zwei verschiedene Werte in der Spalte INHALT gespeichert sind, dann ist $sel= \dfrac{1}{2}$. In diesem Fall qualifizieren sich genau 50 Zeilen für die Ergebnismenge, falls das Prädikat INHALT = X zu TRUE evaluiert.

Dieses Beispiel betrachtet Spezialfälle, die Schlüsseleigenschaft einer Spalte oder die Gleichverteilung der Attributwerte einer Spalte kann im Allgemeinen nicht vorausgesetzt werden. Deshalb muss der Anfrageoptimierer mithilfe von statistischen Werten die Kardinalitäten abschätzen, um einer Abfrage einen Selektivitätsfaktor zuordnen zu können.^[4]

Kardinalität und Indizes

Zum Indexieren von Spalten mit hoher Kardinalität eignen sich B-Baum-Indexe gut, beim Indexieren von Spalten mit niedriger Kardinalität sind Bitmapindexe passend^[5]. Allerdings ist für die Effizienz der Indexnutzung immer die Selektivität einer Abfrage ausschlaggebend – Bitmapindizes sind zwar bei Daten mit niedriger Kardinalität besser geeignet als B-Baum-Indizes, aber bei Abfragen mit schwacher Selektivität nicht sonderlich effizient, denn Abfragen mit schwacher Selektivität können im Allgemeinen nicht effizient mithilfe von Indizes ausgeführt werden.

Einzelnachweise

1. ↑ Alfons Kemper, André Eickler: Datenbanksysteme. Eine Einführung. Oldenbourg, München 2004, ISBN 3-486-27392-2, Seite 254
2. ↑ Definition der Spaltenkardinalität bei Microsoft, abgerufen am 27. Mai 2010
3. ↑ Definition der Spaltenkardinalität bei der Online-Dokumentation der Oracle-DB, abgerufen am 6. März 2010
4. ↑ Alfons Kemper, André Eickler: Datenbanksysteme. Eine Einführung. Oldenbourg, München 2004, ISBN 3-486-27392-2, Seite 255
5. ↑ Erläuterung zu Bitmap-Indexen bei der Online-Dokumentation der Oracle-DB, abgerufen am 6. März 2010