Einführung in funktionale Abhängigkeiten

In diesem Artikel werden wir über funktionale Abhängigkeiten in Datenbanken sprechen – was sie sind, wo sie verwendet werden und welche Algorithmen es gibt, um sie zu finden.

Wir werden funktionale Abhängigkeiten im Kontext relationaler Datenbanken betrachten. Grob gesagt werden in solchen Datenbanken Informationen in Form von Tabellen gespeichert. Als nächstes verwenden wir Näherungskonzepte, die in der strengen relationalen Theorie nicht austauschbar sind: Wir nennen die Tabelle selbst eine Relation, die Spalten - Attribute (ihre Menge - ein Beziehungsschema) und die Menge der Zeilenwerte für eine Teilmenge von Attributen - ein Tupel.

In der obigen Tabelle ist beispielsweise Folgendes zu sehen: (Benson, M, M-Orgel) ist ein Tupel von Attributen (Patient, Paul, Arzt).
Formeller lässt sich dies wie folgt formulieren: [Patient, Geschlecht, Arzt] = (Benson, M, M-Orgel).
Jetzt können wir das Konzept der funktionalen Abhängigkeit (FD) einführen:

Bestimmung 1. Die Beziehung R erfüllt das Bundesgesetz X → Y (wobei X, Y ⊆ R) genau dann, wenn für alle Tupel , ∈ R gilt: if [X] = [X] also [Y] = [J]. In diesem Fall sagen wir, dass X (die Determinante oder definierende Menge von Attributen) Y (die abhängige Menge) funktional bestimmt.

Mit anderen Worten, das Vorhandensein eines Bundesgesetzes X → Y. bedeutet das, wenn wir zwei Tupel haben R und sie stimmen in den Attributen überein X, dann stimmen sie in ihren Attributen überein Y.
Und jetzt der Reihe nach. Schauen wir uns die Attribute an Der Patient и Geschlecht wofür wir herausfinden wollen, ob es Abhängigkeiten zwischen ihnen gibt oder nicht. Für einen solchen Satz von Attributen können folgende Abhängigkeiten bestehen:

1. Patient → Geschlecht
2. Geschlecht → Patient

Wie oben definiert, muss jede einzelne Spalte einen eindeutigen Wert haben, damit die erste Abhängigkeit erhalten bleibt Der Patient Es muss nur ein Spaltenwert übereinstimmen Geschlecht. Und für die Beispieltabelle ist dies tatsächlich der Fall. Dies funktioniert jedoch nicht in die umgekehrte Richtung, das heißt, die zweite Abhängigkeit ist nicht erfüllt, und das Attribut Geschlecht ist keine Determinante für Geduldig. Ebenso, wenn wir die Abhängigkeit nehmen Arzt → Patient, können Sie sehen, dass es verletzt ist, da der Wert Rotkehlchen Dieses Attribut hat verschiedene Bedeutungen - Ellis und Graham.

Somit ermöglichen funktionale Abhängigkeiten die Ermittlung der bestehenden Beziehungen zwischen Mengen von Tabellenattributen. Von hier aus betrachten wir die interessantesten Zusammenhänge bzw. solche X → Y.was sie sind:

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

Die bisher betrachteten Abhängigkeiten waren streng, das heißt, sie sahen keine Verstöße in der Tabelle vor, aber darüber hinaus gibt es auch solche, die eine gewisse Inkonsistenz zwischen den Werten der Tupel zulassen. Solche Abhängigkeiten werden in einer separaten Klasse namens Approximation abgelegt und dürfen für eine bestimmte Anzahl von Tupeln verletzt werden. Dieser Betrag wird durch den Maximalfehlerindikator emax reguliert. Zum Beispiel die Fehlerquote = 0.01 kann bedeuten, dass die Abhängigkeit von 1 % der verfügbaren Tupel auf dem betrachteten Satz von Attributen verletzt werden kann. Das heißt, bei 1000 Datensätzen können maximal 10 Tupel gegen das Bundesgesetz verstoßen. Wir betrachten eine etwas andere Metrik, die auf paarweise unterschiedlichen Werten der verglichenen Tupel basiert. Für Sucht X → Y. auf Haltung r es wird so betrachtet:

