TY - THES A1 - Vitagliano, Gerardo T1 - Modeling the structure of tabular files for data preparation T1 - Modellierung der Struktur von Tabellarische Dateien für die Datenaufbereitung N2 - To manage tabular data files and leverage their content in a given downstream task, practitioners often design and execute complex transformation pipelines to prepare them. The complexity of such pipelines stems from different factors, including the nature of the preparation tasks, often exploratory or ad-hoc to specific datasets; the large repertory of tools, algorithms, and frameworks that practitioners need to master; and the volume, variety, and velocity of the files to be prepared. Metadata plays a fundamental role in reducing this complexity: characterizing a file assists end users in the design of data preprocessing pipelines, and furthermore paves the way for suggestion, automation, and optimization of data preparation tasks. Previous research in the areas of data profiling, data integration, and data cleaning, has focused on extracting and characterizing metadata regarding the content of tabular data files, i.e., about the records and attributes of tables. Content metadata are useful for the latter stages of a preprocessing pipeline, e.g., error correction, duplicate detection, or value normalization, but they require a properly formed tabular input. Therefore, these metadata are not relevant for the early stages of a preparation pipeline, i.e., to correctly parse tables out of files. In this dissertation, we turn our focus to what we call the structure of a tabular data file, i.e., the set of characters within a file that do not represent data values but are required to parse and understand the content of the file. We provide three different approaches to represent file structure, an explicit representation based on context-free grammars; an implicit representation based on file-wise similarity; and a learned representation based on machine learning. In our first contribution, we use the grammar-based representation to characterize a set of over 3000 real-world csv files and identify multiple structural issues that let files deviate from the csv standard, e.g., by having inconsistent delimiters or containing multiple tables. We leverage our learnings about real-world files and propose Pollock, a benchmark to test how well systems parse csv files that have a non-standard structure, without any previous preparation. We report on our experiments on using Pollock to evaluate the performance of 16 real-world data management systems. Following, we characterize the structure of files implicitly, by defining a measure of structural similarity for file pairs. We design a novel algorithm to compute this measure, which is based on a graph representation of the files' content. We leverage this algorithm and propose Mondrian, a graphical system to assist users in identifying layout templates in a dataset, classes of files that have the same structure, and therefore can be prepared by applying the same preparation pipeline. Finally, we introduce MaGRiTTE, a novel architecture that uses self-supervised learning to automatically learn structural representations of files in the form of vectorial embeddings at three different levels: cell level, row level, and file level. We experiment with the application of structural embeddings for several tasks, namely dialect detection, row classification, and data preparation efforts estimation. Our experimental results show that structural metadata, either identified explicitly on parsing grammars, derived implicitly as file-wise similarity, or learned with the help of machine learning architectures, is fundamental to automate several tasks, to scale up preparation to large quantities of files, and to provide repeatable preparation pipelines. N2 - Anwender müssen häufig komplexe Pipelines zur Aufbereitung von tabellarischen Dateien entwerfen, um diese verwalten und ihre Inhalte für nachgelagerte Aufgaben nutzen zu können. Die Komplexität solcher Pipelines ergibt sich aus verschiedenen Faktoren, u.a. (i) aus der Art der Aufbereitungsaufgaben, die oft explorativ oder ad hoc für bestimmte Datensätze durchgeführt werden, (ii) aus dem großen Repertoire an Werkzeugen, Algorithmen und Frameworks, die von den Anwendern beherrscht werden müssen, sowie (iii) aus der Menge, der Größe und der Verschiedenartigkeit der aufzubereitenden Dateien. Metadaten spielen eine grundlegende Rolle bei der Verringerung dieser Komplexität: Die Charakterisierung einer Datei hilft den Nutzern bei der Gestaltung von Datenaufbereitungs-Pipelines und ebnet darüber hinaus den Weg für Vorschläge, Automatisierung und Optimierung von Datenaufbereitungsaufgaben. Bisherige Forschungsarbeiten in den Bereichen Data Profiling, Datenintegration und Datenbereinigung konzentrierten sich auf die Extraktion und Charakterisierung von Metadaten über die Inhalte der tabellarischen Dateien, d.h. über die Datensätze und Attribute von Tabellen. Inhalts-basierte Metadaten sind für die letzten Phasen einer Aufbereitungspipeline nützlich, z.B. für die Fehlerkorrektur, die Erkennung von Duplikaten oder die Normalisierung von Werten, aber sie erfordern eine korrekt geformte tabellarische Eingabe. Daher sind diese Metadaten für die frühen Phasen einer Aufbereitungspipeline, d.h. für das korrekte Parsen von Tabellen aus Dateien, nicht relevant. In dieser Dissertation konzentrieren wir uns die Struktur einer tabellarischen Datei nennen, d.h. die Menge der Zeichen in einer Datei, die keine Datenwerte darstellen, aber erforderlich sind, um den Inhalt der Datei zu analysieren und zu verstehen. Wir stellen drei verschiedene Ansätze zur Darstellung der Dateistruktur vor: eine explizite Darstellung auf der Grundlage kontextfreier Grammatiken, eine implizite Darstellung auf der Grundlage von Dateiähnlichkeiten und eine erlernte Darstellung auf der Grundlage von maschinellem Lernen. In unserem ersten Ansatz verwenden wir die grammatikbasierte Darstellung, um eine Menge von über 3000 realen CSV-Dateien zu charakterisieren und mehrere strukturelle Probleme zu identifizieren, die dazu führen, dass Dateien vom CSV-Standard abweichen, z.B. durch inkonsistente Begrenzungszeichen oder dem Enthalten mehrere Tabellen in einer einzelnen Datei. Wir nutzen unsere Erkenntnisse aus realen Dateien und schlagen Pollock vor, einen Benchmark, der testet, wie gut Systeme unaufbereitete CSV-Dateien parsen. Wir berichten über unsere Experimente zur Verwendung von Pollock, in denen wir die Leistung von 16 realen Datenverwaltungssystemen bewerten. Anschließend charakterisieren wir die Struktur von Dateien implizit, indem wir ein Maß für die strukturelle Ähnlichkeit von Dateipaaren definieren. Wir entwickeln einen neuartigen Algorithmus zur Berechnung dieses Maßes, der auf einer Graphen-basierten Darstellung des Dateiinhalts basiert. Wir nutzen diesen Algorithmus und schlagen Mondrian vor, ein grafisches System zur Unterstützung der Benutzer bei der Identifizierung von Layout Vorlagen in einem Datensatz, d.h. von Dateiklassen, die die gleiche Struktur aufweisen und daher mit der gleichen Pipeline aufbereitet werden können. Schließlich stellen wir MaGRiTTE vor, eine neuartige Architektur, die selbst- überwachtes Lernen verwendet, um automatisch strukturelle Darstellungen von Dateien in Form von vektoriellen Einbettungen auf drei verschiedenen Ebenen zu lernen: auf Zellebene, auf Zeilenebene und auf Dateiebene. Wir experimentieren mit der Anwendung von strukturellen Einbettungen für verschiedene Aufgaben, nämlich Dialekterkennung, Zeilenklassifizierung und der Schätzung des Aufwands für die Datenaufbereitung. Unsere experimentellen Ergebnisse zeigen, dass strukturelle Metadaten, die entweder explizit mit Hilfe von Parsing-Grammatiken identifiziert, implizit als Dateiähnlichkeit abgeleitet oder mit Machine-Learning Architekturen erlernt werden, von grundlegender Bedeutung für die Automatisierung verschiedener Aufgaben, die Skalierung der Aufbereitung auf große Mengen von Dateien und die Bereitstellung wiederholbarer Aufbereitungspipelines sind. KW - data preparation KW - file structure KW - Datenaufbereitung KW - tabellarische Dateien KW - Dateistruktur KW - tabular data Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-624351 ER - TY - THES A1 - Jiang, Lan T1 - Discovering metadata in data files N2 - It is estimated that data scientists spend up to 80% of the time exploring, cleaning, and transforming their data. A major reason for that expenditure is the lack of knowledge about the used data, which are often from different sources and have heterogeneous structures. As a means to describe various properties of data, metadata can help data scientists understand and prepare their data, saving time for innovative and valuable data analytics. However, metadata do not always exist: some data file formats are not capable of storing them; metadata were deleted for privacy concerns; legacy data may have been produced by systems that were not designed to store and handle meta- data. As data are being produced at an unprecedentedly fast pace and stored in diverse formats, manually creating metadata is not only impractical but also error-prone, demanding automatic approaches for metadata detection. In this thesis, we are focused on detecting metadata in CSV files – a type of plain-text file that, similar to spreadsheets, may contain different types of content at arbitrary positions. We propose a taxonomy of metadata in CSV files and specifically address the discovery of three different metadata: line and cell type, aggregations, and primary keys and foreign keys. Data are organized in an ad-hoc manner in CSV files, and do not follow a fixed structure, which is assumed by common data processing tools. Detecting the structure of such files is a prerequisite of extracting information from them, which can be addressed by detecting the semantic type, such as header, data, derived, or footnote, of each line or each cell. We propose the supervised- learning approach Strudel to detect the type of lines and cells. CSV files may also include aggregations. An aggregation represents the arithmetic relationship between a numeric cell and a set of other numeric cells. Our proposed AggreCol algorithm is capable of detecting aggregations of five arithmetic functions in CSV files. Note that stylistic features, such as font style and cell background color, do not exist in CSV files. Our proposed algorithms address the respective problems by using only content, contextual, and computational features. Storing a relational table is also a common usage of CSV files. Primary keys and foreign keys are important metadata for relational databases, which are usually not present for database instances dumped as plain-text files. We propose the HoPF algorithm to holistically detect both constraints in relational databases. Our approach is capable of distinguishing true primary and foreign keys from a great amount of spurious unique column combinations and inclusion dependencies, which can be detected by state-of-the-art data profiling algorithms. N2 - Schätzungen zufolge verbringen Datenwissenschaftler bis zu 80% ihrer Zeit mit der Erkundung, Bereinigung und Umwandlung ihrer Daten. Ein Hauptgrund für diesen Aufwand ist das fehlende Wissen über die verwendeten Daten, die oft aus unterschiedlichen Quellen stammen und heterogene Strukturen aufweisen. Als Mittel zur Beschreibung verschiedener Dateneigenschaften können Metadaten Datenwissenschaftlern dabei helfen, ihre Daten zu verstehen und aufzubereiten, und so wertvolle Zeit die Datenanalysen selbst sparen. Metadaten sind jedoch nicht immer vorhanden: Zum Beispiel sind einige Dateiformate nicht in der Lage, sie zu speichern; Metadaten können aus Datenschutzgründen gelöscht worden sein; oder ältere Daten wurden möglicherweise von Systemen erzeugt, die nicht für die Speicherung und Verarbeitung von Metadaten konzipiert waren. Da Daten in einem noch nie dagewesenen Tempo produziert und in verschiedenen Formaten gespeichert werden, ist die manuelle Erstellung von Metadaten nicht nur unpraktisch, sondern auch fehleranfällig, so dass automatische Ansätze zur Metadatenerkennung erforderlich sind. In dieser Arbeit konzentrieren wir uns auf die Erkennung von Metadaten in CSV-Dateien - einer Art von Klartextdateien, die, ähnlich wie Tabellenkalkulationen, verschiedene Arten von Inhalten an beliebigen Positionen enthalten können. Wir schlagen eine Taxonomie der Metadaten in CSV-Dateien vor und befassen uns speziell mit der Erkennung von drei verschiedenen Metadaten: Zeile und Zellensemantischer Typ, Aggregationen sowie Primärschlüssel und Fremdschlüssel. Die Daten sind in CSV-Dateien ad-hoc organisiert und folgen keiner festen Struktur, wie sie von gängigen Datenverarbeitungsprogrammen angenommen wird. Die Erkennung der Struktur solcher Dateien ist eine Voraussetzung für die Extraktion von Informationen aus ihnen, die durch die Erkennung des semantischen Typs jeder Zeile oder jeder Zelle, wie z. B. Kopfzeile, Daten, abgeleitete Daten oder Fußnote, angegangen werden kann. Wir schlagen den Ansatz des überwachten Lernens, genannt „Strudel“ vor, um den strukturellen Typ von Zeilen und Zellen zu klassifizieren. CSV-Dateien können auch Aggregationen enthalten. Eine Aggregation stellt die arithmetische Beziehung zwischen einer numerischen Zelle und einer Reihe anderer numerischer Zellen dar. Der von uns vorgeschlagene „Aggrecol“-Algorithmus ist in der Lage, Aggregationen von fünf arithmetischen Funktionen in CSV-Dateien zu erkennen. Da stilistische Merkmale wie Schriftart und Zellhintergrundfarbe in CSV-Dateien nicht vorhanden sind, die von uns vorgeschlagenen Algorithmen die entsprechenden Probleme, indem sie nur die Merkmale Inhalt, Kontext und Berechnungen verwenden. Die Speicherung einer relationalen Tabelle ist ebenfalls eine häufige Verwendung von CSV-Dateien. Primär- und Fremdschlüssel sind wichtige Metadaten für relationale Datenbanken, die bei Datenbankinstanzen, die als reine Textdateien gespeichert werden, normalerweise nicht vorhanden sind. Wir schlagen den „HoPF“-Algorithmus vor, um beide Constraints in relationalen Datenbanken ganzheitlich zu erkennen. Unser Ansatz ist in der Lage, echte Primär- und Fremdschlüssel von einer großen Menge an falschen eindeutigen Spaltenkombinationen und Einschlussabhängigkeiten zu unterscheiden, die von modernen Data-Profiling-Algorithmen erkannt werden können. KW - data preparation KW - metadata detection KW - data wrangling KW - Datenaufbereitung KW - Datentransformation KW - Erkennung von Metadaten Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-566204 ER - TY - THES A1 - Koumarelas, Ioannis T1 - Data preparation and domain-agnostic duplicate detection N2 - Successfully completing any data science project demands careful consideration across its whole process. Although the focus is often put on later phases of the process, in practice, experts spend more time in earlier phases, preparing data, to make them consistent with the systems' requirements or to improve their models' accuracies. Duplicate detection is typically applied during the data cleaning phase, which is dedicated to removing data inconsistencies and improving the overall quality and usability of data. While data cleaning involves a plethora of approaches to perform specific operations, such as schema alignment and data normalization, the task of detecting and removing duplicate records is particularly challenging. Duplicates arise when multiple records representing the same entities exist in a database. Due to numerous reasons, spanning from simple typographical errors to different schemas and formats of integrated databases. Keeping a database free of duplicates is crucial for most use-cases, as their existence causes false negatives and false positives when matching queries against it. These two data quality issues have negative implications for tasks, such as hotel booking, where users may erroneously select a wrong hotel, or parcel delivery, where a parcel can get delivered to the wrong address. Identifying the variety of possible data issues to eliminate duplicates demands sophisticated approaches. While research in duplicate detection is well-established and covers different aspects of both efficiency and effectiveness, our work in this thesis focuses on the latter. We propose novel approaches to improve data quality before duplicate detection takes place and apply the latter in datasets even when prior labeling is not available. Our experiments show that improving data quality upfront can increase duplicate classification results by up to 19%. To this end, we propose two novel pipelines that select and apply generic as well as address-specific data preparation steps with the purpose of maximizing the success of duplicate detection. Generic data preparation, such as the removal of special characters, can be applied to any relation with alphanumeric attributes. When applied, data preparation steps are selected only for attributes where there are positive effects on pair similarities, which indirectly affect classification, or on classification directly. Our work on addresses is twofold; first, we consider more domain-specific approaches to improve the quality of values, and, second, we experiment with known and modified versions of similarity measures to select the most appropriate per address attribute, e.g., city or country. To facilitate duplicate detection in applications where gold standard annotations are not available and obtaining them is not possible or too expensive, we propose MDedup. MDedup is a novel, rule-based, and fully automatic duplicate detection approach that is based on matching dependencies. These dependencies can be used to detect duplicates and can be discovered using state-of-the-art algorithms efficiently and without any prior labeling. MDedup uses two pipelines to first train on datasets with known labels, learning to identify useful matching dependencies, and then be applied on unseen datasets, regardless of any existing gold standard. Finally, our work is accompanied by open source code to enable repeatability of our research results and application of our approaches to other datasets. N2 - Die erfolgreiche Durchführung eines datenwissenschaftlichen Projekts erfordert eine Reihe sorgfältiger Abwägungen, die während des gesamten Prozessesverlaufs zu treffen sind. Obwohl sich der Schwerpunkt oft auf spätere Prozessphasen konzentriert, verbringen Experten in der Praxis jedoch einen Großteil ihrer Zeit in frühen Projektphasen in denen sie Daten aufbereiten, um sie mit den Anforderungen vorhandener Systeme in Einklang zu bringen oder die Genauigkeit ihrer Modelle zu verbessern. Die Duplikaterkennung wird üblicherweise während der Datenbereinigungsphase durchgeführt, sie dient der Beseitigung von Dateninkonsistenzen und somit der Verbesserung von Gesamtqualität und Benutzerfreundlichkeit der Daten. Während die Datenbereinigung eine Vielzahl von Ansätzen zur Durchführung spezifischer Operationen wie etwa dem Schema-Abgleich und der Datennormalisierung umfasst, stellt die Identifizierung und Entfernung doppelter Datensätze eine besondere Herausforderung dar. Dabei entstehen Duplikate, wenn mehrere Datensätze, welche die gleichen Entitäten repräsentieren, in einer Datenbank vorhanden sind. Die Gründe dafür sind vielfältig und reichen von einfachen Schreibfehlern bis hin zu unterschiedlichen Schemata und Formaten integrierter Datenbanken. Eine Datenbank duplikatfrei zu halten, ist für die meisten Anwendungsfälle von entscheidender Bedeutung, da ihre Existenz zu falschen Negativ- und Falsch-Positiv-Abfragen führt. So können sich derartige Datenqualitätsprobleme negativ auf Aufgaben wie beispielsweise Hotelbuchungen oder Paketzustellungen auswirken, was letztlich dazu führen kann, dass Benutzer ein falsches Hotel buchen, oder Pakete an eine falsche Adresse geliefert werden. Um ein breites Spektrum potenzieller Datenprobleme zu identifizieren, deren Lösung die Beseitigung von Duplikaten erleichtert, sind eine Reihe ausgefeilter Ansätze erforderlich. Obgleich der Forschungsbereich der Duplikaterkennung mit der Untersuchung verschiedenster Effizienz und Effektivitätsaspekte bereits gut etabliert ist, konzentriert sich diese Arbeit auf letztgenannte Aspekte. Wir schlagen neue Ansätze zur Verbesserung der Datenqualität vor, die vor der Duplikaterkennung erfolgen, und wenden letztere auf Datensätze an, selbst wenn diese über keine im Vorfeld erstellten Annotationen verfügen. Unsere Experimente zeigen, dass durch eine im Vorfeld verbesserte Datenqualität die Ergebnisse der sich anschließenden Duplikatklassifizierung um bis zu 19% verbessert werden können. Zu diesem Zweck schlagen wir zwei neuartige Pipelines vor, die sowohl generische als auch adressspezifische Datenaufbereitungsschritte auswählen und anwenden, um den Erfolg der Duplikaterkennung zu maximieren. Die generische Datenaufbereitung, wie z.B. die Entfernung von Sonderzeichen, kann auf jede Relation mit alphanumerischen Attributen angewendet werden. Bei entsprechender Anwendung werden Datenaufbereitungsschritte nur für Attribute ausgewählt, bei denen sich positive Auswirkungen auf Paarähnlichkeiten ergeben, welche sich direkt oder indirekt auf die Klassifizierung auswirken. Unsere Arbeit an Adressen umfasst zwei Aspekte: erstens betrachten wir mehr domänenspezifische Ansätze zur Verbesserung der Adressqualität, zweitens experimentieren wir mit bekannten und modifizierten Versionen verschiedener Ähnlichkeitsmaße, um infolgedessen das am besten geeignete Ähnlichkeitsmaß für jedes Adressattribut, z.B. Stadt oder Land, zu bestimmen. Um die Erkennung von Duplikaten bei Anwendungen zu erleichtern, in denen Goldstandard-Annotationen nicht zur Verfügung stehen und deren Beschaffung aus Kostengründen nicht möglich ist, schlagen wir MDedup vor. MDedup ist ein neuartiger, regelbasierter und vollautomatischer Ansatz zur Dublikaterkennung, der auf Matching Dependencies beruht. Diese Abhängigkeiten können zur Erkennung von Duplikaten genutzt und mit Hilfe modernster Algorithmen effizient ohne vorhergehenden Annotationsaufwand entdeckt werden. MDedup verwendet zwei Pipelines, um zunächst auf annotierten Datensätzen zu trainieren, wobei die Identifizierung nützlicher Matching-Abhängigkeiten erlernt wird, welche dann unabhängig von einem bestehenden Goldstandard auf ungesehenen Datensätzen angewendet werden können. Schließlich stellen wir den im Rahmen dieser Arbeit entstehenden Quellcode zur Verfügung, wodurch sowohl die Wiederholbarkeit unserer Forschungsergebnisse als auch die Anwendung unserer Ansätze auf anderen Datensätzen gewährleistet werden soll. T2 - Datenaufbereitung und domänenagnostische Duplikaterkennung KW - duplicate detection KW - data cleaning KW - entity resolution KW - record linkage KW - data preparation KW - data matching KW - address normalization KW - machine learning KW - matching dependencies KW - Adressnormalisierung KW - Datenbereinigung KW - Datenabgleich KW - Datenaufbereitung KW - Duplikaterkennung KW - Entitätsauflösung KW - Maschinelles Lernen KW - Abgleich von Abhängigkeiten KW - Datensatzverknüpfung Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-489131 ER -