Post on 30-May-2020
transcript
Universität HamburgFakultät für Mathematik,Informatik und Naturwissenschaften
Bachelorarbeit
Entwurf und Implementierung einesadaptiven und flexiblen Frameworks zurDuplikaterkennung in probabilistischen
Daten
Lars Grote
7grote@informatik.uni-hamburg.de
Bachelor of Science, Informatik
Matr.-Nr. 5811957
Fachsemester 7
Abgegeben am 01.03.2011
Betreuende Personen:
Prof. Dr. Professor Norbert Ritter
Dr. Axel Schmolitzky
Fabian Panse
ADRIANA:
I see two husbands, or mine eyes deceive me.
DUKE SOLINUS:
One of these men is Genius to the other;
And so of these. Which is the natural man,
and which the spirit? who deciphers them?
William Shakespeare, The Comedy of Errors, Act V
Inhaltsverzeichnis i
Inhaltsverzeichnis
1. Einleitung 1
2. Grundlagen 3
2.1. Traditionelle Duplikatenerkennung . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1. Schritte der Traditionelle Duplikatenerkennung . . . . . . . . . . . 5
i. Vorbereitung der Daten . . . . . . . . . . . . . . . . . . . . 6
ii. Suchraumdefinition . . . . . . . . . . . . . . . . . . . . . . 6
iii. Attributwerte Abgleich . . . . . . . . . . . . . . . . . . . . 7
iv. Entscheidungsmodell . . . . . . . . . . . . . . . . . . . . . 7
v. Clustern der Duplikate . . . . . . . . . . . . . . . . . . . . 9
vi. Verifikation . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2. Existierende Systeme zur Duplikatenerkennung in relationalen Daten . . 10
2.3. Probabilistische Daten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4. Duplikatenerkennung in Probabilistischen Datenbeständen . . . . . . . . . 13
2.4.1. Attributwerte Abgleich . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.2. Entscheidungsmodell . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3. Anforderungen an das Framework 17
3.1. Theoretische Anforderrungen . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.1. Datenmodell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2. Softwaretechnische Flexibilität . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.1. Das Phasen Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.2. Modell zu Erkennung von Duplikaten . . . . . . . . . . . . . . . . . 22
3.2.3. Metadaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3. Speicherung von Zwischenergebnissen . . . . . . . . . . . . . . . . . . . . 23
3.4. Anforderungen an die Skalierbarkeit . . . . . . . . . . . . . . . . . . . . . . 23
4. Implementierung des Phasen Modells 25
4.1. Phasenmodell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.1. Phasen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1.2. Phasen Managment . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.1.3. Pausieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2. Kommunikation und Serialisierung . . . . . . . . . . . . . . . . . . . . . . 28
4.2.1. InputStorage / OutputStorage . . . . . . . . . . . . . . . . . . . . . 29
ii Inhaltsverzeichnis
4.2.2. Hook-Methoden und Listener . . . . . . . . . . . . . . . . . . . . . . 31
4.3. Konfiguration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5. Prototypische Duplikatenerkennung 355.1. ULDB Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2. Duplikatenerkennung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2.1. Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.2.2. Suchraumdefinition . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2.3. Attributwerte Abgleich . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2.4. Alternativen Abgleich . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2.5. Entscheidungsmodell . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2.6. Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6. Fazit 41
Appendix 431. HumMer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2. Ablauf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3. UML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4. Code-Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Literaturverzeichnis 49
Eidesstattliche Erklärung 53
1
1. Einleitung
Die Erkennung von Duplikaten in Datenbeständen, insbesondere in Datenbanken, ist ein
viel behandeltes und umfangreich erforschtes Thema. Es existieren diverse Algorithmen,
welche anhand der Ähnlichkeit der Daten entscheiden, ob es sich bei den betrachteten
Datenobjekten, um zwei Objekte oder um ein Duplikat handelt. Insbesondere im Kon-
text der Datenintegration [Len02] und der Datenreinigung [MF05] ist dieses von beson-
derer Bedeutung. In der Regel das Ziel, dass genau eine logische Repräsentation eines
realweltlichen Objektes in einem Datenbestand existiert.
Um diese zu erlangen existieren Modelle für relationale Datenbanken für relationale
Datenbanken [BGMM+09][CGM05][FS69][HS95] sowie für XML-Datenbestände [WN06].
Für probabilistische Daten [BGMP02][BDSH+08][HAKO09] ist diese Feld jedoch weitge-
hend unerforscht und es existieren keine Implementationen um eine Datenbereinigung
durchzuführen. Der Gebrauch von probabilistischen gewinnt jedoch mehr und mehr an
Bedeutung [SCH][BCMP10]. Deshalb soll im Rahmen des QloUD (Quality of UncertainData)-Projektes1 eine solche Implementation realisiert werden.
Das Projekt Quality of Uncertain Data ist an der Universität Hamburg im Fachbereich
Verteilte Systeme und Informatiossysteme2 des Informatik Departments beheimatet und
wird, zum Zeitpunkt der Erstellung dieser Arbeit hauptsächlich von F. Panse3 betreut.
In [PVKDKR10] ist von F. Panse ein Ansatz für eine mögliche Adaptionen von
herkömmlichen Duplikatenerkennungsverfahren für probabilistische Datenmodelle
beschrieben. Im Allgemeinen handelt es sich bei der Duplikaterkennung um einen sehr
Domain abhängigen Prozess. Dementsprechend sollte ein Duplikatenerkennungssystem
höchst flexibel und adaptiv gestaltet sein.
Die Duplikatenerkennung in probabilistischen Daten bringt jedoch im Vergleich zu
herkömmlichen neue Probleme, aber auch Lösungsansätze mit sich und das nicht nur
dadurch das die Wahrscheinlichkeit für die einzelnen Datenobjekte berücksichtigt wer-
den muss. Die Möglichkeiten die vorhanden sind noch nicht vollständig erforscht de-
shalb ist die Flexibilität dieses Frameworks von besonderen Wichtigkeit.
Ziel meiner Arbeit ist die Implementation eines Frameworks, welches auf dem in
[PVKDKR10] vorgeschlagenen Phasenmodell basiert, gleichzeitig aber auch flexibel
genug ist, um Modelländerungen oder Modellerweiterungen realisieren zu können. Die
konkrete Optimierung der jeweiligen Teilprozesse des Duplikatenerkennung ist nicht
1Homepage des Projektes: http://vsis-www.informatik.uni-hamburg.de/projects/QloUD/2http://vsis-www.informatik.uni-hamburg.de/3http://vsis-www.informatik.uni-hamburg.de/members/info.php/1052
2 1. Einleitung
Teil dieser Arbeit. Vielmehr soll die Basis geliefert werden, um die Einzelteile möglichst
unabhängig voneinander entwickeln und kombinieren zu können.
Um die Funktionstüchtigkeit des Frameworks zu demonstrieren wird lediglich ein rudi-
mentäres Verfahren zur Duplikatenerkennung exemplarisch implementiert werden.
3
2. Grundlagen
Das Ziel dieser Arbeit ist die Implementierung eines Frameworks zur Erforschung der
Duplikatenerkennung in probabilistischen Daten. Duplikatenerkennung im traditionelle
Sinne ist ein gut erforschter und vielfältig bearbeiteter Themenbereich. Als
traditionelle sind hier die Verfahren und Arbeiten bezeichnet die sich mit klassischen
Eingabeformaten wie Textdateien, Relationale Datenbanken und XML Dateien auseinan-
dersetzen. Die Forschung zu diesen Arbeiten lässt sich zu sehr großen Teilen für die
Duplikatenerkennung in probabilistischen Daten adaptieren. Die grundsätzliche Vorge-
hensweise und die damit verbundenen Probleme sind synonym. Deshalb ist es sinnvoll
existierenden Systemen zu Duplikatenerkennung in meine Überlegungen mit einzube-
ziehen. Die zu Grunde liegenden Datenmodelle unterscheiden sich jedoch in einigen As-
pekten.
Der Umstand, dass Werte nicht eindeutig sondern wahrscheinlichkeitsbasiert sind,
führt nicht nur zu zusätzlichen Schritten während der Erkennung von Duplikaten, son-
dern auch zu der Notwendigkeit die vorgegebenen Wahrscheinlichkeiten in den bereits
vorhandenen Schritten zu berücksichtigen.
Die bisher genannten Themen: Traditionelle Duplikatenerkennung, Existierenden Sys-
teme zu Duplikatenerkennung und probabilistischen Daten, sollen in diesem Kapitel er-
läutert werden, um einen Überblick über die grundsätzlichen Problematiken dieses The-
menbereiches zu geben und eine Grundlage zur Erläuterung der Anforderungen an das
zu implementierende Framework zu schaffen, welches schließlich in Kapitel 3 behandelt
wird. Abschließend wird in diesem Kapitel ein Verfahren zu Duplikatenerkennung in
probabilistischen Datenbeständen dargestellt, welches die zentrale theoretische Grund-
lage der Implementation ist.
2.1. Traditionelle Duplikatenerkennung
Die Aufgabe der Duplikatenerkennung ist eng mit dem Begriff der Datenqualität ver-
bunden, da das Ziel der Duplikatenerkennung oft die Verbesserung der Datenqualität
ist. Tayi und Ballou haben Datenqualität im allgemeineren Sinne als Benutzbarkeit (fitnessfor use) der Daten definiert [TB98]. Diese Definition ist zwar ungenau, vermittelt aber
am griffigsten eine Idee des zugrunde liegenden Zweckes. Eine genauere Definition der
Datenqualität untergliedert sie in fünfzehn Dimensionen, die in vier Kategorien zusam-
mengefasst werden können:
4 2. Grundlagen
• Intrinsität (Glaubwürdigkeit, Präzision, Objektivität, Reputation)
• Kontextualität (Mehrwert, Relevanz, Aktualität, Vollständigkeit, Angemessene
Menge)
• Repräsentativität (Interpretierbarkeit, Eingängigkeit, Repräsentative Konsistenz,
Prägnanz)
• Zugänglichkeit (Zugänglichkeit, Zugriffkontrolle) [WS96]
Die meisten der genannten Dimensionen sind von der subjektiven Wahrnehmung des
Betrachters abhängig. Jedoch hat die Duplikatenerkennung mit seinen Folgeschritten
einen direkten Einfluss auf die Dimensionen Präzision1 und Vollständigkeit2. Auf viele
der anderen Dimension hat sie einen indirekten Einfluss [NH10, S.3].
Die Duplikatenerkennung selbst ist in der Regel Teil eines größeren Prozesses der ein
übergeordnetes Ziel verfolgt. Dieses Ziel hängt oft mit dem Gewinn von Datenqualität
zusammen, muss dies aber nicht. Ein typisches Beispiel eines solchen Prozesses ist die
Datenbereinigung innerhalb eines Datenbestandes [NH10, S.3]. Exemplarisch einer Na-
mensdatenbank:
Eine bestimmte Person wird versehentlich zweimal eingetragen. Die kann
durch einen Tippfehler entstanden sein oder dadurch dass der Name nicht
buchstabenweise diktiert wurde. Resultat ist, dass eine reale Person mit dem
Namen Jens Meyer nun zweimal in der Datenbank steht, einmal mit dem
richtigen Name und einmal mit dem Namen Jenz Meyer, und es ist nicht un-
wahrscheinlich, dass er eines Tage auch mit dem Namen Jenz Meier in der
Datenbank stehen wird. In einem anderen Fall hat sich der Name von MelanieWeis durch Heirat in Melanie Herschel geändert.
Die formale Konsistenz, die durch die Integritätsbedingungen des Datenbanksystems
mittels Triggern und Constraints sichergestellt wird, ist zwar gewahrt, jedoch nicht die
Konsistenz in Bezug auf die reale Welt [KE04, S. 157ff]. Wünschenswert ist, dass ein real-
weltliches Objekt nur durch genau einen Datensatz in einer Datenbank repräsentiert wird
[BS06, S. 97ff]. Dies kann durch anschließendes Fusionieren der, als Duplikate erkannten
Einträge erreicht werden oder durch einfaches löschen der überzähligen Einträge.
Ein anderes Szenario in dem die Duplikatenerkennung ist die Datenintegration. Unter
Datenintegration wird das zusammenfüheren mehrerer Datenbestände [NH10, S. 2f]. Ein
typisches Beispiel ist das Folgende:
0Wie z.B. Deduplikation, Datenfusion1Die Korrektheit, Zuverlässigkeit und Fehlerlosigkeit der Daten. Sie wird als Verhältnis der Gesamtzahl zu
der Anzahl von Datensätzen mit Fehlern angegeben.2Die Vollständigkeit lässt sich auf zwei Ebenen betrachten. Die Vollständigkeit einen Datensatzes (Wird
durch Datenfusion in der Regel erhöht) und die Vollständigkeit der Datensätze in Bezug auf die dieDatensätze der Domäne.
2.1. Traditionelle Duplikatenerkennung 5
Zwei Firmen fusionieren und wollen eine gemeinsame Adressdatenbank er-
halten. Bei der Integration dieser Datenbestände kann es leicht dazu kommen,
dass für eine reale Person mehrere Datenbankeinträge entstehen.
Das Ziel der Datenintegration ist einen möglichst korrekten und vollständigen Daten-
bestand zu erhalten. Um diese Ziel zu erreichen ist es nötig durch Duplikatenerkennung
die Tupel zu identifizieren die für ein reales Objekt stehen.
Zwischen den beiden genannten Szenarien bestehen gewisse Unterschiede, die dif-
ferente Prozesse erfordern. Das erste Beispiel bezieht sich auf einen Datenbestand in-
nerhalb dessen Duplikate gefunden und zusammen gefasst werden. Sogenannte Intra
Source Duplicates. Hingegen bei dem zweiten Beispiel zwei Datenbestände zu einem in-
tegrierten zusammen geführt werden sollen. In diesem Fall wird nach Inter Source Dupli-
cates gesucht [NH10, S. 6f]. Unterschiedliche Datenbestände verwenden in den seltensten
Fällen identische Schemata, um die Daten zu repräsentieren. In einem solchen Fall kann
es notwendig sein zunächst ein Schemamatching durchzuführen. Abhängig davon wie
komplex die Datentypen sind, in denen Duplikate gefunden werden sollen, kann das ein
sehr aufwändiger Prozess sein.
In dieser Arbeit eine automatisches Schemamatching nicht weiter behandelt [BS06, S.
99ff].3
Auch wenn es sich nicht um komplexe Typen handelt, muss bei der Datenintegration
in der Regel zunächst eine Standardisierung der Schemata durchgeführt werden. Zum
Beispiel könnte die eine Firma die Anschrift in einer einzigen Spalte gespeichert haben
wobei die andere Firma die Anschrift z.B. nach Straße, Hausnummer, Plz, und Ort getren-
nt gespeichert hat. Erst nach der Standardisierung kann mit der Suche nach Duplikaten
begonnen werden.
Im Prinzip muss nun jeder Datensatz der Firma A mit jedem Datensatz der Firma
B verglichen werden (Inter Source Duplicates). Es wären demnach |A| × |B| Vergleiche
nötig (unter ders Vorraussetzung das A und B duplikatenfrei sind, oder Intra Source
Duplicates nicht betrachtet werden). Bei der Suche nach Intra Source Duplicates in dem
Datenbestand A wären |A|2 Vergleiche nötig.4 Für reale Systeme, die mit großen Daten-
mengen umgehen ist das bei Weitem zu viel. Es muss also Möglichkeiten geben den
Suchraum, in dem Einträge verglichen werden einzuschränken. Weiterhin kann es sehr
unterschiedliche Modelle geben nach denen entschieden wird, ob es sich bei zwei Einträ-
gen um Duplikate handelt oder nicht.
2.1.1. Schritte der Traditionelle Duplikatenerkennung
Im Folgenden wird ein allgemeiner Prozess zur Duplikatenerkennung dargestellt welch-
er mit den zuvor angesprochenen und weiteren Problematiken umgeht. Duplikatenerken-
3Weiterführendes zum Thema Schemamatching: [RB01][vKdKA05][WN06]4Komplexitätsklasse O(n2)
6 2. Grundlagen
nung5 besteht nach Batini und Scannapieco im Allgemeinen aus fünf Schritten[BS06, S.
102f]. Es wird zusätzlich noch das Clustern von Duplikaten erläutert, welches in der Prax-
is oft von großem Interesse ist [NH10, S. 52ff].
i. Vorbereitung der Daten
Zunächst müssen die Daten in eine standardisierte Form gebracht werde, so dass eine
Erkennung der Duplikate erleichtert wird.6 Diese Standardisierung kann abhängig von
der jeweiligen Domäne sehr unterschiedlich ausfallen. Handelt es sich bei den behandel-
ten Daten um Strings, dann werden oft alle Großbuchstaben zu Kleinbuchstaben trans-
formiert (z.B. Apple, APPLE⇒ apple). Allgemein ist das Ziel mögliche unterschiedliche
Schreibweisen durch eine einzige zu ersetzen. Wenn genügend Wissen über die Domäne
vorhanden ist, können Synonyme und Akronyme behandelt werden (z.B.
International Business Machines, I.B.M.⇒ ibm). Bei anderen Feldtypen kann
es andere Standardisierungen geben. So sollten Datumsangaben in ein einheitliches For-
mat gebracht werden (z.B. 9/11/01, 9. September 2001⇒ 09.11.2001). Je mehr
Domänenwissen vorhanden ist desto mehr lässt sich Standardisieren. Vieles von dem
was hier angewendet wird, ist analog zu dem was vor dem erstellen eines Index im Infor-mation Retrieval passiert. Jedoch wird dort die Standardisierung noch um einiges weiter
getrieben [MRS08, S. 49ff].
ii. Suchraumdefinition
Zwei Datensätze A und B sollen auf Duplikate überprüft werden.7 Wie bereits erwähnt
entspricht die Anzahl der Vergleiche |A| × |B|. Aufgabe der Suchraumdefinition ist es,
möglichst ohne ein Duplikat nicht zu erkennen, die Anzahl der Vergleiche zu reduzieren.
Um das zu erreichen existieren drei Methoden. Blocking, Sorted Neightborhood, und
Pruning (Filtern) [BS06, S. 104f].
• Blocking, mit dieser Methode wird der Suchraum in Blöcke eingeteilt, die Dup-
likatenerkennung wird dann nur innerhalb der Blöcke angewendet. Das Einteilen
in Blöcke kann auf unterschiedliche Weise stattfinden. Eine Möglichkeit ist die
Generierung oder Nutzung eines Blockschlüssels, alle Tupel die denselben Block-
schlüssel erhalten werden in einen Block zusammengefasst und weiter bearbeitet.
Dies kann auch mittels einer geeigneten Hashfunktion geschehen [NH10, S. 43ff].
• Sorted Neighborhood, ist eine Methode bei der die Tupel nach einem geeigneten
Schlüssel sortiert werden. Anschließend wird dann ein Fenster fester Größe über
die Tupel bewegt und nur die Tupel innerhalb des Fensters werden für den Vergle-
ich betrachtet.8 Wichtig ist bei dieser Methode die Wahl des Schlüssels, er muss5Von Batini und Scannapieco als Object Identification bezeichnet6Oft auch Data Preparation [PVKDKR10] oder Preprocessing [BS06, S. 103f] genannt.7Engl. Search Space Reduction8Bei einer Fenstergröße von 10: a5 wird mit b1 − b10 verglichen, a6 mit b2 − b11, . . . )
2.1. Traditionelle Duplikatenerkennung 7
sicherstellen das Duplikate entsprechend der Ordnung des Schlüssels dicht bei
einander liegen. Je besser der Schlüssel ist, desto kleiner kann das Fenster sein
[NH10, S. 45ff].
• Pruning (Filterung), diese Methode geht davon aus, dass es möglich ist nach gewis-
sen Kriterien Tupel aus dem Suchraum zu entfernen die zu keinem anderen ein
Duplikat sein können, ohne wirklich eine Dupklikatenprüfung durchzuführen. Die
Kriterien nach denen gefiltert wird sind dabei in hohem Maße von der jeweiligen
Domäne abhängig.
iii. Attributwerte Abgleich
Die einzelnen Attributwerte der zu vergleichenden Tupel werden mit Ähnlichkeitsfunk-
tionen verglichen.9 Diese Ähnlichkeitsfunktionen geben für zwei Werte a und b eine
Ähnlichkeit aus s = sim(a, b). Je nach Typ des Attributwertes gibt es unterschiedliche
Möglichkeiten einer solchen Ähnlichkeitsfunktion. So könnte für Zahlen eine normal-
isierte Form der Differenz eine adäquate Variante sein. Für Datumsangaben könnte es die
Anzahl der dazwischen liegenden Tage/Stunden/Minuten sein, für Koordinaten wäre
der Abstand sinnvoll. Schwieriger ist es die Ähnlichkeit von Strings zu bestimmen. Es
gibt jedoch ein breites Spektrum an Forschungsarbeiten, die sich diesem Problem wid-
men.10
Bei dem Attributwerte Abgleich der Tupel a und b werden die Tupel als Vektoren
ihrer Attribute betrachtet a = (a1, a2 . . . ai), b = (b1, b2 . . . bi), i = Anzahl der Attribute.
Auf jedes Attributpaar (ai, bi) wird eine individuelle Ähnlichkeitsfunktion simn(an, bn)
angewendet. Diese Ähnlichkeitsfunktion kann sich aus mehreren Ähnlichkeitsfunktio-
nen zusammensetzen, deren Ergebnisse geeignet kombiniert/aggregiert werden. Aus
diesen Berechnungen resultiert für ein Tupelpaar ein Ähnlichkeitsvektor, welcher einen
Ähnlichkeitswert pro Attribut enthält:
~simab = (sim1(a1, b1), sim2(a2, b2), . . . simi(ai, bi)) = (sim1, sim2, . . . simi)
Dieser Ähnlichkeitsvektor ist die Eingabe für das darauf folgende Entscheidungsmod-
ell [PVKDKR10].
iv. Entscheidungsmodell
Auf der Basis des Ähnlichkeitsvektors wird mittels eines Entscheidungsmodells ent-
schieden, ob es sich bei den verglichenen Tupeln um Duplikate handelt oder nicht.
Entsprechend ist ein Entscheidungsmodell eine Funktion, welche einem Tupelpaar (t1, t2)
9Engl. Attribute Value Matching10In dieser Arbeit wird auf die Ähnlichkeitsfunktionen für Strings der Universität Sheffield zurückgegriffen
[Cha].
8 2. Grundlagen
einen Matchingtyp, d.h. einen der Werte (M, P, U) zuordnet, wobei M für matching tuples,
P für possible matching tuples, und U für non-matching tuples steht [PVKDKR10]:
µ(t1, t2) ∈ {M, P, U}
Es gibt viele Möglichkeiten, wie ein solches Entscheidungsmodell gestaltet sein kann. So
ist es nicht unwahrscheinlich, dass es sich bei vielen in der Praxis eingesetzten Implemen-
tationen um Domänen spezifische Heuristiken handelt. Hier sollen jedoch die zwei ver-
breitetesten allgemeinen Entscheidungsmodell Varianten erläutert werden. Eines basiert
auf Domänenwissen, das andere ist Wahrscheinlichkeitsbasiert.
• Wissensbasierte Entscheidungsmodelle sind abhängig von einem Domänen-
experten. Dieser identifiziert Bedingungen und Regeln dafür, dass zwei Tupel als
Duplikate betrachtet werden. Diese Regeln arbeiten mit den Werten des Ähnlich-
keitsvektors und weisen einem Tupelpaar einen Matchingtyp zu. Eine solche Regel
könnte sein:
IF name > 0, 8 AND address > 0.6 THEN MATCHING TYPE match
Diese Regel kann in hohem Maße von dem Wissen des Experten über die Qual-
ität des Datenbestandes abhängig sein. So ist es vorstellbar, dass sich eine generelle
Aussage darüber treffen lässt, welche Attribute einen höheren Wert, also eine höhere
Dikriminanz für die Duplikatenerkennung haben. Entscheidend bei den wissens-
basierten Regeln ist jedoch, dass das gegebene Domainwissen durch die Kombina-
tion von den in den Regeln verwendeten Grenzwerten und Attributen ausgedrückt
wird.
Abschließend wird entweder durch einen finalen Grenzwert entschieden, ob einem
Tupelpaar M oder U zugewiesen wird, oder es wird direkt durch eine Regel ein
Matchingtyp zugeordnet [PVKDKR10] [BS06, S. 122ff].11
• Ein wahrscheinlichkeitsbasiertes Entscheidungsmodell wurde 1969 von Fellegi und
Sunter vorgestellt und seitdem von anderen erweitert und verbessert [FS69][BS06,
S. 107ff][PVKDKR10].Dieses Modell bestimmt zunächst zwei bedingte Wahrschein-
lichkeiten anhand des Ähnlichkeitsverktors. Zum einen die Wahrscheinlichkeit da-
für, dass es sich bei dem betrachteten Tupelpaar um ein Duplikat handelt:
m(c) = P(c|(t1, t2) ∈ M)
11Possible Matches (P) werden bei der Wissensbasierten Technik selten verwendet.
2.1. Traditionelle Duplikatenerkennung 9
zum anderen die Wahrscheinlichkeit dafür, dass es sich nicht um Duplikate han-
delt12:
u(c) = P(c|(t1, t2) ∈ U)
Wie die Funktionen u und m die Wahrscheinlichkeit bestimmen ist nicht vorge-
geben. In der Regel wird es sich um gewichtete und normalisierte Kombinatio-
nen aus den Werten des Ähnlichkeitsvektors handeln. Die resultierenden bedingten
Wahrscheinlichkeiten werden anschließend ins Verhältnis gesetzt und so ein neuer
Wert, das Matchinggewicht R bestimmt.
R =m(c)u(c)
Mit zwei Grenzwerten Ty und Tz wird anhand des Matchinggewichts dem Tupel
einer Matchingtypen M, P, U zugewiesen.13
M : wenn R > Ty
P : wenn Ty ≤ R ≤ Tz
U : wenn R < Tz
Es wird deutlich, dass die Grenzwerte Ty und Tz eine wesentliche Rolle in diesem
Modell spielen. Es gibt unterschiedliche Möglichkeiten sie zu bestimmen. Zum
einen lassen sich mit geeigneten Trainingsdaten Grenzwerte ausprobieren und op-
timieren. Es lassen sich aber auch machine learning Methoden anwenden.
Nach der Zuweisung des Matchingtypes ist die wesentliche Arbeit der Duplikaten-
erkennung getan. Die Tupelpaare, die als possible match deklariert wurden, werden da-
raufhin jeweils durch einen Domänenexperten manuell als match oder non-match klassi-
fiziert. Anschließen können nun, je nach Anwendungsfall die Duplikate geeignet weiter
verarbeitet werden.
v. Clustern der Duplikate
Für die meisten Anwendungsfälle genügt es nicht die Duplikatenpaare zu finden. Das
Ziel ist alle Tupel zu finden die ein realweltliches Objekt repräsentieren. Somit müssen
die gefundenen Duplikate zu Clustern zusammengefasst werden. Dieses Clustering wird
in der Regel über gewisse Formen der Transitivität realisiert [NH10, S. 52ff]. Eine sehr
einfache Form ist es die Transitivehülle über die Duplikate zu bilden.
Schlussendlich müssen die erkannten Cluster geeignet fusioniert werden oder es muss
ausgewählt werden welches der Tupel weiter existieren soll und welches gelöscht wird.
12Zu beachten ist, dass u(c) + m(c) = 1 nicht gelten muss.13Wenn Ty = Tz wird die Menge P (possible match) nicht berücksichtig.
10 2. Grundlagen
Diese Anschlussaufgaben sind jedoch in hohem Maße kontextabhängig und nicht mehr
Teil der eigentlichen Erkennung von Duplikaten.
vi. Verifikation
Die Erkennung von Duplikaten muss nach geeigneten Parametern gemessen und be-
wertet werden, um eine Optimierung des gewählten Modells zu ermöglichen. Bei der
Beurteilung einer Duplikatenerkennung sind zwei wichtige Kenngrößen precision und
recall [MRS08, S. 142f] von Bedeutung. Um diese Größen zu definieren benötigt man zu-
nächst andere Werte. Diese Größen sind insbesondere die Fehlerraten false-non-match und
false-match. Als false-match wird ein Tupelpaar bezeichnet, das kein Duplikat ist, aber von
dem gewählten Modell als Duplikat deklariert wurde. Umgekehrt bezeichnet mit false-non-match ein Tupelpaar welches ein Duplikat ist, von dem Modell aber nicht als ein
solches erkannt worden ist.
Dupliklate kein Duplikat
match true-match false-match
non-match false-non-match true-non-match
Die precision P ist das Verhältnis der Gesamtzahl an gefunden Duplikate zu den fälsch-
licherweise als Duplikate erklärten Tupelpaaren.
P =|true−match|
(|true−match|+ | f alse−match|)
der recall R das Verhältnis der gefundenen Duplikate zu den gesamt existenten Duplikat-
en darstellt. Zu beachten ist dass ein recall von 100% trivial zu erreichen ist, in dem alle
Paare als Duplikate deklariert werden.
R =|true−match|
(|true−match|+ | f alse− non−match|)
Die beiden Kenngrößen precision und recall beeinflussen sich wechselseitig, es gilt bei der
Optimierung eines Modells eine geeignete Balance zwischen ihnen zu finden. Generell
lässt sich darüber hinaus sagen, dass in der Regel eine Vergrößerung des Bereiches der
possible-match die Anzahl von false-non-matches und false-matches verringert [BS06, S. 106ff].
Es erhöht sich im Gegenzug die Anzahl der possible matches die durch einen Experten
geprüft werden müssen, was ebenfalls nicht gewünscht ist.
2.2. Existierende Systeme zur Duplikatenerkennung in
relationalen Daten
Zur Erkennung von Duplikaten in klassischen, insbesondere relationalen Datenbestän-
den existieren fertige Systeme. Mit Hilfe dieser Systeme lässt sich zum einen an Verbesse-
2.2. Existierende Systeme zur Duplikatenerkennung in relationalen Daten 11
rungen und Erweiterungen forschen, zum anderen dienen sie teilweise auch dem prak-
tischen Einsatz. Es wird eine Auswahl der existierenden Systeme im Folgenden kurz
vorgestellt.
• AJAX
Dieses Projekt wurde an der Technischen Universität Lissabon von Helena Gal-
hardas um 1999 gegründet. Es wird als deklaratives, erweiterbares Framework zur
Datenbereinigung bezeichnet. Es lassen sich unterschiedliche Datenquellen einbin-
den und integrieren (Text, Datenbank, XML). Der gesamte Prozess der Datenbere-
inigung ist als gerichteter Graph implementiert. Das Kernstück dieses Frameworks
ist die erweiterbare, deklarative Sprache mit welcher der Benutzer den Bereini-
gungsprozess beschreibt. Diese Sprache ist an die SQL Syntax angelehnt. In dem
AJAX Framework sind bestimmte Operationen wie Mapping, Merging und Clus-
tering enthalten, diese lassen sich mittels der eigenen Sprache parametrisieren und
zusammen fügen. Das Matching, also die Duplikatenerkennung basiert auf Ähn-
lichkeitsfunktionen, die mit einem Grenzwert versehen werden und mit If-Blöcken
kombiniert werden. Diese parametrisierten Operationen werden dann zu einem
gerichteten Graphen zusammen gestellt. Zu erwähnen ist, das AJAX keine Such-
raumreduzierung vorsieht, sondern immer von einem Kartesischem Produkt aus-
geht. Technisch basiert das AJAX Projekt auf Java und SQL und verfügt über eine
grafische Oberfläche [GFSS99][GFSS00].
• HumMer,
ist ein Projekt der Humbold Universität zu Berlin, welches seit 2005 existiert und
von Felix Naumann gegründet wurde. Der Name HumMer ist die Kurzform von
Humbold Merger. Das Ziel dieses Projektes ist das automatische oder halb-auto-
matische integrieren von Datenbeständen vielfältiger Art. Auf Grund dessen wird
ein Step-by-Step Ansatz verfolgt. Intern arbeitet HumMer ähnlich wie AJAX mit
einer deklarativen, an SQL angelehnten Sprache. Diese Sprache und deren Aus-
führung stellen den Kern von HumMer dar. Nach außen wird dies über die GUI
nicht notwendigerweise deutlich.14
Nachdem Basiskonfigurationen vorgenommen wurden, wie das Einbinden der
Datenquellen, wird automatisch ein Schemamatching durchgeführt, welches an-
schließend vom Benutzer angepasst werden kann. Dieser Ansatz ist der Grund-
gedanke des Projektes: Zunächst wird ein automatisch erstellter Vorschlag gegeben,
dieser kann dann von dem Benutzer angepasst und optimiert werden. Nach dem
Schemamatching, werden nach dem gleichen Prinzip die Duplikatenerkennung
und anschließend die Datenfusion vorgenommen. Die letztendliche Konfiguration
wird in XML Form gespeichert. Wobei der Fokus darauf liegt, eine Datenintegra-
14Eine Übersicht über die Architekur von HumMer ist im Appendix 1 zufinden.
12 2. Grundlagen
tion einmalig und dafür benutzerfreundlich durchzuführen. Die Duplikatenerken-
nung beinhaltet eine Suchraumdefinition (realisiert durch Pruning), den Vergleich
der Tupelpaare mit Ähnlickeitsfunktionen und Grenzwerten und anschließend eine
Clustering (realisiert als Transitive Hülle). Technisch basiert dieses Projekt auf Java
[BBN+05][NBBW06][BN05][Nau].
• Fusionplex,
ist ein Projekt der George Mason Universität das circa 2004 von Philipp Anokhin
und Amihai Motro gegründet wurde. Es ist in Java, als Server Applikation geschrie-
ben und verfügt über ein Web-Frontend. Im Gegensatz zu dem zuvor vorgestellten
System hat dieses seinen Fokus weniger auf dem Bereich der Duplikatenerken-
nung, sondern auf dem der geeigneten Datenfusion. So wird abhängig von kon-
figurierbaren Metadaten (Zeit der Erstellung, Kosten, Genauigkeit, etc.) eine Fu-
sion der Daten vorgenommen. Diese hat in erster Linie das Ziel die Vollständigkeit
der Daten zu erhöhen. Als Eingabe können dabei mehrere Datenbanken dienen.
Zwischen diesen Datenbanken wird vom Benutzer ein Schemamapping, mittels
Views vorgenommen. Als Anfragesprache dient eine an SQL angelehnte, deklar-
ative Sprache [MA06].
2.3. Probabilistische Daten
Das zu implementierende Framework zeichnet sich insbesondere durch die Fähigkeit aus
probabilistische Daten zu verarbeiten. Um dieses in geeigneter Form zu ermöglichen, ist
zunächst zu klären wie die Datenstrukturen vorherrschender Systeme gestaltet sind. In
der bisherigen Forschung zu diesem Thema sind unterschiedliche Modelle vorgeschla-
gen worden [BGMP02][FR97][vKdKA05], die ersten probabilistische Datenbank Modell
wurde 1987 von Cavallo und Pittarelli konzipiert und 1990 von Barbara, Garcia-Molina
und Porter [CP87][BGMP90][ZDG03]. Mittlerweile sind mehrere protoypische Imple-
mentationen von probabilistischen Datenbanken vorhanden. Zu erwähnen sind hier Mys-
tiq [BDM+05], MayBMS [HAKO09] und Trio [ABS+06]. In dieser Arbeit wird das ULDB
Modell verwendet werden, welches die Basis für Trio liefert und im Folgenden kurz
vorgestellt wird [BDSH+08].
Das ULDB Modell beschäftigt sich mit zwei Themen, der uncertainty und dem lineage.
Die uncertainty meint die Unsicherheit von Datensätzen und damit ihre Wahrschein-
lichkeitsbasiertheit. Das lineage meint die Herkunft der Daten, d.h. aus welchen Quellen
sie gegebenenfalls abgeleitet wurden. Für diese Arbeit ist lediglich die Unsicherheit der
Daten interessant. Das lineage könnte zu einem späteren Zeitpunkt des QloUD Projektes
evtl. im Ausgabeformat Berücksichtigung finden [PVKDKR10].
Das ULDB Modell ist eine Erweiterung des klassischen Datenbankmodells, was be-
deutet, dass jede traditionelle Datenbank mit ULDB abgebildet werden kann. Eine prob-
abilistische Datenbank repräsentiert mehrere mögliche Ausprägungen einer Datenbank.
2.4. Duplikatenerkennung in Probabilistischen Datenbeständen 13
Was sich Formal wie folgt definieren lässt: PDB = (W, P) wobei W = I1 . . . In die mög-
lichen Welten/Ausprägungen sind und P : W → (0, 1] mit ∑I∈W P(I) = 1 die Wahrschein-
lichkeitsverteilung darüber.
Um diese Ausprägungen realisieren zu können verwendet ULDB und damit Trio das
Konzept der x-tuple. Ein x-tuple ist ein Tuple, welches in mehreren, sich gegenseitig auss-
chließenden, Ausprägungen/Alternativen innerhalb einer x-relation vorliegt. Eine
x-relations ist dabei im Wesentlichen dadurch definiert, dass es eine Relation ist welche
x-tuple enthält.
Ein Anwendungsfall für ein x-tuple wäre der Folgende:
Linda hat etwas gerochen und ist sich nicht sicher ob es sich dabei um Zitronen-
oder Orangenaroma gehandelt hat. Vielleicht hat sie auch nichts gerochen,
sondern sich dies nur eingebildet.
Die x-relation gerochen könnte folgendermaßen aussehen:
id name gerochen p(t)
t1 Linda Zitrone 0,3 ?
Linda Orange 0,5
t2 Tine Kirsche 1,0
Das Tupel t1 liegt in drei Ausprägungen vor:
1. Linda hat Zitrone gerochen. p = 0, 3
2. Linda hat Orange gerochen. p = 0, 5
3. Linda hat nicht gerochen. p = 0, 215
Wohingegen Tine mit einer Wahrscheinlichkeit von 1, 0 Kirsche gerochen hat. Das Tu-
pel t2 entspricht somit einem traditionellen Datenbankeintrag ohne die Notwendigkeit
von Eintrittswahrscheinlichkeiten.
In der Definition der ULDB ist formuliert, dass eine unendliche Anzahl von Alterna-
tiven nicht unterstützt wird. Um trotzdem mit unendlichen Domänen, wie den Natür-
lichen Zahlen umgehen zu können, existiert eine Wahrscheinlichkeit auf der Ebene der
Attributwerte. Dies kann durch eine Bedingung realisiert sein (z.B. preis > 5)
2.4. Duplikatenerkennung in Probabilistischen Datenbeständen
Der grundsätzliche Ablauf des gesamt Prozesses der Duplikatenerkennung unterschei-
det sich nicht von dem in Abschnitt 2.1 dargestellten Prozess für traditionelle Daten.
Dieselben aufeinander folgenden Phasen 1. Daten Vorbereitung, 2. Suchraumdefinition,
15Tupel die mit einer gewissen Wahrscheinlichkeit nicht Teil der x-relation sind werden am Ende der Zeilemit ? markiert.
14 2. Grundlagen
3. Attributwerte Abgleich, 4. Entscheidungsmodell und 5. Verifikation sind vorhanden,
jedoch muss jede dieser Phasen auf das in Abschnitt 2.3 beschriebene Datenmodell der
Probabilistischen Daten angepasst werden. Im Folgenden werden die zentralen Phasen
der Duplikatenerkennung der Attributwerte Abgleich und das Entscheidungsmodell für
Probabilistische Daten dargestellt. Die Darstellung entspricht dem von Panse in [PVKDKR10]
vorgeschlagenen Vorgehen und setzen das ULDB Datenmodell voraus [BDSH+08].
2.4.1. Attributwerte Abgleich
Im traditionelle Modell wird die Ähnlichkeit zweier Tupel zunächst durch einen Ähn-
lichkeitsvektor ausgedrückt (siehe iii), welcher Eingabe für das anschließende Entschei-
dungsmodell ist. Bei dem Vergleich von x-tuplen kommt ein Zwischenschritt hinzu. Ein
x-tuple besteht aus einer oder mehr Alternativen t = t1, t2, . . . tn. Die Ähnlichkeit zweier x-tuple t1 = t11, t12, . . . und t2 = t21, t22, . . . wird über den paarweisen Vergleich ihrer Alter-
nativen berechnet. Für jeden dieser Vergleiche wird ein Ähnlichkeitsvektor entsprechend
dem traditionelle Attributwerte Abgleich erstellt. Genau wie bei der traditionelle Vari-
ante können unterschiedliche Ähnlichkeitsfunktionen verwendet und kombiniert
werden.
Zu beachten ist, dass es nach dem ULDB Modell auch Wahrscheinlichkeiten auf At-
tributwertebene geben kann. In diesem Fall werden die Attributwerte paarweise ver-
glichen. Die resultierende Ähnlichkeit wird mit dem Produkt, der jeweiligen Wahrschein-
lichkeiten der Attributwerte gewichtet und aufsummiert. Das Ergebnis ist die erwartete
Ähnlichkeit der Attributwerte von zwei Alternativen a1 und a2 (z.B. t11.gerochen und
t21.gerochen) der Tupel t1 und t2 (D̂ = {D∧⊥}Die jeweilge Domäne und die Möglichkeit
der Nicht-Existenz).
sim(a1, a2) = ∑d1∈D̂
∑d2∈D̂
P(a1 = d1, a2 = d2) · sim(d1, d2)
Führt man die Berechnung wie oben beschrieben durch, so erhält man für jedes Paar
von Alternativen welches verglichen wird einen Ähnlichkeitsvektor mit einem Eintrag
für jedes Attribut. Bei dem Vergleich von zwei x-tuplen entsteht somit eine Ähnlichkeits-
matrix, wobei jede Zeile einem Ähnlichkeitsvektor eines Alternativenpaares entspricht.
Für die Duplikatenerkennung in Probabilistische Daten ist diese Matrix das Ergebnis
des Attributwerte Abgleiches. Auf der Basis dieser Matrix bestimmt im Anschluss ein
Entscheidungsmodell, ob es sich um ein Duplikat handelt oder nicht.
2.4.2. Entscheidungsmodell
Das Entscheidungsmodell für Probabilistische Daten lässt sich als Funktion verstehen,
welche einer Ähnlichkeitsmatrix einen der Werte M, P oder U zuordnet. Dies kann auf
unterschiedliche Weise geschehen. Im Folgenden werden zwei Varianten vorgestellt eine
Ähnlichkeitsbasierte und eine Entscheidungsbasierte.
2.4. Duplikatenerkennung in Probabilistischen Datenbeständen 15
1. Das ähnlichkeitsbasierte Modell berechnet mit einer Kombinationsfunktion für
jedes Alternativenpaar einen Ähnlichkeitswert (Schritt 1). Die Kombinationsfunk-
tion erhält den Ähnlichkeitsvektor des Alternativenpaares als Eingabe und kann
somit Gewichtungen der einzelnen Attribute vornehmen. Es resultiert ein Ähn-
lichkeitsvektor, welcher einen Eintrag pro Alternativenpaar enthält. Aus diesem
Vektor wird anschließend die Ähnlichkeit des Tupelpaares abgeleitet, mit Hilfe ein-
er sogenannten Ableitungsfunktion (Schritt 2). Mit diesem Ähnlichkeitswert und
ein oder zwei Grenzwerten wird dem Tupelpaar dann ein Wert aus M, P, U oder
aus M, U zugeordnet (Schritt 3).16
Eine naheliegende Ableitungsfunktion wäre die Bestimmung des Erwartungswer-
tes der Tupelähnlichkeit zu berechnen. Diese Berechnung ist nicht so trivial wie
sie zunächst scheint. Es genügt nicht die Ähnlichkeitswerte der Alternativen ein-
fach mit der zugehörigen Wahrscheinlichkeit zu multiplizieren und die jeweiligen
Ergebnisse aufzusummieren. Der Grund dafür ist das im ULDB Modell ein x-tupleeine Wahrscheinlichkeit dafür besitzt, ob es überhaupt Teil der Relation ist. Ist die
Summe der Wahrscheinlichkeiten seiner Alternativen kleiner als eins, dann gibt es
eine genau definierte Wahrscheinlichkeit dafür, dass das betrachtete Tupel nicht
Teil der Relation ist [BDSH+08].
Für die Bestimmung der Ähnlichkeit zwischen zwei Alternativen ist die Betrach-
tung der möglichen Nicht-Mitgliedschaft in einer Relation allerdings unerheblich.
Die Ähnlichkeit zwischen zwei Alternativen kann, nachdem hier vorgestellten Ver-
fahren nur unter der Bedingung bestimmt werden, dass beide Alternativen ex-
istieren. Demzufolge darf die Möglichkeit der Nicht-Mitgliedschaft in einer Re-
lation keinen Einfluss auf den Erwartungswert haben, da dieser sonst den Ähn-
lichkeitswert verzerren könnte. Das bedeutet, dass die Wahrscheinlichkeit jeder Al-
ternative normalisiert bzw. skaliert werden muss [ABS+06].
Weiterhin ist zu beachten, dass nicht normalisierte Ergebnisse von Ähnlichkeits-
funktionen17 die Ähnlichkeitswerte auch verzerren können.18
Um die Ähnlichkeit zwischen den Tupeln t1 und t2 zu bestimmen ist folgende
Formel notwendig:
sim(t1, t2) = ∑i∈[1,k]
∑j∈[1,l]
p(ti1)
p(t1)· p(tj
2)
p(t2)· sim(ti
1, tj2)
Anschließend wird das Tupelpaar t1 und t2 mit einer durch zwei Grenzwerte defi-
nierten Relation auf die Menge {M, P, U} abgebildet.
16Abhängig davon ob Possible Matches gewünscht sind oder nicht.17Nicht normalisiert bedeutet das sie ihr Ergebnis nicht auf dem Intervall [0, 1] zurückgeben.18Vergleiche dazu ein Beipspiel in [PVKDKR10, IV.B]
16 2. Grundlagen
2. Das entscheidungsbasierte Modell geht etwas anders vor. Zunächst wird, wie bei
dem ähnlichkeitsbasierten Modell der Ähnlichkeitswert für zwei Alternativen, mit
einer Kombinationsfunktion bestimmt. Anhand dieses Ähnlichkeitswertes und
einem oder zwei Grenzwerten wird ein Alternativenpaar nun in M, P oder U klas-
sifiziert (Schritt 1). Mit dieser Klassifizierung arbeitet anschließend die Ableitungs-
funktion (Schritt 2). Diese bestimmt auf Basis der Klassifizierung und der dazu
gehörenden bedingten Wahrscheinlichkeit einen Ähnlichkeitswert für das Tupel-
paar. Dieser Ähnlichkeitswert wird anschließend final in M, P oder U klassifiziert
(Schritt 3).
Berücksichtigt man bei der Ableitungsfunktion für das entscheidungsbasierte Mod-
ell die Wahrscheinlichkeitstheorie, so ist eine naheliegende Variante die Berech-
nung der Ähnlichkeit als Verhältnis (Vergleiche dazu [PVKDKR10, Formel 7-9]. Ins
Verhältnis gesetzt werden die Wahrscheinlichkeit, dass es sich um ein Duplikat han-
delt (P(m)) zu der Wahrscheinlichkeit, dass es sich nicht um ein Duplikat handelt
(P(u)) (ähnlich wie Fellegi und Sunter [FS69, Abschnitt 1]).
sim(t1, t2) =P(m)
P(u)
Die Ableitungsfunktion für das entscheidungsbasierte Modell muss, wie die des
ähnlichkeitsbasierten Modelles, die Normalisierung bzw. Skalierung der
Wahrscheinlichkeiten der Alternativen berücksichtigen. Dementsprechend sehen
die Formeln zur Bestimmung der beiden benötigten Wahrscheinlichkeiten folgen-
dermaßen aus:
P(m) = ∑(ti
1,tj2)∈M
p(ti1)
p(t1)· p(tj
2)
p(t2)
P(u) = ∑(ti
1,tj2)∈U
p(ti1)
p(t1)· p(tj
2)
p(t2)
17
3. Anforderungen an das Framework
Diese Arbeit ist nur ein Teil des größeren Projekts Quality of Uncertain Data1, welch-
es sich zur Aufgabe gemacht hat die Qualität von probabilistischen Daten zu er-
forschen. Ein spezieller Fokus liegt dabei auf der Duplikatenerkennung in Prob-
abilistischen Daten, wobei in diesem Projekt die Duplikatenerkennung in einem
größeren Prozess wie dem der Datenbereinigung oder der Datenintegration von
Interesse ist.
Ziel dieser Arbeit ist es, ein adaptives und flexibles Framework zu implementieren,
welches auf dem in Abschnitt 2.3 vorgestelltem Modell basiert. Das Framework soll
die Forschung im Bereich der Datenqualität von Probabilistischen Daten erleichtern
und ist demnach hauptsächlich als Werkzeug für Wissenschaftler zu betrachten. Da
die Forschung in eben diesem Bereich noch nicht weit fortgeschritten ist, muss das
Framework so flexibel sein, Änderungen und Erweiterungen leicht integrieren zu
können. Trotz all der geforderten Flexibilität ist auch zu berücksichtigen, dass das
fertige Framework in der Lage sein muss große Datenmengen zu verarbeiten.
Am Informatik Department in Hamburg wird vornehmlich die Programmierspra-
che Java gelehrt und verwendet. Da das Projekt auch in Zukunft unter anderem
durch Abschlussarbeiten von Studenten voran getrieben werde soll, wurde als Rah-
menbedingung die Programmiersprache Java gewählt. Das sich die Sprache Java
für Systeme dieser Art bewährt hat, lässt sich auch dadurch belegen, dass die drei
in Abschnitt 2.2 erwähnten Systeme AJAX, Fusionplex und HumMer in Java im-
plementiert sind.
Die wichtigsten, der hier grob skizzierten Anforderungsbereiche an das zu im-
plementierende Framework werden im folgenden Abschnitt detaillierter erläutert.
Dabei handelt es sich um (i) der Bereich Theoretische Anforderungen, aus welchem
die konkreten Anforderungen der geleisteten Forschung entspringen. (ii) die Anfor-
derungen, die sich an das Softwaredesign richten und sich aus der Forderung der
Flexibilität ergeben. (iii) Wird erläutert, wie die Arbeit mit der Software durch die
Ermöglichung von Zwischenergebnissen erleichtert werden kann und welche An-
forderungen sich daraus ergeben. (iv) Abschließend wird erläutert welche Anfor-
derungen sich aus der Forderung der Skalierbarkeit ergeben.
1http://vsis-www.informatik.uni-hamburg.de/projects/QloUD
18 3. Anforderungen an das Framework
3.1. Theoretische Anforderrungen
Das in Abschnitt 2.3 vorgestellte Modell zu Duplikatenerkennung in Probabilistis-
chen Daten ist Ausgangspunkt des Quality of Uncertain Data Projektes und damit
Basis für diese Implementierung. Das vorgestellte Modell geht von einem von Bati-
ni dargestellten, allgemeinen Phasenmodell der Duplikatenerkennung aus erweit-
ert um das Clustern der Duplikate (siehe Abschnitt 2.1). Dieses Phasenmodell sieht
somit sechs Phasen vor:
1) Datenvorbereitung, 2) Suchraumdefinition, 3) Attributwerte Abgleich,
4) Entscheidungmodell, 6) Clustern der Duplikate und 6) Verifikation. Dieses Mod-
ell muss mit Hilfe des Framework abgebildet werden können. Die fachliche Im-
plementation steht nicht im Zentrum dieser Arbeit. Jedoch sollen die wichtigsten
Phasen implementiert werden. Besonderer Wert wird dabei auf die Phasen At-
tributwerte Abgleich auf Entscheidungmodell gelegt. Diese Phasen führen die
wesentlichen Schritte der Duplikatenerkennung durch. Andere Phasen werden triv-
ial (Suchraumdefinition) oder nicht implementiert (Datenvorbereitung, Verifika-
tion). In dem Modell taucht die Phase des Duplikatennclusterings nicht auf, sie
taucht jedoch in anderen Modellen auf, und
Bei der Implementation des Attributwerte Abgleich ist zu beachten, dass bei dem
Vergleich von zwei x-tuplen jeweils alle Alternativen miteinander verglichen wer-
den müssen. Beim Vergleich der Alternativen müssen alle Attribute und jeweils alle
Versionen der Attributwerte verglichen werden.2 Diese Anforderungen ergeben
sich aus dem von F. Panse vorgeschlagenen Modell [PVKDKR10]. Darüber hinaus
muss es möglich sein für ein Attribut mehrere Ähnlichkeitsfunktionen zu definieren
und die daraus resultierenden Ähnlichkeiten (pro Attribut pro Ähnlichkeitsfunk-
tion) gewichtet zu aggregieren.
In der Implementation des Frameworks sollten einige Ähnlichkeitsfunktionen vor-
liegen, es müssen jedoch bei Bedarf neue hinzugefügt werden können. Die Ähn-
lichkeitsfunktionen sollten dabei normiert sein, d.h. immer einen Wert zwischen 0
und 1 zurückgeben, da sonst die Wahrscheinlichkeiten verzerrt werden können.3
Das von F. Panse skizzierte Modell enthält zwei Entscheidungsmodelle. Daraus
ergibt sich sofort, dass die Implementation in der Lage sein muss unterschiedliche
Entscheidungsmodelle anzuwenden. Die einzelnen Entscheidungsmodelle müssen
darüber hinaus in hohem Maße konfigurierbar sein. In Abschnitt 2.3 ist erläutert,
dass in den von F. Panse vorgeschlagenen Modellen, zunächst durch eine Kombina-
tionsfunktion die Ähnlichkeit zweier Alternativen bestimmt wird. Dabei ist wün-
schenswert, dass es mehrere Kombinationsfunktionen geben kann deren Ergebnis
anschließend geeignet aggregiert wird.
2Vergleiche dazu Abschnitt 2.33Vergleiche dazu [PVKDKR10]
3.1. Theoretische Anforderrungen 19
Die Möglichkeit mehrere Kombinationsfunktionen würden es erlauben durch diese
Kombinationsfunktionen und eine entsprechende Aggregationsfunktion Knowledge-Rules4 abzubilden. Nach Anwendung der Kombination folgt bei dem ähnlichkeits-
basierten Entscheidungsmodell eine Ableitungsfunktion, die innerhalb des Frame-
works austauschbar und parametrisierbar sein muss, was auch für die anschließ-
ende Klassifikation gilt.
Die andere vorgeschlagene Variante des Entscheidungsmodelles, das entschei-
dungsbasierte Modell führt nach der Kombination eine Klassifikation der Alterna-
tiven durch. Diese Klassifikation muss austauschbar und konfigurierbar sein. Da-
rauf folgen eine Ableitungsfunktion und anschließend eine finale Klassifikation.
Für diese gelten ebenfalls die Flexibilitätsansprüche. Zu bemerken ist an dieser
Stelle, dass die Ableitungsfunktionen der beiden Modelle unterschiedliche Daten-
typen als Eingabe erhalten, somit lassen sie sich nicht identisch behandeln (siehe
dazu Appendix 2).
Die Forschung zu dem Thema Duplikatenerkennung in probabilistischen Daten
soll im Rahmen des Quality of Uncertain Data Projektes noch deutlich weiter geführt
werden. Das schließt ein, dass es neue Entscheidungsmodelle sowie neue Varianten
des Attributwerte Abgleiches geben kann. Desweiteren können gänzlich neue
Phasen hinzukommen.
Diese Annahmen führen dazu, dass es nicht sinnvoll ist, dass ein zu vergleichen-
des Tupelpaar alle Phasen nacheinander durchläuft und anschließend das näch-
ste Tupelpaar, wie es das Pipelinemodell5 vorsehen würde. Dieser Ansatz wäre
mit einiger Sicherheit performanter, dem wissenschaftlichen Modell ist ein sequen-
zielles Abarbeiten der Phasen jedoch näher. Da die wissenschaftliche Arbeit mit
diesem Framework im Vordergrund steht, wird dieser Ansatz gewählt. Eine Phase
wird auf alle Tupelpaare angewendet, anschließend wird die nächste Phase ge-
startet.
3.1.1. Datenmodell
Die einzelnen Bestandteile der Duplikatenerkennung sollen leicht austauschbar und
erweiterbar sein. Um diese zu gewährleisten ist es hilfreich ein einheitliches Daten-
modell zu verwenden. Desweiteren sollen später viele unterschiedliche Eingabfor-
mate verwendet werden können, wie XML oder probabilistische Datenbanken. Es
gibt jedoch keinen einheitlichen Standard für probabilistische Daten, deshalb soll
ein möglichst mächtiges und flexibles Datenmodell implmentiert werden.
4Knowledge-Rules sind von Domänenexperten erstellte Regeln welche die Erkennung von Duplikaten un-terstützen. Vergleich [BS06]
5Zu Pipelineprogramming vergleiche [pip]
20 3. Anforderungen an das Framework
In dem Abschnitt 2.3 ist das ULDB Modell vorgestellt worden, welches von Trio
für die Implementation verwendet wird. Dieses Modell hat sich in der Praxis be-
währt und wird dieser Arbeit zu Grunde gelegt. Es muss also eine Adaption des
ULDB Modell in Form einer Java Objekthierarchie erstellt werden, welche die für
die Duplikatenerkennung notwendigen Funktionen bereitstellt.
Für neue Eingabeformate muss somit lediglich ein Adapter geschrieben werden,
der die Daten in Java Objekte umwandelt die das Interface der Java-Repräsentation
des ULDB Modells implementieren.
3.2. Softwaretechnische Flexibilität
Im voran gegangenen Abschnitt wurde an vielen Stellen schon auf die geforderte
Flexibilität der Software eingegangen. Jedwede Art von Ähnlichkeitsberechnung
sollte parametrisierbar6 und austauschbar sein. Es sollen ganze
Phasen austauschbar sein und es soll variabel viele Phasen geben dürfen, da zu
diesem Zeitpunkt noch nicht klar ist wieviele Phasen es geben wird. Es ist gut
möglich das Phasen hinzukommen die noch nicht im aktuellen Modell zu Dup-
likatenerkennung berücksichtigt sind. Wobei für die Phasen die Typen der Eingabe-
werte nicht feststehen. Weiterhin variieren die Kardinalitäten der Ein- und Aus-
gabemengen. Z.B. könnte die Suchraumdefinition zwei Relationen als Eingabe er-
halten, generiert daraus aber sehr viele Tupelpaare, wohingegen die Phase des At-
tributwerte Abgleiches die Kardinalität der Mengen beibehält.
All diese Konfigurationen sollen zur Laufzeit geschehen. Zu einem späteren Zeit-
punkt soll eine grafische Oberfläche zu diesem Framework existieren, in welch-
er das konkrete Modell zur Duplikatenerkennung konfiguriert und sofort genutzt
wird. Ein zweiter Aspekt der Konfiguration ist die Forderung das dem Framework
Komponenten hinzugefügt werden können ohne das diese dafür neu kompiliert
werden muss.
Die bisher genannten Anforderungen lassen sich in zwei Bereiche aufteilen. Die
einen beziehen sich auf die Konfigurierbarkeit und Austauschbarkeit der einzelnen
Komponenten, aus denen das von F. Panse vorgeschlagene Modell besteht. Dazu
gehören die Ähnlichkeits-, Ableitungs- und Kombinationsfunktionen. Die anderen
Anforderungen beziehen sich auf größere Komplexe, wie die Austauschbarkeit von
Phasen und die Abfolge von Phasen und ähnliches. Diese als zweites genannten
Anforderungen sind tiefliegender, da sie die Implementation von allen Bestand-
teilen beeinflussen. Daraus folgend werden diese zuerst behandelt.
6Die Ableitungsfunktionen müssen beispielsweise mit Grenzwerten konfiguriert werden.
3.2. Softwaretechnische Flexibilität 21
3.2.1. Das Phasen Modell
Um eine solch flexibles System zur Duplikatenerkennung zu implementieren, ist
zunächst eine Infrastruktur nötig, die einen flexiblen Umgang mit den Phasen er-
möglicht. Diese Infrastruktur wird hier mit ihren grundsätzlichen Anforderungen
und Lösungsskizzen, in Form eines Phasenmodells dargestellt. Zunächst wird er-
läutert, was unter einer Phase verstanden wird.
Eine Phase liest ihre Eingabeelemente sequenziell, wendet eine Funktion für jedes
Element an und kann Ausgabeelemente produzieren (mehr oder weniger als es
Eingabeelemente gab). Entscheidend ist, dass eine Phase immer genau einmal über
eine Menge von Eingabeelementen iteriert. Dieser sehr einfache Lebenszyklus wird
durch andere Ereignisse ergänzt. So müssen bestimmte Initialisierungen oder Auf-
räumarbeiten beim Start oder Ende einer Phase erledigt werden. Um für konkrete
Implementationen flexibel zu sein, sollten viele Möglichkeiten gegeben werden an
Punkten im Lebenszyklus einer Phase einzugreifen. Diese kann über unterschied-
liche Konzepte geschehen, wie das Observer-Pattern [FFBS04] oder mittels des Tem-
plate-Patterns [FFBS04], das Methoden anbietet die im Lebenszyklus aufgerufen
werden, die überschrieben werden können. Um eine solche Phase flexibel und hand-
habbar zu gestalten gibt es viele Mittel, es ist abzuwägen wie viele im ersten Wurf
dieses Frameworks eingebaut werden. Zu beachten ist weiterhin, dass eine Phase
über einen flexiblen Mechanismus verfügen muss, wie Konfigurationen aufgenom-
men und intern verfügbar gemacht werden können.
Geht man davon aus, dass die Implementation einer Phase vorliegt, so muss nun
ermöglicht werden, dass die Phasen in einer frei wählbaren Reihenfolge hinter
einander ausgeführt werden können. Beliebig viele dieser Phasen müssen zu einem
Ablauf zusammengefügt werden können, hier noch einmal einige Anforderungen
für einen solchen Ablauf.
• Beliebig viele Phasen
• Variable Ein- und Ausgabewerte
• Die Phasen werden sequenziell bearbeitet
• Phasen müssen über gemeinsame Metadaten verfügen.
Phasen sollen beliebige Datentypen behandeln können deshalb sollen sie Ein- und
Ausgabe Wert vom Typ Object sein. Diese Variante bietet die höchste Flexibilität
verzichtet dabei aber auf die Typensicherheit. Der Grund frü diese Verzicht liegt
darin, dass jederzeit ohne neues kompilieren neue Phasen zum Modell hinzugefügt
werden können sollen und somit kein Generischertyp ausreichend flexibel wäre
und gleichzeitig eine nennenwerte Typensicherheit liefern würde. Das Prüfen der
Kompatibilität der Phasen muss deshalb z.B. von der GUI übernommen werden. Im
22 3. Anforderungen an das Framework
Zusammenhang mit der Speicherung von Zwischenergebnissen (siehe Abschnitt
3.3) lässt sich die Typensicherheit nur sehr schwer garantieren.
3.2.2. Modell zu Erkennung von Duplikaten
Das vorgestellte Phasenmodell enthält noch keinerlei Abhängigkeit von den proba-
bilistischen Daten. Es dient lediglich dem Management der Phasen. Der Bezug zur
Duplikatenerkennung in probabilistischen Daten muss anschließend auf Ebene der
einzelnen Phasen entstehen. Ein Schritt des theoretischen Modells aus Abschnitt 2.1
und Abschnitt 2.3 wird dann durch mindestens eine Phase Implementiert werden.
Jedoch kann es in einigen Fällen sinnvoll sein, einen Schritt des Theoretischen Mod-
ells auf zwei Phasen in der Implementation zu verteilen. Zu erwarten ist dieses am
ehesten innerhalb des Entscheidungsmodells.
Wie in Abschnitt 3.1 erwähnt, ist die Austauschbarkeit und die Parametrisierbarkeit
der einzelnen Komponenten dieses Bereiches von besonderem Interesse. Die Kom-
ponenten die austauschbar gestaltet werden können und sollen sind zahlreich.
Außerdem müssen sie auf unterschiedlichen Ebenen konfigurierbar sein. So müssen
z.B. Ähnlichkeitsfunktionen und Kombinationsfunktionen gesetzt werden können,
es muss aber auch möglich sein ein ganzes Entscheidungsmodellen auszutauschen.
Diese Flexibilität ermöglicht es Teile der Duplikatenerkennung getrennt weiter zu
entwickeln. Zum Beipspiel an einer anderen Universität.
Es muss aber nicht nur die Implementation einer bestimmten Komponente aus-
gewählt werden, sonder darüber hinaus müssen für die ausgwählten Komponen-
ten, die nötigen Parametern konfiguriert werden (z.B. die Grenzwerte für das
Entscheidungsmodell).
3.2.3. Metadaten
Die Daten die von dem Phasen Modell bearbeitet und weitergegeben werden be-
ziehen sich immer auf ein Tupel. Es kommt aber vor das Daten nötig sind die sich
auf eine Gruppe von Tupeln oder auf die Gesamtheit der Tupel beziehen. Daten
dieser Art werden als Metadaten bezeichnet und diese Daten müssen von jeder
Phase aus zugreifbar sein. Bei diesen Daten handelt es sich um kleine Datenmen-
gen, wie z.B. die Anzahl aller Tupel. Diese Daten können über die gesamte Laufzeit
im Arbeitsspeicher verbleiben. Ein Beispiel in dem solche Daten relevant sind wäre
eine Ähnlichkeitsfunktion die auf tf-idf basiert (term frequency–inverse document fre-quency).7
tf-idfd,t = tfd,t × idft
7 d =das betrachtete Dokument, t = der betrachtete Term, es kann sich um ein Wort, einen Buchstaben odereine andere Einheit von Zeichen handeln. N = Anzahl aller Dokumente, dft = Anzahl der Dokumentein denen der Term t vorkommt.
3.3. Speicherung von Zwischenergebnissen 23
Um die inverse document frequency zu berechnen ist es nötig die Anzahl aller Doku-
mente zu kennen.
idfd,t = logNdft
In einem solchen Fall könnte eine frühere Phasen den Wert in den Metadaten spe-
ichern, so dass er aus einer Ähnlichkeitsfunktion zugreifbar ist.
3.3. Speicherung von Zwischenergebnissen
Die bisher aufgezeigten Anforderungen an die Implementation dieses Frameworks
machen die Adaptivität und Flexibilität deutlich. Ein weiter Punkt in Bezug auf
die Flexibilität soll die Arbeit mit diesem Framework erleichtern, die Speicherung
von Zwischenergebnissen. Die Duplikatenerkennung ist ein sehr rechenaufwändi-
ger Prozess, so dass es sinnvoll ist Zwischenstände festzuhalten, da es sonst zu
Mehrfachberechnungen kommen könnte.
Die Analyse von Problemen bei der Duplikatenerkennung beschränkt sich in der
Regel zu einem Zeitpunkt auf einen bestimmten Teil des Prozesses. Oftmals werden
Grenzwerte ausprob trainiert um ein optimales Ergebnis zu erzielen. Es wäre bei
großen Datenmengen zeitaufwändig und überflüssig bei kleinen Änderungen den
gesamten Prozess neu anzustoßen. Es ist deshalb sinnvoll, dass ein Gesamtprozess
von einem bestimmten Zwischenschritt aus, gestartet werden kann und die dem
entsprechenden, vorberechneten Daten verwenden kann. Dieses erfordert, dass die
Ergebnisse der einzelnen Phasen persistiert werden können.
Das HumMer Projekt verfolgt einen Step-By-Step Ansatz bei der Duplikatenerken-
nung, bei dem sich der Benutzer schrittweise mit den einzelnen Zwischenergebnis-
sen auseinander setzen kann [Nau]. Diese Möglichkeit soll für das hier zu imple-
mentierende Framework durch die Einführung von Zwischenergebnissen geschaf-
fen werden.
3.4. Anforderungen an die Skalierbarkeit
Die Erkennung von Duplikaten ist besonders in großen Datenbeständen von
Relevanz. Da bei solchen Datenbeständen eine manuelle Bearbeitung nicht mehr
möglich ist. Es wurden Anwendungsbeispiele wie die Verwendung von probabilis-
tischen Daten in der Astrophysik, insbesondere im Zusammenhang mit mehreren
Teleskopen genannt [SCH]. Hinzu kommt, dass im schlechtesten Fall, also bei kein-
er Suchraumdefinition die quadratische Anzahl an Tupelpaaren verglichen werden
muss. Das hier vorgestellte Modell geht davon aus, dass die Phasen nacheinander
bearbeitet und abgeschlossen werden, somit können die Tupelpaare nicht sequen-
24 3. Anforderungen an das Framework
ziell abgearbeitet werden (Pipelinemodell [pip]). Aus diesen Bedingungen ergibt
sich, dass es nicht möglich ist alle Daten gleichzeitig im Arbeitsspeicher zu halten.
Die Phasen bearbeiten die Daten sequenziell. Es somit notwendig, dass die einzel-
nen Phasen ihre Eingabedaten sequenziell vom persistenten Speicher lesen und
ihre Ausgabedaten sequenziell persistent schreiben. Entscheidend ist die Wahl, in
welcher Form die Daten persistiert werden. Ein sehr wichtiger Faktor bei der Wahl
ist die Geschwindigkeit des Lesens und des Schreiben. Es gibt jedoch noch weitere
Faktoren.
Es ist sinnvoll bestimmten Tupelmengen aus dem persistenten Speicher selektieren
zu können, und nicht alle Elemente lesen zu müssen. So wäre es sinnvoll, dass die
Phase nach dem Entscheidungsmodell (z.B. Duplikatenclustering) in der Lage ist,
nur die Tupelpaare zu lesen die als match deklariert wurden. Die Alternative wäre,
dass jeweils alle Daten gelesen und anschließend gefiltert werden. Dieser Ansatz
ist zwar einfach jedoch wesentlich langsamer.
Zu beachten ist weiterhin, dass die Daten geeignet serialisiert und deserialisiert
werden müssen. Es gibt unterschiedlichste Methoden wie Java-Objekte serialisiert
werden können.8 Jedoch verfügen nicht alle Mechanismen über ausreichende Flex-
ibilität. Die Objekte, die persistiert werden müssen sind nicht weiter definiert, es
können beliebige sein, dem entsprechend muss der Serialisierungprozess mit be-
liebigen Objekten umgehen können. Diese Forderung nach Flexibilität schränkt die
Auswahl der möglichen Serialisierungsmethoden erheblich ein.
8Serialisierung von Java-Objekten ist die Umwandlung in eines Java-Objektes in einen Bytestream. Dieserkann persisitiert oder gesendet werden und anschließend via Deserialisierung wieder in ein Java-Objektkonvertiert. In Java werden Klassen die Serialisierung unterstützen mit dem Serializable Interfacegekennzeichnet [Zuk01].
25
4. Implementierung des Phasen Modells
Die Anforderungen, welche dieses Framework erfüllen soll, sind im vorangegan-
genen Abschnitt dargestellt worden. Bei dieser Darstellung wurden die ersten An-
sätze deutlich, welches Vorgehen bei der Implementierung verwendet werden wird.
Am deutlichsten wurde, dass das Phasenmodell eine wichtige Basis darstellt und
somit als erstes entwickelt werden muss. Die infrastrukturellen Themen, wie die
Serialisierung und die Kommunikation zwischen den Phasen sind eng mit dem
Phasenmodell verbunden. Jedoch sollen auch diese Programmteile austauschbar
sein, sodass das Phasenmodell selbst zur Gänze auf Interfaces arbeiten wird.
Mit den genannten Punkten besteht schon das Phasen Modell aus einer Vielzahl an
Komponenten, die geeignet konfiguriert werden müssen. Diese Konfiguration find-
et auf zwei Ebenen statt. Zum einen werden die Komponenten zusammen gestellt
und bekannt gemacht, dies geschieht bevor das Programm geladen wird. Der an-
dere Teil ist Konfiguration, die zur Laufzeit erstellt und abgearbeitet wird.
Die skizzierten Punkte werden im Anschluss detailliert erläutert. Es wird auf die
Konzepte eingegangen aus denen die Modellierung in der vorliegenden Form ent-
standen ist. Desweiteren sind eine Vielzahl von Entwurfsmustern angewendet wor-
den, deren Nutzen in der jeweiligen Situation dargestellt wird. Kritische Punkte
werden mit Ausschnitten aus dem Quellcode verdeutlicht werden.
4.1. Phasenmodell
Abstrahiert man von der konkreten Gestaltung einzelner Phasen, so steht im zen-
trum ein grundlegendes Phasenmodell mit den folgenden Eigenschaften:
1. Es gibt Phasen die beliebig viele Ein- und Ausgabewerte haben.
2. Phasen sollen hintereinander ausgeführt werde.
Diese zwei Punkte beschreiben die wesentlichen Komponenten, die implementiert
werden müssen: das Grundmodell einer Phase und eine Art von Manager, der den
Ablauf steuert. Diese Beschreibung, so zutreffend sie auch ist, vereinfacht das Prob-
lem. Um diese zwei Kernkomponenten herum müssen viele zusätzliche Funktio-
nen realisiert werden. Es bedarf eines Ablaufplanes nachdem die Phasen bearbeitet
werden, die Phasen müssen sich Metainformationen teilen können und die Ein-
und Ausgabewerte müssen verwaltet werden.
26 4. Implementierung des Phasen Modells
4.1.1. Phasen
Die Aufgabe einer Phase ist es eine Entität einzulesen, beliebiges damit zu tun und
beliebig viele Werte wieder auszugeben. Eine solche Entität kann ein beliebiges
Java-Objekt sein, wie z.B. ein Tuplepaar oder ein Table. Diese Anforderung er-
fordert einen sehr flexiblen Lösungsansatz. Diese Sicht auf eine Phase berücksichtigt
nur den internen Anteil einer Phase, steht aber auch in einem größeren Kontext.
Sie hat eventuell eine vorangegangene Phase und/oder eine nachfolgende Phase.
Zwischen diesen Phasen muss kommuniziert werden. Diese Sicht ist eher eine Außen-
sicht und beschreibt die Phase im Zusammenspiel mit anderen.
Das Laden der Daten ist eine Aufgabe, die jede Phase erfüllen muss. Das konkrete
Laden wird dabei nicht von der Phase selbst erledigt. Sie erhält einen sogenannten
InputStorage, der nach dem Prinzip eines Iterators funktioniert.1 Der Datenbe-
stand wird dabei sequenziell gelesen. Auf die Implementierung dieses
InputStorageswird im nächsten Abschnitt genauer eingegangen. Vorerst genügt
es von seiner Existenz auszugehen.
Nachdem ein Datensatz gelesen wurde soll etwas mit ihm geschehen. Was genau
geschehen soll ist nicht Teil des Phasenmodells. Es muss lediglich die Möglichkeit
gegeben werden, dass ein anderes Stück Software möglichst leicht eine neue Funk-
tionalität einbauen oder eine bestehendeFunktionalität ändern kann. Es gibt die
unterschiedlichsten Entwurfsmuster, mit denen dies geschehen kann. Die Entschei-
dung ist auf das Templating Method Pattern gefallen. Dieses scheint den gegebenen
Umständen am besten zu entsprechen.
Eine Phase ist mittels eines Interfaces definiert und wird durch die Abstrakte Klasse
AbstractPhase2 implementiert. Die AbstractPhase implementiert das Inter-
face Phase bis auf eine Methode, die als abstrakte Methode belassen wird voll-
ständig. Diese Methode (apply(...)) muss von jeder erweiternden Klasse imple-
mentiert werden, sie ist jedoch auch die Einzige die implementiert werden muss.
Diese Aussage gilt zumindest für den Fall von dem hier ausgegangen wurde, d.h.
ein Eingabewert und beliebig viele Ausgabewerte.
1Ein Iterator ist vergleichbar mit einem Cursor auf Datenbankebene [KE04, S. 137ff]2de.unihamburg.vsis.probdi.control.AbstractPhase
4.1. Phasenmodell 27
Ein Beispiel für eine konkrete Implementierunmg einer sehr einfachen Phase, die
Integer als Eingabewerte erhält und dessen Quadrat berechnet und wieder ausgibt,
ist die Folgende:
Listing 4.1: Exemplarische apply Methode
1 public class SqrPhase extends AbstractPhase {
2 public void apply(Object value, Context context) {
3 Integer i = (Integer) value;
4 context.getOutputWriter().write(i * i);
5 }
6 }
In diesem Quellcode Beispiel ist die Signatur der apply Methode zu sehen. Auf-
fällig ist, dass die Methode keinen Wert zurückgibt. Der Grund dafür ist die vari-
ierende Anzahl an Rückgabewerten. Es wäre möglich gewesen eine Liste mit 0 bis nEinträgen zurückzugeben. Jedoch werden die Werte dann nicht einzeln, sondern
gebündelt in einem Container (z.B. der Liste) zurückgegeben. Dieses Konzept wäre
zwar vorstellbar gewesen, an dieser Stelle jedoch scheint das Callback Entwurfs-
muster besser und flexibler. Insbesondere dadurch das bei der Rückgabe eines Con-
tainers, dieser Im Arbeitsspeicher gehalten werden müsste, womit die Anzahle der
Rückgabewerte durch den verfügbaren Arbeitsspeicher begrenzt wäre.
In diesem Fall wird innerhalb des Objektes context ein Objekt des Typs
OutputWriter mitgegeben in welches die Ausgabewerte geschrieben werden.
Der OutputWriter bekommt die Objekte somit einzeln und kann sie einzeln ve-
rarbeiten. Der genannte Context wird bei jedem Methodenaufruf von apply mit
dem zu bearbeitenden Objekt (in dem Beispiel mit dem Bezeichner value)
übergeben. In dem Context sind Objekte und Funktionen gebündelt, welche die
Ein- und Ausgabe betreffen (wie der OutputWriter) gebündelt. Darüberhinaus
findet sich an dieser Stelle aber auch die Metadatenverwaltung. Diese Metadaten
sind aktuell mittels des Interfaces MetaDataProvider3 zugreifbar. Dieses Inter-
face definiert aktuell eine Untermenge der Funktionen die durch eine Map4 definiert
sind. Diese Variante bietet ein hohes Maß an Flexibilität und lässt sich leicht imple-
mentieren. Sollten zu einem späteren Zeitpunkt erweiterte Metadaten notwendig
sein, lässt sich das Interface MetaDataProvider ergänzen.
Der Context und die enthaltenden Klassen lassen sind durch recht einfache Inter-
faces definieren. Somit können sie auch als inline classes oder als inner classes von
der Phase erstellt werden. Insbesondere für den OutputWriter bietet sich diese
Vorgehensweise an.
3de.unihamburg.vsis.probdi.control.MetaDataProvider4java.util.Map der Java JRE
28 4. Implementierung des Phasen Modells
4.1.2. Phasen Managment
Im voran gegangenen Abschnitt wurde beschrieben mit welchen Eingaben eine
Phase arbeitet. Alle nötigen Informationen werden durch den Methodenaufruf von
apply(Object value, Context context) übergeben. Das Aufrufen dieser
Methode und damit das Managment der Metadaten und der Ein- und Ausgabew-
erte wird vom PhaseHandler und der AbstractPhase übernommen. Der
PhaseHandler behandelt dabei den globalen Ablauf. Er führt die Phasen nach
einander aus und sorgt dafür das jeweils die richtigen Eingabewerte gelesen wer-
den.
Die AbstracPhase implementiert wie der PhaseHandler5 das Interface
Runnable. Wenn eine Phase die AbstractPhase erweitert mit dem Aufruf von
run() gestartet wird, sorgt die AbstractPhase dafür das die Eingabewert enst-
spechend der gesetzten Filter gelesen werden und ruft für jeden gelesenen Wert die
apply(...)-Methode auf.
In der Klasse AbstractPhase werden viele wichtige Events die in dem Abschnitt
4.2.2 genauer erläutert werden verwaltet und erzeugt.
4.1.3. Pausieren
Der Durchlauf einer Phase oder einer Folge von Phasen kann, abhängig von der
Menge der Datensätze sehr lange dauern. Deshalb ist es wünschenswert auf den
Ablauf Einfluss nehmen zu können und ihn gegebenenfalls unterbrechen zu kön-
nen. Um diese Möglichkeit zu bieten lässt sich ein PhaseHandler pausieren, weit-
erführen und stoppen.
Der PhaseHandler selber delegiert dabei die Befehle (z.B. den Stop-Befehl) an die
aktuell laufende Phase. Diese Phase sorgt dann für ein sauberes beenden nach dem
aktuellen Datensatz. In der Kombination mit der Möglichkeit der Sondierung durch
die Listener lässt sich so zu exakten Punkten im Durchlauf der Phasen eine Phase
stoppen oder pausieren. Mit dieser Kombination lässt sich folgendes Szenario sehr
leicht implementieren:
Pausiere den Ablauf immer zu Beginn einer neuen Phase und warte bis der Be-nutzer den Fortgang bestätigt hat.
4.2. Kommunikation und Serialisierung
Die einzelnen Phasen deren Grundkonzept im vorherigen Abschnitt 4.1.1 im De-
tail erläutert wurde stehen jeweils zu mehreren anderen Software- Komponenten
5de.unihamburg.vsis.probdi.control.PhaseHandler
4.2. Kommunikation und Serialisierung 29
in Beziehung. Am engsten zu den anderen Phasen, die ihnen im globalen Ablauf
voraus gegangen sind oder ihnen nachfolgen. Sie stehen aber auch in Beziehung zu
der Steuerung des Ablaufes der Phasen, der, wie erläutert, durch den PhaseHandler
realisiert ist.
Die Verbindungen, die zwischen den Phasen bestehen, lassen sich in entsprechend
der Anforderungen in Abschnitt 3.2 in zwei Bereiche teilen. 1.) Eine Phase liest Dat-
en der vorangegangenen Phase ein und gibt Daten an die Nachfolgende weiter.
Diese Verbindung ist der Zweck des Phasenmodells. Jedoch ist das Konzept da-
rauf ausgelegt, dass alle Eingabedaten vom selben Typ sind und in großer Zahl
verarbeitet werden. Für viele Daten treffen diese Einschränkungen nicht zu, ins-
besondere Daten die statistische Werte über den aktuellen Datenbestand enthalten.
Zum anderen werden mittels des Eingabe/Ausgabedatenflusses immer nur Dat-
en an die nächste Phase weitergegeben. Deshalb gibt es 2.) die Metadaten. Diese
Daten sind nachdem sie geschrieben sind von alle folgenden Phasen zugreifbar.
Implementiert ist diese Funktionalität mit Hilfe der Contexts der jedem Aufrauf
der apply Methode mitgegeben wird. Dieser enthält einen MetaDataProvider6.
Dieser liegt über die gesamte Laufzeit des Frameworks im Arbeitsspeicher. Der
MetaDataProvider in lediglich für kleine Datenmengen konzipiert, es soll lediglich
Metadaten wie z.B. Anzahl der Tuplepaare etc. enthalten.
4.2.1. InputStorage / OutputStorage
Für den Hauptdatenfluss der Arbeitsdaten von Phase zu Phase ist es nicht möglich
ihn im Arbeitsspeicher vorzuhalten. Die Datenmenge ist potenziell zu groß, ins-
besondere dann, wenn eine triviale Suchraumdefinition verwendet wird und das
kartesische Produkt der zu vergleichenden Datenbestände bearbeitet werden muss.7
Wie in Abschnitte 3.4 dargestellt müssen die Daten geeignet serialisiert werden.
Entscheidend ist, dass dabei zum einen die Serialisierung der einzelnen Datensätze
und zum anderen der Zugriff auf die persistenten Daten. Diese beiden Punkte sind
für die Geschwindigkeit von besonderer Bedeutung.
In den Interfaces InputStorage und OutputStorage sind die Funktionen defi-
niert, die zur Verfügung stehen müssen. Eine Phase erhält als Eingabe immer einen
IntputStorage und braucht einen OutputStorage in den sie die Ausgabewerte
schreiben kann. Der InputStorage ist dabei iterierbar8 und kann somit sehr ein-
fach sequenziell verarbeitet werden.
Für den InputStorage gibt es zwei Methoden um auf die persistenten Daten zuzu-
greifen. Mit der einen (get()) lassen sich alle Daten sequenziell lesen. Mit der an-
6deMetaDataProvider7Vergleiche dazu Abschnitt ii8Das Interface Iterable<Object> wird Implementiert und gibt ihn Iterator<Object> zurück
30 4. Implementierung des Phasen Modells
deren Methode (get(List<Criterium<String,String>> crit)) lässt sich
eine
Teilmenge selektieren und sequenziell lesen. Es wird eine Liste von Kriterien über-
geben. Jedes Kriterium besteht aus zwei Strings, einem der den Typ beschreibt,
einem der die Ausprägung festlegt (z.B. Typ: Farbe, Ausprägung: blau). Die Ele-
mente die alle diese Kriterien erfüllen werden zurück gegeben. An dieser Stelle ist
keine vollwertige Anfragesprache nötig, es soll lediglich eine einfache Selektion er-
möglicht werden, um nicht alle Datensätze lesen und filtern zu müssen. Das lesen
aller Datensätze ist sehr aufwendig, nicht nur weil sie von der Platte gelesen wer-
den müssen, sondern auch weil die Objekte jeweils wieder Deserialisiert werden
müssen.
Das Interface OutputStorage enthält die zu dem Interface InputStorage komple-
mantären - schreibenden Methoden (write(Object value) und
write(List<Criterium<String, String>> criterium, Object val)).
Eine Implementation dieser Interfaces muss die Daten nicht notwendigerweise auf
die Festplatte persistieren. In dem Framework sind zwei Implementationen vorhan-
den, eine arbeitet nur im Arbeitsspeicher, die andere persistiert auf die Festplat-
te. Beide Varianten arbeiten mit dem Lucene Framework.9 Im Vergleich zu an-
deren Systemen, die eine Anfragesprache bieten (z.B. Datenbanken) ist Lucene sehr
schnell im sequenziellen Schreiben von Datensätzen. Das Schreiben von sequen-
ziellen Dateien wäre zweifellos schneller, jedoch sind diese auch nur sequenziell
lesbar. Lucene hingegen bietet einen sehr schnellen Zugriff auf beliebig parametri-
sierte Einträge, ohne einen nennenswerten Geschwindigkeitsverlust beim sequen-
ziellen Lesen in Kauf nehmen zu müssen. Lucene ist jedoch ursprünglich nicht
darauf ausgelegt sequenziell große Mengen von Daten zu lesen. Um dieses den-
noch zu ermöglichen, muss diese Funktionalität auf der Lucene API implementiert
werden. Diese Implementation liegt bereits vor, jedoch ist sie nicht Teil der Lucene
Distribution, zu finden ist sie im Jira des Lucene Projektes.10
Die Java Objekte werden zwischen den Phasen persistiert. Um dieses zu gewährleis-
ten müssen sie geeignet serialisiert und deserialisiert werden. Es gibt unterschied-
liche Methoden Objekte zu serialisieren. Oft werden Objekte in Form von XML
Dateien serialisiert11 oder in Form von Bytestreams12. In diesem Framework wurde
die Standardvariante zur Serialisierung verwendet der ObjectOutputStream der
Java JRE. Diese Variante ist sehr einfach zu verwenden, jedoch bei komplizierten
9Lucene ist ein Top Level Projekt der Apache Software Foundation (http://www.apache.org). Luceneist eine Java Implementation einer High-Performance Volltextsuche. Durch die flexible Architektur unddie hohe Schreib-Geschwindigkeit lässt sich Lucene als leichtgewichtiger, parametrisierter, persistenterSpeicher verwenden [luc].
10https://issues.apache.org/jira/browse/LUCENE-221511Ein Beispiel ist XStream (http://xstream.codehaus.org)12Ein sehr performantes Beispiel ist PROTOCOL BUFFERS von GOOGLE Inc. (http://code.google.com/
p/protobuf/)
4.2. Kommunikation und Serialisierung 31
Objekten sehr langsam.
Es gibt aber Möglichkeiten die Serialisierung zu beschleunigen. Eine sehr einfach
Methode ist die Verwendung von transient mit dieser Markierung wird fest-
gelegt das diese Exemplarvariable eines Objektes nicht persistiert werden soll. Et-
was aufwändiger ist die Verwendung der beiden Methoden:
a) readObject(ObjectInputStream in)
b) writeObject(ObjectOutputStream out)
Wenn diese beiden Methoden als private Methoden in einem Objekt vorhanden
sind, das serialisiert werden soll, so werden sie automatisch aufgerufen und anstatt
der Standardserialisierung verwendet. Besonders bei Collections kann dieses einen
großen Geschwindigkeitsgewinn bringen. Für die wichtigsten Typen des Modells
wurden die beiden Methoden implementiert [Gre00].
4.2.2. Hook-Methoden und Listener
Dieses Framework zur Duplikatenerkennung soll später mit einer graphische Ober-
fläche versehen werden. Damit die graphische Oberfläche später gut mit dem
Framework kommunizieren kann, müssen Möglichkeiten geschaffen werden mit-
tels derer sich die Oberfläche in den Ablauf des Frameworks einklinken kann.
Dieses ist z.B. schon für eine Statusanzeige nötig. Diese Funktionalität gehört zur
Infrastruktur des Phasen Modells und wird deshalb von der Implementation dieses
Modells beretgestellt. Um eine flexible Kommunikation zu gewährleisten sind zwei
Varianten vorgesehen. Zum einen gibt es entsprechend des Templating Patterns
Hook-Methoden. Diese Hook-Methoden werden während des Ablaufes der Phasen
an bestimmten Punkten des Zyklus aufgerufen. Im Normallfall enthalten diese
Methoden einen leeren Rumpf, sie können jedoch von Klassen, die AbstractPhase
erweitern, überschrieben werden. So können an den nötigen Punkten in dem Ablauf
einer Phase Initialisierungen oder ähnliches vorgenommen werden. Ebenso können
diese Methoden verwendet werden, um die GUI über Ereignisse zu informieren.
Für diesen Zweck eignet sich ein anderes zur Verfügung stehendes Pattern jedoch
besser.
Die AbstractPhase implementiert das Listener/Observer Pattern. Mittels eines
sehr kurzen Interface können sich beliebige Objekte als Listener anmelden. Sie wer-
den zu denselben Zeitpunkten aufgerufen wie die Hook-Methoden. Ihnen wird
der Typ des Ereignisses so wie - wenn vorhanden - der jeweils aktuelle Datensatz
als Parameter übergeben. Um eine Implementation für neue Phasen oder Listen-
er zu vereinfachen existiert die Klassen GenericListenerHandler<T, U> und
das Interface Listener<T, U>. Diese Implementieren einen generisches Listen-
er/Observer Entwurfsmuster und könne deshalb gut als Ausgangspunkt dienen
und erweitert werden.
32 4. Implementierung des Phasen Modells
Beide Varianten sind annähernd gleich mächtig und lassen sich in vielen Fällen
gegeneinander austauschen. Konzeptionell sind die Hook-Methoden für die von
AbstractPhase erbenden Klassen gedacht. Dieses Pattern soll die Implementa-
tion der Logik erleichtern. Wohingegen das Listener/Observer Pattern besser als
Verbindung zu GUI geeignet ist, da es eine losere Kopplung ermöglicht. Insbeson-
dere für Statusanzeigen und andere sondierende Funktionalitäten ist diese Variante
zu bevorzugen.
4.3. Konfiguration
In Abschnitt 3.2 wurden die Anforderungen an die Konfigurierbarkeit kurz er-
läutert. Die Konfigurierbarkeit lässt sich in zwei Bereiche aufteilen. Zum einen
muss es möglich sein neue Komponenten nutzbar zu machen ohne dass, das ganze
Framework neue kompiliert werden muss. Zum anderen müssen sich die einzelne
Komponenten zur Laufzeit mit Parametern konfigurieren lassen (z.B. Grenzwerte
für die Klassifikation).
Der erste Bereich der Konfigurierbarkeit ist sehr wichtig damit das Framework flex-
ible und leicht zu erweitern ist. Es ist damit sehr gut möglich dass, das einzelne
Komponente des Frameworks getrennt von einander weiter entwickelt werden.
Die zentrale Datei, um diese Framework zu konfigurieren, ist die Datei
settings.xml. In dieser Datei werden dem Framework neue Implementationen
bekannt gemacht, es können auch statischen Konfigurationen eingetragen werden.
Zu diesem Zweck enthält die XML Datei pro konfigurierbarem Objekttyp (Phase,
AttributMatcher, MatchingFunktions, . . . ) ein Element, welches als Kindele-
ment eine Liste mit den zu Verfügung stehenden Implementationen enthält. Die
Implementationen sind über ihren vollständigen Klassennamen angegeben. Inner-
halb des Elementes, dass eine Implementation definiert, können beliebige weiter
Elemente angelegt werden.
Jede der Klassen die in der settings.xml angegeben ist, muss ein Interface im-
plementieren das dem Framework bekannt ist (z.B. Phase, AttributeMatcher,
AttributeMatchingFunction, . . . ). Da alle Interfaces, die einen konfigurier-
baren Typ definieren, das Interface Configurable erweitern ist garantiert, dass
jede Implementation dieses Interface implementiert. Das Configurable Interface
sorgt dafür, dass es möglich ist dem Objekt ein DOM Element zu übergeben.13
Wird eine Klasse aus der settings.xml geladen und instanziiert, so werden dem
neuen Objekt seine Kindelemente aus der XML Datei als DOM Element injiziert.
13DOM ist ein Akronym für Document Object Model und bezeichnet die Objektrepräsentation einer XMLDatei
4.3. Konfiguration 33
Das Laden der Klassen und das instanziieren werden von der Klasse Settings
übernommen. Diese enthält für jedes Interface das Configurable implementiert
ist ein get Methode (getPhases()), die eine Liste mit jeweils einer Instanz pro
aufgelisteter Implementationen enthält.
Das gezeigte Vorgehen löst das Problem der statischen Konfiguration und der Er-
weiterbarkeit des Frameworks. Das Configurabel Interface kann darüber hinaus
auch zur Laufzeit genutzt werden, um Configurationen zu übergeben. Ein DOM El-
ement bietet sich durch die flexible Verwendbarkeit und die Strukturierbarkeit zur
Übergabe von Konfigurationen an.
Für die Konfiguration der Elemente zur Laufzeit ist damit eine Grundlage geliefert.
Die gesamte Konfiguration ist in der Klasse Configuration zusammengefasst.
Trotz der Möglichkeiten bleibt die Konfiguration sehr aufwendig. Da die Anzahl
der Komponenten sehr groß ist und ein hohes Maß an Flexibilität geboten ist, lässt
sich dieses leider schwer umgehen. Um die Konfiguration trotzdem etwas zu erle-
ichtern existiert die Klasse ConfigurationUtil. Diese beinaltet Methoden zum
Speichern und Laden von Konfigurationen und enthält diverse Methoden die Stan-
dardkonfigurationen zusammenstellen.
Die Konfiguration zur Laufzeit soll durch eine GUI realisiert werden. Da die Kon-
figuration für einzelne Komponenten strukturell sehr Unterschiedlich sein kann
könnte es für die Entwicklung der GUI sinnvoll sein, in den statischen Konfig-
urationsbereich der zu konfigurierenden Komponente den Klassennamen, eines
speziefischen Konfigurators einzutragen. Dieser Konfigurator der selber ein GUI-
Widget sein könnte, kann dann mittels der Refelction API geladen werde. Diese
Variante böte eine sehr hohes Maß an Flexibilität, würde aber auch verlangen das
zu nahezu jeder Komponente ein Konfigurator geschrieben werden müsste.
34 4. Implementierung des Phasen Modells
35
5. Prototypische Duplikatenerkennung
Im vorangegangenen Abschnitt wurde auf die Implementation der Phasen Modells
eingegangen. Diese liefert die Basis und die Infrastruktur für die darauf implemen-
tiert Duplikatenerkennung.
Für die Implementation der Duplikatenerkennung in probabilistischen Daten liefert
das ULDB Modell die fachliche Basis und das Datenmodell von dem bei der Im-
plementation ausgegangen wird. Diese Implementation wird als erstes dargestellt.
Anschließend wird die Implementation der wichtigsten Phasen der Duplikaten-
erkennung erläutert.
Wie schon in Abschnitt 3.2.2 erwähnt werden die Phasen des Attributwerte-
Abgleiches und die Phase des Entscheidungsmodells auführlich implementiert. An-
dere Phasen die zur Duplikatenerkennung nötig sind wurden, wie die Suchraum-
definition oder das Duplikatenclustering trivial oder wie im Falle der Datenvor-
bereitung nicht implementiert.
5.1. ULDB Modell
Das ULDB Modell ist das Datenmodell in dem die probabilistischen Daten repräsen-
tiert werden. Warum die Wahl auf diese Modell gefallen ist wurde in Abschnitt 2.3
erläutert. Es wird nun die Umsetzung des ULDB Modells in eine Java Klassenhier-
archie dargestellt.
Das Modell ist komplett auf Interfaces aufgebaut und besteht somit aus zwei Teilen.
Zum einen der Definition durch die Interfaces und zum anderen die Implementa-
tionen der Interface. Das Zusammenspiel der Interfaces und ihre Abhängigkeiten
voneinander ist in dem UML Modell im Appendix 2 verdeutlicht. Zum Design der
Interface ist zu bemerken, dass sie minimalitisch gehalten sind und streng dem Zi-
tat von Joshua Bloch folgen: „When in doubt, leave it out!“1
Auffällig an dem API Design der Interface ist, dass keines eine schreibende Meth-
ode aufweist, die Interfaces können lediglich lesend verwendet werden. Begründet
1Joshua Bloch ist Principal Software Engineer bei Google Inc. zitiert ist ein Satz aus seinem Vortrage „Howto Design a Good API and why it Matters“ Proc. 21st ACM SIGPLAN Conference für OOPSLA (Object-Oriented Programming, Systems, Languages Applications), 2006
36 5. Prototypische Duplikatenerkennung
ist Entscheidung mit der Zuverlässigkeit der API. Das ULDB Modell ist die Grund-
lage auf der der Rest des Frameworks arbeitet, es ist wünschenswert, dass sich diese
Grundlage so wenig wie möglich ändert. Mit der Nichtaufnahme von schreiben-
den Operationen soll diese Zuverlässigkeit suggeriert werden. Konsequent wäre
es, die Implementation insgesamt unveränderbar (immutable) 2 zu gestalten. Jedoch
lässt sich dieses nicht mit allgemeinen Interfaces der Java JRE nach außen deutlich
machen.3 Ein weiteres Problem ist, dass ein Table oftmals nicht zur Gänze in den
Arbeitsspeicher passen wird und somit sequenziell aus einem persistenten Speich-
er gelesen werden muss. In diesem Fall ist es sehr schwer Unveränderbarkeit zu
garantieren.
Die Struktur dieses Datenmodells sollte aus der Erläuterung in Abschnitt 2.3 und
dem UML Diagramm UML in Appendix 2 deutlich werden, auf sie wird nicht weit-
er eingegangen. Zu erwähnen ist noch der Umgang mit Mengen von Objekten in
dieser API.
Die meisten Objekte dieses Datenmodells sind Containerelemente für andere Ob-
jekte. So enthält ein Objekt der Klasse Table eine Menge von Objekten der Klasse
x-tuple und ein Objekt der Klasse x-tuple eine Menge von Objekten der Klasse
Alternative. Dabei fungieren die Objekte meist als ein Elternknoten in einem
globalen Objektbaum. Um die Arbeit mit diesen Objekten zu erleichtern, imple-
mentieren diese Containerelemente jeweils das generische Interface Iterable<T>.
Durch dieses Interface wird ermöglicht, dass die erweiterte for-Schleife direkt
angewendet werden kann.
Außerdem ist das Interface Iterable weniger restriktive als das Interface
Collection. Dieses ist insbesondere für die Klasse Table relevant. Wie schon
erwähnt ist es gut möglich, dass ein Table zu groß für den Arbeitsspeicher ist. Das
Interface Iterable ermöglicht es, eine Implementation zu realisieren in welch-
er der Table mit einem Datenbank Cursor arbeitet. Diese Methode ist sowohl im
Hinblick auf die Performance als auch auf die Speichereffizienz sehr gut geeignet.
5.2. Duplikatenerkennung
Die Duplikatenerkennung ist auf dem Phasen Modell implementiert. Die wichtig-
sten Bestandteile sind: der Attributwerte Abgleich, der Alternativen Abgleich und
2Es ist sehr von Vorteil wenn ein Objekt die Eigenschaft immutable also Unveränderbarkeit besitzt. Es ist indiesem Fall nicht mehr nötig interne Kopien anzulegen um zu garantieren das sich im Hintergrund nichtsan den Objekten ändert. Insbesondere für Collections ist diese Eigenschaft wünschenswert. Java bietetzu diesem Zweck Utilitie-Methoden an Collections.unmodifiableCollection(...) welche füreine eingabe Collectionen eine Unveränderbare zurückgeben. Wenn ein Objekt immutable ist impliziertdieses dass es Threadsafe ist [SUN].
3Es ist wünschenswert, dass eine Liste das Interface java.util.List implementiert, jedoch suggeriertdieses Interface das die Implementation veränderlich (mutable) ist, was sie in diesem Kontext nicht seinsoll.
5.2. Duplikatenerkennung 37
Listing 5.1: Dieser Analyter zählt alle XTuple1 public class XTupleCount extends AbstractConfigurable implements
Analyzer {2 private MetaDataProvider metaDataProvider;3 private int count;45 public void start(MetaDataProvider metaDataProvider) {6 this.metaDataProvider = metaDataProvider;7 this.count = 0;8 }9
10 public void analyze(XTuple tuple) {11 count++;12 }1314 public void finished() {15 this.metaDataProvider.put("xtuple.count", count);16 }1718 public void newTable() {19 }20 }
das Entscheidungsmodell. Der Alternativen Abgleich wurde ursprünglich als Teil
des Entscheidungsmodells betrachtet. Da sich je nach Vorgehensweise des Alterna-
tiven Abgleiches auch das Entscheidungsmodell ändert (z.B. Ähnlichkeits- Entschei-
dungsbasiert vergleiche Abschnitt 2.4.2).
Diese Bestandteile sind jeweils als eine eigenständige Phase realisiert. Wobei die
Phase lediglich als Rahmen auftritt und als Aufrufer mit jeweils neuen Parametern
fungiert. Im Folgenden werden die implementierte Phasen detaillierter vorgestellt.
5.2.1. Analyse
Weder in den Anforderungen noch in einem der Modelle wurde eine Analysephase
explizit erwähnt. Dennoch wurde sie als separate Phase implementiert. Diese Phase
dient zum sammeln von Metadaten. In Abschnitt 3.2.3 wurde die tf-idf als Beispiel
für die Notwendigkeit von Metadaten verwendet. Mit dieser Phase lassen sich
derartige Metadaten sehr einfach sammeln. Die Phase nimmt als Eingabewerte
Tables auf und iteriert nach einander über alle Table die übergeben wurden.
Die Phase ruft für jedes XTuple die Methode analyze auf allen registrierten Ana-
lyzern auf. In der Abbildung 5.1 ist ein Analyzer dargestellt welcher die Anzahl an
XTuplen bestimmt.
38 5. Prototypische Duplikatenerkennung
5.2.2. Suchraumdefinition
In dem Abschnitt zu den Grundlagen der Duplikatenerkennung Abschnitt ii sind
einige Varianten der Suchraumdefinition vorgestellt worden. Die Definition des
Suchraums hat einen sehr großen Einfluss auf das Ergebnis der Duplikatenerken-
nung. Desweiteren gibt es sehr viele Möglichkeiten wie eine Solche Definition op-
timiert werden kann. Dieses gilt für die neuen Möglichkeiten die sich in der Dup-
likatenerkennung in probabilistischen Daten in besonderem Maße.
Aus diesem Grund wurde nur eine triviale Suchraumdefinition implementiert,
welche das Kartesisches Produkt der Tables bildet.
Das Inteface um eine Suchraumdefinition zu implementieren ist sehr einfach gehal-
ten, es ist lediglich eine Methode zu implementieren. Desweiteren ist es durch die
Verwendung des Callback-Entwurfmusters sehr flexible zu implementieren.
5.2.3. Attributwerte Abgleich
Der Attributwerte Abgleich ist der erste Schritt des Vergleiches der Tuplepaare. Im
in Abschnitt 2.4 vorgestellten Modell zur Duplikatenerkennung wurde die Theo-
rie des Attributwerte Abgleiches vorgestellt. Im Folgenden wird ein Attributwerte
Abgleich vorgestellt welcher die Flexibilitätsansprüchen aus Abschnitt 3.1 erfüllt.
Als Eingabe für die Phase des Attributwerte Abgleichs dient eine Menge von Tu-
plepaaren, welche in einer vorangegangenen Phase, der Suchraumdefinition zu-
vor zum Vergleich ausgewählt wurden. Diese Menge an Tuplepaaren dient nun als
Eingabe für den Abgleich der Attributwerte. Als Container für dieses Paar dient
die Klasse TuplePair, welche nicht nur das TuplePair enthält sondern auch die
Ergebnisse der jeweiligen Phase. So haben die Phasen auf möglichst viele Daten
Zugriff und das Entwickeln von weitern Phasen wird erleichtert.
Der wirkliche Vergleich wird von einem AttributMatcher (siehe UML in Ap-
pendix 3) vorgenommen. Dieser verfügt pro Attribut über eine Menge von Ver-
gleichsfunktionen und einem Aggregator. Es wird nun für jedes Alternativenpaar,
das in dem Tuplepaar enthalten ist ein Ähnlichkeitswert pro Attribut errechnet.
Für diese Berechnung wird jede für das Attribut registrierte Ähnlichkeitsfunktion
angewendet, das Ergebnis wird dem Aggregator für das Attribut hinzugefügt.
Dieser gibt anschließend das aggregierte Ergebnis zurück.
In dem Framework enthalten sind aktuell 23 unterschiedliche Ähnlichkeitsfunktio-
nen. All diese Funktionen nehmen sich nur dem Problem der Stringähnlichkeit an,
da diese in der Regel die wichtigste bei der Duplikatenerkennung ist. Alle Ähn-
lichkeitsfunktionen sind normiert und geben damit einen Wert zwischen 0 und
1 zurück. Bei diesen Ähnlichkeitsfunktionen handelt es sich um die SimMetrics
Bibliothek, die von der Natural Language Processing Group an der Universität
5.2. Duplikatenerkennung 39
Sheffield entwickelt wird [Cha]. Für dieses Framework wurde lediglich pro Funk-
tion eine Adapterklasse geschrieben so dass die Funktionen das Interface
AttributeMatchingFunction4 implementieren.
Sowohl die Ähnlichkeitsfunktionen als auch die Aggregatoren sind Interfaces die
sehr einfach implementiert werden können, somit ist es leicht möglich eigene Funk-
tionen zu implementieren. Für andere Objekttypen oder ähnliches, aber auch für
den Aggregator sind andere Varianten vorstellbar. Die wohl gebräuchlichste Vari-
ante wird ein Aggregator sein, der einen gewichteten Durchschnitt der eingegebe-
nen Werte berechnen. Denkbar ist aber auch ein Maximum- oder Minimumaggre-
gator.
Die Rückgabe des Attributmatchers ist ein Ähnlichkeitsvektor pro Alternativen-
paar. Dieses Ergebnis wird in das TuplePair geschrieben, damit ist der Attributwerte
Abgleich für ein Tupelpaar abgeschlossen und der Kontrollfluss wird wieder an das
Phasenmodell zurückgegeben.
5.2.4. Alternativen Abgleich
Der Abgleich der Alternativenpaare verläuft nun wieder ähnlich dem Ablauf des
Attributwerte Abgleiches. Die Logik ist im AlternativeMatcher enthalten.
Dieser enthält eine Menge von Kombinationsfunktionen und einen Aggregator.
Die Alternativenpaare werden nacheinander durchlaufen. Es werden alle Kombi-
nationsfunktionen angewendet und die Ergebnisse dem Aggregator hinzugefügt.
Dieser gibt anschließend das kombinierte Ergebnis zurück. Nach Abschluss dieser
Phase liegt für jedes TuplePair ein Ähnlichkeitsvektor vor. Dieser Vektor enthält
einen Eintrag pro Alternativenpaar und kann damit für jedes Tuplepaar unter-
schiedlich lang sein.
Nach dieser Phase liegt das Ergebnis vor, welches das in Abschnitt 2.4 beschriebene
Modell nachdem Attributwert Abgleich annimmt. Dieses ist nun Eingabe für eines
der Entscheidungsmodelle.
5.2.5. Entscheidungsmodell
Im Grundlagenabschnitt dieser Arbeit wurden zwei Entscheidungsmodelle vor-
gestellt (siehe Abschnitt 2.4.2), ein ähnlichkeitsbasiertes und ein entscheidungs-
basiertes. Für beide Modelle liegt eine konkrete Implementation vor. Das Entschei-
dungsmodell ist ein sehr wichtiger Schritt in der Duplikatenerkennung und es ist
wahrscheinlich, dass es mehrere unterschiedliche Ansätze geben wird. Um eine
große Flexibilität bieten zu können, und eine Mehrfachprgrammierung gleicher
4de.unihamburg.vsis.probdi.function.AttributeMatchingFunction
40 5. Prototypische Duplikatenerkennung
Teilabläufe zu vermeiden, ist das Entscheidungsmodell auf zwei bzw. drei Phasen
aufgeteilt.
Für das ähnlichkeitsbasierte Modell gibt es eine Phase in der Mittels einer Ablei-
tungsfunktion die Ähnlichkeit zweier XTuple als Wahrscheinlichkeit bestimmt wird.
Diese Wahrscheinlichkeit ist die Eingabe für die zweite Phase, die Klassifikation,
die mit einem oder zwei Grenzwerten bestimmt, ob es sich um einen match einen
possible-match oder einen none-match handelt.
Die entscheidungsbasierte Variante beinhaltet eine Phase mehr. Zunächst wird jedes
Alternativenpaar als Match, Possible Match oder None Match deklariert. Diese
Klassifikation arbeitet wiederum mit ein bis zwei Grenzwerten. Anhand dieser
Menge an Grenzwerten für ein Tuplepaar wird nun eine Wahrscheinlichkeit bes-
timmt, mit der es sich um Dubletten handelt. Diese Wahrscheinlichkeit wird an-
schließend, wie im ähnlichkeitsbasierten Modell, klassifiziert.
Mit der Klassifikation ist die Duplikatenerkennung im Kern abgeschlossen. Um ein
global konsistentes Ergebnis zu gewährleisten folgt schließlich noch eine Phase des
Duplikatenclusterings. Dieses behandelt die Frage: „Wenn a und b Dubletten sindund b und c auch. Sind dann a und c auch Dubletten?“ In diesem Fall handelt es sich
um die Frage nach der Transitivität der Dubletteneigenschaft. Eine einfache Vari-
ante des Clusterings ist die Transitivehülle mit dieser Eigenschaft zu bilden. Diese
Variante liegt als Implementation vor. Es sind jedoch weitaus bessere und interes-
santere Varianten denkbar. Beim Clustering der Duplikate können die Verfahren
für traditionelle Daten verwendet werden.5
5.2.6. Clustering
Die Implementation des Clusterings ist etwas schwieriger als die der bisherigen
Schritte. Der Grund dafür ist das bei der Bildung der Cluster alle Tuple gefunden
werden müssen die als Duplikate zu einem bestimmten Tuple gefunden wurden.
Dieses lässt sich nicht performant durch sequenzielles lesen der Tuple realisieren.
Um ein sinvolles Clustering zu implementieren müssen die Tuple in der Phase zu-
vor markiert worden sein, damit sie jetzt, über die Filter für den InputStorage zu-
greifbar sind.
Ein Beispiel welches das Vorgehen verdeutlicht ist die Implementierung des Clus-
terings mittels der Transitivenhülle (siehe Appendix 4).
5Weitere Clusteringmethode sind in [NH10, S. 52ff] beschrieben.
41
6. Fazit
Das Ziel und der Titel dieser Arbeit ist der Entwurf und die Implementierung einesadaptiven und flexiblen Frameworks zur Duplikaterkennung in Probabilistischen Daten.
Dieses Ziel ist erfüllt. Das implementierte Framework ist auf mehreren Ebenen kon-
figurierbar und erweiterbar ohne das neues kompilieren nötig ist. Die Trennung
des Phasen Modells von der Duplikatenerkennung macht dieses flexibel für andere
Szenarien.
Es ist eine prototypische Duplikatenerkennung implementiert welche erwartungs-
gemäß funktioniert und zu sinnvollen Ergebnissen führt. Diese prototypische Im-
plementierung ist als Ausgangspunkt für weitere Implemenrierungen zu betracht-
en. Die Phasen Attributwerte Vergleich und Alternativen Vergleich sind entsprechend
dem Verfahren von F. Panse implementiert und funktionsfähig. Andere Phasen sind
trivial implementiert und müssen zu einem späteren Zeitpunkt sinnvoll implemen-
tiert werden.
Das Ziel, dass das Framework adaptive und flexibel sein soll ist erreicht. Es ist aber
zu beachten dass es noch nicht in der realen Forschung zu probabilistischen Daten
eingesetzt wurde. Somit ist diese Version als Beta-Version zu betrachten.
Dieses Framework besteht aus vielen Komponenten was dazu führt, dass es sehr
aufwändig zu konfigurieren ist. Mit einer geeigneten graphischen Obefläche lässt
sich diesem Problem begegnen. Es ist jedoch wahrscheinlich dass es auch zu API
Änderungen kommen wird um das Entwickeln mit diesem Framework zu erle-
ichtern. Diese sind Themen die im praktischen Einsatz zu evaluieren sind. Eine
Basis für die Forschung zur Duplikatenerkennung in probabilistischen Daten ist
gelegt. Das Framework muss nun entsprechend der Rückmeldungen aus dem Be-
trieb weiter entwickelt werden.
42 6. Fazit
43
Appendix
1. HumMer
Abbildung 1.: Architektur HumMer
44 Appendix
2. Ablauf
Ablauf der Duplikatenerkennung in ProbDI Teil 1
2. Ablauf 45
Ablauf der Duplikatenerkennung in ProbDI Teil 2
46 Appendix
3. UML
Abbildung 2.: UML Klassendiagramm des Implementation des ULDB Modells
3. UML 47
Abbildung 3.: UML Klassendiagramm des Implementation des AttributeMatchers
48 Appendix
4. Code-Beispiele
Listing 1: TransitiveClustering1 public class TransitiveClustering extends AbstractConfigurable
implements Clustering {2 ...34 @Override5 public Collection<XTuple> cluster(TupleSearcher searcher, TuplePair
pair) {6 if (this.finished.contains(pair.getValue1().getTid())) {7 log.debug("XTuple " + pair.getValue1().getTid() + " allready
processed, skip it");8 return null;9 }
1011 final Queue<XTuple> queue = new LinkedList<XTuple>();12 final Set<XTuple> duplicates = new HashSet<XTuple>();1314 queue.add(pair.getValue1());15 XTuple t1 = null;16 while ((t1 = queue.poll()) != null) {17 if (!this.finished.contains(t1.getTid())) {18 final List<TuplePair> pairs = searcher.
findPairsByMatchingTypeAndTID(19 MatchingType.Match, t1.getTid());20 log.debug("Pairs found for tid: " + t1.getTid() + " - Num: " +
pairs.size());21 duplicates.add(t1);22 this.finished.add(t1.getTid());23 for (TuplePair tuplePair : pairs) {24 final XTuple t2 = tuplePair.getNot(t1);25 if (!duplicates.contains(t2)) {26 log.debug("add to queue: " + t2.getTid());27 queue.add(t2);28 }29 }30 }31 }32 log.debug("Duplicates: " + duplicates.size());33 return duplicates;34 }35 }
49
Literaturverzeichnis
[ABS+06] P. Agrawal, O. Benjelloun, A.D. Sarma, C. Hayworth, S. Nabar,
T. Sugihara, and J. Widom. Trio: A system for data, uncertainty, and
lineage. In Proceedings of the 32nd international conference on Very largedata bases, pages 1151–1154. VLDB Endowment, 2006.
[BBN+05] A. Bilke, J. Bleiholder, F. Naumann, C. Böhm, K. Draba, and M. Weis.
Automatic data fusion with HumMer. In Proceedings of the 31st in-ternational conference on Very large data bases, pages 1251–1254. VLDB
Endowment, 2005.
[BCMP10] L. Blanco, V. Crescenzi, P. Merialdo, and P. Papotti. Probabilis-
tic models to reconcile complex data from inaccurate data sources.
In Advanced Information Systems Engineering, pages 83–97. Springer,
2010.
[BDM+05] J. Boulos, N. Dalvi, B. Mandhani, S. Mathur, C. Re, and D. Suciu.
MYSTIQ: a system for finding more answers by using probabilities.
In Proceedings of the 2005 ACM SIGMOD international conference onManagement of data, pages 891–893. ACM, 2005.
[BDSH+08] O. Benjelloun, A. Das Sarma, A. Halevy, M. Theobald, and J. Widom.
Databases with uncertainty and lineage. The VLDB Journal,17(2):243–264, 2008.
[BGMM+09] O. Benjelloun, H. Garcia-Molina, D. Menestrina, Q. Su, S.E. Whang,
and J. Widom. Swoosh: a generic approach to entity resolution. TheVLDB Journal, 18(1):255–276, 2009.
[BGMP90] D. Barbara, H. Garcia-Molina, and D. Porter. A probabilistic rela-
tional data model. Advances in Database Technology—EDBT’90, pages
60–74, 1990.
[BGMP02] D. Barbara, H. Garcia-Molina, and D. Porter. The management of
probabilistic data. Knowledge and Data Engineering, IEEE Transactionson, 4(5):487–502, 2002.
[BN05] J. Bleiholder and F. Naumann. Declarative data fusion–syntax, se-
mantics, and implementation. In Advances in Databases and Informa-tion Systems, pages 58–73. Springer, 2005.
50 Literaturverzeichnis
[BS06] C. Batini and M. Scannapieca. Data quality: Concepts, methodologiesand techniques. Springer-Verlag New York Inc, 2006.
[CGM05] S. Chaudhuri, V. Ganti, and R. Motwani. Robust identification of
fuzzy duplicates. In Data Engineering, 2005. ICDE 2005. Proceedings.21st International Conference on, pages 865–876. IEEE, 2005.
[Cha] Sam Chapman. Simmetrics. In
http://staffwww.dcs.shef.ac.uk/people/S.Chapman/simmetrics.html.
[CP87] R. Cavallo and M. Pittarelli. The theory of probabilistic databases. In
Proceedings of the 13th International Conference on Very Large Data Bases,
pages 71–81, 1987.
[FFBS04] E. Freeman, E. Freeman, B. Bates, and K. Sierra. Head first designpatterns. O’Reilly & Associates, Inc., 2004.
[FR97] N. Fuhr and T. Rölleke. A probabilistic relational algebra for the in-
tegration of information retrieval and database systems. ACM Trans-actions on Information Systems (TOIS), 15(1):32–66, 1997.
[FS69] I.P. Fellegi and A.B. Sunter. A theory for record linkage. Journal of theAmerican Statistical Association, 64(328):1183–1210, 1969.
[GFSS99] H. Galhardas, D. Florescu, D. Shasha, and E. Simon. An extensible
framework for data cleaning. 1999.
[GFSS00] H. Galhardas, D. Florescu, D. Shasha, and E. Simon. Declaratively
cleaning your data using AJAX. Journees Bases de Donnees, Oct, 2000.
[Gre00] Todd M. Greanier. Flatten your objects,Discover the secrets of the Ja-
va Serialization API. In http://www.javaworld.com/jw-07-2000/jw-0714-flatten.html, 14 July 2000.
[HAKO09] J. Huang, L. Antova, C. Koch, and D. Olteanu. MayBMS: a proba-
bilistic database management system. In Proceedings of the 35th SIG-MOD international conference on Management of data, pages 1071–1074.
ACM, 2009.
[HS95] M.A. Hernández and S.J. Stolfo. The merge/purge problem for large
databases. In Proceedings of the 1995 ACM SIGMOD international con-ference on Management of data, page 138. ACM, 1995.
[KE04] Alfons Kemper and André Eickler. Datenbanksysteme - Eine Ein-führung, 5. Auflage. Oldenbourg, 2004.
[Len02] M. Lenzerini. Data integration: A theoretical perspective. In Proceed-ings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium onPrinciples of database systems, pages 233–246. ACM, 2002.
Literaturverzeichnis 51
[luc] Apache lucene . In http://lucene.apache.org/java/docs/index.html.
[MA06] A. Motro and P. Anokhin. Fusionplex: resolution of data inconsisten-
cies in the integration of heterogeneous information sources. Infor-mation Fusion, 7(2):176–196, 2006.
[MF05] H. M
üller and J.C. Freytag. Problems, methods, and challenges in comprehen-sive data cleansing. Professoren des Inst. F
ür Informatik, 2005.
[MRS08] Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schtze.
Introduction to Information Retrieval. Cambridge University Press,
New York, NY, USA, 2008.
[Nau] F. Naumann. Hummer. In http://www.hpi.uni-potsdam.de/naumann/hummer/.
[NBBW06] F. Naumann, A. Bilke, J. Bleiholder, and M. Weis. Data fusion in three
steps: Resolving schema, tuple, and value inconsistencies. IEEE DataEng. Bull, 29(2):21–31, 2006.
[NH10] F. Naumann and M. Herschel. An Introduction to Duplicate Detec-
tion. Synthesis Lectures on Data Management, 2(1):1–87, 2010.
[pip] Pipes. In http://www.linfo.org/pipe.html.
[PVKDKR10] F. Panse, M. Van Keulen, A. De Keijzer, and N. Ritter. Duplicate de-
tection in probabilistic data. In Data Engineering Workshops (ICDEW),2010 IEEE 26th International Conference on, pages 179–182. IEEE, 2010.
[RB01] E. Rahm and P.A. Bernstein. A survey of approaches to automatic
schema matching. the VLDB Journal, 10(4):334–350, 2001.
[SCH] D. Suciu, A. Connolly, and B. Howe. Embracing uncertainty in
large-scale computational astrophysics. Ander de Keijzer, Universityof Twente, The Netherlands Maurice van Keulen, University of Twente,The Netherlands, page 63.
[SUN] SUN/Oracle. Immutable Objects. In http://download.oracle.com/javase/tutorial/essential/concurrency/immutable.html.
[TB98] G.K. Tayi and D.P. Ballou. Examining data quality. Communicationsof the ACM, 41(2):57, 1998.
[vKdKA05] M. van Keulen, A. de Keijzer, and W. Alink. A probabilistic XML ap-
proach to data integration. In Data Engineering, 2005. ICDE 2005. Pro-ceedings. 21st International Conference on, pages 459–470. IEEE, 2005.
52 Literaturverzeichnis
[WN06] M. Weis and F. Naumann. Detecting duplicates in complex XML
data. In Data Engineering, 2006. ICDE’06. Proceedings of the 22nd Inter-national Conference on, page 109. IEEE, 2006.
[WS96] R.Y. Wang and D.M. Strong. Beyond accuracy: What data quality
means to data consumers. Journal of management information systems,
12(4):5–33, 1996.
[ZDG03] W. Zhao, A. Dekhtyar, and J. Goldsmith. Query algebra operations
for interval probabilities. In Database and Expert Systems Applications,
pages 527–536. Springer, 2003.
[Zuk01] John Zukowski. Advanced serialization. In
http://java.sun.com/developer/technicalArticles/ALT/serialization/, 2001.
Eidesstattliche Erklärung
Ich versichere, dass ich die vorstehende Arbeit selbstständig und ohne fremde Hil-
fe angefertigt und mich anderer als der im beigefügten Verzeichnis angegebenen
Hilfsmittel nicht bedient habe. Alle Stellen, die wörtlich oder sinngemäß aus Veröf-
fentlichungen entnommen wurden, sind als solche kenntlich gemacht.
Ich bin mit einer Einstellung in den Bestand der Bibliothek des Fachbereiches ein-
verstanden.
Hamburg, den Unterschrift: