Bachelorarbeit - uni-hamburg.de › files › ... · 1 1. Einleitung Die Erkennung von Duplikaten in Datenbeständen, insbesondere in Datenbanken, ist ein viel behandeltes und umfangreich

Universität HamburgFakultät für Mathematik,Informatik und Naturwissenschaften

Bachelorarbeit

Entwurf und Implementierung einesadaptiven und flexiblen Frameworks zurDuplikaterkennung in probabilistischen

Daten

Lars Grote

[email protected]

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

http://vsis-www.informatik.uni-hamburg.de/projects/QloUD/

http://vsis-www.informatik.uni-hamburg.de/

http://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, . . . )


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.


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

http://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]


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


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-


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

java.util.Map


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


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/)

http://www.apache.org

https://issues.apache.org/jira/browse/LUCENE-2215

http://xstream.codehaus.org

http://code.google.com/p/protobuf/

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.


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.


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.


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


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:

Documents

Bachelorarbeit - uni-hamburg.de › files › ... · 1 1. Einleitung Die Erkennung von Duplikaten in Datenbeständen, insbesondere in Datenbanken, ist ein viel behandeltes und umfangreich