Efficiently Publishing Relational Data as XML Documents

Hauptseminar: Datenbanksysteme und XML

Dennis Säring

Inhaltsverzeichnis

1.      Motivation

2.      kurze Wiederholung von XML

3.      Ein Beispiel kurz erläutert mit Quellcode belegt

4.      Ausführliche Vorstellung der Alternativen

5.      Beurteilung der Effizienz aller Alternativen

6.      Abschließender Kommentar und Ansätze für die

Zukunft

7.      Referenzen

8.      Diskussion

1. Motivation & Einführung

XML als kommender Standard, Daten im WWW zu veröffentlichen

Relationale Datenbanken als Industriestandard

Suche nach einer Lösung relationale Daten

in XML – Form zu konvertieren

Was wird dazu benötigt ?

I. SpracheSprache für die Spezifizierung der Konvertierung von rel. Daten in XML

II. Eine effiziente ImplementationImplementation dieser Konvertierung

2. Wiederholung XML Semistrukturiert

Tags kennzeichnen Elemente

Elemente sind geschachtelt angeordnet

<customer id=“C1“> <name> John Doe </name>

<accounts>

<account id=”A1”> 1894654 </account> <account id=”A2”> 3849342 </account> </accounts>

<porders> <porder id=”P01” acct=”A2”> // first purchase order <date> 1 Jan 2000 </date>

<items> <item id=”I1”> shoes </item> <item id=”I2”> bungee ropes </items> </items>

<payments> <payment id=”P1” due Jan 15 </payment> <payment id=”P2” due Jan 20 </payment> <payment id=”P3” due Feb 15 </payment> </payments>

</porders> <porder id=”P02” acct=”A1”> // second purchase order … </porder></customer>

Beispiel

Customer ( id integer, name varchar(20) )

Account ( id varchar(20), custId integer, acctnum integer )

PurchOrder ( id integer, custId integer, acctId varchar(20), date varchar(10) )

Item ( id integer, poId integer, desc varchar(10) )

Payment ( id integer, poId integer, desc varchar(10) )

3. Einstieg

Verwendung der bestehenden SQLanguage

Verschachtelung durch SQL-Struktur

Konstruktion von Tags durch SQL-Funktionen

Verschachtelte Struktur

XMLAGG konkateniert XML Elemente

Verwendung von XML Konstruktoren

XML-Konstruktor

Parameter werden in festgelegte Tags eingebunden

4. Alternativen der KonvertierungKlassifizierung der Alternativen

Ort der Berechnung ( inside / outside )

Geschachtelte Struktur erstellen ( structuring )

Tags müssen erstellt werden ( tagging )

Early Tagging, Early Structuring

Stored Procedure (outside engine)

Feste Ordnung beim join ( schlecht )

Zu viele SQL-queries nötig ( overhead )

Iterative Schachtelung aller in Relation stehenden Elemente

Startpunkt: root-Element

Verwendung vieler queries umgehen, indem nur noch eine große query erstellt wird ( siehe Bsp. )

Correlated CLOB ( inside )

Feste Zuordnung ( correlated ) erfordert Schleifen

zur Schachtelung

XML Fragmente werden als CLOBs

( Character Large Objects ) gespeichert ( teuer )

Grafik: correlated CLOB

keine feste Zuordnung

De-Correlated CLOB ( inside)

auch Speicherung in CLOBs

Verwendung von outer joins

Outer Join 2 od. Mehrere Tabellen werden durch einen Join

zusammengefaßt

Elemente die nicht der join-condition nicht entsprechen

werden:

Inner Join

left / right Outer Join

full Outer Join ( Outer Join )

Grafik: de-correlated CLOB

Late Tagging, Late Structuring

Erstellen der relationalen Daten ( content creation )

Strukturieren und Tags schreiben

( structuring / tagging )

Unterteilung in 2 wesentliche Prozesse

Zusammenfügen aller tables ( join all )

Content Creation: Redundant RelationRedundant Relation

Multiplikative Vergößerung ( schlecht )

Man erhält redundante Daten

Verwendung redundanter Prozesse

Ast wird separat geführt, keine Daten vom Nachbarn

