43
Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

Embed Size (px)

Citation preview

Page 1: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

Semantic Gossiping

Christian Gebhardt

Berlin, 13.07.07

Page 2: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007 2

Übersicht

• Einführung

• Qualitätsmaße

• Gossiping Algorithmus

• Beispiel

• Diskussion

Page 3: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007 3

Übersicht

• Einführung

• Qualitätsmaße

• Gossiping Algorithmus

• Beispiel

• Diskussion

Page 4: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Einführung 4

Overlay Netzwerke

Page 5: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Einführung 5

Peer Data Management System

• allgemein sind PDMS Netzwerk von Informationssystemen

• Bestandteile– Mappings– Peers

P1

P2

P4

P3

Mappings

Page 6: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Einführung 6

Peer Data Management System

Peers

P1

P3

P2

S2

S1

S3

Peer Schema

Lokale Datenquelle

Lokales Mapping

Aufgaben der Peers

•Anfragen stellen•Anfragen planen•Anfragen weiterleiten•Anfrageergebnisse empfangen, transformieren und zurückreichen

Peer Mapping

Page 7: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Einführung 7

Peer Data Management System

Mappings

•VORGESETZTER•persID•anrede

•CHEF

•MITARBEITER•telNr

•persFID•name

•chefID•anrede•raumNr•mitarbeiter

SELECT persID as chefIDanrede as anredenull as raumNrnull as mitarbeiter

FROM VORGESETZTER

UNION SELECT null as chefIDnull as anredenull as raumNrname as mitarbeiter

FROM MITARBEITER

Page 8: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Einführung 8

Peer Data Management System

Mappings

•VORGESETZTER•persID•anrede

•CHEF

•MITARBEITER•telNr

•persFID•name

•chefID•anrede•raumNr•mitarbeiter

SELECT persID as chefIDanrede as anredenull as raumNrname as mitarbeiter

FROM VORGESETZTER,MITARBEITERWHERE VORGESETZTER.persID = MITARBEITER.persFID

Page 9: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Einführung 9

Peer Data Management System

PDMS Sensornetzwerke

• Peers beinhalten Daten- quellen oder integrieren diese

• Einzelne Knoten bekommen ihre Daten aus Sensoreinheit

• Stabile Netzwerk Struktur

• Einzelne Knoten können aus- fallen

• Peers/Knoten können Daten auf Anfrage bereitstellen

• Es ist kein globales Wissen vorhanden

vs.

• Peers können genannte Aufgaben bearbeiten

• Knoten können nur teilweise dieser Aufgaben bearbeiten

Page 10: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Einführung 10

Semantic Gossiping• Allgemein:

– Anfrage vom Benutzer an verteilte Daten– Peers propagieren Anfrage an die Peers zu

denen es Schema-Mappings gibt– ist es auch möglich sie an Peers zu schicken

zu denen es keine Schema-Mappings gibt (durch Tansitivität )

– diese berechnen Resultate und /oderschicken sie weiter

– ergibt sich ein Zyklus zurück zum anfragenden Peer, kann dieser zur Beurteilung der Resultat benutzt werden

Page 11: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Einführung 11

Zyklus

P1

P2

P4

P3

P4

Q

anrede->-

titel->anrede

-

anrede->bezeichnung

bezeichnung->titel

titel->titel

bezeichnung->titel

Page 12: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Einführung 12

Einführung

• Entstehender Informationsverlust bei Anfrage– Fehlende Mappings zu relevanten Peers– Unvollständige Abbildung der Attribute– Herausfiltern von Tupeln

Qualitätsmaße für die Güte der Resultate erforderlich

Page 13: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 13

Übersicht

• Einführung

• Qualitätsmaße

• Gossiping Algorithmus

• Beispiel

• Diskussion

Page 14: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 14

Qualitätsmaße

• Zyklen Mittel zur Bewertung

– Messen der Qualität der Mappings– Messen des Grades semantischer

