Semantic Gossiping Christian Gebhardt Berlin, 13.07.07

Semantic Gossiping

Christian Gebhardt

Berlin, 13.07.07

13.07.2007 2

Übersicht

• Einführung

• Qualitätsmaße

• Gossiping Algorithmus

• Beispiel

• Diskussion

13.07.2007 3

Übersicht

• Einführung

• Qualitätsmaße

• Gossiping Algorithmus

• Beispiel

• Diskussion

13.07.2007Einführung 4

Overlay Netzwerke

13.07.2007Einführung 5

Peer Data Management System

• allgemein sind PDMS Netzwerk von Informationssystemen

• Bestandteile– Mappings– Peers

P1

P2

P4

P3

Mappings

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

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

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

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

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

13.07.2007Einführung 11

Zyklus

P1

P2

P4

P3

P4

Q

anrede->-

titel->anrede

-

anrede->bezeichnung

bezeichnung->titel

titel->titel

bezeichnung->titel

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

13.07.2007Qualitätsmaße 13

Übersicht

• Einführung

• Qualitätsmaße

• Gossiping Algorithmus

• Beispiel

• Diskussion

13.07.2007Qualitätsmaße 14

Qualitätsmaße

• Zyklen Mittel zur Bewertung

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

Übereinstimmung

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

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

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

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

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

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)

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

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)

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

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

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)

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σ

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)

13.07.2007Qualitätsmaße 28

Syntaktische Gleichheit

• Syntaktische Gleichheit (π)

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

W • FVπ

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┴

13.07.2007Qulitätsmaße 30

Semantische Übereinstimmung

• Unterscheidung zwischen – semantischer Übereinstimmung entlang eines

Kreises

und– semantischer Übereinstimmung beim

Betreten fremder Domäns

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

13.07.2007Qualitätsmaße 32

Semantische Übereinstimmung

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

Ak)

13.07.2007Gossiping Algorithmus 33

Übersicht

• Einführung

• Qualitätsmaße

• Gossiping Algorithmus

• Beispiel

• Diskussion

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

13.07.2007Gossiping Algorithmus 35

Gossiping Algorithmus

• Neue Query Message:

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

13.07.2007Gossiping Algorithmus 36

Gossiping Algorithmus

1. auf Zyklus überprüfen

2. Test ob Query schon empfangen wurde

3. Anfrage-Ergebnisse berechnen

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

13.07.2007 38

Übersicht

• Einführung

• Qualitätsmaße

• Gossiping Algorithmus

• Beispiel

• Diskussion

13.07.2007 39

Beispiel

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→ -

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 - +

13.07.2007 42

Übersicht

• Einführung

• Qualitätsmaße

• Gossiping Algorithmus

• Beispiel

• Diskussion

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