Seminar Datenbanksysteme - Data Warehousing

Approximative Anfrageergebnisse in DWH-Umgebungen durch Wavelet-Kodierung

Dipl.-Math. Mazeyar E. Makoui 27.1.2004

1

Einleitung

• Exakte Abfragen können zu lange dauern (großes Datenvolumen)

• Antworten sollen auch möglich sein, wenn Daten teilweise nicht verfügbar sind. (z. B. bei teilweisem nicht Erreichen einzelner DataMarts)

• Daten sind nicht in geeigneter Form vorhanden (komprimiert, aufwendige Berechnungen)

• Anfragende/r ist an schnellen, ungefähren Ergebnissen interessiert, wenn

• er/sie den Datenbestand erkunden will (OLAP),

• er/sie überprüfen will, ob Anfragen wohlformuliert sind.

2

Weshalb approximative Anfrageergebnisse?

Einleitung (2)

• Ungefährer Wert mit Vertrauensintervall,

• Dabei wird eine obere bzw. untere Schranke angegeben.

Beispiele:

• Durchschnittliche Verkäufe von DVD-Playern der Marke Sony in Deutschland im Jahr 2003: 400.000 +/- 2000

• Anzahl von Einbrüchen in der Universität Hannover im Jahre 2001 <= 100

Ergebnisse von Aggregatsfunktionen wie avg, sum und count erfordern nicht immer volle Präzision, sind also ideale Kandi-daten für Approximationen.

3

Was ist überhaupt eine approximative Antwort ?

Standardverfahren zur Approximation

1) Equi-Width-Histogramme

• Breite aller Buckets sind gleich

2) Equi-Depth-Histogramme

• Tiefe aller Buckets (Summe der Häufigkeiten) sind überall gleich

Probleme bei Standard Histogrammen:

• ungeeignet für viele Dimensionen,

• keine Antwortverfeinerung,

• Genauigkeit der Approximation könnte noch besser sein,

• verhältnismäßig lange Antwortzeiten für die Abschätzungen.

Lösung:Wavelet-Kodierung

4

Definition Wavelets

• Signalverarbeitungstechnik zur Reduktion eines D-dimensionalen Signals,

• Idee: „Vereinfachung“ des Signals, indem man „Ausreißer“ ausgleicht, ohne das Gesamtbild zu beeinträchtigen.

Zerlegung des Data Cubes in Wavelet-KoeffizientenDecomposition

Ranking an Threshholding

Reconstruction Nur die wichtigsten Koeffizienten werden berücksichtigt.

Aus den wichtigsten k Koeffizienten wird approxima- tive Antwort rekonstruiert, k je nach verfügbarer Zeit.

Phasen der Wavelet-Kodierung:

5

1D Decomposition

Zusammenfassung zweier Standorte durch Mittelung der beiden Lagerbestände z.B.:

(E + F)/2 = (3 + 5)/2 = 4

A B C D E F G H

0

1

2

3

4

5

6

Ausgangsdaten Lagerbestand am Ort X

AB CD EF GH

0

1

2

3

4

5

1. 1D-Decompostion Lagerbestand am Ort X

ABCD EFGH

0

1

2

3

4

5

2. 1D-Decompostion Lagerbestand am Ort X

6

1D Decomposition (2)

Auflösung Werte Detail-Koeffizienten

8 / l = 3 [2,2,0,2,3,5,4,4]4 / l = 2 [2,1,4,4] [0,-1,-1,0]2 / l = 1 [1.5,4] [0.5,0]1 / l = 0 [2.75] [-1.25]

Decomposition S = [2.75,-1.25,0.5,0,0,-1,-,1,0]

Ausgangsdaten A = [2,2,0,2,3,5,4,4]

• noch kein Informationsverlust,• gleiches Datenvolumen wie Ausgangsdaten,

7

Query-Evaluierung

8

Exakte Evaluierung der Anfrage:

2.75

0

0-1

0.5

-10

-1.25

S'(1)

S'(0)

S'(2) S'(3)

S'(4) S'(5) S'(6) S'(7)

2 0 2 3 5 4 42

Mittel

Stufe 1

Stufe 2

Stufe 3

Stufe 4

• plus, wenn in linker Hälfte • minus, wenn in rechter Hälfte

Bsp.:

S(3) = S'(0) + S'(1) – S'(2) – S'(5) = 2.75 + (- 1.25) - 0.5 - (-1) = 2

S(0) S(1) S(2) S(3) S(4) S(5) S(6) S(7)

Query Evaluierung (2)

Beispiel: Summe (2:5) = 4 *S'(0) – 2 *S'(2) + 2 *S'(3)

S(0) = S'(0) + S'(1) + S'(2) + S'(4)S(1) = S'(0) + S'(1) + S'(2) - S'(4)S(2) = S'(0) + S'(1) – S'(2) + S'(5)S(3) = S'(0) + S'(1) - S'(2) - S'(5)S(4) = S'(0) - S'(1) + S'(3) + S'(6)S(5) = S'(0) - S'(1) + S'(3) - S'(6)S(6) = S'(0) - S'(1) - S'(3) + S'(7)S(7) = S'(0) - S'(1) - S'(3) - S'(7)

Die Koeffizienten „weiter hinten“ haben einen viel kleineren Einfluß auf die Summe und heben sich „oft“ sogar auf.

Heuristik: Reduktion der Datenmenge durch Weglassen der hinteren Koeffizienten

9

Alternative Kodierung der Koeffizienten

Mit bisheriger Darstellung geht die „Bedeutung“ der Koeffizienten aus der Position hervor.Decompostion S = [2.75,-1.25,0.5,0,0,-1,-,1,0]

Alternative Darstellung ohne diese Eigenschaft:

S'= {(4,0),(7,0),(5,-1),(1,-1.25),(3,0),(0,2.75),(6,-1),(2,0.5)}

(4,0) = (S(4), Wert = 0)

S''= {(3,0,0),(3,3,0),(3,1,-1),(1,0,-1.25),(2,1,0),(0,0,2.75),(3,2,-1),(2,0,0.5)}

(3,0,0) = (Stufe 3, Position 0, Wert = 0)

10

Komprimierung

Bislang kein Informationsverlust, aber auch keine Komprimierung.

Komprimierung durch Weglassen weniger „wichtiger“ Koeffizienten, tendenziell die hinteren.

Die wegzulassenden Koeffizienten werden so ausgewählt, daß der „Approximative Fehler“ möglichst klein ist.

Man kann zeigen, daß die Auswahl der größten Koeffizienten (nach einer Normalisierung) den Durchschnittsfehler für alle Anfragen minimiert.

11

2D Decomposition

1) Standard-Decomposition im Mehrdimensionalen- Eine Dimension nach der Anderen betrachten.- Jede „Zeile entlang der Dimension“ gemäß vorgestellten Verfahrens transformieren.

2) Nicht-Standard-Decomposition im Mehrdimensionalen- Dimensionen werden korreliert betrachtet.- Dafür werden neue Berechnunsgvorschriften benötigt.

12

2D Decomposition (2)

3 3 4 3 42 1 2 1 21 3 4 3 40 1 2 1 2

0 1 2 3Ausgangsarray

3 -1 0 -1 02 2,5 -0,5 2,5 -0,51 -1 0 -1 00 2,5 -0,5 2,5 -0,5

0 1 2 31. Decomposition

3 -1 -1 0 02 -1 -1 0 01 2,5 2,5 -0,5 -0,50 2,5 2,5 -0,5 -0,5

0 1 2 31. Neu-Anordnung

3 -1 -1 0 02 -1 -1 0 01 0 0 -0,5 -0,50 2,5 0 -0,5 -0,5

