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

Hausarbeit im Seminar:Verteilte Systeme und Informationssysteme

Duplikatenerkennung in XML

Danny Patrick Gerome Schubert

5schuber@informatik.uni-hamburg.de

Studiengang Master of Science Informatik

Matr.-Nr. 6747985

Fachsemester 1

Betreuer: Professor Dr. Norbert Ritter

Dipl.-Inform. Fabian Panse

Inhaltsverzeichnis 1

Inhaltsverzeichnis

1 Einleitung 3

2 XML Grundlagen 5

3 Duplikatenerkennung mittels XMLDup 73.1 Konstruktion des Bayesschen Netzes . . . . . . . . . . . . . . . . . . . . . . 7

3.2 Berechnung der Wahrscheinlichkeiten für Bayessche Netze . . . . . . . . . 9

3.3 Auswertung des Bayesschen Netzes . . . . . . . . . . . . . . . . . . . . . . 12

4 DogmatiX 17

5 Praktischer Vergleich zwischen XMLDup und DogmatiX 21

6 Fazit 23

Literaturverzeichnis 25

2 Inhaltsverzeichnis

3

1 Einleitung

Diese Ausarbeitung beinhaltet das Auffinden von Duplikaten innerhalb einer XML- Struk-

tur. Hierfür wird zunächst ein neu entwickelter Ansatz vorgestellt ([LCH13]), welcher auf

der Technik von Bayesschen Netzwerken basiert. Im weiteren Verlauf wird noch ein wei-

terer Ansatz mit DogmatiX vorgestellt. Dieser Ansatz beschreibt den den bis dato “state-

of-the-art“ Standard für die Erkennung von Duplikaten innerhalb einer XML-Struktur.

Warum ist es heutzutage so wichtig Duplikate aus XML-Strukturen zu filtern? Dies be-

gründet sich vor allem in der Tatsache, dass es regelrechten Drang dazu gibt, Daten zu

sammeln. Jedoch ist es aufgrund des Menschen nicht trivial jeden Datensatz nur ein-

mal zu erhalten. Dies liegt daran, dass z.B. eine Person in ein Adressbuch oder in eine

Filmdatenbank (als Schauspieler oder Regisseur) eingefügt werden soll. Nun ist es z.B.

einem Redakteur eines Systems möglich, dies in mehreren unterschiedlichen Variationen

zu notieren. So könnte einmal der Name einmal mit dem Vordernamen abgekürzt und

Nachname ausgeschrieben werden (“M. Mustermann“) abgelegt werden. Ein weiteres

mal könnte dies in umgekehrter Reihenfolge erfolgen. Die Darstellung wäre wie folgt:

“Max M.“.

Um eine solche Datenmenge, welche unnötig viele Elemente enthält zu vereinfachen,

befasst sich diese Arbeit mit der Thematik. Durch die beiden oben aufgeführten Ansätze

wird ein Gefühl dafür geschaffen, wie aufwendig und unter Umständen unabdingbar

Duplikatenerkennung sein kann.

4 1 Einleitung

5

2 XML Grundlagen

Um das Verständnis für die nachfolgenden Kapitel zu stärken, werden zunächst benö-

tigte Grundlagen und Grundbegriffe zum Thema XML erörtert. Bei XML handelt sich

um eine beschreibende Sprache für Daten. D.h. die Daten werden in eine Struktur einge-

fügt, welche grundsätzlich nach Belieben aufgebaut werden kann. Für die Struktur gibt

es eine Bedingung. Sie besagt, dass die beschreibenden Elemente in einer Baumstruktur

angeordnet werden müssen. Somit ergibt sich eine hierarchische Struktur. Nachfolgend

wird sowohl auf die Baumstruktur als auch auf die Beschreibende Sprache eingegangen.

Des Weiteren gilt syntaktische Begebenheiten für die sogenannte “Wohlgeformtheit“ ei-

nes XML-Dokuments zu beachten, jedoch werden wir diese in dieser Arbeit nicht aus-

führen.

In Listing 2.1 ist ein XML-Dokument dargestellt. Teile dieses Dokuments werden in den

nachfolgenden Kapiteln noch beispielhaft verwendet.

Listing 2.1: Beispiel XML-Format basierend auf dem Baum aus Abb. 3.1 [CHL10]

1 <?xml version=’1.0’ encoding=’UTF-8’>

2 <mv>

3 <mv1 year="1983" title="Pros and Cons">

4 <dr1>John S.</dr1>

5 <cst1>

6 <ac1>Templeton P.</ac1>

7 <ac2>H.M. Murdock</ac2>

8 </cst1>

9 </mv1>

10 </mv>

Hinweis: Die erste Zeile aus Listing 2.1 ist die Dokumenttyp-Deklaration. Sie gehört zur

Grundstruktur eines XML-Formats (somit auch zur “Wohlgeformtheit“). Um die Kor-

rektheit zu prüfen gibt es einige Validatoren, wie z.B. vom W3C.1

Wie bereits erwähnt ist die Baumstruktur bei XML vorherrschend. D.h. es gibt ein Wur-

