Describing differences between overlapping databases
Creators: name: Müller, Heiko
Publisher: name: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Year: 2009
Subjects: subject: Datenbereinigung
subject: Genomdaten
subject: Widerspruchsmuster
subject: Distanz von Datenbanken
subject: Data cleansing
subject: Genome data
subject: Contradiction pattern
subject: Update distance
subject: 004 Informatik
subject: 28 Informatik, Datenverarbeitung

description: Die Analyse existierender Daten ist wichtiger Bestandteil moderner Forschung. Das Thema Datenqualität gewinnt deshalb im Bereich der wissenschaftlichen Forschung zunehmend an Bedeutung. Existierende Verfahren zur Datenbereinigung sind für wissenschaftliche Daten jedoch nur bedingt einsetzbar. Dies liegt zum einen an der höheren Komplexität der Daten und zum anderen an unserer oftmals noch unvollständigen Kenntnis der Regularien in den entsprechenden Domänen. Die vorliegende Arbeit ist leistet folgende Beiträge im Hinblick auf Datenqualität und Datenbereinigung wissenschaftlicher Daten: Im ersten Teil der Arbeit geben wir einen Überblick über existierende Verfahren zur Datenbereinigung und diskutieren deren Stärken und Schwächen. Aus unseren Ergebnissen folgern wir, daß überlappende Datenquellen großes Potential zur Verbesserung der Korrektheit und Genauigkeit wissenschaftlicher Daten haben. Überlappende Datenquellen decken Bereiche potentiell minderer Datenqualität in Form von (Daten-)konflikten auf und bieten gleichzeitig eine Möglichkeit zur Qualitätsverbesserung durch Datenintegration. Eine wichtige Voraussetzung für die Integration überlappender Datenquellen ist das Auflösen existierender Konflikte. In vielen Fällen treten die Konflikte nicht zufällig auf sondern folgen einer systematischen Ursache. Im zweiten Teil dieser Arbeit entwickeln wir Algorithmen, die das Auffinden systematischer Konflikte unterstützen. Wir klassifizieren Konflikte dabei anhand charakteristischer Muster in den überlappenden Daten. Diese Widerspruchsmuster unterstützen einen Experten bei der Festlegung von Konfliktlösungsstrategien zur der Datenintegration. Im dritten Teil dieser Arbeit verwenden wir ein prozeßbezogenes Model zur Beschreibung systematischer Konflikte, um Abhängigkeiten zwischen Konfliktgruppen aufzeigen zu können. Wir verwenden hierzu Sequenzen mengenorientierter Modifikationsoperationen die eine Datenquelle in die andere überführen. Wir präsentieren Algorithmen zur Bestimmung minimaler Modifikationssequenzen für ein gegebenes Paar von Datenquellen. Die Komplexität des Problems bedingt die Verwendung von Heuristiken. In unseren Experimenten zeigen wir die vielversprechende Qualität der Ergebnisse unserer Heuristiken.
description: Data quality has become an issue in scientific research. Cleaning scientific data, however, is hampered by incomplete or fuzzy knowledge of regularities in the examined domain. A common approach to enhance the overall quality of scientific data is to merge overlapping sources by eliminating conflicts that exist between them. The main objective of this thesis is to provide methods to aid the developer of an integrated system over contradicting databases in the task of resolving value conflicts. We contribute by developing a set of algorithms to identify regularities in overlapping databases that occur in conjunction with conflicts between them. These regularities highlight systematic differences between the databases. Evaluated by an expert user the discovered regularities provide insights on possible conflict reasons and help assess the quality of inconsistent values. Instead of inspecting individual conflicts, the expert user is now enabled to specify a conflict resolution strategy based on known groups of conflicts that share the same conflict reason. The thesis has three main parts. Part I gives a comprehensive review of existing data cleansing methods. We show why existing data cleansing techniques fall short for the domain of genome data and argue that merging overlapping data has outstanding ability to increase data accuracy; a quality criteria ignored by most of the existing cleansing approaches. Part II introduces the concept of contradiction patterns. We present a model for systematic conflicts and describe algorithms for efficiently detecting patterns that summarize characteristic data properties for conflict occurrence. These patterns help in providing answers to questions like “Which are the conflict-causing attributes, or values?” and “What kind of dependencies exists between the occurrences of contradictions in different attributes?”. In Part III, we define a model for systematic conflicts based on sequences of set-oriented update operations. Even though we only consider a restricted form of updates, our algorithms for computing minimal update sequences for pairs of databases require exponential space and time. We show that the problem is NP-hard for a restricted set of operations. However, we also present heuristics that lead to convincing results in all examples we considered.