Einführung in funktionale Abhängigkeiten

In diesem Artikel sprechen wir über funktionale Abhängigkeiten in Datenbanken – was sie sind, wo sie angewendet werden und welche Algorithmen es zur Auffindung gibt.

Wir betrachten funktionale Abhängigkeiten im Kontext von relationalen Datenbanken. Grob gesagt, werden in solchen Datenbanken Informationen in Form von Tabellen gespeichert. Dabei verwenden wir Näherungsbegriffe, die in der strengen relationalen Theorie nicht austauschbar sind: Die Tabelle selbst bezeichnen wir als Relation, die Spalten als Attribute (ihr Set ist das Schema der Relation), und die Menge der Werte einer Zeile für eine Teilmenge von Attributen nennen wir Tupel.

Zum Beispiel in der obigen Tabelle, (Benson, M, M organ) ist ein Tupel bezüglich der Attribute (Patient, Geschlecht, Arzt).
Formell wird dies wie folgt notiert: [Patient, Geschlecht, Arzt] = (Benson, M, M organ).
Nun können wir das Konzept der funktionalen Abhängigkeit (FÄ) einführen:

Definition 1. Eine Relation R erfüllt die FÄ X → Y (wo X, Y ⊆ R) genau dann, wenn für alle Tupel , ∈ R gilt: wenn [X] = [X], dann [Y] = [Y]. In diesem Fall sagt man, dass X (Determinante oder die definierenden Attribute) Y (abhängige Menge) funktional bestimmt.

Anders ausgedrückt, das Vorhandensein der FÄ X → Y bedeutet, dass wenn wir zwei Tupel in R haben und sie sich in den Attributen X, dann werden sie sich auch in den Attributen Y.
übereinstimmen. Lassen Sie uns nun der Reihe nach vorgehen. Betrachten wir die Attribute Patient und Geschlecht für die wir wissen möchten, ob es Abhängigkeiten zwischen ihnen gibt oder nicht. Für eine solche Menge von Attributen können folgende Abhängigkeiten bestehen:

1. Patient → Geschlecht
2. Geschlecht → Patient

Laut obiger Definition muss, damit die erste Abhängigkeit bestehen bleibt, jedem einzigartigen Wert in der Spalte Patient genau ein Wert in der Spalte Geschlechtentsprechen. Und für die Beispiel-Tabelle ist das tatsächlich so. Umgekehrt funktioniert es jedoch nicht, das heißt, die zweite Abhängigkeit gilt nicht, und das Attribut Geschlecht ist kein Determinant für Patient.Ähnlich kann man feststellen, dass die Abhängigkeit Arzt → Patientverletz wird, da der Wert Robin für dieses Attribut mehrere verschiedene Werte hat – Ellis und Graham..

Auf diese Weise ermöglichen funktionale Abhängigkeiten die Bestimmung der bestehenden Verbindungen zwischen Mengen von Attributen der Tabelle. Daher werden wir von nun an die interessantesten Zusammenhänge betrachten, genauer gesagt solche X → Y, die sind:

• nicht trivial, das heißt, der rechte Teil der Abhängigkeit ist keine Teilmenge des linken (Y ̸⊆ X);
• minimal, das heißt, es gibt keine solche Abhängigkeit Z → Y, dass Z ⊂ X.

Die bisher betrachteten Abhängigkeiten waren streng, das heißt, sie ließen keine Verstöße in der Tabelle zu. Neben diesen gibt es jedoch auch solche, die eine gewisse Inkonsistenz zwischen den Werten der Tuples zulassen. Diese Abhängigkeiten werden in eine eigene Klasse ausgegliedert, als angenähert bezeichnet und dürfen in einer bestimmten Anzahl von Tuples verletzt werden. Diese Anzahl wird durch den Wert des maximalen Fehlers emax reguliert. Zum Beispiel kann ein Fehleranteil = 0,01 bedeuten, dass die Abhängigkeit in 1 % der vorhandenen Tuples in der betrachteten Attributmenge verletzt werden kann. Das heißt, bei 1000 Datensätzen können maximal 10 Tuples die funktionale Abhängigkeit verletzen. Wir werden jedoch eine etwas andere Metrik betrachten, die auf paarweise unterschiedlichen Werten der verglichenen Tuples basiert. Für die Abhängigkeit X → Y in der Beziehung r wird sie so berechnet:

Berechnen wir den Fehler für Arzt → Patient aus dem obigen Beispiel. Wir haben zwei Tuples, deren Werte sich im Attribut Patientunterscheiden, aber in übereinstimmen.: [Doktor] = (Doktor, Patient) und [Doktor] = (Robin, EllisRobin, Graham, ). Nach der Definition des Fehlers müssen wir alle konfliktierenden Paare berücksichtigen, was bedeutet, dass es zwei davon geben wird: (, ) und deren Inversion (

). Setzen wir in die Formel ein und erhalten wir:

Der zweite Typ sind Abhängigkeiten, die „versteckte“ Daten und zuvor unbekannte Zusammenhänge zwischen Attributen darstellen. Das heißt, über solche Abhängigkeiten wurde beim Design nicht nachgedacht, und sie werden erst für einen bestehenden Datensatz entdeckt, um dann auf der Grundlage vieler identifizierter funktionaler Abhängigkeiten irgendwelche Schlüsse über die gespeicherten Informationen zu ziehen. Genau mit solchen Abhängigkeiten arbeiten wir. Ein ganzes Gebiet des Data Minings mit verschiedenen Suchtechniken und darauf basierenden Algorithmen befasst sich damit. Lassen Sie uns herausfinden, wie gefundene funktionale Abhängigkeiten (genau oder annähernd) in bestimmten Daten nützlich sein können.

Heute gehört die Datenbereinigung zu den Hauptanwendungsbereichen von Abhängigkeiten. Sie umfasst die Entwicklung von Prozessen zur Identifizierung von „schmutzigen Daten“ und deren anschließender Korrektur. Zu den typischen Vertretern „schmutziger Daten“ zählen Duplikate, Fehler in Daten oder Tippfehler, fehlende Werte, veraltete Daten, überflüssige Leerzeichen und Ähnliches.

Beispiel für einen Fehler in den Daten:

Beispiel für Duplikate in den Daten:

Nehmen wir an, wir haben eine Tabelle und einen Satz von funktionalen Abhängigkeiten, die erfüllt werden müssen. Die Datenbereinigung in diesem Fall bedeutet, die Daten so zu ändern, dass die funktionalen Abhängigkeiten korrekt werden. Dabei sollte die Anzahl der Änderungen minimal sein (für dieses Verfahren gibt es eigene Algorithmen, auf die wir in diesem Artikel nicht näher eingehen werden). Im Folgenden wird ein Beispiel für eine solche Datenumwandlung präsentiert. Links ist die ursprüngliche Beziehung, in der offensichtlich die erforderlichen funktionalen Abhängigkeiten nicht erfüllt sind (ein Beispiel für einen Verstoß gegen eine der Funktionalitäten ist rot hervorgehoben). Rechts ist die aktualisierte Beziehung dargestellt, bei der die grünen Zellen geänderte Werte anzeigen. Nach Durchführung dieses Verfahrens wurden die erforderlichen Abhängigkeiten beibehalten.

Ein weiterer beliebter Anwendungsbereich ist das Design von Datenbanken. Hier sollte an die normalen Formen und die Normalisierung erinnert werden. Normalisierung ist der Prozess der Anpassung einer Beziehung an eine bestimmte Menge von Anforderungen, von denen jede nach ihrer eigenen normalen Form definiert wird. Wir werden die Anforderungen verschiedener normaler Formen nicht im Detail ausführen (dies wird in jedem Einsteigerbuch zu Datenbanken behandelt), sondern lediglich feststellen, dass jede dieser Formen auf ihre eigene Weise das Konzept der funktionalen Abhängigkeiten nutzt. Schließlich stellen funktionale Abhängigkeiten im Wesentlichen Einschränkungen der Integrität dar, die bei der Gestaltung einer Datenbank berücksichtigt werden (im Kontext dieser Aufgabe werden funktionale Abhängigkeiten manchmal als Superkeys bezeichnet).