zelelement (engl. root), welches alle anderen Elemente beinhaltet. In unserem Beispiel ist

dies das Element “mv“. Diesem Element können nun Kinder (engl. children) angehängt

werden. Solch ein Kind-Element, wie es “mv1“ darstellt, kann sowohl Attribute wie auch

wiederum untergeordnete Kind-Elemente enthalten.

1https://validator.w3.org/

6 2 XML Grundlagen

Beispiele für Attribute wären hier z.B. “year“ oder “title“. Es befindet sich innerhalb der

Elementdefinition. Es können beliebig viele Attribute an ein Element angefügt werden.

Dies gilt ebenso für die die untergeordneten Kind-Elemente von “mv1“. Es kann eben-

falls beliebig viele Elemente geben. Hier sind z.B. “dr1“ und “cst1“ aufzuführen.

Hinweis: Der hier abgebildete Fall für den Aufbau einer XML-Struktur ist sehr klein.

Diese Struktur kann je nach Wünschen beliebig groß skaliert werden.

Wurzel und Kind-Elemente werden nach dem Vorbild des beschreibenden XML-Formats

angeordnet. Jedoch fällt in Abbildung 2.1 das Schlüsselwort “Parent“ auf. Im vorherigen

Verlauf wurde bereits erläutert, dass es Kind-Elemente gibt. D.h. Elemente welche un-

tergeordnet zu einem Element eingefügt werden. Umgekehrt heißt dies nun, dass die-

ses eingefügte Element eine Elternelement (engl. parent) besitzt. Dieses Elternelement ist

das Element in der Ebene über der eines Kindes. So ist nun “cst1“ ein Kind-Element von

“mv1“ , welches zugleich das Eltern-Element darstellt (parent).

mv1

cst1

@year @title

TempletonP.

ac1 ac2

1983 ProsAndCons

H.M.Murdock

ParentChild

dr1

Abbildung 2.1: Ausschnitt von einem Baum, basierend auf Listing2.1

In diesem kleinen Exkurs im aktuellen Kapitel zum Thema XML Grundlagen wurde

auf die für diese Arbeit wichtigen Punkte eingegangen. So wurde erläutert in welchen

Darstellungsformen XML-Strukturen abgebildet werden können. Des Weiteren wurde

auf Begrifflichkeiten wie Wurzel-, Eltern- und Kind-Elemente eingegangen. Diese bilden

die Grundlage für die weiterführenden Ausführungen.

7

3 Duplikatenerkennung mittels XMLDup

Bayessche Netze (oder auch Netzwerke) sind gerichtete, azyklische Graphen. Im Bereich

der Künstlichen Intelligenz sind diese weit verbreitet. Sie finden dort in Expertensyste-

men zur Wissensrepräsentation Verwendung. In diesem Kapitel wird erörtert, wie Bayes-

sche Netze ebenfalls in einem Ansatz genutzt werden können der XMLDup genannt wird

[LCH13]. Hierbei handelt es sich um eine Methodik zum Erkennen von Duplikaten in

XML.

Zunächst wird eine Struktur gebildet, welche es ermöglicht ein XML-Format in ein Bayes-

sche’s Netz abzubilden. Im Laufe dieses Aufbaues einer Struktur wird deutlich, dass

es einen Mechanismus geben muss, welcher dabei hilft Wahrscheinlichkeiten zu bilden.

Auf diesen wird im zweiten Teil eingegangen. Im dritten Teil geht es um, dass soge-

nannte Pruning (deutsch Beschneiden\Kürzen). Mit Hilfe dieser Technik lässt sich der

Vergleichsprozess optimieren.

3.1 Konstruktion des Bayesschen Netzes

In Abbildung 3.1 sind zwei exemplarische Bäume abgebildet. Diese basieren auf dem

XML Code aus dem Listing 2.1. Bei Baum U’ wurden die Werte und Attribute leicht ver-

ändert. Der Grundsätzliche Aufbau ist jedoch gleich zum XML Listing und Baum U.

mv1

cst1

dr1

@year @title

John S.

TempletonP.

Baum U

ac1 ac2

1983 ProsAndCons

H.M.Murdock

mv1

cst1

dr1

@year @title

J. Smith

T.Peck

Baum U

ac1 ac3

1984 ProsAndCons

Murdock

ac2

B.A.Baracus

Abbildung 3.1: Beispielstruktur im Bezug auf Filme aus [CHL10]

Der nächste Schritt besteht nun daraus, die beiden Bäume zu “Mappen“ (deutsch Ab-

bilden). Das bedeutet die Bäume werden nun miteinander vereinigt. Die Vereinigung

dieser beiden XML Bäume ist in Abbildung 3.2 zu sehen.

8 3 Duplikatenerkennung mittels XMLDup

Vmv11

mv11

Cmv11

cst11

dr11

Ccst11

Vdr11

mv11[year]mv11[title]

ac1*

ac11 ac13

Vac11 Vac13

ac11[value] ac13[value]

ac**

dr11[value]

ac12

Vac12

ac12[value]

ac2*

ac21 ac23

