VL Fusion 2007 - Hasso Plattner Institute · 2014-07-29 · 7 Andreas Zwickel 12.3.60 5 Petra Weger 21.3.76 p_id vorname nachname geboren Employees e Anderes Schema: m ∪ e nicht

InformationsintegrationDatenfusion: Union und Co.

12.7.2006

Jens Bleiholder

„When you use information from one source, it‘s plagiarism; when you use information from many sources, it‘s information fusion.“

[Belur V. Dasarathy]

12.7.2007

2

Rückblick

„Semantische Heterogenität ist ein überladener Begriff ohne klare Definition. Er bezeichnet die Unterschiede in Bedeutung, Interpretation und Art der Nutzung.“

[Öszu, Valduriez 91]

Namenskonflikte

Identität

Datenkonflikte

12.7.2007

3

Semantische Heterogenität

■ Gleiches Objekt mehrfach beobachtet■ Manuelle Erfassung der Daten■ Objekt ändert Eigenschaften von Zeit zu Zeit■ Keine global konsistente ID

□ ISBN, SSN, etc.

081508150815

t

0875✍08150815

0815 4711

Quelle A Quelle B

12.7.2007

4

Typische Anwendungen

■ Personen- und Adressdaten□ Volkszählungen□ Werbeaktionen□ Kundenpflege

■ Bibliographische Daten□ Zentrale Register

■ Waren/Katalogdaten□ Einkauf bei mehreren Shops

■ Webseiten□ Metasuchmaschinen

■ Molekularbiologische Daten

12.7.2007

5

Überblick

Schema Matching

Duplikaterkennung

Datenfusion

Visualisierung/Export

Anwendung

Schritt 1:

Schritt 2:

Schritt 3:

Schritt 4:

DatenquellenNamenskonflikte(schematische Konflikte)

Identitätsproblem

Datenkonflikte

12.7.2007

6

Schema Matching

Findet semantisch gleiche Attribute in Relationen■ Zwei Attribute, die gleiche Bedeutung tragen■ Attributnamen und -werte dürfen sich unterscheiden

Fantasy

Anim.

Sci-Fi

⊥

Crime

Genre

Wachowski1999The Matrix

Adamson2001Shrek

Crowe2001Vanilla Sky

Petersen2004Troy

Ritchie2000Snatch

DirectorYearTitle

Fantasy161999Matrix

Comedy162000Vannile Sky

Sci-FiR2001Vannila Ski

HistoryR2004Troja

CrimeR1999Snatch

GenreRatingJahrTitel

12.7.2007

7

Schema Matching

Formales Problem■ Zwei Tabellen, mit unterschiedlichen Attributen■ Erzeuge eine Abbildung, die jedem Attribut einer Tabelle die semantisch

gleichen der anderen Tabellen zuordnet

Problemerweiterungen■ Mehrere Tabellen■ 1:m und n:m Beziehungen■ XML Dokument, also Nesting

12.7.2007

8

Objektidentifikation

Findet Duplikate in Relationen■ Zwei Tupel, die das gleiche real-world Objekt repräsentieren■ Attributwerte dürfen sich unterscheiden

Fantasy

Anim.

Sci-Fi

⊥

Crime

Genre

5

4

3

2

1

ID

Wachowski1999The Matrix

Adamson2001Shrek

Crowe2001Vanilla Sky

Petersen2004Troy

Ritchie2000Snatch

DirectorYearTitle

5

3

3

2

1

ID

Fantasy161999Matrix

Comedy162000Vannile Sky

Sci-FiR2001Vannila Ski

HistoryR2004Troja

CrimeR1999Snatch

GenreRatingJahrTitel

12.7.2007

9

Objektidentifikation

Formales Problem■ Eine Tabelle (der Größe N), potentiell mit Duplikaten■ Erzeuge für jedes Tupel eine ID, so dass Duplikate gleiche ID‘s erhalten

Problemerweiterungen■ Zwei Tabellen mit unterschiedlichem Schema■ Ein XML Dokument mit Duplikaten

12.7.2007

10

Datenkonflikte

Zwei Duplikate haben unterschiedliche Attributwerte für semantisch gleiches Attribut.

21

DCBAID

1

1ECBAID

unique, check, key

(inter-source)

(intra-source)

12.7.2007

11

Datenkonflikte – Beispiele

amazon.deamazon.de

bol.debol.de

IDID

5.99 €Moby DickHerman Melville0766607194

3.98 €H. Melville0766607194 ⊥

12.7.2007

12

Datenkonflikte – Entstehung

■ Keine Integritätsbedingungen / Konsistenz-Checks■ Redundante Schemata■ Vorhandensein von Duplikaten■ Nicht korrekte Einträge

