Post on 06-Apr-2016
transcript
1
StatiX: Making XML Count
J.Freire, J.R.Haritsa, M.Ramanath, P.Roy, J.Siméon:StatiX: Making XML Count ACM SIGMOD, June 2002
Ann Früchtl16.12.2005
2
Inhalt
Problemstellung Beispiel StatiX System Architektur Wert- / Struktur-Histogramme Kardinalitätsabschätzung XML Schema Transformer Schema Normalisierung Experimente Ausblick / Kritik
3
Problemstellung
Problem: Entwicklung effizienter und präziser Schätzverfahren für XML Anfrageergebnisse
erlaubte Flexibilität beim Definieren von Elementen im XML Datenmodell führt zu ungleichverteilter Struktur Annahme von Gleichverteilung führt zu sehr großen Fehlern
breite und tiefe XML-Dokumente multi-way joins ungenaue Schätzungen durch Fehlervermehrung
4
Problemstellung
welche Statistiken(3.) benutzen um Kardinalität zu schätzen?
welchen Algorithmus(4.) benutzen, wenn 1.-3. gegeben?
4. AlgorithmusAnfrage Kardinalität des
Ergebnisses
1. XMLDokument
2. XMLSchema
3. Statistiken
5
Beispiel Schema
6
Beispiel Dokument
<imdb><show> <!--ID=1--> <title> ... </title> <year> 1993 </year> <aka> ... </aka> <!--ID=12--> <review> ... </review> <!--ID=30--> <review> ... </review> <!--ID=31--> <review> ... </review> <!--ID=32--> <review> ... </review> <!--ID=33--> <box_office> … </box_office></show><show> <!--ID=2--> <title> ... </title> <year> 1994 </year> <seasons> ... </seasons> <review> ... </review> <!--ID=34--> <episode> <aka> ... </aka> <!--ID=13--> </episode></show><show> <!--ID=3--> <title> ... </title> <year> 1990 </year> <seasons> ... </seasons> <review> ... </review> <!--ID=35--> <episode> <aka> ... </aka> <!--ID=14--> <aka> ... </aka> <!--ID=15--> </episode>
<episode> <aka> ... </aka> <!--ID=16--> </episode> <episode> <aka> ... </aka> <!--ID=17--> <guest_director> ... </guest_director> </episode> <episode> <aka> ... </aka> <!--ID=18--> </episode> <episode> <aka> ... </aka> <!--ID=19--> </episode></show><show> <!--ID=4--> <title> ... </title> <year> 1998 </year> <review> ... </review> <!--ID=36--> <review> ... </review> <!--ID=37--> <box_office> ... </box_office></show><show> <!--ID=5--> <title> ... </title> <year> 2000 </year> <seasons> ... </seasons></show></imdb>
7
Architektur
8
Wert-Histogramm
<imdb><show> <!--ID=1--> ... <year> 1993 </year> ...</show><show> <!--ID=2--> ... <year> 1994 </year> ...</show><show> <!--ID=3--> ... <year> 1990 </year> ...</show><show> <!--ID=4--> ... <year> 1998 </year> ...</show><show> <!--ID=5--> ... <year> 2000 </year> ...</show></imdb>
DEFINE STAT Show { CARDINALITY { 5 } ID_DOMAIN { 1 TO 6 } }
DEFINE STAT Show_year { VALUE_DOMAIN { 1990 TO 2001 } BUCKET NUMBER { 2 } BUCKETS { FROM 1990 TO 1995 COUNT 3, FROM 1995 TO 2001 COUNT 2 } }
Figure 4: Statistics Summary for Movie Data
9
Struktur-Histogramm
<imdb><show> <!--ID=1--> ... <review> ... </review> <!--ID=30--> <review> ... </review> <!--ID=31--> <review> ... </review> <!--ID=32--> <review> ... </review> <!--ID=33--> ...</show><show> <!--ID=2--> ... <review> ... </review> <!--ID=34--> ...</show><show> <!--ID=3--> ... <review> ... </review> <!--ID=35--> ...</show><show> <!--ID=4--> ... <review> ... </review> <!--ID=36--> <review> ... </review> <!--ID=37--> ...</show><show> <!--ID=5--> ...</show></imdb>
DEFINE STAT Show { CARDINALITY { 5 } ID_DOMAIN { 1 TO 6 } }
DEFINE STAT Review { CARDINALITY { 8 } ID_DOMAIN { 30 TO 38 } PARENT HISTOGRAM Show { BUCKET NUMBER { 3 } BUCKETS { FROM 1 TO 2 COUNT 4, FROM 2 TO 3 COUNT 1, FROM 3 TO 5 COUNT 3 } } }
Figure 4: Statistics Summary for Movie Data
10
Kardinalitätsabschätzung (1)
Beispielanfrage:FOR $s in document(``myshows.xml´´)/show,
$r in $s/reviewWHERE $s/year < 1992RETURN $r
XPath-Ausdruck:/show[year<1992]/review
11
Kardinalitätsabschätzung (2)
Kardinalitätsabschätzung unter der Annahme der Gleichverteilung innerhalb der Buckets:
Anzahl der Jahre in Bucket 1: 5 (1990-1994)3 Einträge gleichverteilt auf 5 Jahre:2 Jahre sind <1992
2.1532 : )_(1992_ yearShowCard yearShow
JahrEintrag
53
12
Kardinalitätsabschätzung (3)
verteile auf den Bereich Show:
yearShowCard _
1.2) : 6-[1 : ShowKey
13
Kardinalitätsabschätzung (4)
8 Reviews verteilt auf 5 Shows
(Der genaue Wert ist 1.)
22.158 : ) )Review(( Review ShowKeyparentHistfreqCard
ShowReview
58
14
XML Schema Transformer
Durchführung diverser Transformationen zur Normalisierung
Anpassung der Granularität des „statistics gathering process“ an die Anforderungen individueller Anwendungen(feinere Granularität vs.höhere Laufzeit, höherer Speicherplatz)
15
XML Schema Transformer
union distribution
Mehrdeutigkeit verursachende Transformation!
16
Schema Normalisierung
erstelle neue types für alle tags, die wiederholt werden oder optional sind (outline types):
(inline types wäre Rückrichtung, aber nicht Teil derNormalisierung)
17
Schema Normalisierung
erstelle neue types für alle komplexen Strukturen, die innerhalb von Vereinigungen und Wieder-holungen vorkommen (ebenfalls outline types):
18
Experimente
Datensätze: XMark benchmark 10MB, 50MB (tief verschachtelte
Dokumente) ( Internet Movie Database (IMDB; hauptsächlich
flache Struktur) )
Experimente: Bauzeit Größe Genauigkeit
19
Bauzeit
10MB 50MBTwigs preprocessing 10 min > 1 h
phasebuilding 90 sec 450 secphase
StatiX parsing, validation, 70 sec 500 sec(worst case) statistics collection
20
Größe
bsize : Implementationctypes : Tuning-Parameter durch Transformationenbtypes : Tuning-Parameter durch Transformationennbuckets : Tuning-Parameter beim Anlegen der
Histogramme
j jjj
i iii
bsizenbucketsbtypesbsizenbucketsctypessummary
21
Genauigkeit
22
Ausblick / Kritik
XML Schema muss vorhanden sein Im Moment unterstützt StatiX nur verzweigte Pfad-
ausdrücke mit Wertprädikaten Unterstützung von Aggregatfunktionen und Rekursionen beabsichtigt
Bei Updates hängt die Effektivität von StatiX stark von der Qualität der vom System generierten OIDs ab (ID Ranges u.U. nicht mehr kompakt)
nicht bekannt, welche Transformationen ausgeführt werden müssen, um optimale(n) Platz/Bauzeit/Granulärität zu erhalten