Interoperable Informationssysteme - 1 Klemens Böhm DataGuides und Indexstrukturen für semistrukturierte Daten

Interoperable Informationssysteme - 1Klemens Böhm

DataGuides und Indexstrukturen

für semistrukturierte Daten


Gliederung Fragen:

Wie speichert man semistrukturierte Daten, insbes. XML-Dokumente?

Wie evaluiert man Queries effizient?Nicht dasselbe

Gliederungspunkte: DataGuides und

k-Representative Objects,

PAT-Trees, Query Subsumption und Query Filtering

sowie File-basiertes Query Processing, Verwendung von RDBMSen, Verwendung objektorientierter Datenbank-Technologie.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Wiederholung: Querysprachen für semistrukturierte Daten

Mit OEM geht Querysprache einher. Diese Querysprache ähnelt OQL,

erlaubt insbesondere Pfadausdrücke. Beispiele:

select Restaurant.Entrée select Restaurant.Namewhere Restaurant.Entrée = “Burger”

Anfragemechanismen dieser Art sind natürlich auch sinnvoll für XML-Dokumente;Beispiele (zum Protokoll-Dokumenttyp): “Gib’ mir alle Empfehlungen von Roger Weber.” “Gib’ mir alle Beschlüsse, die vor der

Feststellung mit ID=ke (‘Unser Kredit ist erschöpft.’) gefällt wurden.”

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Evaluierung von Queries über semistrukturierten Daten

Problem: Effiziente Evaluierung

von Anfragen mit Pfadausdrücken, Inspektion aller Dokumente

i.a. nicht akzeptabel. Zusammenfassungen der Daten

und Indexstrukturen sind hilfreich für Queryoptimierung und Queryevaluierung.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Ziel 1 - Volltextindex vs. speziellere Indexstrukturen

Beispielquery: “Selektiere alle Empfehlungen von Weber.”

Volltextindex würde uns befähigen, alle Dokumente, die String ‘Weber’ enthalten, schnell zu holen.

Probleme, die Volltextindex nicht löst: Viele Dokumente können String ‘Weber’ in

anderem Zusammenhang enthalten. Wir wollen nur die Empfehlungen,

nicht die ganzen Dokumente. Feldweiser Index wäre besser.

Feld ‘Empfehlender’

Am besten: Index für Text unter jedem Pfad.select Restaurant.Name where Restaurant.Entrée = “Burger”

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Ziel 2 - Schemainformation für Queryoptimierung

Beispiel:select Restaurant.Namewhere Restaurant.Entrée = “Burger”

Query kann nur dann eine Lösung haben, wenn Pfad ‘Restaurant.Entrée’ in der Datenbank überhaupt vorkommt.

Es wäre hilfreich, vor Queryevaluierung schnell nachsehen zu können, ob Pfad in der Datenbank vorkommt.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


DataGuides DataGuides unterstützen sowohl

Indexierung von Text für einzelne Pfade als auch das Nachschauen von Pfaden.

Erst wird das Problem ‘Nachschauen von Pfaden’ angesprochen, dann das erste Problem.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


DataGuides - Gliederung Was sind DataGuides? n

Wie helfen sie bei der Evaluierung von Anfragen? (Problem 1)

Erweiterungen von DataGuides;Annotationen von DataGuides,

Annotationen und Query Evaluierung(Problem 2).

I.a. gibt es mehrere DataGuides für eine Datenbank, was sind die Unterschiede?

Schlussbemerkungen zu DataGuides

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Data Guides Data Guides:

konkrete Zusammenfassung des Datenbank-Inhalts(OEM spricht von ‘Datenbanken’, XML von ‘Dokumenten’. Da DataGuides auf OEM aufsetzen, verwenden wir diese Terminologie.)

Unterschied zwischen ‘DataGuide’ und ‘Schema’:DataGuide ist konform zur Datenbank, nicht umgekehrt.(Denkbar, dass man DataGuide zu einer Datenbank konstruiert, für die ein Schema existiert, und dass DataGuide und Schema nicht übereinstimmen.)

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Beispiel-Datenbank

2

1

3 4

5 6 78 9 10 11

BarRestaurant

Name

Entree Telefon

InhaberManager Name Entree Entree

Chili Burger 555-1234Klein Darbar Lamm Rind

Restaurant

Plus

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


DataGuides - Beispiel

13

12

19

14

15 16 17 18

Bar

Name

Entree TelefonInhaber

Restaurant

Manager

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


DataGuides Definition: Ein DataGuide einer OEM-

Datenbank s ist ein OEM Objekt d, so dass jeder label path in s

genau eine data path-Instanz in d hat, jeder label path von d ein label path von s

ist. DataGuide erlaubt offensichtlich

nachzusehen, welche Pfade in der Datenbank vorkommen.

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


DataGuides

Kurze, akkurate, und ‘geeignete’ Zusammen-fassung der Struktur einer Datenbank. Kürze: DataGuide beschreibt