Übereinstimmung

Page 15: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 15

Qualitätsmaße

• Folgende Anforderungen an Peers zur Unterstützung der Messungen– nach Eingang einer Query entscheiden wohin

die Query weitergeleitet wird– nach Eingang von Resultaten analysieren der

Resultate und anpassen der eigenen Kriterien– und Erneuern der Sicht auf Semantisch

Übereinstimmung

Page 16: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 16

Qualitätsmaße

• Kriterien zur Bewertung der Übersetzungsqualität– wesentlich

• beziehen sich nur auf bearbeitete Anfrage und benötigte Übersetzung

– äußerlich• beziehen sich auf den Grad der Übereinstimmung

über einer Menge Peers und nach einer bestimmten Anzahl von Übersetzungen

Page 17: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 17

Qualitätsmaße

• Peer erhält zurückgegebene Anfragen und Daten– bei Nicht-Übereinstimmung

• einige der Mappings aus Zyklus sind falsch• auch eigenes Mapping

– bei Übereinstimmung• es ist nicht klar ob diese aus der Verbesserung

von Mapping Fehlern, die auf dem Weg passiert sind, resultiert

Page 18: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 18

Qualitätsmaße

• Man benötigt also:– Analyse welche Quelle die höchste Fehler-

Wahrscheinlichkeit besitzt– Analyse bis zu welchem Umfang man eigenen

Mappings trauen kann– Entscheidung wie man diese bei späterem

Routing benutzt

Page 19: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 19

Qualitätsmaße

• Bei Anwendung diese Kriterien auf die Attribute einer transformierten Query entsteht ein Feature Vector der die Ergebnisse der einzelnen Kriterien für jedes Attribut beinhaltet

Page 20: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 20

Qualitätsmaße

• Peer p hält seine Datenbank DBp mit Schema Sp in der relationalen Tabelle R

• Peer kann sein Datenbank befragen– Query q

– Ergebnisse q(DBp)

Page 21: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007 21

Qualitätsmaße

• seien p und p` benachbarte Peers

• Operator:– Tp→p` transformiert für Query qT die Daten

geordnet nach Schema Sp` in Daten, die nach

Schema Sp geordnet sind

Tp→p`(qp)(DBp`) = qp(qT(DBp`))

Page 22: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007 22

Qualitätsmaße

• Query qT hat die Eigenschaft:

qT(DBp`) = πa(μf(DBp`))

• mehrere Transformationen werden schritt- weise auf einzelne Query angewendet

Tn-1→n(…T1 →2(q)…) = T1→2,…,n-1→n(q)

Page 23: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007 23

Qualitätsmaße

• Query Message

query(id,q,p,TT)

mit id – Query identifier q – Query selbst p – Query Ursprung TT – Mapping Route

Page 24: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 24

Qualitätsmaße• Annahme:

q = πap(σp(as)(μfa(DB)))mit

• ap benutze Attribute der Projektion• as benutze Attribute der Selektion• fa Liste angewandter Mapping-Funktion

• Form der transformierte Anfrage

T(q)(DB`) = πap(σp(as)(μfa(πa(μf(DB`)))))

Page 25: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 25

Syntaktische Gleichheit

• nicht alle Attribute in as erhalten

• bestimmte Eigenschaften, die durch diese Attribute ausgedrückt wurden, können nicht mehr bewertet werden

• Feature Vector

FVσ(T1→,…,→n(q)) = (fvσA1,…, fvσ

Ak)

Page 26: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 26

Syntaktische Gleichheit

• sei W Vektor von Gewichten der Attribute

• Syntaktische Gleichheit (σ)