Betrachten wir ihre Anwendung für die vier normalen Formen im Bild unten. Erinnern wir uns daran, dass die Boyce-Codd-Normalform strenger ist als die dritte Form, aber weniger streng als die vierte. Letztere betrachten wir jetzt nicht, da für ihre Anwendung ein Verständnis der mehrwertigen Abhängigkeiten erforderlich ist, die in diesem Artikel für uns nicht von Interesse sind.

Ein weiteres Gebiet, in dem Abhängigkeiten Anwendung fanden, ist die Reduzierung der Dimension des Merkmalsraums in Aufgaben wie dem Aufbau eines naiven Bayesschen Klassifikators, der Identifizierung signifikanter Merkmale und der Reparametrisierung eines Regressionsmodells. In den Originalartikeln wird diese Aufgabe als Bestimmung überflüssiger Merkmale (feature redundancy) und relevanter Merkmale (feature relevancy) [5, 6] bezeichnet, und sie wird aktiv mit der Nutzung von Konzepten aus der Datenbanktechnik gelöst. Mit dem Erscheinen solcher Arbeiten können wir sagen, dass es heute eine Nachfrage nach Lösungen gibt, die es ermöglichen, Datenbanken, Analysen und die Umsetzung der oben genannten Optimierungsprobleme in einem einzigen Werkzeug zu vereinen [7, 8, 9].

Für die Suche nach funktionalen Abhängigkeiten in Datensätzen gibt es zahlreiche Algorithmen (sowohl moderne als auch weniger moderne). Diese Algorithmen können in drei Gruppen unterteilt werden:

• Algorithmen, die algebraische Gitter durchlaufen (Lattice traversal algorithms)
• Algorithmen, die auf der Suche nach konsistenten Werten basieren (Difference- and agree-set algorithms)
• Algorithmen, die auf paarweisen Vergleichen basieren (Dependency induction algorithms)

Eine kurze Beschreibung jedes Algorithmustyps ist in der folgenden Tabelle dargestellt:


Mehr über diese Klassifizierung kann man [4] lesen. Im Folgenden sind Beispiele für Algorithmen für jeden der Typen aufgeführt:

Derzeit tauchen neue Algorithmen auf, die mehrere Ansätze zur Suche nach funktionalen Abhängigkeiten kombinieren. Beispiele für solche Algorithmen sind Pyro [2] und HyFD [3]. Eine Analyse ihrer Funktionsweise ist in den folgenden Artikeln dieser Reihe vorgesehen. In diesem Artikel werden wir nur die grundlegenden Konzepte und das Lemma erläutern, die notwendig sind, um die Techniken zur Identifizierung von Abhängigkeiten zu verstehen.

Lassen Sie uns einfach beginnen – mit dem difference- und agree-set, die im zweiten Typ der Algorithmen verwendet werden. Das Difference-set ist eine Menge von Tupeln, die sich in den Werten unterscheiden, während das agree-set im Gegenteil Tupel mit übereinstimmenden Werten darstellt. Es ist zu beachten, dass wir hier nur den linken Teil der Abhängigkeit betrachten.

Ein weiteres wichtiges Konzept, das bereits erwähnt wurde, ist die algebraische Lattice. Da viele moderne Algorithmen dieses Konzept verwenden, müssen wir verstehen, was es bedeutet.

Um das Konzept der Lattice einzuführen, ist es notwendig, die Definition einer partiell geordneten Menge (oder partially ordered set, abgekürzt – poset) zu haben.

Definition 2. Eine Menge S ist partiell geordnet durch die binäre Relation ⩽, wenn für alle a, b, c ∈ S die folgenden Eigenschaften erfüllt sind:

1. Reflexivität, d.h. a ⩽ a
2. Antisymmetrie, d.h. wenn a ⩽ b und b ⩽ a, dann ist a = b
3. Transitivität, d.h. aus a ⩽ b und b ⩽ c folgt, dass a ⩽ c

Eine solche Relation wird als Relation (nichtstrikter) partieller Ordnung bezeichnet, und die Menge selbst ist eine partiell geordnete Menge. Formale Bezeichnung: ⟨S, ⩽⟩.

Ein einfaches Beispiel für eine partiell geordnete Menge ist die Menge aller natürlichen Zahlen N mit der üblichen Ordnung ⩽. Es ist nicht schwer zu überprüfen, dass alle notwendigen Axiome erfüllt sind.

Ein gehaltvolleres Beispiel. Betrachten wir die Menge aller Teilmengen {1, 2, 3}, geordnet nach der Relation der Einschlussbeziehung ⊆. Tatsächlich erfüllt diese Relation alle Bedingungen einer partiellen Ordnung, daher ist ⟨P({1, 2, 3}), ⊆⟩ eine partiell geordnete Menge. Im folgenden Bild ist die Struktur dieser Menge dargestellt: Wenn von einem Element aus durch Pfeile zu einem anderen Element gegangen werden kann, dann stehen sie in einer Ordnung.

Wir benötigen noch zwei einfache Definitionen aus dem Bereich der Mathematik – Supremum und Infimum.

Definition 3. Sei ⟨S, ⩽⟩ eine partielle Ordnung, A ⊆ S. Die obere Grenze von A ist ein Element u ∈ S, so dass ∀x ∈ S: x ⩽ u. Sei U die Menge aller oberen Grenzen von S. Wenn es in U ein kleinstes Element gibt, wird es als Supremum bezeichnet und als sup A notiert.

Analog wird das Konzept der genauen unteren Grenze eingeführt.

Definition 4. Sei ⟨S, ⩽⟩ eine partielle Ordnung, A ⊆ S. Die untere Grenze von A ist ein Element l ∈ S, so dass ∀x ∈ S: l ⩽ x. Sei L die Menge aller unteren Grenzen von S. Wenn es in L ein größtes Element gibt, wird es als Infimum bezeichnet und als inf A notiert.

Betrachten wir als Beispiel die oben angegebene partielle Ordnung ⟨P ({1, 2, 3}), ⊆⟩ und finden wir darin Supremum und Infimum:

Jetzt können wir die Definition einer algebraischen Lattice formulieren.

Definition 5. Sei ⟨P, ⩽⟩ eine partielle Ordnung, so dass jede zweielementige Teilmenge genaue obere und untere Grenzen hat. Dann wird P als algebraische Lattice bezeichnet. Dabei wird sup{x, y} als x ∨ y notiert, und inf {x, y} als x ∧ y.

Überprüfen wir, ob unser Arbeitsbeispiel ⟨P ({1, 2, 3}), ⊆⟩ eine Lattice ist. Tatsächlich gilt für alle a, b ∈ P ({1, 2, 3}), dass a∨b = a∪b und a∧b = a∩b. Zum Beispiel betrachten wir die Mengen {1, 2} und {1, 3} und finden deren Infimum und Supremum. Wenn wir sie schneiden, erhalten wir die Menge {1}, die das Infimum darstellt. Das Supremum erhalten wir durch deren Vereinigung – {1, 2, 3}.

