Finden Sie effizient funktionale Abhängigkeiten in Datenbanken

Das Auffinden funktionaler Abhängigkeiten in Daten wird in verschiedenen Bereichen der Datenanalyse eingesetzt: Datenbankverwaltung, Datenbereinigung, Datenbank-Reverse Engineering und Datenexploration. Über die Abhängigkeiten selbst haben wir bereits veröffentlicht Artikel Anastasia Birillo und Nikita Bobrov. Dieses Mal teilt Anastasia, eine Absolventin des Informatikzentrums in diesem Jahr, die Entwicklung dieser Arbeit als Teil der Forschungsarbeit, die sie am Zentrum verteidigte.

Aufgabenauswahl

Während meines Studiums am CS-Zentrum begann ich, mich eingehend mit Datenbanken zu beschäftigen, und zwar mit der Suche nach Funktions- und Differenzabhängigkeiten. Dieses Thema hing mit dem Thema meiner Studienarbeit an der Universität zusammen, sodass ich während der Arbeit an der Studienarbeit begann, Artikel über verschiedene Abhängigkeiten in Datenbanken zu lesen. Ich habe eine Rezension zu diesem Bereich geschrieben – eine meiner ersten Artikel auf Englisch und reichte es bei der SEIM-2017-Konferenz ein. Ich war sehr froh, als ich erfuhr, dass sie doch angenommen wurde, und beschloss, mich tiefer mit dem Thema zu befassen. Das Konzept selbst ist nicht neu – es wurde bereits in den 90er Jahren eingesetzt, wird aber auch heute noch in vielen Bereichen eingesetzt.

Während meines zweiten Semesters am Zentrum startete ich ein Forschungsprojekt zur Verbesserung von Algorithmen zum Auffinden funktionaler Abhängigkeiten. Sie arbeitete daran zusammen mit dem Doktoranden Nikita Bobrov von der St. Petersburg State University bei JetBrains Research.

Rechenkomplexität der Suche nach funktionalen Abhängigkeiten

Das Hauptproblem ist die Rechenkomplexität. Die Anzahl der möglichen minimalen und nicht trivialen Abhängigkeiten wird oben durch den Wert begrenzt Wo — Anzahl der Tabellenattribute. Die Betriebszeit der Algorithmen hängt nicht nur von der Anzahl der Attribute, sondern auch von der Anzahl der Zeilen ab. In den 90er Jahren konnten Suchalgorithmen für Bundesgesetze auf einem normalen Desktop-PC Datensätze mit bis zu 20 Attributen und Zehntausenden Zeilen in bis zu mehreren Stunden verarbeiten. Moderne Algorithmen, die auf Mehrkernprozessoren laufen, erkennen Abhängigkeiten für Datensätze, die aus Hunderten von Attributen (bis zu 200) und Hunderttausenden Zeilen in etwa gleichzeitig bestehen. Dies reicht jedoch nicht aus: Eine solche Zeit ist für die meisten realen Anwendungen nicht akzeptabel. Daher haben wir Ansätze entwickelt, um bestehende Algorithmen zu beschleunigen.

Caching-Schemata für Partitionskreuzungen

Im ersten Teil der Arbeit haben wir Caching-Schemata für eine Klasse von Algorithmen entwickelt, die die Partitionsschnittmethode verwenden. Eine Partition für ein Attribut ist eine Reihe von Listen, wobei jede Liste Zeilennummern mit denselben Werten für ein bestimmtes Attribut enthält. Jede dieser Listen wird als Cluster bezeichnet. Viele moderne Algorithmen verwenden Partitionen, um zu bestimmen, ob eine Abhängigkeit besteht oder nicht, und halten sich dabei an das Lemma: Abhängigkeit gehalten, wenn . Hier Es wird eine Partition festgelegt und das Konzept der Partitionsgröße verwendet – die Anzahl der darin enthaltenen Cluster. Algorithmen, die Partitionen verwenden, fügen bei Verletzung der Abhängigkeit zusätzliche Attribute auf der linken Seite der Abhängigkeit hinzu und berechnen sie dann neu, indem sie die Operation der Schnittmenge von Partitionen ausführen. Dieser Vorgang wird in den Artikeln als Spezialisierung bezeichnet. Wir haben jedoch festgestellt, dass Partitionen für Abhängigkeiten, die erst nach einigen Spezialisierungsrunden erhalten bleiben würden, aktiv wiederverwendet werden können, was die Laufzeit der Algorithmen erheblich verkürzen kann, da die Schnittoperation teuer ist.

