Transcript
Page 1: Catalog Integration Made Easy P.J. Marrón, G. Lausen und M. Weber Universität Freiburg

Catalog Integration Made Easy

P.J. Marrón, G. Lausen und M. Weber

Universität Freiburg

Page 2: Catalog Integration Made Easy P.J. Marrón, G. Lausen und M. Weber Universität Freiburg

Integration elektronischer Kataloge

eCatalogs sind die Grundlage des eBusiness.

Gewünscht sind integrierte Kataloge.

… diese funktionieren aber derzeit noch nicht zufriedenstellend:

Physische Integration hat Nachteile,

Logische Integration ebenso.

Schön wäre eine Integration (fast) ohne Aufwand.

das genau kann eine adaptive Auswertung leisten.

Page 3: Catalog Integration Made Easy P.J. Marrón, G. Lausen und M. Weber Universität Freiburg

lokaler Katalog globaler Katalog

products

jammer

name pricecompany

department

price

mobile

product

jammer

personel

name

computing…

company

Anfrage: /department/mobile//jammer/price ?

Page 4: Catalog Integration Made Easy P.J. Marrón, G. Lausen und M. Weber Universität Freiburg

Übersicht

I. Adaptive Auswertung von XPath

i. XPath

ii. XPath Subanfrage-Transformationen

iii. Bewertung von TransformationenII. Integration elektronischer Katalog

i. Architektur

ii. ExperimenteIII. Zusammenfassung

Page 5: Catalog Integration Made Easy P.J. Marrón, G. Lausen und M. Weber Universität Freiburg

Für das Resultat res(Q) der Query Q gilt:

res(Q) = Ln(Cn) = Cn+1.

Der Ausgabe-Kontext einer Subquery ist induktiv definiert zu:

C1 = root,

Ci+1 = Li(Ci), 1 <= i <= n.

Ein Location-Step hat die Form:axis::nodetest[predicate-expression]

Jeder Location-Step Li definiert eine XPath-Subquery qi der Form:

qi = (Ci, Li, Ci+1 ),

wobei Ci der Input-Kontext und Ci+1 der Ausgabe-Kontext.

(i) XPath

Eine XPath-Query Q ist ein Location-Path der Form:L1/L2/.../Ln,

wobei jedes Li eine Funktion geschrieben als Location-Step.

Page 6: Catalog Integration Made Easy P.J. Marrón, G. Lausen und M. Weber Universität Freiburg

A

B

C

A

C

A

C

A

D

B

C B

angenommene Dokumentenstruktur:

(ii) XPath Subanfrage-Transformation

tatsächliche Struktur:

"eliminate" "generalize"

"eliminate"

"generalizeand eliminate"

/A/C /A//B/C

/A/C

/A//B

Anfrage: /A/B/C

Transformation Transformation

Transformation

Page 7: Catalog Integration Made Easy P.J. Marrón, G. Lausen und M. Weber Universität Freiburg

No transformation (n): verarbeite Subanfrage unverändert,

Subquery generalization (g): ändern der Achse:

child descendent

parent ancestor

Subquery elimination (e): übergehe die Subanfrage.

(ii) Subanfrage Transformation:

Page 8: Catalog Integration Made Easy P.J. Marrón, G. Lausen und M. Weber Universität Freiburg

(iii) Bewertung von Transformationen

Sei qi = (Ci, Li, Ci+1 ).

Anwendung der 3 Transformationsregeln "keine Transformation", "Generalisierung", und "Eliminierung" ergibt 3 Versionen von qi mit den entsprechenden Ausgabe-Kontexten NCi+1, GCi+1, ECi+1.

Somit:

Ci+1 = NCi+1 U GCi+1 U ECi+1.

Bewertung der Antworten in Ci+1 mittels einer Fitness-Funktion in Abhängigkeit der angewandten Transformationsregel und der bereits berechneten Bewertung des Eingabe-Kontextes Ci.

Page 9: Catalog Integration Made Easy P.J. Marrón, G. Lausen und M. Weber Universität Freiburg

Verwendete Fitness-Funktion

Jeder Knoten n erhält einen Fitnesswert vn.

Sei Ci der aktuelle Eingabe-Kontext. Sei n є Ci und Ci+1= NCi+1 U GCi+1 U ECi+1.Sei m є Ci+1.

vm ist das Maximum von:

wenn m є NCi+1 , dann vm = b2 + vn.

wenn m є GCi+1 , dann vm = b + vn.

wenn m є ECi+1, dann vm = 1 + vn.

Und b = 10.

Page 10: Catalog Integration Made Easy P.J. Marrón, G. Lausen und M. Weber Universität Freiburg

Rechtfertigung der Fitness-Funktion

Wir müssen Worte aus {n, g, e}* bewerten.

Intuitiv sollte „n“ >> „g“, „n“ >> e“ sein. Jedoch warum „g“ >> „e“?

Formal können wir auf den Worten eine gewünschte Ordnung definieren und die Fitness Funktion entsprechend definieren (sofern unsere Ordnung konsistent mit „n“ >> „g“, „n“ >> e“ ist).

Page 11: Catalog Integration Made Easy P.J. Marrón, G. Lausen und M. Weber Universität Freiburg

Beispiel einer Ordnung:

eee < perm{g,e,e} < perm{e,g,g} < ggg < perm{e,e,n} < perm{e,n,g} < perm{g,g,n} < perm{e,n,n} < perm{n,n,g} < nnn

Seien e, g, n die entsprechenden Fitnessbewertungen.

Dann können sie berechnet werden wie folgt:

3e < 2e+g; n > g

2e+g < e+2g; g > e

… n-3g+2e > 0

2n+g<3n

Allgemein:

n > g, g > e, n – qlg + (ql - 1) e > 0, wobei ql Länge der Anfrage.

n=5, g=2, e=1

Page 12: Catalog Integration Made Easy P.J. Marrón, G. Lausen und M. Weber Universität Freiburg

II. Integration elektronischer Kataloge

global catalog Schema

G

local catalogL2

local catalogL1

local catalogL3

Q(G)

Q(G)

Q(G)

Q(G)

R(L3)

R(L1,L2,L3)

R(L1)

R(L2)

Page 13: Catalog Integration Made Easy P.J. Marrón, G. Lausen und M. Weber Universität Freiburg

Nodes Depth Outdeg

Global 129 4 16

Alternate 299 5 18

Reichelt 89 5 9

K & M 136 4 22

Artificial 27 3 6

Alt. Rei. K&M Art.

Global 2.8 0.3 4.8 1.8

Level 2.7 0.3 2.6 1.8

Query 2.4 0.1 3.1 1.8

Node 2.3 0.1 3.4 1.0

Alt. Rei. K&M Art.

Alt. - 1.1 2.3 0.9

Rei. 4.8 - 2.4 0.8

K&M 1.6 0.0 - 0.0

Art. 0.0 0.0 6.0 -

Anfragen an den globalen Katalog Anfragen an einen lokalen Katalog

Fehlerraten (in %) bei

Kataloge:

Page 14: Catalog Integration Made Easy P.J. Marrón, G. Lausen und M. Weber Universität Freiburg

III. Zusammenfassung

XPath ist die derzeit am intensivsten studierte Anfragesprache für XML.

Eine adaptive Auswertung von XPath ist praktisch gut motivierbar.

Qualität der adaptiver Auswertung empirisch belegt.

Verschiedene Möglichkeiten zur Verbesserungen des Verfahrens definiert und implementiert.

Adaptive Auswertungstechnik verspricht eine effiziente und skalierbare Integration elektronischer Kataloge.


Recommended