VL 2.3 XML-Speicherung 1+2 [Ausstehend]

Question 1

[mP] Was ist das EDGE Modell? Warum stellt es uns nicht zufrieden?

Answer 1

Idee:

Speicherung der hierarchischen semistruktuierten Daten (XML) als Knoten und Kanten auffassen und in Relationen speichern Jeder Kante und jeder Knoten wird als ein Tupel der Datenbank repräsentiert!

Vorteil:

• • funktioniert Kontextunabhängig
• • einfach

Nicht zufriedenstellend weil:

• Daten, die rein logisch zusammen gehören sind i.d.R. physisch verteilt
  
  • Informationsbedürfnis in einer logisch und physisch zusammenhängenden Relation viel einfacher abzufragen!
  • hier: auf mehrere Relationen verteilt ⇒ vieleJoins nötig usw.

Question 2

[mP] Wieso ist es vorteilhaft, die Struktur eines Dokumentbestands für die Speicherung/ für die Evaluierung von Anfragen zu kennen?

Answer 2

(1) ggf. nur DataGuide nötig (bei VolltextAnnotation)

Anfragen können z.b durch Annotations-Verweise nur mit Hilfe des DataGuide abgearbeitet werden können

Für manche Anfragen nützlich.

(2) Existenz + Häufigkeit

• Existiert überhaupt ein Pfad von nach? = Optimierung; da man sich möglicherweise weitere Zugriffe spart + Annotation von Pfaden möglich
• ⇒ wie häufig kommen diese Pfade im ursprungsdokument vor! Hilfreich für (Count Anfrage) ⇒ Ich kann in Dataguide nachschauen und muss nicht den eigentlichen Datenbestand anschaune

(3) Beschleunigung

Darüber hinaus können wir die DG-Informationen nutzen um die Anfrage auf den tats. Datenbestand zu beschleunigen (Knoten1 vokommen 2 Knoten2 Vorkommen 2000) ⇒ Auswertungreihenfolge kann so optimiert werden (erst k1 auswerten)

Question 3

[mP] Was für unterschiedliche DataGuides kennen Sie?

Answer 3

Es kann zu einem Datenbestand mehrere Dataguides geben

Unterscheidung Minimale und Strong DataGuides

im folgenden Definition Strong DataGuides

Probleme von minimalen DG

• Einfügen von Knoten
  
  • Pfade, werden ggf. erschaffen, die es im Ausgangsdokument nicht gibt!
• Annotationen:
  
  • Zugehörigkeit nicht mehr aufschlüsselbar

Erinnerung

• TargetSet: Menge der Knoten dei ich erreiche, wenn ich entglang diese Label Path nach unten steige
  
  • ⇒im allgemeinen gibt es in eienr Datenbank mehrere Vorkommen eines Label Path. D.h. in einer DB kann diese Target Set beliebig groß sein!
  • ⇒In DataGuide ist es hingegen so, dass es von jedem Pfad nur 1 Vorkommen gibt. D.h. ein Target Set eines Label Path ist immer einelementig

Annotationen maximal präzise in strong DG

Informale DEF

Motivation: Charakterisierung der DataGuides, deren Annotationen maximal präzise sind.

Intuition: Label paths mit dem gleichen
Target Set im DataGuide haben stets das gleiche Target Set in der Datenbank.

⇒ D.h. wir kommen über die gleichen Pfade nicht bei neuen Knoten in Dataguide raus

Formale DEF:

L_s(l) = ist die Menge aller label paths mit dem gleichen Target Set wie l.

L_d(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)

Also wenn das nicht der Fall ist:

Im dataguide führen die Label Path zu gleichen Knoten im Datanbestand aber zu unterschiedlichen, dann ist die wünschendswerte Eigenschaft, dass Annotationen von DataGzuides maximal präzise sind nicht gegeben

Würdem wir Knoten 20 (rechts) Annotieren, hätten wir ein Problem

• wie werden die 20 zwischen den Pfaden aufgeteilt?

Question 4

[mP] Warum ist das Konzept der Subsuming Queries im XML-Kontext von Interesse?

Answer 4

Subsuming Query: Eine Query ist Subsuming Query für eine andere Query,

• Wenn sie stets eine Obermenge (Des Teils des Datenbestands an dem wir eigentlich interessiert sind) des Ergebnisses der anderen Query zurückwirft

select * from Person where salary > 50.000 (Subsuming Query, da Ergebnis OM der anderen)