Berechnen wir den Fehler für Arzt → Patient aus dem Beispiel oben. Wir haben zwei Tupel, deren Werte sich im Attribut unterscheiden Der Patient, aber zusammenfallen Arzt: [Arzt, Patient] = (Robin, Ellis) Und [Arzt, Patient] = (Robin, Graham). Nach der Definition eines Fehlers müssen wir alle widersprüchlichen Paare berücksichtigen, was bedeutet, dass es zwei davon geben wird: (, ) und seine Umkehrung (, ). Setzen wir es in die Formel ein und erhalten:

Versuchen wir nun, die Frage zu beantworten: „Warum ist das alles so?“ Tatsächlich sind die Bundesgesetze unterschiedlich. Der erste Typ sind die Abhängigkeiten, die vom Administrator in der Datenbankentwurfsphase festgelegt werden. Ihre Anzahl ist normalerweise gering, sie sind streng und die Hauptanwendung ist die Datennormalisierung und das relationale Schemadesign.

Der zweite Typ sind Abhängigkeiten, die „verborgene“ Daten und bisher unbekannte Beziehungen zwischen Attributen darstellen. Das heißt, solche Abhängigkeiten wurden zum Zeitpunkt des Entwurfs nicht berücksichtigt und für den vorhandenen Datensatz gefunden, sodass später anhand der vielen identifizierten Bundesgesetze Rückschlüsse auf die gespeicherten Informationen gezogen werden können. Genau mit diesen Abhängigkeiten arbeiten wir. Sie werden von einem ganzen Bereich des Data Mining mit verschiedenen darauf aufbauenden Suchtechniken und Algorithmen bearbeitet. Lassen Sie uns herausfinden, wie nützlich die gefundenen funktionalen Abhängigkeiten (exakt oder ungefähr) in beliebigen Daten sein können.

Eine der Hauptanwendungen von Abhängigkeiten ist heute die Datenbereinigung. Dabei geht es darum, Prozesse zu entwickeln, um „schmutzige Daten“ zu identifizieren und diese dann zu korrigieren. Prominente Beispiele für „schmutzige Daten“ sind Duplikate, Datenfehler oder Tippfehler, fehlende Werte, veraltete Daten, zusätzliche Leerzeichen und dergleichen.

Beispiel für einen Datenfehler:

Beispiel für Duplikate in Daten:

Wir haben zum Beispiel eine Tabelle und eine Reihe von Bundesgesetzen, die umgesetzt werden müssen. Bei der Datenbereinigung geht es in diesem Fall darum, die Daten so zu ändern, dass sie den Bundesgesetzen entsprechen. In diesem Fall sollte die Anzahl der Änderungen minimal sein (dieses Verfahren verfügt über eigene Algorithmen, auf die wir uns in diesem Artikel nicht konzentrieren). Nachfolgend finden Sie ein Beispiel für eine solche Datentransformation. Auf der linken Seite ist die ursprüngliche Beziehung zu sehen, in der offensichtlich die erforderlichen FLs nicht eingehalten werden (ein Beispiel für einen Verstoß gegen eine der FLs ist rot hervorgehoben). Auf der rechten Seite sehen Sie die aktualisierte Beziehung, wobei die grünen Zellen die geänderten Werte anzeigen. Nach diesem Vorgang wurde begonnen, die notwendigen Abhängigkeiten aufrechtzuerhalten.