□ Tippfehler, Übertragungsfehler□ Falsche Rechenergebnisse

■ Obsolete Einträge□ Verschiedene Aktualisierungszeitpunkte

– ausreichende Aktualität einer Quelle– verzögerte Aktualisierung

□ Vergessene Aktualisierung

Innerhalb eines Informationssystems

12.7.2007

13


■ Unterschiedliche Datentypen (mit/ohne Codierung)

□ 1,2,...,5 bzw. "sehr gut", "gut", ..., mangelhaft"

■ Gleicher Datentyp

□ Schreibvarianten– Kantstr. / Kantstrasse / Kant Str. / Kant Strasse– Kolmogorov / Kolmogoroff / Kolmogorow

□ Typische Verwechslungen (OCR)– U<->V, 0<->o, 1<->l, usw.


12.7.2007

14

Datenkonflikte – Behebung

■ Referenztabellen für exakte Wertabbildung□ Z.B. Städte, Länder, Produktnamen, Codes...

■ Ähnlichkeitsmaße□ bei Tippfehlern□ bei Sprachvarianten (Meier, Mayer,...)

■ Standardisieren und transformieren■ Nutzung von Hintergrundwissen (Metadaten)

□ Konventionen (landestypische Schreibweisen)□ Ontologien zur Behandlung von Zusammenhängen□ Thesauri, Wörterbücher zur Behandlung von Homonymen,

Synonymen, ...


12.7.2007

15


■ Lokal konsistent aber global inkonsistent

■ Duplikate

■ Unterschiedliche Datentypen

■ Lokale Schreibweisen/Konventionen

Integration von Informationssystemen

12.7.2007

16

Datenkonflikte – Behebung

■ Präferenzordnung über Datenquellen□ Aktualität□ Trust (Vertrauen)□ Öffnungszeiten □ usw.

■ Informationsqualität■ Konfliktlösungsfunktionen

Integration von Informationssystemen

12.7.2007

17

Datenkonflikte – Implementierung

Prozedural

■ Programm

■ Im DB Kern

Deklarativ

■ Anfragesprache

Schnell Gut in materialisierten ISSchlecht wiederverwendbar

Funktioniert gut in föderierten ISWiederverwendbarLangsamer

12.7.2007

18

Relationale Objektintegration

Union (Vereinigung), z.B.[GUW02]

Eliminierung exakter Duplikate

Minimum Union, [GL94]

Eliminierung subsumierter Tupel

Jedoch

Duplikatintegration

Konfliktlösung

Auch: Join, Merge, Group, …

12.7.2007

19

Relationale Algebra – Vereinigung

34MeierStefanie2

32MüllerPeter1

alternachnamevornamep_id

Mitarbeiter m

44ZwickelAndreas7

28WegerPetra5


Employees e

44ZwickelAndreas7

28WegerPetra5

34MeierStefanie2

32MüllerPeter1


m ∪ e

Frage: Wie sieht m ∪ e aus?

12.7.2007

20

Union zur Informationsintegration?

Was bedeutet UNION compatible?

Gleiche Spaltenzahl Gleiche Datentypen

Verschiedene Schemata?Null-Werte?

Datenkonflikte?

12.7.2007

21


34MeierStefanie2

32MüllerPeter1


Mitarbeiter m

12.3.60ZwickelAndreas7

21.3.76WegerPetra5

geborennachnamevornamep_id

Employees e

Anderes Schema:

m ∪ e nicht definiert!

Problemlösung:

SchemaSQL

Schema Mapping

12.7.2007

22


34ZwickelAndreas7

28WegerPetra5


Mitarbeiter m

⊥ZwickelAndreas7

28WegerPetra5


Employees e

Null-Werte

⊥ZwickelAndreas7

28WegerPetra5

34ZwickelAndreas7


m ∪ e

„ ⊥“ vs. „34“ ist auch ein Konflikt!

12.7.2007

23


34ZwickelAndreas7

32MüllerPeter1


Mitarbeiter m

44ZwickelAndreas7

28WegerPetra5


Employees e44ZwickelAndreas7

28WegerPetra5

34ZwickelAndreas7

32MüllerPeter1


m ∪ e

„44“ vs. „34“ ist erst recht ein Konflikt!

12.7.2007

24

Konfliktbehebung mit Union?

a, ba, -

=> a, ba, -

a, ba, b

=> a, b

a, ba, c

=> a, ba, c

a, -, da, c, -

=> a, -, da, c, -

Quelle 1 →Quelle 2 →

ExakteDuplikate!

12.7.2007