jeden label path mit einer Instanz in der Datenbank genau einmal.

Akkuratheit: DataGuide beschreibt keine label paths, die nicht in der Datenbank vorkommen.

‘Geeignetheit’: DataGuide ist OEM Objekt( Speicherung und Zugriff auf DataGuides mit OEM-Mechanismen möglich.)

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Erzeugung von DataGuides

Äquivalent zu NEA -> DEA

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Query Processing mit DataGuides (1) Aus dem DataGuide kann man

für manche (Teil-)Queries ableiten, ob sie keine Lösung haben.

Beispiel: gpe = Guide.A%.B%

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM

A2A1

C B D


Annotationen der DataGuide-Knoten Beispiele für Annotationen:

Listen von Pointern auf Datenbank-Objekte, d.h. DataGuide ist Speicherstruktur der Form||Label Path --> {Objekt}||,

Häufigkeiten, Volltext-Index.

Annotationen der DataGuide-Knoten können hilfreich sein fürs Query Processing.

Nur Annotationen erklären; nicht, wie sie fürs Query Processing verwendet werden.

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Verwendung DataGuide für Query Processing (3)

DataGuide ist nur Zusammenfassung der Datenbank.Beispiele für Anfragen, die nicht allein mit Hilfe des DataGuides und dieser Art von Annotationen beantwortet werden können:•‘Selektiere alle Restaurants, die einen Inhaber haben.’•‘Selektiere alle Restaurants, in denen es sowohl das Entrée ‘Rind’ als auch das Entrée ‘Lamm’ gibt.’

2

1

3 4

5 6 78 9 10 11

BarRestaurant

Name

Telefon Name EntreeEntree

Chili Burger 555-1234Klein Darbar Lamm Rind

Restaurant

PlusInhaber

EntreeManager

13

12

19

14

15 16 17 18

Bar

Name

Entree TelefonInhaber

Restaurant

Manager

Annotation

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM

Erläutern, wie Anfrage unterstützt wird.


Query Processing mit DataGuides (2) Beispiel:

select DBS.Group_Member.Publication.Yearwhere DBS.Group_Member.Publication.Year < 1975

Effizientere Queryevaluierung: Liste von Pointern auf Datenbank-

Objekte.Wenn man Target Sets beim DataGuide explizit abspeichert: Man erspart sich Navigieren im Datenbestand.

Volltext-Index, Häufigkeitsinformation.

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


DataGuides - weiteres Beispiel

A B

2

1

4

BA

3

B

5

C

6

C

7

C

8

D

9

D

10

D

12

11

13

BA

14

C

15

C

16

D

17

D

18

19

20

C

21

D

Datenbank Zwei entsprechende DataGuidesHier nur sagen, dass es mehrere DataGuides geben kann.

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Minimale DataGuides Es existieren wohlbekannte Techniken

zur Minimierung von DataGuides, d.h. zur Erzeugung eines DataGuides mit minimaler Anzahl von Zuständen aus beliebigem DataGuide.

Nachteile minimaler DataGuides: Änderungen an der Datenbank

verursachen mehr Arbeit, Beispiel

Aussagen über Menge von Objekten in der Datenbank, die über einen label path erreichbar sind, sind weniger gut möglich.Solche Aussagen heissen im folgenden Annotationen. Welche Objekte sind ueber den Label Path ‘A.C.’ erreichbar?

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Strong DataGuides Motivation: Charakterisierung der

DataGuides, deren Annotationen stets eindeutig sind.

Intuition: Label paths mit dem gleichen (singleton) Target Set im DataGuide haben stets das gleiche Target Set in der Datenbank.Naechste Folie Illustration.

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Strong DataGuides - Illustration

2

1

4

BA

3

B

5

C

6

C

7

C

8

D

9

D

10

D

12

11

13

BA

14

C

15

C

16

D

17

D

18

20

C

21

D

Datenbank Entsprechende DataGuides

A B

19 Annotation von Objekt 20:weniger präziseAnnotations-möglichkeitenals im anderenDataGuide.

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Strong DataGuides - Definition OEM Objekte s und d, d ist DataGuide für s, Ts(l) - Target Set von l in s,

Td(l) - (singleton) Target Set von l in d,

Ls(l) = {m|Ts(m)=Ts(l)},d.h. Ls(l) ist die Menge aller label paths mit dem gleichen Target Set wie l,

Ld(l) = {m|Td(m)=Td(l)},d.h. Ld(l) ist die Menge aller label paths in d mit dem gleichen Target Set wie l.

d ist ein Strong DataGuide, wenn für alle label paths l von s: Ls(l)=Ld(l)

Am Beispiel erlaeutern - naechste Folie.

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Strong DataGuides - Illustration

1

4

BA

3

B

5

C

6

C

7

C

8

D

9

D

10

D

12

11

13

BA

14

C

15

C

16

D

17

D

18

20

C

21

D

Datenbank Entsprechende DataGuides

A B