Eine weitere beliebte Anwendung ist das Datenbankdesign. Hier lohnt es sich, an Normalformen und Normalisierung zu erinnern. Unter Normalisierung versteht man den Prozess, eine Beziehung mit einem bestimmten Satz von Anforderungen in Einklang zu bringen, von denen jede auf ihre eigene Weise durch die Normalform definiert wird. Wir werden nicht die Anforderungen verschiedener Normalformen beschreiben (dies wird in jedem Buch über einen Datenbankkurs für Anfänger getan), sondern nur darauf hinweisen, dass jede von ihnen das Konzept der funktionalen Abhängigkeiten auf ihre eigene Weise verwendet. Schließlich handelt es sich bei FLs von Natur aus um Integritätsbeschränkungen, die beim Entwurf einer Datenbank berücksichtigt werden (im Kontext dieser Aufgabe werden FLs manchmal auch Superkeys genannt).

Betrachten wir ihre Anwendung für die vier Normalformen im Bild unten. Denken Sie daran, dass die Boyce-Codd-Normalform strenger als die dritte Form, aber weniger streng als die vierte ist. Letzteres betrachten wir vorerst nicht, da seine Formulierung ein Verständnis mehrwertiger Abhängigkeiten erfordert, die für uns in diesem Artikel nicht interessant sind.

Ein weiterer Bereich, in dem Abhängigkeiten ihre Anwendung gefunden haben, ist die Reduzierung der Dimensionalität des Merkmalsraums bei Aufgaben wie der Erstellung eines naiven Bayes-Klassifikators, der Identifizierung signifikanter Merkmale und der Neuparametrisierung eines Regressionsmodells. In den Originalartikeln wird diese Aufgabe als Bestimmung der Redundanz- und Merkmalsrelevanz bezeichnet [5, 6] und durch den aktiven Einsatz von Datenbankkonzepten gelöst. Mit dem Aufkommen solcher Arbeiten können wir sagen, dass heute ein Bedarf an Lösungen besteht, die es uns ermöglichen, die Datenbank, Analyse und Implementierung der oben genannten Optimierungsprobleme in einem Tool zu kombinieren [7, 8, 9].

Es gibt viele Algorithmen (sowohl moderne als auch nicht so moderne) für die Suche nach Bundesgesetzen in einem Datensatz. Solche Algorithmen können in drei Gruppen unterteilt werden:

• Algorithmen, die die Durchquerung algebraischer Gitter verwenden (Gitterdurchquerungsalgorithmen)
• Algorithmen basierend auf der Suche nach vereinbarten Werten (Differenz- und Übereinstimmungs-Set-Algorithmen)
• Algorithmen basierend auf paarweisen Vergleichen (Abhängigkeitsinduktionsalgorithmen)

Eine kurze Beschreibung jedes Algorithmustyps finden Sie in der folgenden Tabelle:


Mehr zu dieser Klassifizierung können Sie lesen [4]. Nachfolgend finden Sie Beispiele für Algorithmen für jeden Typ:

Derzeit entstehen neue Algorithmen, die mehrere Ansätze zum Auffinden funktionaler Abhängigkeiten kombinieren. Beispiele für solche Algorithmen sind Pyro [2] und HyFD [3]. Eine Analyse ihrer Arbeit wird in den folgenden Artikeln dieser Reihe erwartet. In diesem Artikel werden wir nur die grundlegenden Konzepte und Lemmata untersuchen, die zum Verständnis der Techniken zur Abhängigkeitserkennung erforderlich sind.

Beginnen wir mit einem einfachen – Differenz- und Übereinstimmungssatz, der in der zweiten Art von Algorithmen verwendet wird. Differenzmenge ist eine Menge von Tupeln, die nicht die gleichen Werte haben, während Übereinstimmungsmenge im Gegenteil Tupel sind, die die gleichen Werte haben. Es ist erwähnenswert, dass wir in diesem Fall nur die linke Seite der Abhängigkeit betrachten.

Ein weiteres wichtiges Konzept, auf das wir oben gestoßen sind, ist das algebraische Gitter. Da viele moderne Algorithmen nach diesem Konzept arbeiten, müssen wir eine Vorstellung davon haben, was es ist.