subsumiert

select * from Person where salary > 100.000

Subsuming Q ⇒ kann für meherer Anfragen Subsuming Query sein

select * from Person where salary > 50.000

subsumiertauch

select * from Person where salary > 50.000 and name=”Boehm

¡Jetzt ist man nicht nicht an der Obermenge interessiert, sondern man will das exakte Ergebnis, deshalb gibt es als 2 Konzept das der

Filter Query

d. h. wenn QF auf das Resultat von QS angewendet wird, ist das Ergebnis das gleiche, wie wenn Q evaluiert wird.

Beispiel:

Q: select * from Person where salary > 50.000 and name=”Boehm”

QS: select * from Person where salary > 50.000

QF: select * from QS where name=”Boehm”

Quasi eine Aufteilung und Schrittweises Anwenden

Zur eigentlichen Frage:

Ansatz vorteilhaft, wenn

• Volltext-Engine viel schneller als XML Query Engine,
• und Zwischenergebnis deutlich kleiner als Ausgangskollektion.

Im Beispiel sind Query und Filter Query identisch.

Bild!

Question 5

[mP] Wie kann man die Zahl der Index-Einträge reduzieren (für den Fall, dass es mehrere Indices gibt)?

Answer 5

Die Zahl der Indices, die Möglich sind wenn wir Relationen mit vielen Attributen haben, schnell sehr groß wird!

• Index für mehrere Attribute möglich.
• Index für (gpa, name) nicht dasselbe wie für (name, gpa).
• Wächst mindestens exponentiell (ist Attr teil des Index oder nicht? und die Anordnung macht noch einen Unterschied)
• ⇒(Mehr als) n! mögliche Indices. (wg. der Anordnung daher n!)

⇒Wir lassen bestimmte Index-Einträge einfach weg und wenn eine Anfrage daher kommt schauen wir in der Datenbank nach warum wurden die Index-Einträge weggelassen!

Lösung: (1 Index)

• Wir überlegen uns nur bestimmte Attributwerte zu indexieren
  
  • Bsp. Wir erzeugen nur Indexeinträge für die Tupel, wenn die Note der Studenten 1 oder 2 ist

Combined

Bsp 1

Beobachtung 1: Alle heißen mit Vornamen ‘Frodo’ ⇒ Index-Eintrag nicht hilfreich, Scan genauso teuer. Illustration auf folgender Folie.

Hier sinnvollder rüber realen Datenbestand zu suchen als jede Index-Seite anschauen zu müssen

Ich kann Index-Einträge weglassen, wenn ich bereit bin vergleichsweise kleine konstante Kosten bei der kombinierten Anfrage auf mich zu nehmen

Beobachtung 4 (Fortsetzung): q – Verhältnis der Anzahlen (im Beispiel 999/1000). Je kleiner q, desto größer die Platzeinsparung, geringfügiger die Beschleunigung beim Indexzugriff.

Question 6

[mP] Erklären Sie den STORED-Ansatz. Geben Sie ein Beispiel für eine Anfrage, deren Evaluierung der STORED-Ansatz unterstützt, ein DataGuide jedoch nur unwesentlich.

Answer 6

da

Question 7

[mP] Sehen Sie einen Zusammenhang zwischen Subsuming Queries und STORED?

Answer 7

da

Question 8

[mP] Warum eignet sich der XPath Accelerator für Realisierung mit RDBMS Technologie?

Answer 8

da

Question 9

[mP] Umsetzung des XPath Accelerators nach SQL wiedergeben können.

Answer 9

da

Question 10

[mP] Eine Optimierung des XPath Accelerators erklären können

Answer 10

da

Question 11

[Prüfung]Was ist Dataguide?

Was ist der Unterschied von DataGuide und Schema?

⇒ Kein Schema(im Vorhinein), sondern nachträgliche Zusammenfassung

Wie helfen sie bei der Evaluierung von Anfragen?

Wie hilft uns der DataGuide beim Query Processing?

⇒ Für manche Anfragen nützlich. Existiert überhaupt ein Pfad von nach? = Optimierung; da man sich möglicherweise weitere Zugriffe spart + Annotation von Pfaden möglich ⇒ wie häufig kommen diese Pfade im ursprungsdokument vor! Hilfreich für (Count Anfrage) ⇒ Ich kann in Dataguide nachschauen und muss nicht den eigentlichen Datenbestand anschaune