0 1 2 3

2. Decomposition

C(A + B - C – D)/4

D(A - B - C + D)/4

A(A + B + C + D)/4

B(A - B + C – D)/4

13

2D Decomposition (3)

14

3 -1 -1 0 02 -1 -1 0 01 0 0 -0,5 -0,50 2,5 0 -0,5 -0,5

0 1 2 3

2. Decomposition

3 3 4 3 42 1 2 1 21 3 4 3 40 1 2 1 2

0 1 2 3Ausgangsarray

+

+

+ +

++- --

-

-

+- -+

+-

- - - -

- -- -- -

- -

++ ++

++ ++

+ +

+ +

Berechnungsvorschrift W:=

2D Decomposition (4)

A[0,0] = + W[0,0] + W[0,1] + W[1,1] + W[1,1] - W[0,2] - W[2,2] + W[2,0]

= + 2.5 + 0 + 0 + 0 - (-1) - 0 + (-0.5) = 2.5 - (-1) + (-0.5) = 3

15

+

+

+ +

++- --

-

-

+- -+

+-

- - - -

- -- -- -

- -

++ ++

++ ++

+ +

+ +

Berechnungsvorschrift W:=

3 -1 -1 0 02 -1 -1 0 01 0 0 -0,5 -0,50 2,5 0 -0,5 -0,5

0 1 2 3

2. Decomposition

0

1

2

3

0 1 2 3

Repräsentation der Koeffizienten

Wie kann man die Koeffizienten abspeichern?

• Verallgemeinerung des eindimensionalen Falles

• Größe und Position des Quadrates

• „Muster“ (vier im zweidimensionalen Fall; Muster/Farbe stehen für die „Art der Verrechnung“)

• Wert

16

Wavelet-Repräsentationen einer Relation

1) Attribute werden zu Dimensionen,

2) Zahlen werden zu entsprechenden Anzahl an Tupeln,

3) Danach folgt die bekannte Wavelet-Decomposition, wie eben beschrieben.

Kunden-ID Alter Einkommen KontostandHS31 62 52000 -2000AS36 39 55000 15000

...

Alter

Kontostand

Einkommen

17

Query-Processing

● Herkömmliches relationales Query-Processing:✔ Mengen von Tupeln (Tabellen),✔ Algebra-Operatoren, die aus (einer oder mehreren)

Tabellen neue Tabellen erzeugen.● Jetzt:✔ Mengen von Koeffizienten (natürlich nur die wichtigsten),✔ Gleiche Algebra-Operatoren wie in der rel. Algebra und Aggregationen,✔ Algebra-Operatoren erzeugen aus einer bzw. mehrerer Menge(n) von Koeffizienten neue Menge.

18

Query-Processing (2)

Illustration am Beispiel des Select-Operators:

19

+

+

+ +

-

-- -

D1

D2

+-

D1

D2

+-

Tests

Verfahren Anzahl von Koeffizienten500 1000 2000 5000

Wavelets 0.01s 0.02s 0.04s 0.08sHistogramme 0.98s 1.48s 0.43s 1.26sFaktor 98 74 11 16

Umgebung: Sun Ultra-2/200 MHz, 512 MB RAM, Solaris 2.5.1

Anfrage: Select-Join-Sum, Dauer der exakten Anfrage 3.6s,Anfrage paßte komplett in den Hauptspeicher

20

Literatur

• Kaushik Chakrabarti et al. Approximate Query Processing Using Wavelets Proceedings of the 26th VLDB Conference, Cairo, Egypt, 2000.

• J.S. Vitter, Min Wang. Multidimensional Aggregates of Sparse Data Using Wavelets Proceedings of the 1999 ACM SIGMOD

• Data Warehousing and Mining Vorlesung SS 2002 Prof. Dr.-Ing. Klemens Böhm Otto-von-Guericke-Universität Magdeburg

21

Questions?

22