Content creation: Outer Union ( unsorted )

Nicht immer einheitliche Größe

Immer noch Redundanz ( parent Daten )

Zusammenführung aller Daten am Ende

Path - outer - union Es wird am Pfad entlang entwickelt Wiederholung von parent - Daten ( s.o. )

PATH - NODE

Node - outer - union Parent Daten direkt ins outer union schreiben große Anzahl an Tupeln

Grafik: Path Outer Union

Grafik: Node Outer Union

hash-basierter Tagger

Gruppierung der Elemente mittels Hash-Tabellen

Effizient bei genügend Speicher

Tupel lösen und Tags setzten

Structuring/Tagging

Grafik: Hash - Tables

Customer ( ID,Typ)PurchaseOrder ( custID,Typ)

Account ( custID,Typ)Item ( PoID,Typ)

Payment ( PoID,Typ)

HashTable (Customer)HashTable (PurchaseOrd)HashTable (root)

??? ( AcctID,Typ)

HashTable (Account)

??? ( AcctID,Typ)

??? ( AcctID,Typ)

hashing

tagging

Tupel lösen und Tags nach Typ setzten

Late Tagging, Early Structuring

Late Tagging, Late Structuring benötigt viel Speicher um effizient zu sein

Sortierung bereits im content creation

Folgende Dinge müssen beachtet werden

Structured content: Sorted Outer Union

Parent Informationen kommen vor den child Infos Alle Informationen eines Knotens gehören

zusammen

Sortierung des path-outer-union Ergebnis

( sortiert nach Ids )

Sorted Outer Union

Outer Union

Order by: custId, poDate, poId, acctId, payId, itemId

( type, custId, custName, acctId, acctNum, poId, poAcct, poDate, itemId, itemInfo, payId, payInfo )

( type, custId, custName, acctId, acctNum, poId, poAcct, poDate, itemId, itemInfo, payId, payInfo )

    

 

Tags werden sofort nach auslesen gesetzt

Tagging Sorted Data: Constant Space Tagger

Platz - konstant in Anzahl der Levels

Nur Parent Id merken um Tag zu schließen

5. Beurteilung der Effizienz

Verwendetes System

DB2

Pentium 366 / 256 MB / Win NT 4.0

alle Funktionen innerhalb der Maschine

Verwendung ausgeglichener Strukturen

Messvorbereitung

Einführung von Parametern

Inside Engine (query fan out)

Outside Engine

Ergebnisse ( inside - outside )

Weitere Test inside the engine !

Was kostet Wieviel ?

Execution

Bind out

Tagging

XML File

Änderung am query fan out

mehr joins

corr CLOB am schlechtesten ( loop joins )

unsorted besser als sorted o-u-plan

Änderung an der query depth

Fehler des rel. Optimierers

Sortierung nach XMLAGG ( CLOB )

Änderung an der number of roots

kaum Auswirkungen

correlated CLOB

Änderung an der number of leaf tuples

(+) Speicher: kaum Auswirkung

(-) Speicher: unsort.o-u => kein Ergebnis

Vergleich path & nodeouter union

(+) Speicher: path outer union

weniger Tupel müssen gebildet werden

(-) Speicher: node outer union

mehr redundante Daten

overhead beim Auslagern

Zusammenfassung der Ergebnisse

Inside the engine ist effizienter Bei genügend Speicher liegen die

Unsorted Outer Union Ansätze vorn Zu wenig Speicher: Sorted Outer Union

Überblick: AlternativenLate TaggingEarly Tagging

LateStructuring

EarlyStructuring

Inside Engine

Inside Engine

De-Correlated CLOB

Out

side

Eng

ine

Stored Procedure

Inside Engine

Out

side

Eng

ine

Sorted Outer Union(Tagging inside)

Sorted Outer Union(Tagging outside)

Unsorted Outer Union(Tagging inside)

Unsorted Outer Union(Tagging outside)

Out

side

Eng

ine

Correlated CLOB

6. Kommentar und Zukunft

Parallelmaschinen Laufzeitoperatoren innerhalb der engine Speicherverwaltung Tagger verbessern ( tiefe Strukturen )