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.