In den Algorithmen zur Entdeckung von funktionalen Abhängigkeiten wird der Suchraum oft in Form einer Lattice dargestellt, wo Mengen mit einem Element (lese erste Ebene der Suchlattice, wo die linke Seite der Abhängigkeiten aus einem Attribut besteht) jeweils ein Attribut der ursprünglichen Relation darstellen.
Zu Beginn werden Abhängigkeiten der Form ∅ → betrachtet. Einzelattribut. Dieser Schritt erlaubt es, zu bestimmen, welche Attribute primäre Schlüssel sind (für solche Attribute gibt es keine Determinanten, weshalb die linke Seite leer ist). Danach bewegen sich solche Algorithmen aufwärts in der Lattice. Dabei ist zu beachten, dass die Lattice nicht vollständig durchlaufen werden muss, das heißt, wenn eine gewünschte maximale Größe der linken Seite eingegeben wird, wird der Algorithmus nicht weiter als zu dieser Größe fortschreiten.

Im Bild unten wird gezeigt, wie man ein algebraisches Raster bei der Suche nach FZ verwenden kann. Hier stellt jede Kante (X, XY) eine Abhängigkeit dar X → Y. Zum Beispiel haben wir die erste Ebene durchlaufen und wissen, dass die Abhängigkeit A → B (wir stellen dies durch eine grüne Verbindung zwischen den Knoten dar A und B). Das bedeutet, dass wir beim weiteren Fortschreiten im Raster nach oben die Abhängigkeit A, C → B, weil sie nicht mehr minimal sein wird, nicht überprüfen müssen. Entsprechend würden wir sie auch nicht überprüfen, wenn die Abhängigkeit C → B.

vorhanden wäre. Darüber hinaus verwenden in der Regel alle modernen Algorithmen zur Suche nach FZ eine Datenstruktur namens Partition (im Original — stripped partition [1]). Die formale Definition einer Partition lautet wie folgt:

Definition 6. Sei X ⊆ R eine Menge von Attributen für die Relation r. Ein Cluster ist eine Menge von Indizes von Tupeln aus r, die denselben Wert für X haben, d.h. c(t) = {i|ti[X] = t[X]}. Eine Partition ist eine Menge von Clustern, die Cluster der Einzel Länge ausschließt:

Einfach gesagt, stellt die Partition für das Attribut X eine Menge von Listen dar, wobei jede Liste die Zeilennummern mit denselben Werten für Xenthält. In der modernen Literatur wird die Struktur, die Partitionen darstellt, als Position List Index (PLI) bezeichnet. Cluster der Einzel Länge werden zum Zweck der Kompression von PLI ausgeschlossen, da dies Cluster sind, die nur die Nummer des Satzes mit einem einzigartigen Wert enthalten, der immer leicht festgestellt werden kann.

Betrachten wir ein Beispiel. Gehen wir zurück zu derselben Tabelle mit Patienten und erstellen wir Partitionen für die Spalten Patient und Geschlecht (links ist eine neue Spalte hinzugekommen, in der die Zeilennummern der Tabelle markiert sind):

Dabei wäre gemäß Definition die Partition für die Spalte Patient tatsächlich leer, da Einzelcluster von der Partition ausgeschlossen werden.

Partitionen können über mehrere Attribute erhalten werden. Es gibt dafür zwei Möglichkeiten: Entweder geht man durch die Tabelle und erstellt die Partition sofort für alle erforderlichen Attribute, oder man erstellt sie durch die Schnittoperation von Partitionen über eine Teilmenge von Attributen. Die Algorithmen zur Suche nach FZ verwenden die zweite Variante.

Einfach gesagt, um beispielsweise eine Partition für die Spalten ABCzu erhalten, kann man die Partitionen für AC und B (oder jede andere Menge nicht überlappender Teilmengen) und sie untereinander schneiden. Der Schnittbefehl zweier Partitionen hebt Cluster mit der größten Länge hervor, die in beiden Partitionen gemeinsam sind.

Lassen Sie uns ein Beispiel betrachten:

Im ersten Fall haben wir eine leere Partition erhalten. Wenn man sich die Tabelle ansieht, sieht man tatsächlich, dass es keine identischen Werte in zwei Attributen gibt. Wenn wir jedoch die Tabelle etwas modifizieren (Fall rechts), erhalten wir bereits einen nicht leeren Schnitt. Dabei enthalten die Zeilen 1 und 2 tatsächlich identische Werte in den Attributen. Geschlecht und Doktor.