Vac21 Vac23

ac23[value]

ac22

Vac22

ac22[value]ac21[value]

Abbildung 3.2: Beispiel eines gemappten Baumes. Dieser besteht aus Baum U und U’.

[CHL10]

In Abbildung 3.2 sehen Sie den Oberknoten “mv11". Dieser Knoten lässt schlussfolgern,

ob U ein Duplikat von U’ ist oder nicht. Um die Wahrscheinlichkeitswerte zuweisen zu

können, wird “mv11“ zunächst einmal eine binäre Zufallsvariable zugewiesen. Diese Va-

riable kann grundsätzlich nur zwei Zustände annehmen:

Tabelle 3.1: Werte, welche die Variable in mv11 annehmen kann

Wert Zustand Beschreibung

1 active Baum U und U’ sind Duplikate

0 inactive Baum U und U’ sind keine Duplikate

Der Zustand (aus Tabelle 3.1) den “mv11“ enthält, sprich ob die beiden Knoten “mv1“

Duplikate sind, ist von zwei Faktoren abhängig:

1. Sind die Attribute Duplikate oder nicht?

2. Sind die Kind-Elemente Duplikate oder nicht?

Der Knoten “Vmv11“ aus Abb. 3.2 beinhaltet die Attribute von “mv“. Ihm wird eine bi-

näre Zufallsvariable zugewiesen um aussagen zu können, ob die Attribute aus den bei-

den Bäumen gleich sind, sprich Duplikate. Selbiges gilt für den Knoten “Cmv11“. Die-

ser beinhaltet die Kind-Elemente der beiden Bäume und stellt fest ob es sich hierbei

3.2 Berechnung der Wahrscheinlichkeiten für Bayessche Netze 9

ebenfalls um Duplikate handelt. Wie bei dem Knoten “Vmv11“ wird hier bei “Cmv11“

ebenfalls eine Wahrscheinlichkeit gebildet. Hierfür wird dem Knoten ebenfalls eine bi-

näre Zufallsvariable zugewiesen, die am Ende den entsprechenden Wert enthält ob die

Kinder-Elemente der beiden Bäume U und U’ tatsächlich Duplikate sind. Somit hängt

die Aussage ob es sich wirklich um ein Duplikat handelt, von den Paaren, die aus den

einzelnen Knoten der Bäume U und U’ gebildet werden, ab.

Ähnlich wird für die Knoten “dr“ und “cst“ vorgegangen. Hier werden gleichermaßen

binäre Zufallsvariablen zugewiesen. In diesem Fall sind dies “Ccst11“ und “Vdr11“. Sie

enthalten wiederum die Wahrscheinlichkeiten für die Knoten “cst1“ und “dr1“ aus den

Bäumen U und U’.

Für den Fall, dass es mehrere ähnliche Knoten vorhanden sind, wie anhand “ac**“ zu

sehen ist, wird für jeden einzelnen Knoten geprüft, ob es ein Duplikat gibt. Somit be-

nötigt jedes Element aus beiden Bäumen eine eigene binäre Variable die den Wert der

Wahrscheinlichkeit enthält. Im nächsten Schritt wird jeder Pfad aus Baum U mit jedem

Pfad aus Baum U’ auf Duplikate geprüft.

3.2 Berechnung der Wahrscheinlichkeiten für Bayessche Netze

Im 3.1 wurde bereits erwähnt, dass es binäre Zufallsvariablen gibt, welche Wahrschein-

lichkeiten enthalten. Sie geben für die Knoten der zu vergleichenden Bäume U und U’

an, ob diese Duplikate sind oder nicht.

Es kann nachfolgend grundsätzlich zwischen zwei Wahrscheinlichkeitstypen unterschie-

den werden:

• A-priori-Wahrscheinlichkeiten:

Exkurs: A-priori-Wahrscheinlichkeiten sind sozusagen eine Vordefinition der Wahr-

scheinlichkeit für einen Standardisierten Zustand. Sofern nichts anderes bekannt

ist, wird diese Wahrscheinlichkeit angenommen und für Berechnungen verwendet.

[CHL10] et. al. gibt wieder, dass es Anwendungsfälle gibt, in welchen es nicht

möglich oder nicht Effizient genug wäre mit berechneten Wahrscheinlichkeiten zu

starten. Hierfür wird eine Standard-Wahrscheinlichkeit in einer Konstanten ka de-

finiert.

10 3 Duplikatenerkennung mittels XMLDup

• Zustands-Wahrscheinlichkeiten:

Es gibt zusätzlich vier Zustands-Wahrscheinlichkeiten die in [CHL10] ausgeführt

werden. Diese werden nachfolgen betrachtet:

1. CP1:

CP1 besagt, dass die Wahrscheinlichkeit für Duplikate auf Ebene der Daten

durch die einzelne paarweisen Übereinstimmungen gegeben ist.

2. CP2:

Die Wahrscheinlichkeit, dass die Kind-Elemente Duplikate sind, wird gegeben

durch die Tatsache, dass die einzelnen Kinder übereinstimmen. Im Falle einer