19 l=A.C

Ls(l)={A.C}

Ld(l)={A.C, B.C}

1

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Aufbau eines Strong DataGuides// MakeDG: algorithm to build a strong DataGuide

// Input: o, the root oid of a source database

// Effect: dg is a strong DataGuide for o

targetHash: global empty hash table, to map source target sets to DataGuide objects

dg: global oid, initially empty

MakeDG(o) {

dg = NewObject()

targetHash.Insert({o}, dg)

RecursiveMake({o}, dg)

}

RecursiveMake(t1, d1) {

p = all children <label, oid> of all objects in t1

foreach (unique label l in p) {

t2 = set of oids paired with l in p

d2 = targetHash.Lookup(t2)

if (d2 != nil) {

add an edge from d1 to d2 with label l

} else {

d2 = NewObject()

targetHash.Insert(t2, d2)

add an edge from d1 to d2 with label l

RecursiveMake(t2, d2)

} } }

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Aufbau eines Strong DataGuides - Illustration

2

1

3

BB

4

C

5

C

dg = 6 Neues Objekt

targetHash = {({1}, 6)} Hash-Tabelle

Aufruf ‘RecursiveMake({1}, 6)’

p={(B,2), (B,3)} Menge der Kinder eines der Objekte

l=B, t2={2,3}, d2=NILd2=7, targetHash = {({1}, 6), ({2,3}, 7)}Aufruf ‘RecursiveMake({2,3}, 7)’

p={(C,4), (C,5)}l=C, t2={4,5}, d2=NILd2=8targetHash = {({1},6), ({2,3},7), ({4,5},8)}Aufruf ‘RecursiveMake ({4,5},8)’

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Einordnung DataGuides

Noch akkuratere Beschreibung der Datenbank grundsätzlich möglich, z.B. um festzulegen, welche Kombination von Labels von ausgehenden Kanten vorkommen, z.B.‘Inhaber’ oder ‘Manager’ (geht mit XML-DTDs).

Motivation

DataGuide

- Einleitung

- Struktur

- Query Proc.

- Strong DGs

- Einord.

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


DataGuides und Alternativen DataGuides: Relativ akkurate Beschreibung, k-Representative Objects (k-ROs)

und k-Indices/T-Indices: ungefähre Beschreibung, Idee: Man kann nur Pfade bis zu einer

bestimmten Länge nachschauen. Labels der Knoten der k-ROs

entsprechen Labels von Kanten in der Datenbank.

Im folgenden Bsp. ist jene Pfadlänge 2.(Beispiel ist aber zufällig richtig für längere Pfade.)

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


k-Representative Objects Ziel: ‘Weniger ausführliche’ Beschreibung

der Daten, die vorkommen dürfen. Beispiel:

2

1

3

aa

4

c

5

b

6

a

ab

b

1

a

cb

b

a cb

DataGuide:

$

b

a c

AnvisierteStruktur:

Labels an Knoten statt Kantenk=1$ - kuerzere Pfade - per Def. nur diedirekt von der Wurzel.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Verwendung von k-Representative Objects

Annotationen der Knoten sind wiederum möglich, Zustand, in den uns die Kante führt, als Annotation

der Knoten im k-RO.

2

1

3

aa

4

c

5

b

6

a

ab

b

$

b

a c

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Verwendung von k-Representative Objects

Ausführlicheres Objekt erlaubt genauere Annotationen (vergleichbar mit Strong DataGuides).

2

1

3

aa

4

c

5

b

6

a

ab

b

$

b

a ca

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


k-Representative Objects k-Representative Object (k-RO) enthält

die Pfade in der Datenbank bis zur Länge k+1.

k-RO enthält Obermenge der Label Paths in der Datenbank.Im Beispiel zufällig nicht zu sehen.

Anwendung: Gezielte Evaluierung von

Pfadausdrücken, Queryoptimierung.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


PAT-Tree - Gliederung Was sind PAT-Trees? n

Wie werden PAT-Trees aufgebaut? Was für Anfragen werden unterstützt,

und wie?

Motivation

DataGuide

Repres.Objects

PAT-Trees

- Struktur

- Aufbau

- Suche

-Sonstiges

Algebra

Mehrstufig-keit

STORED

HyperStorM


PAT-Tree Volltext-Indexstruktur, die auch für

Strukturanfragen hilfreich ist.(Erst wird Volltext-Unterstützung erklärt, dann Evaluierung von Strukturanfragen.)

Jeder Position im Text entspricht ein Pfad im Baum,d.h. jedes Blatt identifiziert eine Position im Text.

Kante entspricht i.d.R. einem Zeichen, kann aber auch für Zeichenfolge stehen.

Motivation

DataGuide

Repres.Objects

PAT-Trees

- Struktur

- Aufbau

- Suche

-Sonstiges

Algebra

Mehrstufig-keit

STORED

HyperStorM


PAT-Trees

2

1

2

3 3

7 5

4 8

5 1

4 2

