TY - THES A1 - Shaabani, Nuhad T1 - On discovering and incrementally updating inclusion dependencies N2 - In today's world, many applications produce large amounts of data at an enormous rate. Analyzing such datasets for metadata is indispensable for effectively understanding, storing, querying, manipulating, and mining them. Metadata summarizes technical properties of a dataset which rang from basic statistics to complex structures describing data dependencies. One type of dependencies is inclusion dependency (IND), which expresses subset-relationships between attributes of datasets. Therefore, inclusion dependencies are important for many data management applications in terms of data integration, query optimization, schema redesign, or integrity checking. So, the discovery of inclusion dependencies in unknown or legacy datasets is at the core of any data profiling effort. For exhaustively detecting all INDs in large datasets, we developed S-indd++, a new algorithm that eliminates the shortcomings of existing IND-detection algorithms and significantly outperforms them. S-indd++ is based on a novel concept for the attribute clustering for efficiently deriving INDs. Inferring INDs from our attribute clustering eliminates all redundant operations caused by other algorithms. S-indd++ is also based on a novel partitioning strategy that enables discording a large number of candidates in early phases of the discovering process. Moreover, S-indd++ does not require to fit a partition into the main memory--this is a highly appreciable property in the face of ever-growing datasets. S-indd++ reduces up to 50% of the runtime of the state-of-the-art approach. None of the approach for discovering INDs is appropriate for the application on dynamic datasets; they can not update the INDs after an update of the dataset without reprocessing it entirely. To this end, we developed the first approach for incrementally updating INDs in frequently changing datasets. We achieved that by reducing the problem of incrementally updating INDs to the incrementally updating the attribute clustering from which all INDs are efficiently derivable. We realized the update of the clusters by designing new operations to be applied to the clusters after every data update. The incremental update of INDs reduces the time of the complete rediscovery by up to 99.999%. All existing algorithms for discovering n-ary INDs are based on the principle of candidate generation--they generate candidates and test their validity in the given data instance. The major disadvantage of this technique is the exponentially growing number of database accesses in terms of SQL queries required for validation. We devised Mind2, the first approach for discovering n-ary INDs without candidate generation. Mind2 is based on a new mathematical framework developed in this thesis for computing the maximum INDs from which all other n-ary INDs are derivable. The experiments showed that Mind2 is significantly more scalable and effective than hypergraph-based algorithms. N2 - Viele Anwendungen produzieren mit schnellem Tempo große Datenmengen. Die Profilierung solcher Datenmengen nach ihren Metadaten ist unabdingbar für ihre effektive Verwaltung und ihre Analyse. Metadaten fassen technische Eigenschaften einer Datenmenge zusammen, welche von einfachen Statistiken bis komplexe und Datenabhängigkeiten beschreibende Strukturen umfassen. Eine Form solcher Abhängigkeiten sind Inklusionsabhängigkeiten (INDs), die Teilmengenbeziehungen zwischen Attributen der Datenmengen ausdrücken. Dies macht INDs wichtig für viele Anwendungen wie Datenintegration, Anfragenoptimierung, Schemaentwurf und Integritätsprüfung. Somit ist die Entdeckung von INDs in unbekannten Datenmengen eine zentrale Aufgabe der Datenprofilierung. Ich entwickelte einen neuen Algorithmus namens S-indd++ für die IND-Entdeckung in großen Datenmengen. S-indd++ beseitigt die Defizite existierender Algorithmen für die IND-Entdeckung und somit ist er performanter. S-indd++ berechnet INDs sehr effizient basierend auf einem neuen Clustering der Attribute. S-indd++ wendet auch eine neue Partitionierungsmethode an, die das Verwerfen einer großen Anzahl von Kandidaten in früheren Phasen des Entdeckungsprozesses ermöglicht. Außerdem setzt S-indd++ nicht voraus, dass eine Datenpartition komplett in den Hauptspeicher passen muss. S-indd++ reduziert die Laufzeit der IND-Entdeckung um bis 50 %. Keiner der IND-Entdeckungsalgorithmen ist geeignet für die Anwendung auf dynamischen Daten. Zu diesem Zweck entwickelte ich das erste Verfahren für das inkrementelle Update von INDs in häufig geänderten Daten. Ich erreichte dies bei der Reduzierung des Problems des inkrementellen Updates von INDs auf dem inkrementellen Update des Attribute-Clustering, von dem INDs effizient ableitbar sind. Ich realisierte das Update der Cluster beim Entwurf von neuen Operationen, die auf den Clustern nach jedem Update der Daten angewendet werden. Das inkrementelle Update von INDs reduziert die Zeit der statischen IND-Entdeckung um bis 99,999 %. Alle vorhandenen Algorithmen für die n-ary-IND-Entdeckung basieren auf dem Prinzip der Kandidatengenerierung. Der Hauptnachteil dieser Methode ist die exponentiell wachsende Anzahl der SQL-Anfragen, die für die Validierung der Kandidaten nötig sind. Zu diesem Zweck entwickelte ich Mind2, den ersten Algorithmus für n-ary-IND-Entdeckung ohne Kandidatengenerierung. Mind2 basiert auf einem neuen mathematischen Framework für die Berechnung der maximalen INDs, von denen alle anderen n-ary-INDs ableitbar sind. Die Experimente zeigten, dass Mind2 wesentlich skalierbarer und leistungsfähiger ist als die auf Hypergraphen basierenden Algorithmen. T2 - Beitrag zur Entdeckung und inkrementellen Aktualisierung von Inklusionsabhängigkeiten KW - Inclusion Dependency KW - Data Profiling KW - Data Mining KW - Algorithms KW - Inclusion Dependency Discovery KW - Incrementally Inclusion Dependencies Discovery KW - Metadata Discovery KW - S-indd++ KW - Mind2 KW - Change Data Capture KW - Incremental Discovery KW - Big Data KW - Data Integration KW - Foreign Keys KW - Dynamic Data KW - Foreign Keys Discovery KW - Data Profiling KW - Data Mining KW - Algorithmen KW - Inklusionsabhängigkeiten KW - Inklusionsabhängigkeiten Entdeckung KW - Datenintegration KW - Metadaten Entdeckung Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-471862 ER - TY - THES A1 - Kruse, Sebastian T1 - Scalable data profiling T1 - Skalierbares Data Profiling BT - distributed discovery and analysis of structural metadata BT - Entdecken und Analysieren struktureller Metadaten N2 - Data profiling is the act of extracting structural metadata from datasets. Structural metadata, such as data dependencies and statistics, can support data management operations, such as data integration and data cleaning. Data management often is the most time-consuming activity in any data-related project. Its support is extremely valuable in our data-driven world, so that more time can be spent on the actual utilization of the data, e. g., building analytical models. In most scenarios, however, structural metadata is not given and must be extracted first. Therefore, efficient data profiling methods are highly desirable. Data profiling is a computationally expensive problem; in fact, most dependency discovery problems entail search spaces that grow exponentially in the number of attributes. To this end, this thesis introduces novel discovery algorithms for various types of data dependencies – namely inclusion dependencies, conditional inclusion dependencies, partial functional dependencies, and partial unique column combinations – that considerably improve over state-of-the-art algorithms in terms of efficiency and that scale to datasets that cannot be processed by existing algorithms. The key to those improvements are not only algorithmic innovations, such as novel pruning rules or traversal strategies, but also algorithm designs tailored for distributed execution. While distributed data profiling has been mostly neglected by previous works, it is a logical consequence on the face of recent hardware trends and the computational hardness of dependency discovery. To demonstrate the utility of data profiling for data management, this thesis furthermore presents Metacrate, a database for structural metadata. Its salient features are its flexible data model, the capability to integrate various kinds of structural metadata, and its rich metadata analytics library. We show how to perform a data anamnesis of unknown, complex datasets based on this technology. In particular, we describe in detail how to reconstruct the schemata and assess their quality as part of the data anamnesis. The data profiling algorithms and Metacrate have been carefully implemented, integrated with the Metanome data profiling tool, and are available as free software. In that way, we intend to allow for easy repeatability of our research results and also provide them for actual usage in real-world data-related projects. N2 - Data Profiling bezeichnet das Extrahieren struktureller Metadaten aus Datensätzen. Stukturelle Metadaten, z.B. Datenabhängigkeiten und Statistiken, können bei der Datenverwaltung unterstützen. Tatsächlich beansprucht das Verwalten von Daten, z.B. Datenreinigung und -integration, in vielen datenbezogenen Projekten einen Großteil der Zeit. Die Unterstützung solcher verwaltenden Aktivitäten ist in unserer datengetriebenen Welt insbesondere deswegen sehr wertvoll, weil so mehr Zeit auf die eigentlich wertschöpfende Arbeit mit den Daten verwendet werden kann, z.B. auf das Erstellen analytischer Modelle. Allerdings sind strukturelle Metadaten in den meisten Fällen nicht oder nur unvollständig vorhanden und müssen zunächst extahiert werden. Somit sind effiziente Data-Profiling-Methoden erstrebenswert. Probleme des Data Profiling sind in der Regel sehr berechnungsintensiv: Viele Datenabhängigkeitstypen spannen einen exponentiell in der Anzahl der Attribute wachsenden Suchraum auf. Aus diesem Grund beschreibt die vorliegende Arbeit neue Algorithmen zum Auffinden verschiedener Arten von Datenabhängigkeiten – nämlich Inklusionsabhängigkeiten, bedingter Inklusionsabhängigkeiten, partieller funktionaler Abhängigkeiten sowie partieller eindeutiger Spaltenkombinationen – die bekannte Algorithmen in Effizienz und Skalierbarkeit deutlich übertreffen und somit Datensätze verarbeiten können, an denen bisherige Algorithmen gescheitert sind. Um die Nützlichkeit struktureller Metadaten für die Datenverwaltung zu demonstrieren, stellt diese Arbeit des Weiteren das System Metacrate vor, eine Datenbank für strukturelle Metadaten. Deren besondere Merkmale sind ein flexibles Datenmodell; die Fähigkeit, verschiedene Arten struktureller Metadaten zu integrieren; und eine umfangreiche Bibliothek an Metadatenanalysen. Mithilfe dieser Technologien führen wir eine Datenanamnese unbekannter, komplexer Datensätze durch. Insbesondere beschreiben wir dabei ausführlicher, wie Schemata rekonstruiert und deren Qualität abgeschätzt werden können. Wir haben oben erwähnte Data-Profiling-Algorithmen sowie Metacrate sorgfältig implementiert, mit dem Data-Profiling-Programm Metanome integriert und stellen beide als freie Software zur Verfügung. Dadurch wollen wir nicht nur die Nachvollziehbarkeit unserer Forschungsergebnisse möglichst einfach gestalten, sondern auch deren Einsatz in der Praxis ermöglichen. KW - data profiling KW - metadata KW - inclusion dependencies KW - functional dependencies KW - distributed computation KW - metacrate KW - Data Profiling KW - Metadaten KW - Inklusionsabhängigkeiten KW - funktionale Abhängigkeiten KW - verteilte Berechnung KW - Metacrate Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-412521 ER -