Unvollständigkeit der Bäume gilt umso mehr Kinder übereinstimmen, desto

größer ist die Wahrscheinlichkeit, dass die Eltern-Elemente ebenfalls überein-

stimmen.

3. CP3:

Die Wahrscheinlichkeit, dass zwei Knoten Duplikate sind, ist durch die Tatsa-

chen gegeben, indem die Kind-Elemente und Ihre Daten gleich sind.

4. CP4:

In einem Satz von Knoten, ist die Wahrscheinlichkeit für den ganzen Satz

durch die Tatsache gegeben, dass die einzelnen Paare in diesem Satz Dupli-

kate sind. Hieraus lässt sich schließen, dass umso mehr Paare Duplikate sind,

desto höher ist die Wahrscheinlichkeit für den ganzen Satz ein Duplikat zu

sein.

• Endgültige Wahrscheinlichkeit:

Nachdem alle A-priori- und Zustands-Wahrscheinlichkeiten definiert wurden, kann

durch nachfolgende Formel, die Endgültige Wahrscheinlichkeit für Duplikate der

Bäume berechnet werden. Nachstehend ist die Formel basierend auf Basis von Abb.

3.2 dargestellt.

(P (mv11 [title]) + P (mv11 [year])) steht für die Zusammengeführten Attribute des

Knoten mv1 aus den Bäumen U und U’. Der Ausdruck

(P (dr11 [title]) +

(1−

∏3i=1 (1− P (ac1i [value])) + 1−

∏3i=1 (1− P (ac2i [value]))

)× 1

2

)steht für die Kind-Elemente dr1 und cst1.

3.2 Berechnung der Wahrscheinlichkeiten für Bayessche Netze 11

Da es nur einen Director gibt, gibt es auch nur eine Wahrscheinlichkeit. Im Fall

des Knotens cst1 für die Schauspieler, gibt es eine Mehrzahl in beiden zu Verglei-

chenden Bäumen. Da diese sich im Aufbau unterscheiden, werden Sie getrennt von

einander behandelt (siehe Abb. 3.2).Zunächst werden Sie für den jeweiligen “Teil-

baum“ mittels Multiplikation berechnet und aufaddiert. Um nun die letztendliche

Wahrscheinlichkeit zu erhalten wird dieses Ergebnis mit 12 multipliziert.

Die Gesamtwahrscheinlichkeit setzt sich schlussendlich aus der Wahrscheinlichkeit

der Attribute und des zweiten Teilbaumes des Casts zusammen. Da diese ebenfalls

den Knoten mv11 aufteilen, wird dies nochmals mit 12 multipliziert. Ist das Ergeb-

nis am Ende 1 bzw. nahe 1 kann von einem Duplikat ausgegangen werden. Ist dies

nicht der Fall, so ist kein Duplikat vorhanden.

12 3 Duplikatenerkennung mittels XMLDup

3.3 Auswertung des Bayesschen Netzes

Für die Auswertung des aufgestellten Netzes von Bayes wird anschließend eine kurze

Einführung gegeben. Die Problematik, welcher sich gestellt werden muss, ist der Zeit-

faktor. Es ist notwendig das gesamte Netz zu analysieren. Hinzu kommt das für jeden

einzelnen Knoten die Wahrscheinlichkeit berechnet werden muss. Dies kann bei einer

Komplexität von O(n × n′) ein zeitraubender Vorgang sein. n und n’ stehen an dieser

Stelle für die Anzahl der Knoten, welche Verglichen werden muss. Aufgrund dieser Tat-

sache haben die Autoren [LCH13] Ansätze gefunden diesen Vorgang zu beschleunigen.

Dafür führen Sie folgende vier Unterpunkte auf:

1. Netzwerk Pruning

Pruning bedeutet wörtlich übersetzt etwas “stutzen“. In Bezug auf das Bayessche

Netz gilt es hier eine Eingrenzungsstrategie zu finden, welche verlustfrei ist. Ver-

lustfrei bedeutet bei [LCH13] et. al. das keine Duplikate verloren gehen bei der

Eingrenzung. Es sollen lediglich die Duplikate wegfallen, die einen eigens festge-

legten Schwellwert nicht erreichen.

Zunächst wird mittels dem Bottom-Up Verfahren allen Variablen der Knoten ei-

ne A-priori-Wahrscheinlichkeit zugewiesen. Durch den enormen Rechenaufwand,

der durch diesen Vorgang entstehen würde, ist die Idee nun, diese Zuweisung erst

anzuwenden, wenn diese unbedingt notwendig ist.

Bei jedem Schritt wird die Ähnlichkeit berechnet und die endgültige Gleichheit

geschätzt unter der Berücksichtigung, dass die bekannten und unbekannten Ähn-

lichkeiten den Wahrscheinlichkeitswert 1 haben. Wenn festgestellt wird, dass die

Netzwerk-Wurzelknoten-Wahrscheinlichkeit den festgelegten Schwellenwert nicht

mehr übertreffen kann, dann wird das Objektpaar abgelegt und die restlichen Be-

