Hasso-Plattner-InstitutSDG am HPI
Hasso-Plattner-InstitutDSG am HPI
Login
 

Martin Schirneck

"Aufzählungsalgorithmen für das Data Profiling"

Data Proling ist die Erhebung von Metadaten über relationale Datenbanken. Gerade in Zeiten stetig wachsender Datenmengen ist es wichtig diesen Prozess zu automatisieren und dafür eziente Algorithmen bereitzustellen. Eine wichtige Klasse von Metadaten sind Abhängigkeiten zwischen verschiedenen Spalten, wie eindeutige Spaltenkombinationen (UCCs) - eine Art Fingerabdruck für die gesamte Datenbank - sowie funktionale Abhängigkeiten (FDs) und Inklusionsabhängigkeiten (INDs). Für diese gibt es zwei wesentliche algorithmische Probleme. Beim Detektionsproblem soll entschieden werden, ob eine Datenbank
eine Abhängigkeit eines bestimmt Typs und Gröÿe aufweist; beim Entdeckungsproblem müssen alle gültigen Abhängigkeiten aufgezählt werden.

In der Doktorarbeit untersuchen wir zunächst die Komplexität dieser Probleme. Dabei nehmen sogenannte Hitting Sets in Hypergraphen eine zentrale Stellung ein. Wir beweisen, dass die Datenbankprobleme für UCCs, FDs und INDs alle auf die ein oder andere Art äquivalent zu einer Variante des Hitting-Set-Problems sind. Das Finden von Hitting Sets ist in der theoretischen Informatik ein schweres, aber gut erforschtes Problem. Das bedeutet einerseits, dass das Detektieren und Entdecken von Abhängigkeiten in Datenbanken ebenfalls schwer ist; andererseits können wir aber auch viele Techniken aus der Theorie der Hypergraphen auf den Datenbankbereich übertragen.

Diese Erkenntnis nutzen wir in der weiteren Arbeit, um neuartige Entdeckungsalgorithmen für eindeutige Spaltenkombinationen zu entwickeln und zu analysieren. Dabei wird der Ressourcenverbrauch, wie z.Bsp. die Laufzeit oder Speicherauslastung, sowohl theoretisch abgeschätzt als auch in Experimenten mit Datenbanken aus der Praxis empirisch gemessen. Für den höchstentwickelsten unserer Algorithmen Hitting Set Enumeration with Partial Information and Validation (HPIValid; dt. etwa Aufzählung von Hitting Sets mit partieller Information und Validierung) zeigen wir auÿerdem, dass er den aktuellen Stand der Technik im Bereich der UCC-Entdeckung deutlich übertrit. HPIValid kann zudem Datenbanken verarbeiten, für die Data Proling zuvor unmöglich war.