Windowing-Verfahren - Partitionierung zur effizienten Duplikaterkennung in relationalen Daten - page 39

Sortierte
Datenbank

Priority
Queue (PQ)

Vergleiche i mit
Tupeln der PQ

Lese Tupel i

ja nein

Find(i) in der
Priority Queue?

nein Duplikate von i

gefunden?

i++

Neuer Cluster
in PQ

ja

Union (i,j)

Abbildung 4.3: Ablauf der Union/Find-Methode 13

4.4 Inkrementelle Duplikaterkennung

Eine inkrementelle Duplikaterkennung 14 ist sinnvoll, wenn bereits ein bereinigter
Datenbestand existiert, in den neue Datensätze integriert werden sollen. Für jede
Duplikatgruppe wird ein Repräsentant ausgewählt. Für die Auswahl des Reprä-
sentanten existieren verschiedene Strategien, z.B. kann der vollständigste, der zu-
letzt eingefügte oder ein beliebiger Datensatz gewählt werden. Die Sorted-Neigh-
borhood-Methode läuft dann über die Menge der Repräsentanten und die neuen
Datensätze. Anschließend muss wieder die transitive Hülle gebildet werden. Hier-
bei kann es vorkommen, dass Duplikatgruppen zusammen gefasst werden können,
wenn ein neuer Datensatz das Duplikat mehrerer Repräsentanten ist. Für jedes wei-
tere inkrementelle Einfügen von Datensätzen können wieder neue Repräsentanten
ausgewählt werden.

13 Quelle: in Anlehnung an [24], S. 24
14 vgl. hierzu und zum Folgenden [5] S. 115 f. und [19], S. 343