rechnungen werden damit vermieden. Der Algorithmus in Form von Pseudocode

ist in [LCH13, Algorithm 1.] et. al. einzusehen.

Diesem wird der gewünschte Schwellenwert und der gemappte Baum aus Abb.

3.2 übergeben. Nach der Übergabe werden zunächst die Knoten sortiert unter der

Annahme der Tatsache, dass alle Wahrscheinlichkeiten 1 betragen. Wenn der aktu-

elle Knoten einer Value (Daten) entspricht, dann wird der Wert aus der Berechnung

der Ähnlichkeit der beiden Knoten angenommen. Wenn hingegen der Knoten noch

Eltern-Elemente besitzt, dann wird die Wahrscheinlichkeit der rekursiven Berech-

nung der Eltern-Elemente entnommen. Die Beweisführung für die Richtigkeit ist

[LCH13, 4.1] et. al. zu entnehmen.

3.3 Auswertung des Bayesschen Netzes 13

Im Anschluss wird ein neuer Schwellwert berechnet, welcher auf dem übergebenen

Schwellwert und dem bisher erzielten Wert basiert. An dieser Stelle wird geprüft,

mit Hilfe der Zustandswahrscheinlichkeiten aus Kap. 3.2, wie die Wahrscheinlich-

keit am besten berechnet werden kann aufgrund der vorliegenden Daten. Nachdem

der Wert berechnet wurde, wir noch abschließend geprüft, ob der Wert für den ge-

mappten Baum weiterhin über dem Schwellwert ist und entscheidet dann ob die

Berechnung beendet wird oder nicht.

2. Effekt von Knotenanordnung beim Pruning

Es kann der Fall eintreten, wie in in Abb. 3.1, dass es unter Umständen auf einer

Seite mehr Knoten gibt als auf der anderen. So wie z.B. bei den Schauspielern. Um

hier nun nicht unnötig Rechenleistung zu verschwenden, da hier ja unter Umstän-

den früher erkannt wird, dass es sich um ein Duplikat handelt, bevor alle Knoten

verglichen wurden, muss es eine spezielle Sortierung geben. Diese basiert auf un-

terschiedlichen heuristischen Ansätzen. Diese Ansätze können sein:

a) Tiefensortierung

b) Durchschnittliche String Größe

c) Unverwechselbarkeit

Je nach Art der Gewichtung beim Sortieren kann jeder Ansatz als einzelner ver-

wendet werden oder eine Kombination aus diesen drei Ansätzen. So wird [LCH13,

4.2] et. al. darauf hingewiesen, dass sich hierdurch eine Zeitersparnis, von bis zu

60% erreichen lässt.

3. Variation des Pruning Faktors

Zu Beginn besitzt jeder Knoten die Wahrscheinlichkeit von 1. Das ist der Pruning

Faktor. Bei der Annahme, dass der Faktor gesenkt werden kann. Dies hat zur Folge,

dass das Netzwerk beschleunigt wird.

Bei der von Anfang an definierten Wahrscheinlichkeit wird der Wert 1 zunächst fest

definiert. Durch diesen Faktor wird grundsätzlich kein Paket verloren. Wird dieser

Faktor nun verkleinert, würde hier jetzt erwartet werden, dass viele Duplikate ver-

loren gehen, jedoch ist dies nicht der Fall.

4. Automatisierung der Pruning-Faktoren-Selektierung

Eine Automatisierung der Selektion des Pruning-Faktors kann nicht nur die Ar-

beit erleichtern sondern auch den Prozess der Duplikatenerkennung optimieren.

14 3 Duplikatenerkennung mittels XMLDup

Hierfür haben die Autoren [LCH13] et. al. einen Ablauf kreiert, welch dies ermög-

licht.

Dieser Ablauf besteht aus drei Schritten:

a) Zuweisen von Pruning-Faktoren an die Attribute

b) Zuweisung auf bestehenden Daten weiterentwickeln (Lernen)

c) Pruning-Faktoren für Innere Knoten

zu a.:Für die Zuweisung von Pruning-Faktoren an die Attribute stellen sich die Autoren

in [LCH13, Kap. 4.4.1] et. al. die Frage, wie die Wahrscheinlichkeit bestimmt wer-

den kann ohne alle Vergleiche berechnen zu müssen.

Die Lösung besteht darin, eine “Mapping-Funktion“ zu finden, welche die Mög-

lichkeit bietet ein Attribut als Eingabe zu bekommen und den dazugehörigen Pru-

ning Faktor zurück zu erhalten.

Hierfür werden die Attribute bestmöglich charakterisiert. So sind folgende 5 Grup-

pen entstanden:

• “Uniqueness features:“

“Uniqueness features:“ sind vorkommen, welche die Attribute auf einzigarti-

ge Art und Weise unterscheiden.

• “Format features:“

Diese Sektion, bezieht sich darauf, welche Information in den Attributen zu

finden ist. Z.B. Text, Zahlen oder beides in Kombination.

• “Content length features“

“Content length features“ vergleichen eine Durchschnittsgröße und den Infor-

