Hasso-Plattner-Institut
Hasso-Plattner-Institut
  
Login
 

Thorsten Papenbrock

Data Profiling -Efficient Discovery of Dependencies

Data Profiling ist eine Disziplin der Informatik, die sich mit der Analyse von Datensätzen auf deren Metadaten beschäftigt. Die verschiedenen Typen von Metadaten reichen von einfachen Statistiken wie Tupelzahlen, Aggregationen und Wertverteilungen bis hin zu komplexen Strukturen, insbesondere lnklusionsabhängigkeiten (INDs), eindeutige Spaltenkombinationen (UCCs) und funktionale Abhängigkeiten (FDs). Diese Statistiken und Strukturen dienen, sofern vorhanden, dazu die Daten effizient zu speichern, zu lesen, zu andern und zu verstehen. Die meisten Datensätze stellen ihre Metadaten aber nicht explizit zur Verfügung, so dass Informatiker sie mittels Data Profiling bestimmen müssen. Während einfache Statistiken noch relativ schnell zu berechnen sind, stellen die komplexen Strukturen schwere, zumeist NP-vollständige Entdeckungsaufgaben dar. Es ist daher auch mit gutem Domänenwissen meist nicht möglich sie manuell zu entdecken. JI.us diesem Grund wurden verschiedenste Profiling Algorithmen entwickelt, die die Entdeckung automatisieren. Keiner dieser Algorithmen kann allerdings Datensatze von heutzutage typischer Größe verarbeiten, weil entweder der Ressourcenverbrauch oder die Rechenzeit effektive Grenzen überschreiten. 

In dieser Arbeit stellen wir neuartige Profiling Algorithmen vor, die automatisch die drei populärsten Typen komplexer Metadaten entdecken können, nämlich INDs, UCCs, und FDs, die alle unterschiedliche Formen von Schlüssel-Abhängigkeiten beschreiben. Die Aufgabe dieser Algorithmen ist es alle gültigen Vorkommen der drei Metadaten-Typen aus einer gegebenen relationalen Instanz zu extrahieren. Sie nutzen dazu bekannte Entdeckungstechniken aus verwandten Arbeiten und ergänzen diese um algorithmische Paradigmen wie Teile-und-Herrsche, hybrides Suchen, Progressivität, Speichersensibilität, Parallelisierung und zusätzliche Streichungsregeln. Unsere Experimente zeigen, dass die vorgeschlagenen Algorithmen um Größenordnungen schneller sind als alle verwandten Arbeiten und insbesondere nun Datensatze realer Größe, d.h. mehrerer Gigabyte Größe mit vernünftigem Speicher-und Zeitverbrauch verarbeiten können. 

Neben den Entdeckungsalgorithmen wurde in dieser Arbeit auch Metanome entwickelt, eine erweiterbare Profiling Plattform, die nicht nur unsere eigenen sondern auch viele weitere Algorithmen anderer Forscher integriert. Mit Metanome machen wir unsere Forschungsergebnisse fi.ir alle IT-Fachkräfte zuganglich, die ein modernes Data Profiling Werkzeug benötigen. Zusätzlich zur tatsachlichen Metadaten-Entdeckung bietet die Plattform Unterstützung bei der Bewertung und Visualisierung gefundener Metadaten. 

Alle syntaktisch korrekten Metadaten effizient finden zu können führt natürlicherweise zur Folgeaufgabe daraus nur die semantisch bedeutsamen Teile zu extrahieren. Das ist eine Herausforderung, weil zum einen die Mengen der gefundenen Metadaten extrem groß sein können und zum anderen die Entscheidung über die Anwendungsfall-spezifische semantische Relevanz einzelner Metadaten-Aussagen schwierig ist. Um zu zeigen, dass die Vollständigkeit der Metadaten sehr wertvoll für ihre Nutzung ist, veranschaulichen wir die effiziente und effektive Verarbeitung von FDs bei der Schema Normalisierung.