25

Konfliktbehebung mit Union?

Ungeeignet

■ Es werden nur „echte“ Duplikate entfernt.

■ In SQL nur mit DISTINCT (Aufwand!)

Außerdem

■ Es können leicht strukturelle Konflikte auftreten:

□ Primärschlüssel

■ Es muss Schemagleichheit herrschen

12.7.2007

26

Minimum Union

Seien R1 und R2 Relationen mit Schemata S1 bzw. S2.

Outer Union füllt R1 und R2

zunächst mit NULL-Werten auf, so dass beide dem Schema S1∪S2 entsprechen.

Dann wird die Vereinigung der beiden aufgefüllten Relationen gebildet.

Beispiel aus [Cod79]

21Q

12P

21P

CBA

R

V3

U2

DB

S

V⊥3⊥

U⊥2⊥

2

1

2

C

⊥1Q

⊥2P

⊥1P

DBA

Outer Union, [Cod79]

Frage: Wie sieht aus?

12.7.2007

27

Minimum Union

Ein Tupel t1 subsumiert ein Tupel t2, wenn

- es über die gleichen Attribute definiert ist,

- t2 hat mehr NULL Werte als t1,

- t1 = t2 für alle nicht-NULL Werte von t2.

Schreibweise:R↓ ergibt die Tupel aus R, die nicht subsumiert sind.

2Meyer⊥2

2⊥Wiebke2

42⊥Peter1

32⊥Peter1

⊥⊥Peter1

⊥MüllerPeter1

32MüllerPeter1


R

42⊥Peter1

2⊥Wiebke2

2Meyer⊥2

32MüllerPeter1


R↓

Frage: Wieviele Tupel hat R↓?

Subsumption, [Ull89]

12.7.2007

28

Minimum Union – NULL-Werte

Semantik der NULL? [GUW02]

■ Wert unbekannt ("unknown")□ Es gibt einen Wert, ich kenne ihn aber nicht□ Bsp.: Unbekannter Geburtstag

■ Wert nicht anwendbar ("inapplicable")□ Es gibt keinen Wert, der hier Sinn macht□ Bsp.: Ehemann/-frau für Ledige

■ Wert zurückbehalten ("withheld")□ Wir dürfen den Wert nicht erfahren□ Bsp.: Geheime Telefonnummer

12.7.2007

29

Minimum Union – NULL-Werte

C.J. Date:- "Into the Unknown"- "Much Ado About Nothing"- "NOT Is Not Not!"- "Oh No Not Nulls Again"-…

"Value does not exist"

"Value undefined"

"Value not supplied"

"Total ignorance" NULL

„Distinguished" NULL

Im weiteren: "Unknown"

12.7.2007

30

Minimum Union – Beispiel

⊥

55

32

alter

MeyerWiebke3

SchmidtFranz2

MüllerPeter1

nachnamevornamep_id

Kunde K

56

⊥

32

alter

⊥3

Schmidt2

Müller1

nachnamep_id

Customer C

Minimum Union, [GL94]

56⊥⊥3

⊥

55

32

alter

MeyerWiebke3

SchmidtFranz2

MüllerPeter1

nachnamevornamep_id

56⊥⊥3

⊥Schmidt⊥2

32Müller⊥1

⊥

55

32

alter

MeyerWiebke3

SchmidtFranz2

MüllerPeter1

nachnamevornamep_id

12.7.2007

31

Konfliktbehebung mit Minimum Union?

a, ba, -

=> a, b

a, ba, b

=> a, b

a, ba, c

=> a, ba, c

a, -, da, c, -

=> a, -, da, c, -


Nicht in Standard-DBMS implementiert!

Subsumption!

12.7.2007

32

Und was ist mit Join?

28LehmannKlaus4

⊥

55

32

alter

MeyerWiebke3

SchmidtFranz2

MüllerPeter1

nachnamevornamep_id

Kunde K

47Weger5

56

⊥

32

alter

Meier3

Schmidt2

⊥1

nachnamep_id

Customer C

⊥

55

32

K.alter

Wiebke

Franz

Peter

K.vorname

Meier

Schmidt

⊥

C.nachname

56

⊥

32

C.alter

Meyer3

Schmidt2

Müller1

K.nachnamep_id

K ⋈p_id C

Frage: Ist Join zur Konfliktbehebung geeignet?

12.7.2007

33

Merge und Prioritized Merge

■ Vermischt Join und Union zu einem Operator

■ COALESCE beseitigt NULLs

■ Priorisierung möglich (⊳)

■ Lässt sich mit Hilfe von SQL ausdrücken