mationsgehalt eines Strings, mit den in der “Mapping-Funkton“ vorhandenen

Daten.

• “Absence features“

Lediglich die Anzahl der vermissten Attribute ist hier enthalten. Attribute,

welche in mehreren Objekten vermisst werden, sollten vernachlässigt werden.

• “Occurence features“

Alleinig die Anzahl der Häufigkeit des Auftretens der Attribute wird hier ge-

messen.

zu b.:Zum Lernen für die “Mapping-Funktion“ werden Daten benötigt. Optimale Daten

für das Lernen wären hier z.B. ein Satz von Attributen mit idealen Pruning Fakto-

ren. Das es nicht sehr wahrscheinlich ist solche Datensätze zu erhalten, muss ein

3.3 Auswertung des Bayesschen Netzes 15

alternativer Ansatz dazu gefunden werden.

Die Autoren mit einem leicht modifizierten Ansatz von “Simulated annealing“:

“SA is an algorithm intended to determine the maximum (or minimum) value of

a function with several independent variables, under a fraction of the time needed

to find an absolute maximum (or minimum) in a large search space.“[LCH13, Kap.

4.4.2]

Der Unterschied besteht darin, dass neue Zustände nur akzeptiert werden, wenn

der Verlust der Anteile weniger als 10% beträgt.

So wird nun diese Methodik dafür genutzt um einen gut “gebildete“ “Mapping

Funktion“ zu erhalten, die schlussendlich für die Berechnung des Pruning Faktors

der Daten genutzt werden kann.

zu c.:Bisher behandelten die Ansätze lediglich Pruning Faktoren im Bezug auf Attribu-

te. Jedoch für die Auswertung eines Bayesschen Netzes muss der Pruning Faktor

ebenfalls für jeden Knoten erstellt werden.

An diesem Punkt bedienen sich die Autoren [LCH13] et. al. einer einfachen Lö-

sung. Sie bestimmen für jede Leaf Node den Pruning Faktor. Da diese Faktoren

als Obergrenze angesehen werden können, werden diese Werte entlang des Netz-

werks weiter gereicht, als ob Sie die tatsächlichen Wahrscheinlichkeitswerte wären.

Der an jedem Knoten berechnete Wert kann wiederum als Pruning Faktor verwen-

det werden.

16 3 Duplikatenerkennung mittels XMLDup

17

4 DogmatiX

Nachdem mit der Anwendung von Bayesschen Netzen ein neuer Ansatz für die Duplika-

tenerkennung vorgestellt wurde, wird im nachfolgenden Kapitel der bis dato “state-of-

the-art“ Ansatz für die Duplikatenerkennung in XML vorgestellt. Der Ansatz heißt Dog-

matiX. Hierbei handelt es sich um ein Frameworkaufbau für die Erkennung von XML.

Der Aufbau und Ablauf des Frameworks wird in Abb. 4.2 dargestellt. Aus dieser Ab-

bildung ergeben sich 3 Schritte, auf denen das Framework für die Erkennung von XML

Duplikaten basiert.

Schema Dirty Data

Candidate Definition

Candidate Selection

Duplicate Definition

Description Selection

Duplicate Classification

Duplicate Detection

(1) Candidate Query Exec.

Duplicate Candidates

(2) Description Query Exec.

(3) OD Generation

Object Descriptions (ODs)

(4) Comparison Reduction

(5) Comparisons

Duplicate Pairs

Duplicate Clustering

(6) Duplicate Clustering

Query Formulation

Query Formulation

Abbildung 4.1: Framework Darstellung aus [WN05]

18 4 DogmatiX

1. “Candidate Definition“

Zunächst wird mit der “Candidate Definition“ begonnen. In diesem Schritt ist das

Ziel, zu erkennen welche Objekte für den Vergleich relevant sind um dadurch be-

reits vor dem eigentlichen Vergleich, geeignete Kandidaten ausfindig zu machen.

Dies hat den Vorteil, dass die Anzahl von Vergleichen bereits reduziert wird.

So kann z.B. eine Suche nach Schauspielern gewünscht werden. Dies könnte mit-

hilfe der Bäume aus Abb. 3.1 folgenden Suchpfad ergeben: S = {/mv/cst/ac} .

Aufgrund von dieser Definition ist es nun möglich einen Satz (engl. Set) von XML

Elementen zu liefern, welches den Schauspielern entspricht. Im Bezug auf Abb. 3.1

wäre der zurück gegebene Satz an Daten aci, dass was die Bäume U und U’ an

Schauspieler enthalten. Somit hat man im ersten Schritt seine potentiellen Kandi-

daten für den Vergleich auf Duplikate erhalten.

2. “Duplicate Definition“

Bei der Identifizierung von potentiellen Kandidaten aus dem vorangegangen wird

nicht beachtet, dass es unter Umständen dazu kommen kann, dass auch nicht benö-

tigte Informationen mit identifiziert werden. Dies soll eingedämmt werden, indem

zunächst eine Definition von der Duplikat Struktur erzeugt wird. Nachdem diese

Struktur erstellt wurde, wird diese mit Hilfe von XQuery ausdrücken abgebildet.

