1

6.4 Verwaltung semistrukturierter Daten6.4 Verwaltung semistrukturierter Daten

- was ist das?Datenverwaltung für XML-Dokumente

- Daten in XML-Gewand- eigentlich XML-Dokumente- Abbildung auf relationale und objektrelationale DBS- Indexierung

- Anfragesprachen: XML Query- RDF-Datenbanken: erste Versuche

6.2

IndexierungIndexierung

Performance matters !

Naive Lösung zur Auswertung von existsNode etc: Parsen des Dokuments, Baum traversieren CLOB mit invertierten Listen (wie oben: z.B.

Intermedia)

Grundsätzliches Problem: Indexierung Semistrukturierter Daten Warum eigentlich schwierig??

Wertindex / Textindex "Finde alle Objekte, die über einen Pfad erreichbar

sind" : Pfadindex

6.3

IndexierungIndexierung

Dataguides* Idee:

- alle Pfade des Datengraphen merken- Index, wenn die erreichbaren Objekte gespeichert werden

Lore-System (Stanford '97)Abiteboul et al.: Indexing semistructured data, Tech. Rep, Stanford Univ., ftp://db.stanford.edu/pub/papers/semiindexing98.ps.

* Datenverzeichnis (keine Standardübersetzung)

6.4

Dataguide (2) Dataguide (2)

Definition

Gegeben eine semistrukturierte DB (typisch hierarchisch, auch für Graph-DB definiert)

Ein Datenverzeichnis (Dataguide) für DB ist ein Graph G mit:

Jeder Pfad in DB kommt in G vor (Bezeichner-Pfad, nicht Daten!)

Jeder Pfad in G kommt in DB vor Pfade in G sind eindeutig

(aber nicht in DB!)

6.5

Dataguides (3) Dataguides (3)

Problem: mehr als ein korrektes Datenverzeichnis für eine DB

6.6

Dataguides (4) Dataguides (4)

1 III

a bc

{1} {I,II}

{c} {a,b}

{x}

{x} {z,z'}

{z} {z'}

{I,II}{1}

{a,b,c}

{x,z,z'}

"Strong Dataguide": äquivalente Pfade in Guide äquivalent in DB

Nicht stark (strong)

6.7

Dataguides (5)Dataguides (5)

Algorithmus zur "Indexerstellung": Dataguide G:

Knoten (G) = { {wurzel}}

Kanten = while Veränderung do s = nonDetSelect (Knotenmenge (G))

a = Select (Labels)

Knoten (G) =+ {s'={y|x in s, es existiert (x->y, label a) in Kantenmenge(DB)} Kanten (G) =+ (x->y, label a)

6.8

Dataguides (6)Dataguides (6)

b

1

2 3 45 6

13121110987

xx

a

x

x

x

a aa

a

bc d

1

2,3,4,5,6

7,8,10,12,13 7,13

9 11

x

ab

d

c

DB

Dataguide G

Kann offenbar groß werdenWenn DB Baum: Größe von G <= Größe DB

Beachte: Konstruktion eines deterministischen aus nichtdetermini-stischem Automaten!

6.9

Indexierung Indexierung

Bsp: Lore-System (Stanford '97)Abiteboul et al.: Indexing semistructured data, Tech. Rep, Stanford Univ., ftp://db.stanford.edu/pub/papers/semiindexing98.ps.

Ein hierarchisches Datenbänken...

... Und ein "DataGuide" (Widom et al.: "DataGuides: Enabling Query.....", Proc VLDB 1997)

- enthält jeden möglichen Pfad der hierarchischen DB

- "gibt es einen bestimmten Pad in der DB"- wie heißen die Nachfolger des aktuellen Knotens

- Erweiterung zu Index durch Menge der erreichbaren Objekte

... und die zughörigen Pfade

6.10

Systeme: TaminoSysteme: Tamino

Tamino (SoftwareAG)

"Native data store"

6.11

... Tamino... Tamino

Beispiel für Integration mit tabellarischen Daten

Anfrage: ...?_xql=hospital/patient[p-surname="Jones"]/doctor

Sprache: X-Query