Als Nächstes benötigen wir den Begriff der Partitionsgröße. Formal:

Einfacher ausgedrückt, die Größe der Partition ist die Anzahl der Cluster, die in die Partition eingehen (denken wir daran, dass einzelne Cluster nicht in die Partition aufgenommen werden!):

Jetzt können wir eines der Schlüsseltheoreme definieren, das für die vorgegebenen Partitionen es ermöglicht festzustellen, ob eine Abhängigkeit besteht oder nicht:

Theorem 1. Die Abhängigkeit A, B → C besteht, wenn und nur wenn

Laut dem Theorem sind vier Schritte erforderlich, um zu bestimmen, ob eine Abhängigkeit besteht:

1. Berechnen Sie die Partition für die linke Seite der Abhängigkeit
2. Berechnen Sie die Partition für die rechte Seite der Abhängigkeit
3. Berechnen Sie das Produkt der ersten und zweiten Schritte
4. Vergleichen Sie die Größen der Partitionen, die im ersten und dritten Schritt erhalten wurden.

Im Folgenden finden Sie ein Beispiel zur Überprüfung, ob die Abhängigkeit nach dem gegebenen Theorem besteht:

In diesem Artikel haben wir Konzepte wie funktionale Abhängigkeit, angenäherte funktionale Abhängigkeit erörtert, wo sie angewendet werden und welche Algorithmen zur Suche nach FZ existieren. Zudem haben wir grundlegende, aber wichtige Konzepte detailliert behandelt, die in modernen Algorithmen zur Suche nach FZ aktiv verwendet werden.

Literaturverweise:

1. Huhtala Y. et al. TANE: Ein effizienter Algorithmus zur Entdeckung funktionaler und approximativer Abhängigkeiten // The computer journal. – 1999. – Band 42. – Nr. 2. – S. 100-111.
2. Kruse S., Naumann F. Effiziente Entdeckung approximativer Abhängigkeiten // Proceedings of the VLDB Endowment. – 2018. – Band 11. – Nr. 7. – S. 759-772.
3. Papenbrock T., Naumann F. Ein hybrider Ansatz zur Entdeckung funktionaler Abhängigkeiten // Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – S. 821-833.
4. Papenbrock T. et al. Entdeckung funktionaler Abhängigkeiten: Eine experimentelle Auswertung von sieben Algorithmen // Proceedings of the VLDB Endowment. – 2015. – Band 8. – Nr. 10. – S. 1082-1093.
5. Kumar A. et al. Join oder nicht join?: Zweimal über Joins nachdenken, bevor Merkmale ausgewählt werden // Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – S. 19-34.
6. Abo Khamis M. et al. In-Datenbank-Lernen mit spärlichen Tensoren //Aktenschriften des 37. ACM SIGMOD-SIGACT-SIGAI Symposiums über die Grundsätze von Datenbanksystemen. – ACM, 2018. – S. 325-340.
7. Hellerstein J. M. et al. Die MADlib-Analytikbibliothek: oder MAD-Fähigkeiten, das SQL //Aktenschriften der VLDB-Stiftung. – 2012. – Bd. 5. – Nr. 12. – S. 1700-1711.
8. Qin C., Rusu F. Spekulative Annäherungen an teraskalige verteilte Gradientabstieg-Optimierung //Aktenschriften des vierten Workshops über Datenanalytik in der Cloud. – ACM, 2015. – S. 1.
9. Meng X. et al. Mllib: Maschinelles Lernen in Apache Spark //Das Journal für Forschungsarbeiten zum maschinellen Lernen. – 2016. – Bd. 17. – Nr. 1. – S. 1235-1241.

Autoren des Artikels: Anastasia Birillo, Forscherin bei JetBrains Research, Studentin im CS-Zentrum und Nikita Bobrov, Forscherin bei JetBrains Research

Quelle: habr.com