Um das Konzept eines Gitters einzuführen, ist es notwendig, eine teilweise geordnete Menge (oder teilweise geordnete Menge, abgekürzt als Poset) zu definieren.

Bestimmung 2. Eine Menge S heißt durch die binäre Beziehung ⩽ teilweise geordnet, wenn für alle a, b, c ∈ S die folgenden Eigenschaften erfüllt sind:

1. Reflexivität, also a ⩽ a
2. Antisymmetrie, das heißt, wenn a ⩽ b und b ⩽ a, dann ist a = b
3. Transitivität, das heißt, für a ⩽ b und b ⩽ c folgt, dass a ⩽ c

Eine solche Beziehung wird als (lose) Teilordnungsbeziehung bezeichnet, und die Menge selbst wird als teilweise geordnete Menge bezeichnet. Formale Schreibweise: ⟨S, ⩽⟩.

Als einfachstes Beispiel einer teilweise geordneten Menge können wir die Menge aller natürlichen Zahlen N mit der üblichen Ordnungsrelation ⩽ nehmen. Es ist leicht zu überprüfen, ob alle notwendigen Axiome erfüllt sind.

Ein aussagekräftigeres Beispiel. Betrachten Sie die Menge aller Teilmengen {1, 2, 3}, geordnet nach der Inklusionsrelation ⊆. Tatsächlich erfüllt diese Beziehung alle Teilordnungsbedingungen, sodass ⟨P ({1, 2, 3}), ⊆⟩ eine teilweise geordnete Menge ist. Die folgende Abbildung zeigt die Struktur dieser Menge: Wenn ein Element durch Pfeile zu einem anderen Element erreicht werden kann, stehen sie in einer Ordnungsbeziehung.

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

Bestimmung 3. Sei ⟨S, ⩽⟩ eine teilweise geordnete Menge A ⊆ S. Die Obergrenze von A ist ein Element u ∈ S mit ∀x ∈ S: x ⩽ u. Sei U die Menge aller Obergrenzen von S. Wenn es in U ein kleinstes Element gibt, dann heißt es Supremum und wird mit sup A bezeichnet.

Das Konzept einer exakten Untergrenze wird auf ähnliche Weise eingeführt.

Bestimmung 4. Sei ⟨S, ⩽⟩ eine teilweise geordnete Menge A ⊆ S. Das Infimum von A ist ein Element l ∈ S mit ∀x ∈ S: l ⩽ x. Sei L die Menge aller unteren Schranken von S. Wenn es ein größtes Element in L gibt, dann heißt es Infimum und wird als inf A bezeichnet.

Betrachten Sie als Beispiel die obige teilweise geordnete Menge ⟨P ({1, 2, 3}), ⊆⟩ und finden Sie darin das Supremum und Infimum:

Jetzt können wir die Definition eines algebraischen Verbandes formulieren.

Bestimmung 5. Sei ⟨P,⩽⟩ eine teilweise geordnete Menge, so dass jede zweielementige Teilmenge eine Ober- und Untergrenze hat. Dann heißt P ein algebraischer Verband. In diesem Fall wird sup{x, y} als x ∨ y und inf {x, y} als x ∧ y geschrieben.

Überprüfen wir, ob unser Arbeitsbeispiel ⟨P ({1, 2, 3}), ⊆⟩ ein Verband ist. Tatsächlich gilt für jedes a, b ∈ P ({1, 2, 3}), a∨b = a∪b und a∧b = a∩b. Betrachten Sie beispielsweise die Mengen {1, 2} und {1, 3} und ermitteln Sie deren Infimum und Supremum. Wenn wir sie schneiden, erhalten wir die Menge {1}, die das Infimum darstellt. Wir erhalten das Supremum, indem wir sie kombinieren – {1, 2, 3}.