( SELECT K.p_id, K.vorname, Coalesce(K.nachname, C.nachname), Coalesce(K.alter, C.alter)

FROM K LEFT OUTER JOIN C ON K.p_id = C.p_id )

UNION

( SELECT C.p_id, K.vorname, Coalesce(C.nachname, K.nachname), Coalesce(C.alter, K.alter)

FROM K RIGHT OUTER JOIN C ON K.p_id = C.p_id )

Merge (⊠), [GPZ01]

12.7.2007

34

Merge – Beispiel

28LehmannKlaus4

⊥

55

32

alter

MeyerWiebke3

SchmidtFranz2

MüllerPeter1

nachnamevornamep_id

Kunde K

47Weger5

56

⊥

32

alter

Meier3

Schmidt2

⊥1

nachnamep_id

Customer C

47Weger⊥5

28LehmannKlaus4

56MeyerWiebke3

56

55

32

alter

Wiebke

Franz

Peter

vorname

Meier3

Schmidt2

Müller1

nachnamep_id

C ⊠ KFragen: Wiesieht das Schema aus? Wie das Ergebnis?

12.7.2007

35

Konfliktbehebung mit Merge?

a, ba, -

=> a, b

a, ba, b

=> a, b

a, ba, c

=> a, ba, c

a, -, da, c, -

=> a, c, d


KeineSubsumption!

12.7.2007

36

Und was gibt es sonst noch?

Match Join [YaÖz99]

■ Komplexer Operator

ConQuer [FuFM05]

■ „Consistent Query Answering“

■ Rewriting einer SQL Anfrage

Burdick et. al. [BDJR05]

■ Uncertainty in Data Warehouses

■ „Possible Worlds“

Probabilistische Modelle [Mich89]

■ Erweitern das Schema um Wahrscheinlichkeiten

12.7.2007

37

Was sollte Duplikatintegration können?

a, ba, -

=> a, b

a, ba, b

=> a, b

a, ba, c

=> a, cr(b,c)

a, -, da, c, -

=> a, c, d


Konfliktbehandlung

12.7.2007

38

Konfliktbehandlung

Lösungsidee(Strategie)

Ausführung(Funktion)

Benutzer

System

12.7.2007

39

Strategien, um Konflikte zu…

Pass it on

Take the informationNo Gossiping

Trust your friends

Cry with the wolvesRoll the dice

Meet in the middle

Nothing is older thanthe news from yesterday

…ignorieren

…vermeiden

…lösen

12.7.2007

40

Konfliktlösungsfunktionen

….….

Benutzt eine TaxonomieMostAbstract, MostSpecific

Nimmt aktuellsten WertMostRecent

Gruppiert, fügt zusammenGroup, Concat

Nimmt ersten nicht-null WertCoalesce

QuellenauswahlChoose(source)

Wahl abhängig von val in colChooseDepending(col, val)

MehrheitsentscheidVote

Nimmt längsten/kürzesten WertLongest, Shortest

Nimmt ersten/letzten Wert, reihenfolgeabhängigFirst, Last

ZufallswahlRandom

Standard AggregationsfunktionenMin, Max, Sum,

Count, Avg, StdDev

12.7.2007

41

Ausführung von Konfliktlösung

Union, Joinund Co.

Gruppierung(nach ID)

Mit SQL Bordmitteln?

12.7.2007

42

Gruppierung – Beispiel

21.1.95Martina

2006.6.99Jochen

25.4.02Martina

113.3.01Franz

1212.7.03Peter

3023.4.02Peter

2010.11.03Peter

wertdatumname

Bestellungen b

SELECT name, SUM(wert)

FROM BestellungenGROUP BY name

200Jochen

4Martina

11Franz

62Peter

wertname

12.7.2007

43

Gruppierung und Aggregation

■ Gruppierung weist jedem Attribut zu:

□ Gruppierung oder

□ Aggregation

■ Tupel werden gruppiert nach gleichen Gruppierungswerten, alle anderen Attribute werden innerhalb der Gruppen aggregiert.

■ NULL-Werte bilden eigene Gruppe

SELECT name, SUM(wert)

FROM BestellungenGROUP BY name

12.7.2007

44

Gruppierung zur Integration

■ Outer-Union auf alle Quellen

■ Mit SQL GROUP BY umschließen

□ Gruppierung nach ID Attribut

□ Aggregat-Funktionen als Konfliktlösungsfunktion für alle anderen Attribute.

12.7.2007

45


SELECT p_id, RESOLVE(vorname), RESOLVE(nachname), RESOLVE(alter) FROM K ] CGROUP BY p_id

55MeyerWiebke3

55SchmidtFranz2

