Upload
dietlinde-giesing
View
108
Download
0
Embed Size (px)
Citation preview
Interoperable Informationssysteme - 1Klemens Böhm
Systeme 1: Materialisierungen und
Indexstrukturenfür semistrukturierte Daten
Interoperable Informationssysteme - 2Klemens Böhm
Gliederung Fragen:
Wie speichert man semistrukturierte Daten, insbes. XML-Dokumente?
Wie evaluiert man Queries effizient?
Gliederungspunkte: DataGuides, PAT-Trees, Query Subsumption und Query Filtering
sowie File-basiertes Query Processing, Verwendung von RDBMSen, Verwendung objektorientierter Datenbank-Technologie.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 3Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 4Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 5Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 6Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 7Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 8Klemens Böhm
DataGuides - Gliederung Was sind DataGuides? n
Wie helfen sie bei der Evaluierung von Anfragen? (Problem 2)
Erweiterungen von DataGuides;Annotationen von DataGuides,
Annotationen und Query Evaluierung(Problem 1).
I.a. gibt es mehrere DataGuides für eine Datenbank, was sind die Unterschiede?
Schlussbemerkungen zu DataGuides
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 9Klemens Böhm
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.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 10Klemens Böhm
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.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 11Klemens Böhm
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.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 12Klemens Böhm
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.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 13Klemens Böhm
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.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 14Klemens Böhm
Erzeugung von DataGuides
Äquivalent zu NEA -> DEAMotivation
DataGuide
- Einleitung
- Struktur
- Query Proc.
- Strong DGs
- Einord.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 15Klemens Böhm
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.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
A2A1
C B D
Interoperable Informationssysteme - 16Klemens Böhm
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.
Motivation
DataGuide
- Einleitung
- Struktur
- Query Proc.
- Strong DGs
- Einord.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 17Klemens Böhm
Verwendung DataGuide für Query Processing (3)
DataGuide: Nur Zusammenfassung der Datenbank.Anfragen, die nicht allein mit DataGuide/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.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 18Klemens Böhm
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.
Wichtig: Wie genau ist die physische Repräsentation der Dokumente?
Motivation
DataGuide
- Einleitung
- Struktur
- Query Proc.
- Strong DGs
- Einord.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 19Klemens Böhm
Es kann mehrere DataGuides geben.
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 DataGuides
Motivation
DataGuide
- Einleitung
- Struktur
- Query Proc.
- Strong DGs
- Einord.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 20Klemens Böhm
Minimale DataGuides Es existieren wohlbekannte Techniken
zur Minimierung von DataGuides, d.h. zur Erzeugung eines DataGuides mit minimaler Anzahl von Zuständen.
Nachteile minimaler DataGuides: Änderungen an der Datenbank
verursachen mehr Arbeit, Annotationen weniger aussagekräftig.
Motivation
DataGuide
- Einleitung
- Struktur
- Query Proc.
- Strong DGs
- Einord.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 21Klemens Böhm
Strong DataGuides Motivation: Charakterisierung der DataGuides,
deren Annotationen maximal präzise sind. Intuition: Label paths mit dem gleichen (singleton)
Target Set im DataGuide haben stets das gleiche Target Set in der Datenbank.Illustration: Nächste Folie.
Motivation
DataGuide
- Einleitung
- Struktur
- Query Proc.
- Strong DGs
- Einord.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 22Klemens Böhm
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.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 23Klemens Böhm
Strong DataGuides - Definition OEM Objekte s und d, d ist DataGuide für s, Ts(l) - Target Set von l in s, Td(l) - Target Set von l in d
- muss einelementig sein -, Ls(l) = {m|Ts(m)=Ts(l)}, m ist label path.
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)
Beispiel – nächste Folie.
Motivation
DataGuide
- Einleitung
- Struktur
- Query Proc.
- Strong DGs
- Einord.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 24Klemens Böhm
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.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 25Klemens Böhm
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.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 26Klemens Böhm
Aufbau eines Strong DataGuides - Illustration
2
1
3
BB
4
C
5
C
dg = 6 Neues ObjekttargetHash = {({1}, 6)} Hash-TabelleAufruf ‘RecursiveMake({1}, 6)’
p={(B,2), (B,3)} Kinder eines Objektsl=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.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 27Klemens Böhm
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.
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 28Klemens Böhm
PAT-Tree - Gliederung Was sind PAT-Trees? n
Wie werden PAT-Trees aufgebaut? Was für Anfragen werden unterstützt,
und wie?
Motivation
DataGuide
PAT-Trees
- Struktur
- Aufbau
- Suche
-Sonstiges
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 29Klemens Böhm
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
PAT-Trees
- Struktur
- Aufbau
- Suche
-Sonstiges
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 30Klemens Böhm
PAT-Trees
2
1
2
3 3
7 5
4 8
5 1
4 2
6 3
01100100010111… Dokument
123456789… Position
Warum folgt (5) auf (3)?
Motivation
DataGuide
PAT-Trees
- Struktur
- Aufbau
- Suche
-Sonstiges
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 31Klemens Böhm
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
PAT-Trees
- Struktur
- Aufbau
- Suche
-Sonstiges
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 32Klemens Böhm
Aufbau des PAT-Trees
2
1
2
3 3
7 5
4 8
5 1
4 2
6 3
01100100010111… Text
123456789… Position
5 9
4
Motivation
DataGuide
PAT-Trees
- Struktur
- Aufbau
- Suche
-Sonstiges
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 33Klemens Böhm
Suche mit PAT-Trees Prefix Search, Range Search (wird nicht explizit erklärt), regex Search, Evaluierung von Pfadausdrücken.
Motivation
DataGuide
PAT-Trees
- Struktur
- Aufbau
- Suche
-Sonstiges
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 34Klemens Böhm
Prefix-Search mit PAT-Trees
2
1
2
3 3
7 5
4 8
1
4 2
6 3
01100100010111… Text
123456789… Position
5 9
4
Motivation
DataGuide
PAT-Trees
- Struktur
- Aufbau
- Suche
-Sonstiges
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Beispiele: 110 0000 01
11000000000
01
Interoperable Informationssysteme - 35Klemens Böhm
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’.) Problem 1:
– Beispiel: /restaurant//entrée– ‘Naive’ regex-Suche wäre aber nicht gut,
weil man über das Ende der entrée-Elemente hinaus nach </entrée> sucht.
Problem 2: //entrée
Motivation
DataGuide
PAT-Trees
- Struktur
- Aufbau
- Suche
-Sonstiges
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 36Klemens Böhm
PAT-Trees - Anmerkungen Schwachpunkte:
Hoher Platzbedarf, nachträgliches Einfügen mühsam, nur Primärstruktur.
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
PAT-Trees
- Struktur
- Aufbau
- Suche
-Sonstiges
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 37Klemens Böhm
Gliederung für die folgenden Punkte Query-Algebra
(im Gegensatz zu ‘Querysprache’), Mehrstufige Verfahren
zur Evaluierung von XML-Queries – Motivation und Begriffsbildung,
File-basiertes Query-Processing – zwei Alternativen.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 38Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 39Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 40Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 41Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
- Motivation
- Subsumpt.
- File-bas.
- Baum-b.
- Event-bas.
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 42Klemens Böhm
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 Filter Query und Subsuming Query noch sinnvoll?Ein System kann nur Subsuming Query, nicht aber Filter Query evaluieren, ist aber sehr schnell.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
- Motivation
- Subsumpt.
- File-bas.
- Baum-b.
- Event-bas.
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 43Klemens Böhm
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 Adressen aller Restaurants mit PLZ 92310.”
“92310”
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
- Motivation
- Subsumpt.
- File-bas.
- Baum-b.
- Event-bas.
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 44Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
- Motivation
- Subsumpt.
- File-bas.
- Baum-b.
- Event-bas.
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 45Klemens Böhm
Zwei Alternativen Baum-basiert, Event-basiert.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
- Motivation
- Subsumpt.
- File-bas.
- Baum-b.
- Event-bas.
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 46Klemens Böhm
Baum-basierte Queryevaluierung Aufbau der Baumstruktur im Hauptspeicher
unter Verwendung der Callback-Schnittstelle, Baum wird nur hierfür gebraucht
und dann wieder weggeworfen. Vergleich mit Datenbank-Scan. Algebraische Repräsentation der Query, Set-at-a-time Query Evaluierung.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
- Motivation
- Subsumpt.
- File-bas.
- Baum-b.
- Event-bas.
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 47Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
- Motivation
- Subsumpt.
- File-bas.
- Baum-b.
- Event-bas.
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 48Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
- Motivation
- Subsumpt.
- File-bas.
- Baum-b.
- Event-bas.
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 49Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
- Motivation
- Subsumpt.
- File-bas.
- Baum-b.
- Event-bas.
STORED
CombinedIndices
HyperStorM
SQL-Server
Grosses Dreieck: Dokumentkleines Dreieck: Ausschnitt,der gebraucht wird fuer die Query.
Interoperable Informationssysteme - 50Klemens Böhm
BOTTOM 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.”
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
PAT-Trees
Algebra
Mehrstufig-keit
- Motivation
- Subsumpt.
- File-bas.
- Baum-b.
- Event-bas.
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 51Klemens Böhm
OUT 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.”
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
PAT-Trees
Algebra
Mehrstufig-keit
- Motivation
- Subsumpt.
- File-bas.
- Baum-b.
- Event-bas.
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 52Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
- Motivation
- Subsumpt.
- File-bas.
- Baum-b.
- Event-bas.
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 53Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
- Motivation
- Subsumpt.
- File-bas.
- Baum-b.
- Event-bas.
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 54Klemens Böhm
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. Am Ende des Kapitels:
XML-Features von SQL-Server.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 55Klemens Böhm
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”.
Query Containment – wird als gegeben angenommen, wird hier nicht betrachtet.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 56Klemens Böhm
Verwendung von RDBMSen Eine mögliche Verwendungsmöglichkeit
von RDBMSen: Speicherung der Annotationen der DataGuides,
Jedem DataGuide-Knoten entspricht z.B. eine Relation, Indexierung bekommt man dann ‘kostenlos’.
DataGuide selbst muss/sollte nicht in der Datenbank sein, kann im Hauptspeicher sein.
Ziel im folgenden: Nicht nur Evaluierung von Pfadausdrücken, sondern Queries allgemein.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 57Klemens Böhm
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
(bzw. wo sie besser ist als bisherige Repräsentationen).
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 58Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 59Klemens Böhm
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;
ausserdem Overflow Graph wegen Verlustfreiheit. Problem:
Auswahl der Sichten, die man materialisieren will; mögliche Randbedingungen: Plattenplatz, Maximalanzahl von Relationen, gewichteter Query-Mix.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 60Klemens Böhm
Relationale Sichten auf semistrukturierte Daten
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
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 weggelassen.Unterschied zu OEM: Geordnetheit.
Interoperable Informationssysteme - 61Klemens Böhm
Relationale Speicherung – Fortsetzung des Beispiels
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
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 1. RDBMS-Schema ist dokumenttyp-spezifisch.
2. Unterschiedliche Tables für einen Elementtyp.
3. Daten zu einem Element auf mehrere Relationen verteilen.
Interoperable Informationssysteme - 62Klemens Böhm
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)
OID bei inneren Knoten, Textinhalt bei Blättern.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 63Klemens Böhm
Storage Queries - Erläuterungen Erste Variable in der FROM-Klausel ist
per Default Schlüssel-Variable,(d.h. man geht offensichtlich davon aus, dass Objekte OID haben, die man auslesen kann)
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 64Klemens Böhm
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 nochmals das Aufteilen von Daten auf mehrere Relationen.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 65Klemens Böhm
Auswahl der Sichten (1) Wie kommt man zu den Storage Queries? (Strukturelle) Patterns finden,
die häufig vorkommen. Diese Patterns auf Storage Queries abbilden. Patterns, z.B.
Audit.taxpayer: {name[1], phone[2],address[1]: {street[1], city[1]}}
phone[1] kann weggelassen werden. Beispiel-Pattern hat fünf Blätter.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 66Klemens Böhm
Auswahl der Sichten (2) Weiteres Beispiel-Pattern mit ‘*’:
Audit.taxpayer: {name[1], phone[2],address[*]: {street[1], city[1]}}
Viele address-Elemente in taxpayer-Element – genestete Relation vorteilhaft:
Wenige address-Elemente – inlining besser:
Schwellenwert c von aussen vorgeben; genaue Anzahl ist egal.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
oid name audit1 audit2 tax-amount
tax- evasion
o07 Böhm 06/06/01 0 likely o24 Glusch-
ko 10/12/63 12332
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 street no apt zip o24 Nordstrasse 174 8037 o24 Jahnstrasse 34 62487 o24 Heidelberger
Strasse 102 62487
o24 Pallaswiesen-strasse
152 62485
Interoperable Informationssysteme - 67Klemens Böhm
Auswahl der Sichten (2) Definition: Support eines Patterns –
Anzahl der Vorkommen des Patterns. 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.
Je grösser Query-Support, für desto mehr Queries ist das Pattern Teil des Ergebnisses.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 68Klemens Böhm
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.
Query Support ist monoton.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 69Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Auswahl der obligatorischen (und optionalen) Attribute pro Pattern, zu viele optionale Attribute ->
mehr NULL-Werte, mehr Über-lappung mit anderen Patterns,
zu wenige optionale Attribute -> zu wenige Daten werden gematcht.
Erzeugung der Storage Queries.
Interoperable Informationssysteme - 70Klemens Böhm
Queryevaluierung
Man unterscheidet mehrere Fälle: Query sucht Pattern, das exakt
mit einer Sichtdefinition übereinstimmt – einfacher, angenehmer Fall. Q=V
Query sucht Pattern, das ‘Storage Pattern’ enthält: In diesem Fall mehrstufiges Query-Processing, wie zuvor besprochen. QV
Was kann man machen, wenn Query Pattern sucht, das in ‘Storage Pattern’ enthalten ist? QV
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 71Klemens Böhm
Beurteilung Grundsätzlicher Ansatz: interessant,
man vermeidet Nachteile einer starren Abbildung, Concurrency Control
‘nicht ganz unproblematisch’, Heuristiken, die dem Algorithmus zur Sichtauswahl
zugrundeliegen, m.E. unmotiviert – Parameter? Mining-Algorithmus funktioniert nicht
bei Dokumenten mit ‘normaler’ Anzahl Elementen. Evaluierung –
berücksichtigt Ausnahmen nur unzureichend.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
- Einleitung
- Abbildung
- Mining
- Ausblick
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 72Klemens Böhm
Combined Indices Zunächst anhand von Relationen,
dann Verallgemeinerung. Relation hat mehrere Attribute, z.B.
Indexierung einzelner Attribute i.d.R. sinnvoll, z.B. alle Vorkommen des Vornamens ‘Klemens’.
‘Kombinierte Anfragen’; d.h. Anfragen über mehrere AttributeBeispiel: Vorname=‘Klemens’Alter=25
Combined Index, d.h. Vorkommen von Werte-Kombinationen indexieren.
# Kombinationsmöglichkeiten wächst exponentiell.
Name Vorname Beruf Alter Büro-Nummer
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 73Klemens Böhm
Combined Indices – Anzahl der Kombinationen
Beobachtung 1: Sehr viele Vorkommen von Vorname ‘Klemens’ Indexierung nicht hilfreich, Scan genauso teuer.
Beobachtung 2: Angenommen, Vorname ‘Klemens’ nur einmal in Datenbank. Indexeinträge (‘Klemens’, ‘Böhm’),
(‘Klemens’, 25), (‘Klemens’, ‘C45.2’)werden nicht gebraucht.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 74Klemens Böhm
Vorgehen Index für alle Kombinationsmöglichkeiten vorsehen. Werte-Tupel (v1, …, vn) bekommt Indexeintrag,
wenn deutlich weniger Instanzen als Instanzen der Tupel (v1, v3, …, vn), (v2, …, vn), …, (v1, …, vn-1).(Ausserdem Beobachtung 1 berücksichtigen.)
Wenn Teilmuster fast genauso häufig, Zugriff auch über Teilmuster möglich.
Beispiel (Fortsetzung von eben): Query:
Vorname=‘Klemens’ Büronummer=C45.2 Es reicht, alle Tupel mit Vorname ‘Klemens’
über Index zu holen. Dann Test, ob Büronummer=C45.2
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 75Klemens Böhm
Verallgemeinerung für Text und semistrukturierte Daten
Technik wurde ursprünglich für n-Grams entwickelt (von Herrn Schek),
Ziel: Indexierung von Vorkommen von Worten im Text.
Beispiel: Text enthält das Wort ‘character’.5-Grams: ‘chara’, ‘harac’, ‘aract’, …
Indexeintrag mit ‘chara’ wird erzeugt, wenn deutlich seltener als ‘char’, ‘hara’, etc.
Gleiches Vorgehen möglich für Pfade (im XML-Dokument).
Man kann Technik verallgemeinern für Indexierung Pfadfragment – Dokumenttext.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 76Klemens Böhm
HyperStorM
Ziele: Modellierung der Semantik von Hypermedia-Dokumentbestandteilen
in der DatenbankBeispiele: Hyperlink-Elemente,
die andere Dokumentbestandteile referenzieren, Elemente in Dokumenten mit Multimedia-Bestandteilen,
die den Präsentationsablauf spezifizieren. 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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 77Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 78Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 79Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
<title>Dramatis Personae</title><persona>CLAUDIUS</persona><persona>HAMLET</persona>
Interoperable Informationssysteme - 80Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 81Klemens Böhm
Bewertung Anforderung ‘Unterstützung der Semantik
von Dokumentbestandteilen’ wurde erfüllt für Hypermedia-Aspekte, allerdings gab es keine Anwendungen und Dokumente, und auch Anforderung ‘Nebenläufiges Ä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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 82Klemens Böhm
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
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
Interoperable Informationssysteme - 83Klemens Böhm
XML Features von SQL Server 2000
Transformation von Relationen (insbesondere Queryergebnisse) nach XML, Alternativen, unterschiedlich ausgefeilt.
Anfragen und Updates bezüglich XML Views, ‚XML Shredding‘: XML Relationen.
Generisch vs. individuell.
Insgesamt: Viel manuelle Intervention erforderlich. Kein automatisches Erzeugen eines
Dokumenttyp-spezifischen DB-Schemas und Einfügen/Herausholen der Dokumente.
Konfiguration m.E. etwas unübersichtlich.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
- Einleitung
- SQL-bas. Mechan.
- XML- Sichten + Zugriff
- XMLDB
Interoperable Informationssysteme - 84Klemens Böhm
HTTP Zugriff
URLs enthalten Domainname und Name der virtuellen Root.
Beispiel:http://dbspc15/sitzungen?sql=select%20'<root>';select+*+from+protokolle+FOR+XML+AUTO;select%20'</root>'
Virtual Root: Abstraktion, die DB-Server, DB-Instanz, Zugriffsrechte etc. versteckt.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
- Einleitung
- SQL-bas. Mechan.
- XML- Sichten + Zugriff
- XMLDB
Interoperable Informationssysteme - 85Klemens Böhm
HTTP Zugriff – URL Typen URL Query
http://localhost/demos?sql=select+*+from+Customers+FOR+XML+Auto&root=root
Direct Query Accesshttp://localhost/demos/dbobject/Employees[@EmployeeID=1]/@PhotoXPath-mässige Query Syntax
Template Accesshttp://server/vroot/vname?paramsTemplate = XML Dokument
XPath XML View Accesshttp://server/vroot/vname/xpath?params1. XML View, definiert in Schema File,2. Auswertung XPath Ausdruck
gegen diese Sicht.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
- Einleitung
- SQL-bas. Mechan.
- XML- Sichten + Zugriff
- XMLDB
Interoperable Informationssysteme - 86Klemens Böhm
Generierung von XML aus SQL-Queryergebnissen (1)
unterschiedlich ausgefeilte (und unterschiedlich komplizierte) Mechanismen für die direkte Erzeugung von XML aus Anfrageergebnis: raw, auto, explicit
raw Modus: Erzeugt XML Dokument mit kanonischem
Elementtyp row ‘in quadratischer Form’, primitiv.
Beispiel: http://dbspc15/sitzungen?sql=select+*+from+protokolle+FOR+XML+RAW&root=root
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
- Einleitung
- SQL-bas. Mechan.
- XML- Sichten + Zugriff
- XMLDB
Interoperable Informationssysteme - 87Klemens Böhm
Generierung von XML aus SQL-Queryergebnissen (2)
Auto Modus: Erzeugt XML Dokument mit Nesting mit
regelmässigem Aufbau, Reihenfolge der Table-Aliase in select-Klausel, Beispiel:
http://dbspc15/sitzungen?sql=select+*+from+protokolle+FOR+XML+AUTO&root=root
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
- Einleitung
- SQL-bas. Mechan.
- XML- Sichten + Zugriff
- XMLDB
Interoperable Informationssysteme - 88Klemens Böhm
Generierung von XML aus SQL-Queryergebnissen (3)
Query:SELECT Customers.CustomerID, OrderIDFROM Customers LEFT OUTER JOIN OrdersON Customers.CustomerID =
Orders.CustomerIDORDER BY Customers.CustomerIDFOR XML auto
Resultat:
<Customers CustomerID=“ALFKI”> <Orders OrderID=“10643” /> <Orders OrderID=“10692” /></Customers><Customers CustomerID=“ANATR”> <Orders OrderID=“10308” /> …
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
- Einleitung
- SQL-bas. Mechan.
- XML- Sichten + Zugriff
- XMLDB
Interoperable Informationssysteme - 89Klemens Böhm
Generierung von XML aus SQL-Queryergebnissen (4)
Explicit Modus: Flexibelster, aber kompliziertester Ansatz, Query erzeugt Tabelle, die Struktur des XML-Dokuments
explizit kodiert (‘Universal Table Format’) Beispiel – Dokument, das erzeugt werden soll:
<root> <Customer cid="ALFKI"> <name>Alfreds Futterkiste</name> <Order oid="O-10643" /> <Order oid="O-10692" /> <Order oid="O-10702" /> … </Customer> <Customer cid="BOLID"> <name>Bólido Comidas preparadas</name> <Order oid="O-10326" /> … </Customer></root>
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
HyperStorM
SQL-Server
- Einleitung
- SQL-bas. Mechan.
- XML- Sichten + Zugriff
- XMLDB
Spalten der Customer-Relation
Interoperable Informationssysteme - 90Klemens Böhm
Generierung von XML aus SQL-Queryergebnissen (5)
Unterschiedliches Mapping von Customer-Spalten:– cid Attribut– name Subelement
Entsprechende Tabelle im ‘Universal Table Format’:
TAG PARENT Customer!1!cid!id Customer!1!name!element Order!2!oid!id1 NULL ALFKI Alfreds Futterkiste NULL2 1 ALFKI NULL O-106432 1 ALFKI NULL O-106922 1 ALFKI NULL O-107022 1 ALFKI NULL O-108352 1 ALFKI NULL O-109522 1 ALFKI NULL O-110111 NULL BOLID Bólido Comidas preparadas NULL2 1 BOLID NULL O-103262 1 BOLID NULL O-108012 1 BOLID NULL O-10970
Spielt keine Rolleim explicit-Modus
Interoperable Informationssysteme - 91Klemens Böhm
Generierung von XML aus SQL-Queryergebnissen (4)
Erläuterungen zu eben: Jede Zeile wird ein Element. Elementname ergibt sich aus Name der Spalten;
Einzelheiten werden ausgelassen. Query, die Tabelle erzeugt, mit UNION.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
- Einleitung
- SQL-bas. Mechan.
- XML- Sichten + Zugriff
- XMLDB
Interoperable Informationssysteme - 92Klemens Böhm
Templates (1) XML-Dokument,
das parametrisierte Anfrage enthält, Kann z.B. angestossen werden
über action-Attribut eines form-Elements. Anfrage selbst – im wesentlichen
gleicher Mechanismus wie bisher. Beispiel:
<root xmlns:sql="urn:schemas-microsoft-com:xml-sql" sql:xsl="path to XSLT file" > <sql:header> <sql:param name="state">WA</sql:param> </sql:header> <sql:query> Hier eine Anfrage mit Zeile … And Region LIKE @state … </sql:query></root>
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
- Einleitung
- SQL-bas. Mechan.
- XML- Sichten + Zugriff
- XMLDB
Interoperable Informationssysteme - 93Klemens Böhm
Templates (2) Beispiel für Einbindung Template –
Parameter über Formular:
<html><body><form name="protokoll" action="http://dbspc15/sitzungen/templates/insert_Template.xml" method="POST"><input type=hidden name="contenttype" value="text/xml"><textarea name="state" cols=70 rows=30></textarea><br><input type=Submit value="Submit"></form></body></html>
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
- Einleitung
- SQL-bas. Mechan.
- XML- Sichten + Zugriff
- XMLDB
Interoperable Informationssysteme - 94Klemens Böhm
XML Sichten mit Annotated Schemata
XML-Data – Microsoft-Pendant zu XML Schema. Annotationen –
definieren Beziehungen zwischen Elementen. Erläuterung des folgenden Beispiels –
Struktur der erzeugten Dokumente:<Customer ID=…>
<Order OrderID=…/></Customer>
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
- Einleitung
- SQL-bas. Mechan.
- XML- Sichten + Zugriff
- XMLDB
Interoperable Informationssysteme - 95Klemens Böhm
XML Sichten mit Annotated Schemata – Beispiel
<?xml version="1.0" ?><Schema xmlns="urn:schemas-microsoft-com:xml-data" xmlns:sql="urn:schemas-microsoft-com:xml-sql">
<ElementType name="Customer" sql:relation="Customers">
<AttributeType name="ID" /> <attribute type="ID" sql:field="CustomerID" /> <element type="Order"> <sql:relationship key-relation="Customers" key="CustomerID" foreign-relation="Orders" foreign-key="CustomerID"/> </element></ElementType>
<ElementType name="Order" sql:relation="Orders"> <AttributeType name="OrderID" /> <attribute type="OrderID" sql:field="OrderID"/></ElementType></Schema>
unterschiedliche Namen!
Interoperable Informationssysteme - 96Klemens Böhm
Unterschiede zur Standard XPath-Semantik ‘any-match’ statt ‘first-match’
(angeblich nicht abbildbar auf RDBMSe), keine stringint Coercion,
Beispiel für Verwendung: http://domainserver/dbvroot/schema/CustOrd.xdr/Customer[@ID=‘ALFKI’] CustOrd.xdr –
Name des Annotated Schemas von vorangegangener Folie,
Pfadausdruck ‚ Customer[@ID=‘ALFKI’]‘ wird angewendet auf erzeugtes XML-Dokument.
XPath-Derivat für Zugriff auf XML Sicht
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
- Einleitung
- SQL-bas. Mechan.
- XML- Sichten + Zugriff
- XMLDB
Interoperable Informationssysteme - 97Klemens Böhm
Relationale Sicht auf XML Daten
Anwendung: Einfügen von XML in RDBMS, OpenXML Rowset Provider –
erzeugt Tupel aus XML Dokumenten, edge-table view vs. shredded-rowset view. Shredded-rowset view:
XPath-Ausdruck identifiziert Knoten, die zu Tupeln werden.
Motivation
DataGuide
PAT-Trees
Algebra
Mehrstufig-keit
STORED
CombinedIndices
HyperStorM
SQL-Server
- Einleitung
- SQL-bas. Mechan.
- XML- Sichten + Zugriff
- XMLDB