In Algorithmen zur Identifizierung physikalischer Probleme wird der Suchraum oft in Form eines Gitters dargestellt, wobei Sätze eines Elements (sprich die erste Ebene des Suchgitters, wo die linke Seite der Abhängigkeiten aus einem Attribut besteht) jedes Attribut darstellen der ursprünglichen Beziehung.
Zunächst betrachten wir Abhängigkeiten der Form ∅ → Einzelnes Attribut. Mit diesem Schritt können Sie bestimmen, welche Attribute Primärschlüssel sind (für solche Attribute gibt es keine Determinanten und daher ist die linke Seite leer). Darüber hinaus bewegen sich solche Algorithmen entlang des Gitters nach oben. Es ist erwähnenswert, dass nicht das gesamte Gitter durchlaufen werden kann, d. h. wenn die gewünschte maximale Größe der linken Seite an die Eingabe übergeben wird, dann wird der Algorithmus nicht über eine Ebene mit dieser Größe hinausgehen.

Die folgende Abbildung zeigt, wie ein algebraischer Verband bei der Suche nach einem FZ verwendet werden kann. Hier ist jede Kante (X, XY) stellt eine Abhängigkeit dar X → Y.. Wir haben zum Beispiel die erste Stufe bestanden und wissen, dass die Sucht bestehen bleibt A → B. (Wir werden dies als grüne Verbindung zwischen den Eckpunkten anzeigen A и B). Das bedeutet, dass wir die Abhängigkeit möglicherweise nicht überprüfen, wenn wir uns entlang des Gitters nach oben bewegen A, C → B, weil es nicht mehr minimal sein wird. Ebenso würden wir es nicht überprüfen, wenn die Abhängigkeit besteht C → B.

Darüber hinaus verwenden in der Regel alle modernen Algorithmen zur Suche nach Bundesgesetzen eine Datenstruktur wie eine Partition (in der Originalquelle - gestrippte Partition [1]). Die formale Definition einer Partition lautet wie folgt:

Bestimmung 6. Sei X ⊆ R eine Menge von Attributen für die Beziehung r. Ein Cluster ist eine Menge von Indizes von Tupeln in r, die denselben Wert für X haben, d. h. c(t) = {i|ti[X] = t[X]}. Eine Partition ist eine Gruppe von Clustern, mit Ausnahme von Clustern mit einer Einheitslänge:

Mit einfachen Worten: eine Partition für ein Attribut X ist eine Reihe von Listen, wobei jede Liste Zeilennummern mit denselben Werten für enthält X. In der modernen Literatur wird die Struktur, die Partitionen darstellt, als Positionslistenindex (PLI) bezeichnet. Cluster mit Einheitslänge sind für PLI-Komprimierungszwecke ausgeschlossen, da es sich um Cluster handelt, die nur eine Datensatznummer mit einem eindeutigen Wert enthalten, der immer leicht zu identifizieren ist.

Schauen wir uns ein Beispiel an. Kehren wir mit den Patienten zum selben Tisch zurück und bauen Partitionen für die Spalten Der Patient и Geschlecht (Links ist eine neue Spalte erschienen, in der die Tabellenzeilennummern markiert sind):

Darüber hinaus ist laut Definition die Partition für die Spalte Der Patient wird tatsächlich leer sein, da einzelne Cluster von der Partition ausgeschlossen sind.

Partitionen können durch mehrere Attribute erhalten werden. Und es gibt zwei Möglichkeiten, dies zu tun: Erstellen Sie durch Durchgehen der Tabelle eine Partition mit allen erforderlichen Attributen auf einmal oder erstellen Sie sie mithilfe der Operation der Schnittmenge von Partitionen mithilfe einer Teilmenge von Attributen. Suchalgorithmen für Bundesgesetze verwenden die zweite Option.

Mit einfachen Worten, um beispielsweise eine Partition nach Spalten zu erhalten ABC, können Sie Partitionen für übernehmen AC и B (oder jede andere Menge disjunkter Teilmengen) und schneiden sie miteinander. Die Operation der Schnittmenge zweier Partitionen wählt Cluster mit der größten Länge aus, die beiden Partitionen gemeinsam sind.