Sσ(q,(T1→,…,→n(q)) = W•FVσ

W • FVσ

Page 27: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 27

Syntaktische Gleichheit

• nicht alle Attribute in ap erhalten

• dadurch sind manche Ergebnisse fehlerhaft oder unvollständig

• Feature Vector (π)

FVπ (T1→,…,→n(q)) = (fvπA1,…, fvπ

Ak)

Page 28: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 28

Syntaktische Gleichheit

• Syntaktische Gleichheit (π)

Sπ (q,(T1→,…,→n(q)) = W•FVπ

W • FVπ

Page 29: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 29

Semantische Übereinstimmung

• Für eine gegebene Transformation T ist der sourceT(A) definiert als

sourceT(A) =

{A1,…,Ak}, falls ein F ℮ fa existiert mit A:=F(A1,…,Ak)

, sonst┴

Page 30: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qulitätsmaße 30

Semantische Übereinstimmung

• Unterscheidung zwischen – semantischer Übereinstimmung entlang eines

Kreises

und– semantischer Übereinstimmung beim

Betreten fremder Domäns

Page 31: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 31

Semantische Übereinstimmung

• entlang eines Zyklus

• Ausgangs Peer ist wieder erreicht

• dieses analysiert nun und stellt fest– Fall 1 sourceT (Ai) = {Ai}

– Fall 2 sourceT (Ai) = { }

– Fall 3 sourceT (Ai) = {Aj} wo i≠j

1→…→n

1→…→n

1→…→n

Page 32: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Qualitätsmaße 32

Semantische Übereinstimmung

FVC (Tk→j(q)) = (fvCA1,…, fvC

Ak)

Page 33: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Gossiping Algorithmus 33

Übersicht

• Einführung

• Qualitätsmaße

• Gossiping Algorithmus

• Beispiel

• Diskussion

Page 34: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Gossiping Algorithmus 34

Gossiping Algorithmus

• für die Definition des Algorithmus haben wir 4 Maße für die Berechnung der Verluste

• zusätzlich:– Vektor W von Gewichten der Attribute– sel entsprechende Selektivitäten

– Smin Wert der minimalen Gleichheit

Page 35: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Gossiping Algorithmus 35

Gossiping Algorithmus

• Neue Query Message:

query(id,q,p,TT,W,sel,Smin,FVσ,FVπ,FVC,FVH)

Page 36: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Gossiping Algorithmus 36

Gossiping Algorithmus

1. auf Zyklus überprüfen

2. Test ob Query schon empfangen wurde

3. Anfrage-Ergebnisse berechnen

Page 37: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Gossiping Algorithmus 37

Gossiping Algorithmus

5. Mapping auf Anfrage anwenden

6. Maße für Transformation anpassen

7. Feature Vektoren für Gleichheit testen

8. Weiterleiten der Query, falls alle Feature Vektoren 1

Page 38: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007 38

Übersicht

• Einführung

• Qualitätsmaße

• Gossiping Algorithmus

• Beispiel

• Diskussion

Page 39: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007 39

Beispiel

Page 40: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Beispiel 40

Beispiel

A

ED

F

G

B

C

titel→name

titel→name

titel→name

titel→description/name

name→titelname→titel

titel→description/name

name→description/name

Q

-

- -

titel→ -

name→name

titel→acronym

titel→titeltitel→titel -

titel→titel

titel→ -

titel→ -

Page 41: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007Beispiel 41

BeispielCycle TpA-pC fehlerbehaftet TpB-pD fehlerbehaftet

A,B,D,E,A + -

A,B,D,E,F,A + -

A,B,E,A + +

A,B,E,F,A + +

A,B,F,A + +

A,D,E,A - +

A,D,E,B,F,A - +

A,D,E,F,A - +

Page 42: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007 42

Übersicht

• Einführung

• Qualitätsmaße

• Gossiping Algorithmus

• Beispiel

• Diskussion

Page 43: Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

13.07.2007 43

Diskussion

• Kritik:– Beispiel umfasst nur ein Attribut was gemappt

wird– semantische Gleichheit bei Zyklen hängt nur

von den einzelnen Wahrscheinlichkeit für die Attribute ab und nicht von der Query