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.

lokaler Katalog globaler Katalog

products

jammer

name pricecompany

department

price

mobile

product

jammer

personel

name

computing…

company

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

Übersicht

I. Adaptive Auswertung von XPath

i. XPath

ii. XPath Subanfrage-Transformationen

iii. Bewertung von TransformationenII. Integration elektronischer Katalog

i. Architektur

ii. ExperimenteIII. Zusammenfassung

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.

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

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:

(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.

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.

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

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

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)

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:

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.