Schauen wir uns ein Beispiel an:

Im ersten Fall erhielten wir eine leere Partition. Schaut man sich die Tabelle genau an, erkennt man, dass es tatsächlich keine identischen Werte für die beiden Attribute gibt. Wenn wir die Tabelle leicht modifizieren (der Fall rechts), erhalten wir bereits einen nicht leeren Schnittpunkt. Darüber hinaus enthalten die Zeilen 1 und 2 tatsächlich die gleichen Werte für die Attribute Geschlecht и Arzt.

Als nächstes benötigen wir ein Konzept wie die Partitionsgröße. Formal:

Einfach ausgedrückt ist die Partitionsgröße die Anzahl der in der Partition enthaltenen Cluster (denken Sie daran, dass einzelne Cluster nicht in der Partition enthalten sind!):

Jetzt können wir eines der Schlüssellemmas definieren, das es uns für gegebene Partitionen ermöglicht, zu bestimmen, ob eine Abhängigkeit besteht oder nicht:

Lemma 1. Die Abhängigkeit A, B → C gilt genau dann, wenn

Um festzustellen, ob eine Abhängigkeit gilt, müssen dem Lemma zufolge vier Schritte ausgeführt werden:

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 aus dem ersten und zweiten Schritt
4. Vergleichen Sie die Größen der im ersten und dritten Schritt erhaltenen Partitionen

Unten sehen Sie ein Beispiel für die Überprüfung, ob die Abhängigkeit gemäß diesem Lemma gilt:

In diesem Artikel haben wir Konzepte wie funktionale Abhängigkeit und ungefähre funktionale Abhängigkeit untersucht, untersucht, wo sie verwendet werden und welche Algorithmen für die Suche nach physikalischen Funktionen existieren. Wir haben auch die grundlegenden, aber wichtigen Konzepte ausführlich untersucht, die in modernen Algorithmen zur Suche nach Bundesgesetzen aktiv verwendet werden.

Verweise:

1. Huhtala Y. et al. TANE: Ein effizienter Algorithmus zur Entdeckung funktionaler und ungefährer Abhängigkeiten //Das Computerjournal. – 1999. – T. 42. – Nr. 2. – S. 100–111.
2. Kruse S., Naumann F. Effiziente Entdeckung ungefährer Abhängigkeiten // Proceedings of the VLDB Endowment. – 2018. – T. 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 Bewertung von sieben Algorithmen //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Nr. 10. – S. 1082–1093.
5. Kumar A. et al. Beitreten oder nicht beitreten?: Vor der Funktionsauswahl zweimal über Beitritte nachdenken //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – S. 19–34.
6. Abo Khamis M. et al. Datenbankinternes Lernen mit spärlichen Tensoren //Vorträge des 37. ACM SIGMOD-SIGACT-SIGAI-Symposiums zu Prinzipien von Datenbanksystemen. – ACM, 2018. – S. 325–340.
7. Hellerstein JM et al. Die MADlib-Analysebibliothek: oder MAD-Kenntnisse, die SQL //Proceedings der VLDB-Stiftung. – 2012. – T. 5. – Nr. 12. – S. 1700-1711.
8. Qin C., Rusu F. Spekulative Approximationen für die Optimierung des verteilten Gradientenabstiegs im Teramaßstab //Vorträge des vierten Workshops zur Datenanalyse in der Cloud. – ACM, 2015. – S. 1.
9. Meng X. et al. Mllib: Maschinelles Lernen in Apache Spark //The Journal of Machine Learning Research. – 2016. – T. 17. – Nr. 1. – S. 1235–1241.

Artikelautoren: Anastasia Birillo, Forscher bei JetBrains-Forschung, Student des CS-Zentrums и Nikita Bobrov, Forscher bei JetBrains-Forschung

Source: habr.com