Exkurs: XQuery ist eine Abfragesprache die auf XML basiert. Für nähere Informa-

tion können Sie gibt das W3C weiterführende Hilfe.1

Entsprechend führt [CHL10] der Objektbeschreibung wie folgt aus: <text,xpath>.

Hierbei steht die “xpath“ für den absoluten Pfad zum Knoten, welcher für einen

Duplikat Vergleich herangezogen werden soll.“text“ steht hier für die Daten sprich

die “value“ des XML-Knotens.

In Abb. 3.1 benennt der Autor aus [CHL10] die Filmeigenschaften Titel und Di-

rektor als gute Quellen um herauszufinden, ob es sich hierbei um ein Duplikat des

jeweilig anderen Baums handelt. In Tabelle 4.1 aus [CHL10] wird ersichtlich, wie

diese Beschreibung der Beziehungen zwischen den einzelnen Elementen der Bäu-

me aussehen kann:

Tabelle 4.1: Beispiel von Beziehungen zw. zwei Baumelementen aus [CHL10]

Objekt Objektbeschreibung

U {< “ProsandCons“, /mv@title >,< “JohnS.“, /mv/dr/text() >}U’ {< “ProsandCons“, /mv@title >,< “JohnS.“, /mv/dr/text() >}

1http://www.w3.org/XML/Query/

19

Da das Auffinden von Knoten, welche verglichen werden sollen, sehr aufwendig

ist, kann die Arbeit mittels heuristischer Regeln [CHL10] automatisiert werden. An-

hand des Knotens “cst1“ wird dies nachfolgend dargestellt.

a) r-Distanz Vorgänger: Vorfahren u bis zu einer bestimmten Entfernung r. Abb.

4.2 unter (a) zeigt das Ergebnis für r = 1.

b) r-Distanz Nachkommen: Nachkommen u bis zu einer bestimmten Entfernung

r. Ein Beispiel ist in Abb. 4.2 (b) zu sehen. Hier wird ebenfalls mit dem Wert r

= 1 gearbeitet.

c) k-nächstgelegene Nachkommen: Wählt die ersten Nachkommen k von u und

beginnt bei u. Fortgefahren wird mittels dem Breitensuchen-Algorithmus(engl.

Bread-First-Order). Unter (c) in Abb. 4.2 ist ein solches Bespiel mit k = 3 abge-

bildet.

Exkurs: Bei der Bread-First Order oder zu Deutsch auch Breitensuche genannt, han-

delt es sich um einen Algorithmus für das durchsuchen von Graphen. Hier wird

ein Graph von Ausgangspunkt u durchstöbert. Zuerst wird auf der durch u aus-

gewählten Ebene gesucht. Ist der Ausdruck hier nicht zu finden, so wird auf der

nächsten Unterebene gesucht. Dies wird letzten Endes solange durchgeführt, bis

der Ausdruck gefunden wurde oder nicht.

mv1

cst1@year @title

T.PeckB.A.

Baracus Murdock

1984 ProsandCons

cst1

ac3ac2ac1

T.PeckB.A.

Baracus

cst1

ac2ac1

1

2 3

(a) (b) (c)

Abbildung 4.2: Bildliche Darstellung der oben aufgeführten heuristischen Regeln aus[CHL10]

3. “Duplicate Detection“

Nach der Definition für das Suchen und Vergleichen von Duplikaten, wird nun auf

die eigentliche Erkennung dieser eingegangen. Begonnen wird nun in dem die An-

zahl von paarweisen Vergleichen reduziert wird. Die Reduzierung wird ermöglicht,

indem nach Kandidaten gesucht wird, welche die gleichen Beschreibungen enthal-

ten.

20 4 DogmatiX

Hierfür wird schlussendlich ein Filter eingesetzt. Die Logik, die hinter dem Fil-

ter steckt, ist simpel. Es wird ein Verhältnis zwischen einer Menge von gegebenen

Objektbeschreibungen und der Menge von Informationen in allen Objektbeschrei-

bungen berechnet.

Die Menge an Information wird durch eine Kombination von IDF’s (Inverse Do-

cument Frequency measure) ermittelt. Für diesen Gebrauch eignen sich die so ge-

nannten “soft IDF’s“.

Zu sehen ist es an der nachfolgenden [CHL10] Formel zur Berechnung des Wer-

tes auf Gleichheit zwischen den Bäumen U und U’ aus [CHL10].

sim(U,U ′) = softIDF (Pros andCons)

softIDF (Pros andCons) + softIDF (JohnS.) + softIDF (J.Smith)

Nach dem Filtern findet nun der eigentliche Vergleich statt. Hierfür werden die ein-

zelne Elemente der Paare verglichen. Alle Paare, welche einen definierten Schwell-

wert erreichen, werden als Duplikate deklariert. Für die Berechnung dieses Wertes

werden die Objektbeschreibungen beider Kandidaten herangezogen. Diese werden

im nächsten Schritt relativ zu den Werten der nicht ähnlichen Objektbeschreibun-

gen gesetzt und berechnet.