6 3

01100100010111… Text

123456789… Position

Warum folgt (5) auf (3)?Knotennummern erklaeren

Motivation

DataGuide

Repres.Objects

PAT-Trees

- Struktur

- Aufbau

- Suche

-Sonstiges

Algebra

Mehrstufig-keit

STORED

HyperStorM


Aufbau des PAT-Trees Pfad im Baum wird durchlaufen, bis man

Blatt erreicht. Blatt wird ersetzt durch kleinen Teilbaum. U.U. muss eine Kante aufgespalten werden,

und man geht gar nicht bis zu einem Blatt.(Warum wird in diesem Fall nur eine Kante aufgespalten?)

Motivation

DataGuide

Repres.Objects

PAT-Trees

- Struktur

- Aufbau

- Suche

-Sonstiges

Algebra

Mehrstufig-keit

STORED

HyperStorM


Aufbau des PAT-Trees

2

1

2

3 3

7 5

4 8

5 1

4 2

6 3

01100100010111… Text


5 9

4

Motivation

DataGuide

Repres.Objects

PAT-Trees

- Struktur

- Aufbau

- Suche

-Sonstiges

Algebra

Mehrstufig-keit

STORED

HyperStorM


Suche mit PAT-Trees Prefix Search, Range Search (wird nicht explizit erklärt), regex Search, Evaluierung von Pfadausdrücken.

Motivation

DataGuide

Repres.Objects

PAT-Trees

- Struktur

- Aufbau

- Suche

-Sonstiges

Algebra

Mehrstufig-keit

STORED

HyperStorM


Prefix-Search mit PAT-Trees

2

1

2

3 3

7 5

4 8

1

4 2

6 3

01100100010111… Text


5 9

4

Motivation

DataGuide

Repres.Objects

PAT-Trees

- Struktur

- Aufbau

- Suche

-Sonstiges

Algebra

Mehrstufig-keit

STORED

HyperStorM

Beispiele: 110 0000 01

11000000000

01


Suche mit PAT-Trees regex-Suche:

Automat erzeugen und auf Baum laufenlassen,

Zielzustand - Baum akzeptieren, Blatt - Rest des Automaten auf dem

Dokument laufenlassen. Pfadausdruck kann als regulärer Ausdruck

dargestellt werden, z.B.<restaurant>*<entrée>*</entrée>*</restaurant>

(‘*’ bedeutet hier ‘beliebig viele beliebige Zeichen’.)Erlaeutern, wann regex-Suche sinnvoll, und wann PAT-Tree wenig hilft.

Motivation

DataGuide

Repres.Objects

PAT-Trees

- Struktur

- Aufbau

- Suche

-Sonstiges

Algebra

Mehrstufig-keit

STORED

HyperStorM


PAT-Trees - Anmerkungen Schwachpunkte:

Hoher Platzbedarf, nachträgliches Einfügen mühsam.

Bestandteil von Produkten. Was ist der Zusammenhang

zwischen DataGuides und PAT Trees?Welchen Teil der ‘DataGuide-Funktionalität’ bekommt man auch mit PAT Trees?

Motivation

DataGuide

Repres.Objects

PAT-Trees

- Struktur

- Aufbau

- Suche

-Sonstiges

Algebra

Mehrstufig-keit

STORED

HyperStorM


Gliederung für die folgenden Punkte Query-Algebra (im Gegensatz zu

‘Querysprache’), n

Mehrstufige Verfahren zur Evaluierung von XML-Queries - Motivation und Begriffsbildung,

File-basiertes Query-Processing -zwei Alternativen.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


PAT Query Algebra Algebraische Darstellung von Queries über

semistrukturierte Daten, Algebra-Darstellung entspricht

möglicherweise Evaluierungsstrategie, Analogie: SQL vs. relationale Algebra. Ein mögliches Beispiel für Query Algebra:

PAT Algebra.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


PAT Query Algebra - Syntax Syntax:

<Elementtyp-Name> ist zulässiger Algebra-Ausdruck,

Wenn T1, T2 Ausdrücke sind, dann auch:– CONTENT_SELECT(T1, <String-Pattern>),– ATTR_SELECT(T1, <Attr.-Name>, <Attr.-Wert>),– T1 UNION T2, – T1 DIFF T2,– T1 INCLUDS T2

– T1 INCL_IN T2

– (T1) Beispiel-Query:FIRSTNAME INCL_IN (CONTENT_SELECT(AUTHOR, ‘Böhm’))

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


PAT Query Algebra - Semantik Semantik:

<ET-Name> - Menge aller Elemente mit Label <ET-Name>

CONTENT_SELECT(T1, <String-Pattern>) –alle Elemente aus T1, die <String -Pattern> enthalten,

ATTR_SELECT(T1, <A.-Name>, <A.-Wert>) – alle Elemente aus T1 mit Attribut <A.-Name> mit Wert <A.-Wert>,

