Describing differences between overlapping databases [Elektronische Ressource] / von Heiko Müller

Heiko Müller

Sujets

• Informatik

Informations

• Publié par: humboldt-universitat_zu_berlin
• Publié le: 01 janvier 2008
• Nombre de lectures: 14
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Institut für Informatik
Dissertation
Describing Differences between
Overlapping Databases
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften (doctor rerum naturalium)
eingereicht an der
Mathematisch-Naturwissenschaftliche Fakultät
der Humboldt-Universität zu Berlin
von
Diplom-Informatiker Heiko Müller,
geboren am 29. Oktober 1970 in Berlin
Präsident der Humboldt-Universität zu Berlin:
Prof. Dr. Christoph Markschies
Dekan der Mathematisch-Naturwissenschaftlichen Fakultät II:
Prof. Dr. Wolfgang Coy
Gutachter: 1. Prof. Johann-Christoph Freytag, Ph.D.
2. Prof. Ulf Leser
3. Prof. Bertram Ludäscher
Datum der Einreichung: 22. April 2008
Datum der Promotion: 19. Dezember 2008 ii Acknowledgements
I thank my advisors Prof. Johann-Christoph Freytag and Prof. Ulf Leser for their support, their helpful
advice, and the time they spend with me in informative discussions during the preparation of this the-
sis. I especially want to thank Prof. Freytag for his always open words and the patience he had with
me during my work. His database department at the Humboldt University Berlin provided a really
inspiring research environment for me. Prof. Leser was the one who created the idea of writing this
thesis in me. His valuable and challenging comments throughout my work significantly influenced the
topic of this thesis and helped to improve its final outcome.
This work was financially supported by the Berlin and Brandenburg Graduate School for Distributed
Information Systems. The graduate School with its regular workshops and evaluation by its professors
provided a challenging, but supportive and productive environment for me and my research. I would
like to thank all my colleagues and all professors for their comments throughout the years.
I discussed my work with many colleagues at Humboldt University and the database group. I thank
Prof. Felix Naumann for his support and for introducing me to the problems and challenges of data
quality. I also thank Dr. Stephan Heymann and Peter Rieger for sharing their knowledge about genome
research and quality pitfalls of genome data. I would like to thank Heinz Werner and Thomas Morgen-
stern for their excellent technical support and Ulrike Scholz for her administrative support. Finally, a
big ‘Thank You’ to all my colleagues during the years at he database group who made my time an
enjoyable one.
Outside of the academic world, I want to thank my family and friends for their support. I assume it
hasn’t always been easy to ‘endure’ me during that time. I dedicate this work to my father and my
grand mother, who both were very proud to see me working on this thesis, but who both are no longer
with us to witness the final moments.
iii iv Zusammenfassung
Die Analyse existierender Daten ist wichtiger Bestandteil vieler Forschungsaktivitäten. Insbesondere
im Bereich der medizinischen und pharmazeutischen Forschung entscheiden die Ergebnisse dabei
nicht nur über eine erfolgversprechende Verwendung finanzieller Mittel, sondern oftmals auch über
das Wohlergehen von Probanden und Patienten. Analysen die auf der Grundlage von fehler- oder man-
gelhaften Daten durchgeführt werden können deshalb schwerwiegende negative Folgen haben. Aus
diesem Grund hat das Thema Datenqualität im Bereich der wissenschaftlichen Forschung in den ver-
gangenen Jahren zunehmend an Bedeutung und Aufmerksamkeit gewonnen. Existierende regelbasierte
Verfahren zur Qualitätskontrolle und 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 und mit Unsicherheit behaftet Kenntnis der Regularien in den
entsprechenden Domänen. Die vorliegende Arbeit ist in drei Teile gegliedert und leistet folgende Bei-
träge im Hinblick auf Datenqualität und Datenbereinigung in wissenschaftlichen Datensammlungen:
Im ersten Teil der Arbeit geben wir einen Überblick über existierende Verfahren zur Datenbereinigung
und diskutieren deren Stärken und Schwächen hinsichtlich der Beseitigung von Qualitätsproblemen in
wissenschaftlichen Daten.
Wir beginnen mit einer Klassifikation von Unzulänglichkeiten in existierenden Datenbanken, die zu
einer Minderung der Datenqualität führen. Datenqualität wird generell als Vektor unterschiedlicher
Qualitätskriterien definiert. Für jede der definierten Problemklassen geben wir die Qualitätskriterien
an, die von diesen Problemen negativ beeinträchtigt werden. Auf Grundlage dieser Zuordnung geben
wir einen Überblick über existierende Ansätze zur Bereinigung von Daten und zeigen auf, welche
Qualitätskriterien von welchen Ansätzen bedient werden. Aus unseren Ergebnissen folgern wir, daß
überlappende Datenquellen großes Potential hinsichtlich Verbesserung der Korrektheit und Genauig-
keit von Daten haben. Der vergleich überlappender Datenquellen deckt Bereiche potentiell minderer
Datenqualität in Form von Datenkonflikten auf. Gleichzeitig bieten die überlappenden Daten eine
Möglichkeit zur Qualitätsverbesserung durch Datenintegration.
Am Beispiel von Genomdaten zeigen wir, daß Datenqualitätsprobleme in wissenschaftlichen Daten
zum großen Teil im Produktionsprozeß der Daten begründet sind. Wir analysieren den Produktions-
prozeß und identifizieren verschiedene Formen von Qualitätsproblemen und deren Verursacher. Da
eine manuelle Qualitätskontrolle während der Datengenerierung aus Effizienzgründen nicht praktika-
bel ist, muß eine Datenbereinigung a posteriori vorgenommen werden. Anhand praktischer Arbeiten
diskutieren wir die Vor- und Nachteile unterschiedlicher Ansätze. Die Integration überlappender Da-
tenquellen stellt besonders in diesem Bereich einen vielversprechenden Ansatz dar.
v Eine wichtige Voraussetzung für die Integration überlappender Datenquellen besteht in einem geziel-
ten Auflösen der auftretenden Datenkonflikte (kurz Konflikte). Aus einer Menge an widersprüchlichen
Werten gilt es den oder die zuverlässigsten Werte auszuwählen und daraus einen sog. Repräsentanten
abzuleiten. In vielen Fällen treten die Konflikte nicht zufällig auf sondern folgen einer systematischen
Ursache. Eine Kenntnis dieser Systematik erlaubt es Konflikte mit gleicher Ursache gemeinsam zu
lösen. Wir bezeichnen dies als kontextabhängige Konfliktlösung. Im zweiten Teil dieser Arbeit ent-
wickeln wir eine Reihe von Algorithmen, die das Auffinden von systematischen Unterschieden in
überlappenden Daten unterstützen.
Wir präsentieren ein Modell für systematische Konflikte in überlappenden Daten. Wir klassifizieren
Konflikte dabei anhand charakteristischer Muster in den überlappenden Daten, die im Zusammenhang
mit diesen Konflikten auftreten. Diese Widerspruchsmuster dienen einem Experten als Unterstützung
bei der Festlegung von Konfliktlösungsstrategien im Rahmen der Datenintegration. Widerspruchsmu-
ster stellen eine spezielle Form von Assoziationsregeln dar. Basierend auf existierenden Techniken
präsentieren wir effiziente Algorithmen zur Suche nach Widerspruchsmustern in überlappenden Da-
tenquellen. Um die Vielzahl der potentiellen Widerspruchsmuster handhaben zu können definieren wir
verschiedene Maße für deren Relevanz. In unseren Experimenten diskutieren wir den Einfluß dieser
Maße auf die Aussagekraft und die Anzahl der gefundenen Widerspruchsmuster.
Widerspruchsmuster sind hilfreich bei der Identifikation von Konflikten, die eine gemeinsame Kon-
fliktursache haben. Im dritten Teil dieser Arbeit verwenden wir ein prozeßbezogenes Model zur Be-
schreibung 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. Jede Sequenz die eine Datenquelle in die andere überführt muß sämtliche
Konflikte zwischen den Quellen auflösen. Die minimale Sequenz hinsichtlich der Anzahl an Operatio-
nen ist die kleinstmögliche Zusammenfassung sämtlicher Unterschiede zwischen den Datenquellen.
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 für
große Datensätze. Wir präsentieren eine Reihe solcher Heuristiken, die jedoch nicht immer die optima-
le (sprich minimale) Lösung finden. In unseren Experimenten zeigen wir, daß die Qualität der Ergeb-
nisse unserer Heuristiken dennoch sehr vielversprechend ist.
Die in dieser Arbeit präsentierten Widerspruchsmuster und Modifikationssequenzen helfen systemati-
sche Unterschiede zwischen überlappenden Datenquellen aufzudecken. Unsere Algorithmen liefern
somit wertvolle Informationen zur qualitativen Bewertung überlappender Daten. Die Ergebnisse kön-
nen sowohl zur Spezifikation von