Bei ähnlichen Objekten wird eine normalisierte Entfernung zwischen den Daten

festgelegt. Unterbieten die normalisierten Entfernungen den Schwellwert, so han-

delt es sich hierbei um Duplikate. Für gleiche und nicht gleiche Beschreibungen

wird die Bedeutung durch die “soft IDF measure“ gegeben.

21

5 Praktischer Vergleich zwischen XMLDupund DogmatiX

Im nachfolgenden wird nun ein Vergleich zwischen XMLDup und DogmatiX dargestellt.

Die Testreihe die hier aufgeführt wird, wurde von den Autoren aus [LCH13] durchge-

führt. Sie benutzten für Ihren Test die Programmiersprache JAVA inkl. der DOM API

zum XML-Handling. Des Weiteren führten Sie Ihre Tests mittels 4 verschiedenen reeller

Datensätze durch. Für den Umfang der Daten wurden große Datensätze (z.B. CD 2) so-

wie kleine (z.B. Restaurant) zum Testen verwendet. Des Weiteren besitzen alle Datensätze

bis auf die des Restaurants 3 Ebenen. Der Datensatz des Restaurants hingegen besitzt 4

Ebenen. Für alle Durchläufe, d.h. sowohl für XMLDup wie auch DogmatiX, wurde ein

Schwellenwert von 0.5 definiert.

In Abbildung 5.1 sind die Testergebnisse für alle vier Datensätzen und beide Duplikatenerkennungs-

Methoden grafisch dargestellt. Dabei wird klar ersichtlich, dass der Ansatz der Baye-

schen Netze, welcher in XMLDup angewendet wird, einen effektiveren Weg darstellt

Duplikate zu finden.

Abbildung 5.1: Übersicht des Vergleichs zwischen XMLDup und DogmatiX für alle 4 Da-

tensätze [LCH13]

22 5 Praktischer Vergleich zwischen XMLDup und DogmatiX

Anhand der Tabelle 5.2 wird diese Aussage bekräftigt. Vor allem mit Hilfe des Faktors

für die Beschneidung von den Bäumen die in Kapitel 3.3 erläutert wird, ist ein zuverläs-

siger Faktor für einen Speed-Up bei den aufgezeigten Tests.

Tabelle 5.2: Zeitmessung der Duplikatenerkennung [LCH13]

Es bleibt zu erwähnen, dass es durchaus auch Bereiche gibt, in welchen DogmatiX

schneller ist, so z.B. zu sehen in Tabelle 5.2 bei dem “IMDB + FD“ Datensatz in Spalte

“XMLDup(np)“. Jedoch wird kein Pruning in XMLDup eingesetzt. Aufgrund der Daten-

menge ist DogmatiX schneller. Es lässt sich jedoch wiederum ein Geschwindigkeitsge-

winn gegenüber DogmatiX erzielen, indem mit dem Pruning Faktor gearbeitet wird.

In diesem Kapitel wurde anhand von Beispielen mit reellen Datensätzen gezeigt, wie

effizient und schnell XMLDup gegenüber DogmatiX ist. Es wurde verständlich gemacht,

dass es XMLDup kleinere Schwächen hat in Bezug auf sehr große Daten, sofern nicht mit

einem Pruning Faktor gearbeitet wird.

23

6 Fazit

In dieser Arbeit wurde sich mit der Thematik der Duplikatenerkennung befasst. Sie ist

ein sehr komplexes Thema. Angegangen wurde die Thematik mit Hilfe von dem neu ent-

wickelten XMLDup, sowie mit dem “state-of-the-art“ Erkennungsframework DogmatiX.

Im Laufe dieser Arbeit stellte sich heraus, dass es bei XMLDup um einen sehr interes-

sante Technik handelt um Duplikate innerhalb eines XML-Formats ausfindig zu machen.

Es verspricht einen Geschwindigkeits- sowie einen Effizienzgewinn gegenüber Dogma-

tiX. Dies wird großteils durch das Beschneiden der Baumstruktur gewährleistet.

Abschließend bleibt zu sagen, dass auch der XMLDup Ansatz kleinere Schwächen auf-

weist. So lässt sich bemerken, dass es anwendungsfallabhängig sein kann, für welchen

dieser beiden aufgezeigten Ansätze angewendet werden soll.

24 6 Fazit

25

Literaturverzeichnis

[CHL10] CALADO, Pável ; HERSCHEL, Melanie ; LEITÃO, Luís: An overview of XML

duplicate detection algorithms. In: Soft Computing in XML Data Management.Springer, 2010, S. 193–224

[LCH13] LEITAO, Luis ; CALADO, Pavel ; HERSCHEL, Melanie: Efficient and effective

duplicate detection in hierarchical data. In: Knowledge and Data Engineering,IEEE Transactions on 25 (2013), Nr. 5, S. 1028–1041

[WN05] WEIS, Melanie ; NAUMANN, Felix: DogmatiX tracks down duplicates in XML.

In: Proceedings of the 2005 ACM SIGMOD international conference on Managementof data ACM, 2005, S. 431–442