T1 INCLUDS T2 – alle Elemente aus T1, die eins aus T2 enthalten,

T1 INCL_IN T2– alle Elemente aus T1, die in einem aus T2

enthalten sind. Was bedeutet die Beispiel-Query?

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM

Hier Schreibfehler im Handout


Mehrstufiges Query Processing Man kann sich immer Queries ausdenken,

die mit Hilfe des Index allein nicht evaluiert werden können,

Ansatz: Man verwendet Index, um Menge der Dokumente einzuschränken, und inspiziert die verbleibenden Dokumente (Kandidaten) “von Hand” (d.h. ohne Zuhilfenahme eines Index).

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

- Motivation

- Subsumpt.

- File-bas.

- Baum-b.

- Event-bas.

STORED

HyperStorM


Subsuming Query und Filter Query Query QS subsumiert Q gdw.

<QS> <Q> für beliebige Kollektionen,Query QS ist Subsuming Query für Q.

Filter Query QF für Query Q und Subsuming Query QS: <QF>(<QS>) = <Q>, d.h. wenn QF auf das Resultat von QS angewendet wird, ist das Ergebnis das gleiche, wie wenn Q evaluiert wird.

Wann ist Aufteilung einer Query in Subsuming Query und Filter Query noch sinnvoll?Ein System kann nur Subsuming Query, nicht aber Filter Query evaluieren, ist aber sehr schnell.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

- Motivation

- Subsumpt.

- File-bas.

- Baum-b.

- Event-bas.

STORED

HyperStorM


Subsuming Query und Filter Query - Beispiel

Ansatz ist vorteilhaft, wenn Volltext-Engine erheblich schneller als XML Query Engine,

und Zwischenergebnis deutlich kleiner als Ausgangskollektion.

Im Beispiel sind Query und Filter Query identisch, das muss aber nicht so sein.

XML-Query

Volltext-Engine

XML Query-Engine

Query-Resultat

- langsam -

Zwischen-ergebnis

(Kandidaten)

Sub-sumingQuery

“Finde die Adressen aller Restaurants mit PLZ 92310.”

“92310”

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

- Motivation

- Subsumpt.

- File-bas.

- Baum-b.

- Event-bas.

STORED

HyperStorM


Query-Evaluierung ohne Indexstrukturen

Application

XML-Processor(XML-Engine)

Callback-Methoden

DOM-Methoden

Aufruf fürXML-Dok.

query

Thema im folgenden: Techniken zur effizienten Evaluierung von XML Queries auf Dokumenten konform zur XML Spezifikation (d.h. XML Files).

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

- Motivation

- Subsumpt.

- File-bas.

- Baum-b.

- Event-bas.

STORED

HyperStorM


Zwei Alternativen Baum-basiert, Event-basiert.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

- Motivation

- Subsumpt.

- File-bas.

- Baum-b.

- Event-bas.

STORED

HyperStorM


Baum-basierte Queryevaluierung Aufbau der Baumstruktur im Hauptspeicher

unter Verwendung der Callback-Schnittstelle,

Algebraische Repräsentation der Query, Set-at-a-time Query Evaluierung.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

- Motivation

- Subsumpt.

- File-bas.

- Baum-b.

- Event-bas.

STORED

HyperStorM


Baum-basierte Queryevaluierung - Beispiel

AUTHORS

SURNAME CHRNAME

Grabs Torsten

AUTHORFUNCTION=PHOTOGR

SURNAME CHRNAME

Weber Roger

AUTHORFUNCTION=AUTHOR

INCL_IN

CHRNAME

NAME CONTENT_SELECT‘Grabs’

SURNAME

INCLUDS

Dokument(logische Struktur):

Query(Algebra- Repräs.):

NAMENAME

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

- Motivation

- Subsumpt.

- File-bas.

- Baum-b.

- Event-bas.

STORED

HyperStorM


Baum-basierte Queryevaluierung - Optimierungen

Idee: Nur die Teilbäume erzeugen, die für die Queryevaluierung wirklich gebraucht werden.

TOP Optimierung OUT Optimierung BOTTOM Optimierung

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

- Motivation

- Subsumpt.

- File-bas.

- Baum-b.

- Event-bas.

STORED

HyperStorM


TOP Optimierung Beispiel (Query von vorhin):

“Selektiere alle CHRNAME-Elemente, die in einem NAME-Element enthalten sind, die ein SURNAME-Element mit Inhalt ‘Böhm’ enthalten.”

Queryergebnisse haben die folgende Struktur:

Es genügt, Teilbäume zu betrachten, deren Wurzel vom Typ NAME ist.

NAME

CHRNAME

Böhm

SURNAME

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

- Motivation

- Subsumpt.

- File-bas.

- Baum-b.

- Event-bas.

STORED

HyperStorM


BOTTOM Optimierung Beispiel (Query von vorhin):


Wir brauchen nur Elemente, die String ‘Böhm’ enthalten, oder die ein Element vom Typ CHRNAME enthalten,