Darüber hinaus können wir die DG-Informationen nutzen um die Anfrage auf den tats. Datenbestand zu beschleunigen (Knoten1 vokommen 2 Knoten2 Vorkommen 2000) ⇒ Auswertungreihenfolge kann so optimiert werden (erst k1 auswerten)

Answer 11

Def:

• (1) Genau die Pfade, die im Ausgangsdokument vorhanden sind, sind auch im DataGuide vorhanden
• (2) Es gibt im DataGuide keine Pfade, die nicht im Ausgangsdokument existieren!

Ideein Form des Dataguides hat man eine Kompakte Zusammenfassung des Datenbestands

DataGuide ist selbst wieder Instanz von OEM z.b ⇒ Vorteil weiterverwenbarkeit der Werkzeugen

In diesem Kapitel: Datenbank ⇔ Dokument-Kollektion bzw. einzelnes Dokument; Datenbank ist gerichteter Graph (OEM-Instanz).

Kompakt bedeutet:

• 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 Datenbank (⇒ Speicherung und Zugriff auf DataGuides mit den gleichen Mechanismen möglich.)

Definition: Ein DataGuide d einer Datenbank s ist selbst wieder Datenbank, 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.

• Unterschied zwischen DataGuide und Schema: DataGuide ist konform zur Datenbank, nicht umgekehrt.
• Denkbar, dass DataGuide und Schema nicht übereinstimmen – nicht alle Varianten, die Schema erlaubt, kommen tatsächlich vor. Beispiel hierfür[grüne Frage]?

Question 12

[mP] Was für Alternativen sehen Sie, um DataGuides zu annotieren? Was bringen die einzelnen Annotationsarten? Geben Sie Beispiele für Anfragen, deren Evaluierung unterstützt/nicht unterstützt wird.(Es gibt 3 Annotations Varianten)

Answer 12

Trade off:

basic Annotation (einzelne Zahlen) ⇔ umfangreiche Annotation (Verweise/volltext-Index)

Bsp: Gib mir alle Instanzen des Pfads “Restaurant–>Entree”

Lösung: Variante 2 einfach Verweise zurückgeben!

D.H. ⇒ Version mit den Verweisen deutlich ausdrucksmächtiger, da durch die Rückgabe der Liste von Verweisen manche Anfragen nur mit Hilfe des DataGuide abgearbeitet werden können!

+ Suche von Bottom up möglich in DG. Suche Entree = “Lamm” –> Einstieg in Blattknoten in DG und man hat die 3 Verweise!

vs. 3 (n) mal von Wurzel zu Entree im Datenbestand

Variante 3: Volltext-Index. (alles oben gilt auch hier noch besser)

Keine Unterstützung: Beispiele für Anfragen, die nicht allein mit DataGuide/Annotationen beantwortbar?

• Es kommt darauf an wie die Datenbank implementiert ist
  
  • Möglich, dass man nur von Wurzel an Kanten nach unten Steigen darf
  • ⇒ DataGuide hilft hier nichts!
• Es werden nur Pfadausdrücke unterstützt. Sind wir an Mustern interessiert, die keine Pfade sind, stößt man an Grenzen (TelfeonNr aller Restaurants, die jetzt als Entree Lamm Haben) (also 2 Knoten hier) –> Entree gefunden, dann hochsteigen und wieder runter. ⇒ Lässt sich nicht allein mit Hilfe des DG und seiern Annotation bewerkstelligen

Gut für Anfragen die sich nur auf Pfadausdrücke beschränken

Question 13

1. Welcher Zusammenhang zwischen relationalen Datenbanken einerseits und DataGuides andererseits?
2. Wie kann man relationale Datenbank bei der Implementierung von DataGuides verwenden?

Answer 13

(1)Wie kann man hier relationale datenbanken hier verwenden?

Lassen wir die Annotationen weg, handelt es sich hier um eine Kompakte darstellung des Datenbestands. D.h. selbst wenn wir hierfür das EDGE Modell (Aufteillen in Relationen Knoten,Kanten) ist der DataGuide relativ klein und im Hauptspeicher weil er so kompakt ist.

Also Vorschlag:

• DataGuide selbst entweder im Hauptspeicher oder (gemäß EDGE-Modell) auf Relation abbilden.

Problem ist die Darstellung der Annotationen

• ⇒Lösung : Annotationen auch als Relationen speichern
  (2) Kein Problem den DataGuide an sich kann man so speichern wie es das EDGE-Modell vorgesehen hat