Effektive Suche nach funktionalen Abhängigkeiten in Datenbanken

Caching-Modelle für die Partitionierung

Im ersten Teil der Arbeit haben wir Caching-Schemata für die Klasse von Algorithmen entwickelt, die das Methode des Partitionenschnitts verwenden. Eine Partition für ein Attribut besteht aus einer Gruppe von Listen, wobei jede Liste die Zeilennummern mit denselben Werten für dieses Attribut enthält. Jede solche Liste wird als Cluster bezeichnet. Viele moderne Algorithmen verwenden Partitionen, um festzustellen, ob eine Abhängigkeit gehalten wird oder nicht, und halten sich dabei an das Lemma: Abhängigkeit wird gehalten, wenn . Hier wird die Partition bezeichnet und das Konzept der Partitionsgröße - die Anzahl der Cluster darin - verwendet. Algorithmen, die Partitionen verwenden, fügen bei Verletzung der Abhängigkeit zusätzliche Attribute in den linken Teil der Abhängigkeit ein und berechnen sie dann neu, indem sie den Schnitt der Partitionen durchführen. Dieser Vorgang wird in den Artikeln als Spezialisierung bezeichnet. Wir haben jedoch festgestellt, dass Partitionen für Abhängigkeiten, die erst nach mehreren Runden der Spezialisierung gehalten werden, aktiv wiederverwendet werden können, was die Laufzeit der Algorithmen erheblich verkürzen kann, da der Schnitt eine kostenintensive Operation ist. Daher haben wir eine Heuristik vorgeschlagen, die auf der Shannon-Entropie und der Ungewissheit von Genie basiert, sowie auf unserer Metrik, die wir als Umgekehrte Entropie bezeichnet haben. Sie ist eine geringfügige Modifikation der Shannon-Entropie und wächst mit zunehmender Einzigartigkeit des Datensatzes. Die vorgeschlagene Heuristik sieht wie folgt aus:

— Der Grad der Einzigartigkeit der kürzlich berechneten Partition

Hier — Grad der Einzigartigkeit einer kürzlich berechneten Partition , und ist die Median der Einzigartigkeitsstufen für einzelne Attribute. Alle drei oben beschriebenen Metriken wurden als Metrik der Einzigartigkeit getestet. Es fällt auch auf, dass die Heuristik zwei Modifikatoren enthält. Der erste gibt an, wie nahe die aktuelle Partition am Primärschlüssel ist und ermöglicht es in größerem Maße, diejenigen Partitionen zwischenzuspeichern, die weit vom potenziellen Schlüssel entfernt sind. Der zweite Modifikator ermöglicht es, die Cache-Auslastung zu überwachen und fördert damit die Aufnahme einer größeren Anzahl von Partitionen in den Cache, wenn Platz vorhanden ist. Die erfolgreiche Lösung dieses Problems erlaubte eine Beschleunigung des PYRO-Algorithmus um 10-40 Prozent, abhängig von dem Datensatz. Es ist erwähnenswert, dass der PYRO-Algorithmus in diesem Bereich am erfolgreichsten ist.

In der untenstehenden Abbildung sind die Ergebnisse der Anwendung der vorgeschlagenen Heuristik im Vergleich zum grundlegenden Ansatz des Cachings zu sehen, der auf dem Werfen einer Münze basiert. Die X-Achse ist logarithmisch.

Alternativer Ansatz zur Speicherung von Partitionen

Dann haben wir einen alternativen Ansatz zur Speicherung von Partitionen vorgeschlagen. Partitionen stellen eine Menge von Clustern dar, in denen die Nummern von Tuplen mit denselben Werten für bestimmte Attribute gespeichert sind. Diese Cluster können lange Sequenzen von Tuplennummern enthalten, beispielsweise wenn die Daten in der Tabelle sortiert sind. Daher haben wir ein Kompressionsschema für die Speicherung von Partitionen vorgeschlagen, nämlich die intervallbasierte Speicherung von Werten in den Clustern der Partitionen:

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Erster~Intervall}, underbrace{7, 8}_{Zweiter~Intervall}, 10}}\ downarrow{Kompression}\ pi(X) = {{underbrace{$, 1, 5}_{Erster~Intervall}, underbrace{7, 8}_{Zweiter~Intervall}, 10}}$$display$$

Diese Methode konnte den Speicherverbrauch während der Ausführung des TANE-Algorithmus um 1 bis 25 % reduzieren. Der TANE-Algorithmus ist ein klassischer Algorithmus zur Suche nach funktionalen Abhängigkeiten, der während seiner Ausführung Partitionen verwendet. Innerhalb der Praxis wurde der TANE-Algorithmus ausgewählt, da es wesentlich einfacher war, die intervallbasierte Speicherung zu implementieren als beispielsweise im PYRO, um zu bewerten, ob der vorgeschlagene Ansatz funktioniert. Die erhaltenen Ergebnisse sind in der untenstehenden Abbildung dargestellt. Die X-Achse ist logarithmisch.

Konferenz ADBIS-2019

Im Ergebnis der Studie im September 2019 habe ich einen Artikel präsentiert Intelligentes Caching zur effizienten Entdeckung funktionaler Abhängigkeiten Auf der 23. Europäischen Konferenz über Fortschritte in Datenbanken und Informationssystemen (ADBIS-2019) bemerkte Bernhard Thalheim, eine bedeutende Persönlichkeit im Bereich der Datenbanken, während seiner Präsentation meine Arbeit. Die Forschungsergebnisse bildeten die Grundlage meiner Masterarbeit im Fachbereich Mathematik und Mechanik an der Universität St. Petersburg, im Rahmen derer beide vorgeschlagenen Ansätze (Caching und Kompression) in die beiden Algorithmen TANE und PYRO integriert wurden. Die Ergebnisse zeigten, dass die vorgeschlagenen Ansätze universell sind, da bei beiden Algorithmen und beiden Ansätzen eine signifikante Reduktion des Speicherverbrauchs sowie eine erhebliche Verkürzung der Laufzeit der Algorithmen beobachtet wurde.

Quelle: habr.com