oder die in einem Element vom Typ CHRNAME

enthalten sind.

NAME

CHRNAME

Böhm

SURNAME

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

- Motivation

- Subsumpt.

- File-bas.

- Baum-b.

- Event-bas.

STORED

HyperStorM


OUT Optimierung Beispiel (Query von vorhin):


Idee: Verwendung der DTD zur Eliminierung von Teilbäumen,

Beispiel (Forts.): DTD sagt uns, dass MONOMED-Elemente nie CHRNAME-Elemente enthalten Teilbäume mit Wurzel MONOMED werden für Queryevaluierung nicht gebraucht.

OUT Optimierung basiert auf der DTD, im Gegensatz zu TOP und BOTTOM.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

- Motivation

- Subsumpt.

- File-bas.

- Baum-b.

- Event-bas.

STORED

HyperStorM


Event-Basierte Queryevaluierung Automat, der der Query entspricht, Events überführen den Automaten in

anderen Zustand. Beispiel: “Selektiere alle Dokumente mit

einem caption-Element, das den String ‘millennium’ enthält.”

Implementierung ist komplizierter als hier dargestellt.

CAPTION begin

CAPTION end

string ‘millennium’

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

- Motivation

- Subsumpt.

- File-bas.

- Baum-b.

- Event-bas.

STORED

HyperStorM


Fazit File-basierte Queryevaluierung (ohne

Index/materialisierte Sichten) “geht immer”, Kombination File-basierter

Queryevaluierung mit Indexstrukturen für semistrukturierte Daten bringt i.a. deutlich bessere Performance als File-basierte Queryevaluierung alleine.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

- Motivation

- Subsumpt.

- File-bas.

- Baum-b.

- Event-bas.

STORED

HyperStorM


Verwendung von RDBMSen - Gliederung

Motivation, ‘naive’ Ansätze, ein ‘weniger naiver’ Ansatz (STORED), Problem: Finden der Abbildung von

‘semistrukturiert’ auf ‘relational’, Aktivitäten an der ETHZ.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM


Verwendung von RDBMSen Ziel: Verwendung eines RDBMSs zur Verwaltung

semistrukturierter Daten. Man hat materialisierte relationale Sichten auf die

semistrukturierten Daten. Man kann die Sichten indexieren.

Datenbank-Funktionalität, z.B. Concurrency Control, Indices, “for free”.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM


Beispiel für relationale Speicherung

<rezept> <zutaten id="x1"> <zutat>Ei</zutat> <zutat>Mehl</zutat> </zutaten> <expertise/> <zutaten id="x2"> <zutat>Salz</zutat> </zutaten></rezept>

Dokument

Source Name VString Target1 rezept x1x1 zutaten 2x1 zutaten 32 zutat Ei3 zutat Mehl1 rezept 44 expertise1 zutaten 55 zutat Salz

Mögliche relationale Darstellung

Reihenfolge-Information nicht berücksichtigt, geht aber grundsätzlich,

zuviele Joins zur Evaluierung von Pfadausdrücken, Einfügen und Auslesen von ganzen Dokumenten dauert zu

lange, unklar, für welche Anfragen die Darstellung vorteilhaft ist.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM


rezept

Source VString Target1 21 31 4

Source VString Target3 53 64 7

zutaten

Source VString Target2

expertise

Beispiel f. relationale Speicherung (2)

Kein substantieller Unterschied zur vorigen Repräsentation!

Source VString Target5 Ei6 Mehl7 Salz

zutat

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM


STORED ‘STORED’ = ‘Semistructured TO RElational Data’ Ziel: Verwendung eines RDBMSs zur Verwaltung

semistrukturierter Daten. Auswahl und freie Definition der relationalen

Sichten, keine generischen Tabellen wie in den vorangegangenen Beispielen.

Relationale Sichten enthalten i.d.R. nur Teil des Dokuments; wegen Verlustfreiheit muss man z.B. das ursprüngliche Dokument behalten.Overflow Graphs erwaehnen

Problem: Auswahl der Sichten, die man materialisieren will; mögliche Randbedingungen: Plattenplatz, Maximalanzahl von Relationen, gewichteter Query-Mix.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM


Relationale Sichten auf semistrukturierte Daten

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM

name

address audited

taxamount

nameaddress

auditedaudited

taxamount

taxevasionname

addressaudited

taxamount

taxevasion

name

owner

taxpayer taxpayer taxpayer company

Audit

street

street zip

street

numberzip

Werte und OIDs weggelassenUnterschied zu OEM: Geordnetheit


Relationale Speicherung – Fortsetzung des Beispiels

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM

oid name street no apt zip audit1 audit2 taxamount taxevasion o24 Gluschko Tyuratam 2c 07099 10/12/63 12332 o21 Kosberg Tyuratam 206 92443 11/1/68 10/12/77 0 likely

oid name address audited taxamount taxevasion o20 Korolev Baikonur 10/12/86 0 likely

name owner Rocket Inc. o24

