TY - GEN A1 - Kruse, Sebastian A1 - Kaoudi, Zoi A1 - Quiane-Ruiz, Jorge-Arnulfo A1 - Chawla, Sanjay A1 - Naumann, Felix A1 - Contreras-Rojas, Bertty T1 - Optimizing Cross-Platform Data Movement T2 - 2019 IEEE 35th International Conference on Data Engineering (ICDE) N2 - Data analytics are moving beyond the limits of a single data processing platform. A cross-platform query optimizer is necessary to enable applications to run their tasks over multiple platforms efficiently and in a platform-agnostic manner. For the optimizer to be effective, it must consider data movement costs across different data processing platforms. In this paper, we present the graph-based data movement strategy used by RHEEM, our open-source cross-platform system. In particular, we (i) model the data movement problem as a new graph problem, which we prove to be NP-hard, and (ii) propose a novel graph exploration algorithm, which allows RHEEM to discover multiple hidden opportunities for cross-platform data processing. Y1 - 2019 SN - 978-1-5386-7474-1 SN - 978-1-5386-7475-8 U6 - https://doi.org/10.1109/ICDE.2019.00162 SN - 1084-4627 SN - 1063-6382 SP - 1642 EP - 1645 PB - IEEE CY - New York ER - TY - GEN A1 - Kruse, Sebastian A1 - Kaoudi, Zoi A1 - Contreras-Rojas, Bertty A1 - Chawla, Sanjay A1 - Naumann, Felix A1 - Quiané-Ruiz, Jorge-Arnulfo T1 - RHEEMix in the data jungle BT - a cost-based optimizer for cross-platform systems T2 - Zweitveröffentlichungen der Universität Potsdam : Reihe der Digital Engineering Fakultät N2 - Data analytics are moving beyond the limits of a single platform. In this paper, we present the cost-based optimizer of Rheem, an open-source cross-platform system that copes with these new requirements. The optimizer allocates the subtasks of data analytic tasks to the most suitable platforms. Our main contributions are: (i) a mechanism based on graph transformations to explore alternative execution strategies; (ii) a novel graph-based approach to determine efficient data movement plans among subtasks and platforms; and (iii) an efficient plan enumeration algorithm, based on a novel enumeration algebra. We extensively evaluate our optimizer under diverse real tasks. We show that our optimizer can perform tasks more than one order of magnitude faster when using multiple platforms than when using a single platform. T3 - Zweitveröffentlichungen der Universität Potsdam : Reihe der Digital Engineering Fakultät - 22 KW - cross-platform KW - polystore KW - query optimization KW - data processing Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-519443 IS - 6 ER - TY - JOUR A1 - Kruse, Sebastian A1 - Kaoudi, Zoi A1 - Contreras-Rojas, Bertty A1 - Chawla, Sanjay A1 - Naumann, Felix A1 - Quiane-Ruiz, Jorge-Arnulfo T1 - RHEEMix in the data jungle BT - a cost-based optimizer for cross-platform systems JF - The VLDB Journal N2 - Data analytics are moving beyond the limits of a single platform. In this paper, we present the cost-based optimizer of Rheem, an open-source cross-platform system that copes with these new requirements. The optimizer allocates the subtasks of data analytic tasks to the most suitable platforms. Our main contributions are: (i) a mechanism based on graph transformations to explore alternative execution strategies; (ii) a novel graph-based approach to determine efficient data movement plans among subtasks and platforms; and (iii) an efficient plan enumeration algorithm, based on a novel enumeration algebra. We extensively evaluate our optimizer under diverse real tasks. We show that our optimizer can perform tasks more than one order of magnitude faster when using multiple platforms than when using a single platform. KW - Cross-platform KW - Polystore KW - Query optimization KW - Data processing Y1 - 2020 U6 - https://doi.org/10.1007/s00778-020-00612-x SN - 1066-8888 SN - 0949-877X VL - 29 IS - 6 SP - 1287 EP - 1310 PB - Springer CY - Berlin 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 -