32MüllerPeter1


56Meier⊥3

⊥Schmidt⊥2

32Müller⊥1

55

55

32

alter

MeyerWiebke3

SchmidtFranz2

MüllerPeter1

nachnamevornamep_id

12.7.2007

46


56Meier⊥3

⊥Schmidt⊥2

32Müller⊥1

55

55

32

alter

MeyerWiebke3

SchmidtFranz2

MüllerPeter1

nachnamevornamep_id

SELECT p_id, MAXLEN(vorname), CHOOSE(nachname,C), MAX(alter) FROM K ] CGROUP BY p_id

56MeierWiebke3

55SchmidtFranz2

32MüllerPeter1


LängsterString

C ist bevorzugteQuelle

größterWert

12.7.2007

47

Gruppierung – Beispiel

SELECT books.isbn,MAXLEN(books.title),MIN(books.price)

FROM (SELECT * FROM books1

UNIONSELECT * FROM books2

)AS books

GROUP BY books.isbn

books1 books2

∪

GROUP+

aggregates

12.7.2007

48

Gruppierung – Vor-/Nachteile

Vorteile■ Effizient

□ Implementierung durch Sortierung■ Behandelt Duplikate innerhalb einer Quelle und zwischen Quellen gleich.■ Simpel / kurz

Nachteile■ Beschränkt auf eingebaute Standard Aggregat-Funktionen:

□ MAX, MIN, AVG, VAR, STDDEV, SUM, COUNT■ Gruppierung nur nach Gleichheit

□ ID Attribut ist notwendig■ Outer Union nicht immer implementiert.

12.7.2007

49

Gruppierung – Vor-/Nachteile

Nachteile genauer:■ Standard Aggregate

□ MAX, MIN, AVG, VAR, STDDEV, SUM, COUNT□ Erweiterung um „user-defined aggregates“

– Optimierung– Assoziativität und Kommutativität nicht sichergestellt.

□ Einzig Informix bot dies an. □ Außerdem zwei Forschungsprojekte

■ Standard Gruppierung□ Implizit ist Gleichheit gefordert.□ Besser wäre: GROUP BY similar(id,name,birthdate)□ Wird nirgends angeboten

– Effizienz ist schwer für den Optimierer abzuschätzen.– Transitivität kann nicht gewährleistet werden.

12.7.2007

50

Dies sollten Sie gelernt haben

Namenskonflikte

Identität

Datenkonflikte

Semantische Heterogenität

Lösungen

(Minimum) Union

Gruppierung/Aggregation

Join, Merge, …

SQL

UrsachenProbleme

12.7.2007

51

Masterarbeiten

■ GenFuse

□ Automatische Generierung von Fusionsanfragen

□ Nutzung historischer Daten

□ Nutzung von Präferenzen

■ DifFuse

□ Erfassung von Differenzen von Fusionen

□ Nutzererfahrungen

□ Maße

12.7.2007

52

Literatur

[GL94] Outerjoins as Disjunctions, Cesar A. Galindo-Legaria, SIGMOD 1994 conference

[Cod79] E. F. Codd: Extending the Database Relational Model to Capture More Meaning. TODS 4(4): 397-434 (1979)

[Ull89] Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989

[GUW02] Hector Garcia-Molina, Jeffrey D. Ullman and Jennifer Widom, Database Systems, Prentice Hall, 2002

[GPZ01] S. Greco, L. Pontieri, E. Zumpano, Integrating and Managing Conflicting Data, Springer, 2001

[YaÖz99] L. L. Yan, T. Özsu, Conflict tolerant queries in AURORA, CoopIS 1999 conference

[FuFM05] A. Fuxman, E. Fazli, R. Miller, Conquer: Efficient Management of inconsistent databases, SIGMOD 2005 conference

[BDJR05] D. Burdick, P. Deshpande, T. Jayram, R. Ramakrishnan, S. Vaithyanathan, OLAP OverUncertain and Imprecise Dat, VLDB 2005 conference

[Mich89] L. DeMichiel, Resolving Database Incompatibility: An Approach to Performing Relational Operations over Mismatched Domains, IEEE Trans. Knowl. Data Eng., 1989(1), p. 485-493

Vielen Dank fürs Zuhören!

■ Zusammenfassung:

□ Datenintegration

□ Relationale Datenfusion

□ Umsetzung

■ Thema Dienstag:

□ Hidden Web

Documents

VL Fusion 2007 - Hasso Plattner Institute · 2014-07-29 · 7 Andreas Zwickel 12.3.60 5 Petra Weger 21.3.76 p_id vorname nachname geboren Employees e Anderes Schema: m ∪ e nicht