Taxpayer1

Taxpayer2

Company

Mehrere Tabellen fuer aehnliche StrukturAufloesung von Mengenbeziehungen


Storage Queries ‘Storage Queries’ beschreiben Abbildung

von semistrukturierten Daten aufs Relationale.

Beispiele:M1a = FROM Audit.taxpayer: $X

{ name: $N, adr: $P, OPT{audited: $A}, OPT{taxamount: $T}}WHERE typeOF($P, “string”)STORE Taxpr($X, $N, $P, $A, $T)

M1b = FROM Audit.taxpayer: $X{ name: $N, adr: {street $S,

OPT{city $C, OPT{zip $Z}}}, OPT{audited: $A}, OPT{taxamount: $T}}WHERE typeOF($P, “string”)STORE Taxpr($X, $N, $S, $C, $Z, $A, $T)

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM


Storage Queries - Erläuterungen Erste Variable in der FROM-Klausel ist per

Default Schlüssel-Variable, Optionale Attribute, die nicht vorhanden

sind, führen zu NULL-Werten I.a. kann es mehrere Sichten auf die

gleichen Daten geben (hier im Beispiel jedoch nicht)

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM


Storage Queries (Fortsetzung) Beispiel:

M2 = FROM Audit.taxpayer: $X{name[1]: $N, audited[1]: $A1, OPT{audited[2]: $A2}}STORE Taxpr2($N, $A1, $A2)

Objekt kann mehrere ausgehende Kanten mit gleichem Label haben.

Beispiel:M3a = FROM Audit.irscenter: $X

{centername: $N, centeraddress: $A} STORE IrsCenter($X, $N, $A)

M3b = FROM Audit.irscenter: $X.hearing: $Y{hearingdate: $D, taxpayername: $TN, auditorname: $AN, decision: $Z} KEY $YSTORE Hearings($Y, $X, $D, $TN, $AN,

$Z)

Beispiel illustriert das Aufteilen von Daten auf mehrere Relationen.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM


Auswahl der Sichten Patterns, z.B.

Audit.taxpayer: {name[1], phone[2],address[*]: {street[1], city[1]}}

phone[1]kann weggelassen werden.

Beispiel-Pattern hat fünf Blätter. Definition: Support eines Patterns –

Anzahl der Objekte oi, die das Pattern enthaltennatuerlich nicht das Wurzelobjekt

Definition: Query Support eines Patterns – gegeben eine Menge von Anfragen Q1, …, Qk mit Gewichten f1, …, fk, ist der Query Support von P die Summe der fi, für die P in Qi enthalten ist.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM


Data Mining in 120 Sekunden… Ziel: Alle Patterns finden, deren Support

grösser ist als ein vorgegebener Schwellwert, d.h. alle Frequent Patterns

Frequent Patterns sind die Grundlage für die Auswahl der relationalen Sichten.

Fk – Menge aller Frequent Patterns mit k Blättern.

Typische Algorithmen finden alle Fk, mit aufsteigendem k.

Apriori-Trick: Pattern aus Fk+1 muss k+1 Subpatterns haben, die in Fk enthalten sind.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM


Algorithmus zur Auswahl der Sichten Erzeugung aller Label Paths mit ausreichendem Support, Erzeugung der Frequent Patterns, Nicht jedes Frequent Pattern kann i.d.R. einer View

entsprechen, daher macht STORED eine greedy-mässige Auswahl der Patterns: Erstes Pattern P1 so wählen, dass es Pfade aus F1, die

sehr hohen Support haben, enthält, Pk so wählen, dass (1) Überlappung mit P1, …, Pk-1

minimal ist, und (2) neue Pfade aus F1 mit hohem Support abgedeckt werden.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM

Auswahl der obligatorischen (und optionalen) Attribute pro Pattern, zu viele optionale Attribute -> mehr

NULL-Werte, mehr Überlappung mit anderen Patterns,

zu wenige optionale Attribute -> zu wenige Daten werden gematcht.

Erzeugung der Storage Queries.


Beurteilung Grundsätzlicher Ansatz ist interessant,

man vermeidet die Nachteile einer starren Abbildung,

Concurrency Control ‘nicht ganz unproblematisch’,

Heuristiken, die dem Mining-Algorithmus zugrundeliegen, kommen m.E. unmotiviert,

Mining-Algorithmus selbst funktioniert nicht bei Dokumenten mit halbwegs vernünftiger Anzahl von Elementen.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM


Was machen wir an der ETH gerade? Ziel: Ermittlung der besten Repräsentation

von Dokument-Kollektionen für unterschiedliche Workloads mit Updates.

Grundsätzlicher Ansatz: Mehrstufiges Verfahren, Subsuming Query wird mit Hilfe von

Indexstrukturen evaluiert, Filter Query wird filebasiert evaluiert.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM


Was machen wir an der ETH gerade?

Alternativen: Volltext-Index,