Daher haben wir eine Heuristik vorgeschlagen, die auf Shannon-Entropie und Ginny-Unsicherheit basiert, sowie unserer Metrik, die wir Reverse Entropy nannten. Es handelt sich um eine geringfügige Modifikation der Shannon-Entropie, die mit zunehmender Einzigartigkeit des Datensatzes zunimmt. Die vorgeschlagene Heuristik lautet wie folgt:

Hier — Eindeutigkeitsgrad der kürzlich berechneten Partition Und ist der Median der Eindeutigkeitsgrade einzelner Attribute. Alle drei oben beschriebenen Metriken wurden als Eindeutigkeitsmetrik getestet. Sie können auch feststellen, dass die Heuristik zwei Modifikatoren enthält. Die erste gibt an, wie nah die aktuelle Partition am Primärschlüssel ist, und ermöglicht Ihnen, die Partitionen, die weit vom potenziellen Schlüssel entfernt sind, in größerem Umfang zwischenzuspeichern. Mit dem zweiten Modifikator können Sie die Cache-Belegung überwachen und dadurch das Hinzufügen weiterer Partitionen zum Cache fördern, wenn freier Speicherplatz verfügbar ist. Die erfolgreiche Lösung dieses Problems ermöglichte es uns, den PYRO-Algorithmus je nach Datensatz um 10–40 % zu beschleunigen. Es ist erwähnenswert, dass der PYRO-Algorithmus in diesem Bereich der erfolgreichste ist.

In der Abbildung unten sehen Sie die Ergebnisse der Anwendung der vorgeschlagenen Heuristik im Vergleich zu einem einfachen Münzwurf-Caching-Ansatz. Die X-Achse ist logarithmisch.

Eine alternative Möglichkeit, Partitionen zu speichern

Wir haben dann eine alternative Möglichkeit zum Speichern von Partitionen vorgeschlagen. Partitionen sind eine Reihe von Clustern, von denen jeder eine Anzahl von Tupeln mit identischen Werten für bestimmte Attribute speichert. Diese Cluster können lange Folgen von Tupelzahlen enthalten, beispielsweise wenn die Daten in einer Tabelle geordnet sind. Daher haben wir ein Komprimierungsschema zum Speichern von Partitionen vorgeschlagen, nämlich die Intervallspeicherung von Werten in Partitionsclustern:

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Erstes Intervall}, underbrace{7, 8}_{Zweites Intervall}, 10}}\ downarrow{ Komprimierung} \ pi(X) = {{underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$

Mit dieser Methode konnte der Speicherverbrauch während der Ausführung des TANE-Algorithmus von 1 auf 25 % gesenkt werden. Der TANE-Algorithmus ist ein klassischer Algorithmus zur Suche nach Bundesgesetzen; er verwendet bei seiner Arbeit Partitionen. Im Rahmen der Praxis wurde der TANE-Algorithmus gewählt, da sich darin die Intervallspeicherung wesentlich einfacher implementieren ließ als beispielsweise in PYRO, um zu bewerten, ob der vorgeschlagene Ansatz funktioniert. Die erzielten Ergebnisse sind in der folgenden Abbildung dargestellt. Die X-Achse ist logarithmisch.

Konferenz ADBIS-2019

Basierend auf den Forschungsergebnissen habe ich im September 2019 einen Artikel veröffentlicht Intelligentes Caching für eine effiziente Erkennung funktionaler Abhängigkeiten auf der 23. Europäischen Konferenz über Fortschritte in Datenbanken und Informationssystemen (ADBIS-2019). Während der Präsentation wurde die Arbeit von Bernhard Thalheim, einer bedeutenden Persönlichkeit auf dem Gebiet der Datenbanken, erwähnt. Die Forschungsergebnisse bildeten die Grundlage meiner Dissertation im Masterstudiengang Mathematik und Mechanik an der Staatlichen Universität St. Petersburg, bei der beide vorgeschlagenen Ansätze (Caching und Komprimierung) in beiden Algorithmen umgesetzt wurden: TANE und PYRO. Darüber hinaus zeigten die Ergebnisse, dass die vorgeschlagenen Ansätze universell sind, da bei beiden Algorithmen mit beiden Ansätzen eine deutliche Reduzierung des Speicherverbrauchs sowie eine deutliche Reduzierung der Betriebszeit der Algorithmen beobachtet werden konnte.

Source: habr.com