der logische Dokumentstruktur ignoriert, Feldweiser Volltext-Index sowohl ohne als

auch mit Redundanzen,Problem: Wie kommt man von vorgegebenem ‘Redundanz-Faktor’ zu der exakten physischen Repräsentation?

Pfad-Index, ebenfalls mit und ohne Redundanzen, (gleiches Problem wie mit feldweisem Index),

STORED-mässiges Vorgehen.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM


Was machen wir an der ETH gerade? (Effiziente) Lösung für das Problem, häufige

Muster in XML-Dokumentkollektionen zu finden. n

Ansatz: Nicht jedes Zwischenergebnis explizit erzeugen.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

- Einleitung

- Abbildung

- Mining

- Ausblick

HyperStorM


HyperStorMZiele: Modellierung der Semantik von Hypermedia-

Dokumentbestandteilen in der DatenbankBeispiele: Elemente in Dokumenten mit Multimedia-

Bestandteilen, die den Präsentationsablauf spezifizieren,

Hyperlink-Elemente, die andere Dokumentbestandteile referenzieren.

Benutzer sollen gleichzeitig unterschiedliche Teile von Dokumenten lesen und schreiben dürfen,

Effiziente Evaluierung von Anfragen, die sich sowohl auf Struktur als auch auf textuellen Inhalt der Dokumente beziehen können.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Ansatz Verwendung objektorientierter Datenbank-

Technologie –generische Abbildung von Objekten auf physische Repräsentation (Relationen bzw. ObjectStore-Strukturen).

Dokumente werden in der Datenbank gespeichert,

Methoden reflektieren XML-Semantik und Semantik von Hypermedia-Dokumentbestandteilen,

Annahme: DTD ist gegeben (SGML statt XML).

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Physische Repräsentation der Dokumente

Naheliegender Ansatz: Jedem Element entspricht ein Datenbank-Objekt zuviele Objekte, Einfügen von Dokumenten in die Datenbank und Auslesen ist teuer, wenn Datenbank kein Clustering vornimmt.

Beispiel für diesen Ansatz: Excelon. Ansatz von GMD-IPSI (‘HyperStorM’):

Anwendung legt physischen Entwurf fest. Hybrider Ansatz –

nur Elemente ‘oben in der Hierarchie’ werden durch Datenbank-Objekte repräsentiert,Elemente ‘weiter unten’ werden in BLOB-Attribut eines Datenbank-Objekts zusammengefasst.

Konfiguration auf DTD-Ebene.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Beispiel

scene

...play

fm acttitle personae

The Tragedy of Hamlet,

Prince of Denmarkacttitle

Act I

stagedirp . . . p

...worldwide

SGML markup...

scenedescr playsubt

Scene Denmark

hamlet

scenetitle

Scene I ...

FRANCISCO ...

speech

speaker line

BERNARDOWho's

there?

DramatisPersona

title

persona persona

CLAUDIUS HAMLET

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM

<title>Dramatis Personae</title><persona>CLAUDIUS</persona><persona>HAMLET</persona>


XML- und Hypermedia-Semantik Methoden reflektieren XML-Semantik, z.B.

Navigation in der Hierarchie, Methoden abstrahieren davon, ob Element

explizit durch ein Datenbank-Objekt repräsentiert wird oder Teil eines BLOBs ist.

Element-ID Datenbank-OID;Element-ID = Datenbank-OID + Position im BLOB(BLOB-Position ist –1, wenn explizite Repräsentation des Elements)

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Bewertung Anforderung ‘Unterstützung der Semantik

von Dokumentbestandteilen’ wurde erfüllt, allerdings gab es keine Anwendungen und Dokumente mit Hypermedia-Eigenschaften, und auch Anforderung ‘Ändern von Dokumenten’ war keine wirkliche Anforderung.

Vor ca. fünf Jahren war es modern, den Datenbank-Kern um möglichst viel Anwendungssemantik zu erweitern(objekt-relationale Datenbanktechnologie, ‘Universal Server’ Konzept)

Features wie Vererbung in o.-o. Datenbanken waren – zumindest in der Forschung – modern, verlangsamen aber das System.

Keine Unterstützung für effizienten deklarativen Zugriff, Aspekte der Indexierung sind orthogonal zu den hier diskutierten.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM


Bewertung (Forts.) Konfiguration der physischen Repräsentation auf

Schema-Ebene – Erweiterung für wohlgeformte XML-Dokumente ist nicht offensichtlich,

Konfiguration erfolgte ‘von Hand’ (obwohl ‘Automatic Tuning’-Mechanismen grundsätzlich anwendbar sind),

keine aussagekräftige Performance-Evaluierung, insbesondere für sehr grosse Dokumentkollektionen.

Motivation

DataGuide

Repres.Objects

PAT-Trees

Algebra

Mehrstufig-keit

STORED

HyperStorM

Documents

Interoperable Informationssysteme - 1 Klemens Böhm DataGuides und Indexstrukturen für semistrukturierte Daten