2 - The Database Research Group

Kap. 13 Data Warehouse
13.1 Was ist ein Data Warehouse, Motivation?
13.2 Data Cube und SQL- Operationen
13.3 Cube Operationen
13.4 Physischer Entwurf, Implementierung von Cubes
OHO2002
Kap13-1
13.1: Was ist Data Warehousing, Motivation
•
Zugriff auf und Kombination von Daten
aus mehreren unterschiedlichen Quellen,
Quelle
•
•
Quelle
Quelle
komplexe Datenanalyse über mehrere Quellen,
multidimensionale Sichten auf die Daten,
die die jeweilige Perspektive reflektieren,
Analyse der zeitlichen Entwicklung,
auch wenn Datenquellen
sich auf aktuellen Datenbank-Zustand beschränken.
OHO2002
Kap13-2
Daten Analyse (J. Gray)
• Benutzer extra-
hiert Daten mit
Anfrage aus der
Datenbank
Spread Sheet
Table
• Dann werden
Daten analysiert
und visualisiert
mit Desktop
Tools
OHO2002
1015
Size vs Speed
Price vs Speed
104
Cache
Nearline
1
Tape Offline
Tape Main
1012
102
Secondary
Disc
Size(B)
Online $/MB
Online
109 Secondary
Disc Tape 100
Tape
Main
106
Nearline
Tape
Offline
Tape
10-2
Cache
103
10-4
-9 -6 -3 0
3
-9 -6 -3 0
3
10 10 10 10 10
10 10 10 10 10
Access Time (seconds) Access Time (seconds)
Kap13-3
OLTP vs. OLAP
•
OLTP (‘Online Transaction Processing’):
Transaktionsorientierte Datenzugriffe, typischerweise Erfassen
von Daten und Lesezugriffe auf diesen.
“Tagesgeschäft bedienen”
ƒ Beispiel aus dem Bankbereich: “Wie hoch ist mein
Kontostand?”
Beispiele für OLTP-Systeme: Buchungssysteme,
Lagerverwaltung, Aktien-/Wertpapierhandel.
•
OLAP (‘On-line Analytical Processing’):
Konsolidierung, Viewing und Analyse der Daten in mehreren
Dimensionen, Berichtsgenerierung (RPG, Decision Support)
“strategische Entscheidungen unterstützen”
ƒ Beispiel: „Was ist der Zusammenhang
zwischen Kontostand und Häufigkeit von Buchungen?“
„They (the users) don‘t even know what they want!
How can we provide it?“
OHO2002
Kap13-4
Beispieltabelle
Model
Chevy
Chevy
Chevy
Chevy
Chevy
Chevy
Chevy
Chevy
Chevy
Ford
Ford
Ford
Ford
Ford
Ford
Ford
Ford
Ford
OHO2002
SALES
Year
1990
1990
1990
1991
1991
1991
1992
1992
1992
1990
1990
1990
1991
1991
1991
1992
1992
1992
Color
red
white
blue
red
white
blue
red
white
blue
red
white
blue
red
white
blue
red
white
blue
Sales
5
87
62
54
95
49
31
54
71
64
62
63
52
9
55
27
62
39
Kap13-5
Beispiel für einen „Bericht“
Sales Roll Up by
Model by Year by
Color
Model
Chevy
Year
1994
Color
black
white
Sales
by Model
by Year
by Color
50
40
Sales
by Model
by Year
Sales
by Model
90
1995
black
white
85
115
200
290
OHO2002
Kap13-6
Operationale Datenbanken vs. Data Warehouses
Operationale Datenbanken
Data Warehouses
Entstehung
jeweils für Anwendungsmehrere Perspektiven
klasse oder aus bestimmter gleichzeitig
Perspektive heraus
Anforde- Bekannt
vage
rungen
Bedeu- alltägliche
Entscheidungen des
tung
Geschäftsabläufe
Managements, die sich auf
Profitabilität auswirken
DatenEin Aufruf liefert wenige
Grosse Datenmengen werden
zugriff
Zeilen zurück.
zugegriffen, um das Ergebnis zu
ermitteln.
Getuned für eher seltene Zugriffe
Tuning
Getuned für häufige
auf grosse Datenmengen
Zugriffe auf kleine
Datenmengen
Grosser Datenbestand wird für
DatenDatenbestand wird für
statist. Analysen, Vorhersagen,
volumen operationales Geschäft
ad hoc Reports gebraucht.
gebraucht.
OHO2002
Kap13-7
Operationale Datenbanken vs. Data Warehouses
(2)
Operationale DatenbankenData Warehouses
Datensolange es das
aufbeTagesgeschäft erfordert
wahrung
Aktuaauf die Minute
lität
Bedeutung
alltägliche
Geschäftsabläufe
Verfügbarkeit
Hohe Verfügbarkeit
erforderlich.
Entwurfs Hohe Performance
ziel
OHO2002
Langfristig, um Reporting über
Zeiträume oder Vergleiche zu
ermöglichen.
Üblicherweise wird ein
bestimmter Zeitpunkt in der
Vergangenheit beschrieben
Entscheidungen des
Managements, die sich auf
Profitabilität auswirken
Nicht ganz so hoch wie in
Produktionsumgebungen,
abhängig davon, ob weltweiter
Zugriff.
Flexibilität
Kap13-8
Data Warehousing - warum reichen
herkömmliche Datenbank-Konzepte und Technologie nicht aus?
Im Prinzip reichen sie schon, aber:
•
Höheres Abstraktionsniveau durch neue, mächtige
Operatoren vereinfachen die Anwendungsentwicklung,
insbesondere durch:
ƒ Cube,
ƒ Drill-Down,
ƒ Roll-Up.
•
Direkte Optimierungsmöglichkeit der neuen
Operatoren! Abbildung auf Standard-SQL hinsichtlich
der Laufzeit nicht akzeptabel.
OHO2002
Kap13-9
13.2 Data Cube und SQL-Operationen
• Idee: Cube wird aus relationaler
DB gebildet, Vorteil:
ƒ Aggregationen werden nahe
bei den Daten durchgeführt.
ƒ Filterung der Daten gleichzeitig
möglich
• Visualisisierung und Exploration
wird auf dem Daten Cube
durchgeführt
200
150-200
150
100-150
100
50-100
0-50
50
Blue
0
1990
OHO2002
1991
1992
Red
ALL
Kap13-10
Aggregations-Funktionen in relationalen DBMS
• SQL hat Aggregatfunktionen
•
•
•
ƒ sum(), min(), max(), count(), avg()
Viele Systeme erweitern diese um:
ƒ statistische Funktionen, Benutzer
definierte Funktion, ...
Hauptidee:
ƒ Berechne aus allen Werten einer
Spalte einen Skalar.
Syntax
select sum(units)
from inventory;
OHO2002
SUM()
Kap13-11
Relationaler Group By Operator
• Group By erlaubt Aggregation über Teilmengen von
•
•
Tupeln
Resultat ist neue Tabelle, eine Zeile pro Gruppe
Table
Syntax:
attribute
select
location,
sum(units)
from
inventory
group by location
having nation =
“USA”;
OHO2002
A
A
A
B
B
B
B
B
C
C
C
C
C
D
D
SUM()
A
B
C
D
Kap13-12
Probleme mit Standard-SQL
•
Histogramme nötig
•
Teilsummen und
Gesamtsumme gleichzeitig
ƒ drill-down & roll-up reports
F() G() H()
•
Pivot-Tabellen nötig
•
Erkenntnis
ƒ Dies sind keine relationalen
Operationen, aber in vielen
Berichtsgeneratoren
vorhanden
OHO2002
AIR
HOTEL
FOOD
MISC
sum
M T W T F S S
Kap13-13
Einführung eines „ALL“-Wertes
• Warum?
ƒ Eine zu SQL passende Erweiterung, um
Aggregationen wieder als (flache) Tupel im
Relationenmodell darstellen zu können
• Bedeutung des ALL-Wertes?
ƒ ALL ist Abkürzung für Menge, die durch Nestung
entlang der Dimension entstehen würde bei
gleichzeitiger Aggregation, also im Beispiel für die
Mengen
¾{red, white, blue} in der Color-Dimension
¾{1990, 1991, 1992} in der Year-Dimension
¾{Chevy, Ford} in der Model-Dimension
OHO2002
Kap13-14
SQL mit ALL-Erweiterung für Berichte?
Model
Chevy
Chevy
Chevy
Chevy
Chevy
Chevy
Chevy
Sales Summary
Year Color Units
1994 black
50
1994 white
40
ALL
1994
90
1995 black
85
1995 white
115
ALL
1995
200
ALL
ALL
290
OHO2002
SELECT Model , ALL, ALL, SUM(Sal es )
FROM Sal es
W
HERE Model = ' Chevy'
GROUP BY Model
UNION
SELECT Model , Year, ALL, SUM(Sal es)
FROM Sal es
W
HERE Model = ' Chevy'
GROUP BY Model , Year
UNION
SELECT Model , Year, Col or, SUM(Sal es)
FROM Sal es
W
HERE Model = ' Chevy'
GROUP BY Model , Year, Col or;
Kap13-15
Der „Data CUBE Operator“ (J. Gray)
...verallgemeinert den Group By-Operator und die Aggregation
Aggregate
Group By
(with total)
Sum
By Color
RED
WHITE
BLUE
Cross Tab
ChevyFord
Sum
By Color
RED
WHITE
BLUE
The Data Cube and
The Sub-Space Aggregates
CH FOR
EV
D
Y
By Make
Sum
By Year
0
199991
1 992
1 993
1
By Make
By Make & Year
RED
WHITE
BLUE
By Color & Year
Sum
OHO2002
By Make & Col
By Color
Kap13-16
Idee: Tupel = Punkt im N-dimensionalen Raum
•
•
N-dimensionale Aggregation (sum(), max(),...)
¾ a1, a2, ...., aN, f()
¾ übliche Aggregation aus den relationalen Rohdaten
Super-Aggregation über N-1 dimensionale Sub-Cubes
¾ ALL, a2, ...., aN , f()
¾ a3 , ALL, a3, ...., aN , f()
¾ ...
¾ a1, a2, ...., ALL, f()
•
ƒ dies sind die N-1 -dimensionalen Cross-Tabellen.
Super-Aggregation über N-2 dimensionale Sub-Cubes
¾ ALL, ALL, a3, ...., aN , f()
¾ ...
¾ a1, a2 ,...., ALL, ALL, f()
OHO2002
Kap13-17
Cube-Beispiel
SALES
Model Year Color
Chevy 1990 red
Chevy 1990 white
Chevy 1990 blue
Chevy 1991 red
Chevy 1991 white
Chevy 1991 blue
Chevy 1992 red
Chevy 1992 white
Chevy 1992 blue
Ford 1990 red
Ford 1990 white
Ford 1990 blue
Ford 1991 red
Ford 1991 white
Ford 1991 blue
Ford 1992 red
Ford 1992 white
Ford 1992 blue
OHO2002
Sales
5
87
62
54
95
49
31
54
71
64
62
63
52
9
55
27
62
39
CUBE
DATA CUBE
Model Year Color
ALL ALL ALL
chevy ALL ALL
ford ALL ALL
ALL 1990 ALL
ALL 1991 ALL
ALL 1992 ALL
ALL ALL red
ALL ALL white
ALL ALL blue
chevy 1990 ALL
chevy 1991 ALL
chevy 1992 ALL
ford 1990 ALL
ford 1991 ALL
ford 1992 ALL
chevy ALL red
chevy ALL white
chevy ALL blue
ford ALL red
ford ALL white
ford ALL blue
ALL 1990 red
ALL 1990 white
ALL 1990 blue
ALL 1991 red
ALL 1991 white
ALL 1991 blue
ALL 1992 red
ALL 1992 white
ALL 1992 blue
Sales
942
510
432
343
314
285
165
273
339
154
199
157
189
116
128
91
236
183
144
133
156
69
149
125
107
104
104
59
116
110
Kap13-18
SQL-Erweiterung: CUBE - Operator
• Im Beispiel:
select
from
where
and
group by
having
model, make, year, sum(units)
car_sales
model in {“chevy”, “ford”}
year between 1990 and 1994
cube model, make, year
sum(units) > 0;
• Beachten:
Select und Group By wiederholen
Aggregationsliste
OHO2002
Kap13-19
Syntax
• CUBE hinter Group By mit Attributliste definiert
Koordinatenachsen (Dimensionen) des Cube
select <field list> <aggregate list>
from
<table expression>
where <search condition>
group by [ cube | rollup] <aggregate list>
having <search condition>
• erlaubt zusätzliche Aggregationen durch
Dimensionshierarchien (e.g., sales by quarter):
select store, quarter, sum(units)
from sales
group by rollup store,
quarter(date)as quarter
and year = 1994;
OHO2002
Kap13-20
13.3 Cube Operationen, Operationen auf
mehrdimensionalen Arrays
Aggregate
Group By
(with total)
Sum
By Color
RED
WHITE
BLUE
Cross Tab
ChevyFord
Sum
By Color
RED
WHITE
BLUE
The Data Cube and
The Sub-Space Aggregates
CH FOR
EV
D
Y
By Make
Sum
By Year
0
199991
1 992
1 993
1
By Make
By Make & Year
RED
WHITE
BLUE
By Color & Year
Sum
OHO2002
By Make & Col
By Color
Kap13-21
Dimensionen, Measures
Dimensionen:
Measures:
Dimensionshierarchie:
Drill-Down, Drill-up:
OHO2002
Koordinatenachsen (x1, ..., xn) des
mehrdimensionalen Arrays (“Datenwürfels”)
Werte der Funktionen f1(x1,...,xn), f2(...),...
In relationaler Terminologie: Measures sind
funktional abhängig von den Dimensionen.
Vergröberung für die Aggregation,
Benannte Partitionierung des Wertebereichs
einer Dimension.
Beispiele: Stadt -> Kanton
Datum -> Monat -> Quartal
Aggregation entlang der Dimensionshierarchie,
Down für Verfeinerung, Up für Vergröberung
Kap13-22
Beispiel Dimensionen vs. Measures
Produkt
Brot
Milch 95
52
Dimensionen:
Produkt, Datum, Filiale
Measure:
Umsatz
Tee
07.01. 08.01.
Irchel
Datum
Central
Wipkingen
Filiale
OHO2002
Kap13-23
Operationen auf multi-dimensionalen Daten
•
Vorbild: Relationenalgebra: Input: Cube(s), Output: Cube, wenige
mächtige Operationen, Mächtigkeit durch geschickte Kombination!
•
Transformation zwischen Measures und Dimensions: Pull & Push
ƒ Dabei nötig: elementbildende Funktionen, damit
Funktionalabhängigkeit „Dimensions -> Measures“ erhalten bleibt.
•
Dimensionsreduktion, falls nur ein Wert vorkommt: Destroy
ƒ sonst: vorher Aggregieren, neue Elemente bilden, Operator Merge!
•
Restriktion: Neuer Cube enthält nur nur noch Werte einer Dimension,
die ein Filterprädikat erfüllen (naheliegend)
•
Join: binäre Operationen!
•
Wir verschaffen uns einen Einblick in Merge/Cross-Tab, Push und
Pull
OHO2002
Kap13-24
Cross-Tabelle
Marke
Opel
12
12
Projektion
mit
Aggregation
auf Teilraum
Audi
5
5
BMW
15
20
5
07.01. 08.01.
Hessen
Datum
Bayern
Saarland
Bundesland
OHO2002
Kap13-25
Push
Marke
Opel
Push-Operation im
Beispiel auf Datum:
setzt Datumswerte
zu bisherigem
Measure.
<12,08.01.>
Audi
<5, 08.01.>
BMW
<15,07.01>
<5, 07.01>
07.01. 08.01.
Hessen
Bayern
Saarland
Datum
Nutzen:
Verwendung von
Aggregationsfunktionen auf die
so erweiterten
Measure-Elemente
Bundesland
OHO2002
Kap13-26
Pull
Marke
<12,B>
Opel
Audi
12
<5,B>
5 <15,H>
BMW
15
<5,H>
5
07.01. 08.01.
H
B
Bundesland
OHO2002
Datum
Pull-Operation
zieht Element aus
Measures heraus
und führt damit
neue Dimension
ein.
Wichtig: mit Push
und Pull transformiert man
zwischen
Measures und
Dimensionen
Kap13-27
13.4 Speicherung multi-dimensionaler Daten
•
Problem: Wie werden Zellen des Cubes
physisch angeordnet?
•
Speicherung multi-dimensionaler Arrays als generelle Antwort
ƒ Aggregationsfunktion apriori nicht bekannt.
ƒ Aggregationsfunktion bekannt
•
Indexierung für Cubes
ƒ Bitmap-Index
OHO2002
Kap13-28
Motivation - Bereichsanfragen
Umsatz
300’
200’
100’
07.01. 08.01.
Datum
100
200
300
MA-Anzahl
OHO2002
Kap13-29
Motivation - Bereichsanfragen - 2
Umsatz
300’
200’
100’
07.01. 08.01.
Datum
100
200
300
MA-Anzahl
OHO2002
Kap13-30
Lineare Speicherzuordnung- Illustration
Bevorzugte
Aggregationsrichtun
g=
Speicheranordnung.
Für andere
Aggregationen:
Replikation mit
anderer
Speicheranordnung
n2
n2+1
n+1 n+2
1
OHO2002
2
3
...
n
Kap13-31
Space-Filling Curves
Row-wise
Hilbert
OHO2002
2
3
0
1
1
2
0
3
Peano
Gray
1
3
0
2
1
2
0
3
Kap13-32
Vorausberechnung von Aggregaten
Array
Prefix-Sum
Array
OHO2002
0
0 3
1 7
2 2
0
0 3
1 10
2 12
1
5
3
4
1
8
18
24
2
1
2
2
3
2
6
3
2
9
21
29
4
2
8
3
3
11
29
40
5
3
2
5
4
13
39
53
5
16
44
63
Kap13-33
Vergröberung durch Blockbildung
Array
Blocked
Prefix-Sum
Array
OHO2002
0
0 3
1 7
2 2
0
0 1 2 -
1
5
3
4
1
18
24
2
1
2
2
3
2
6
3
2
-
4
2
8
3
5
3
2
5
3
29
40
4
-
5
44
63
Kap13-34
Bitmap Indexing
•
Eigenschaften von Data Warehouses:
ƒ Read-Mostly Umgebungen,
ƒ komplexe Anfragen,
ƒ grosses Datenvolumen.
Erfordert/ermöglicht genauere Betrachtung von Indexmechanismen
•
Ansatz dazu: Bitmap Indexing, d.h.
•
Invertierte Listen werden durch Bitvektoren repräsentiert.
•
Vorteile:
ƒ Kompaktheit von Bitvektoren ermöglicht relativ oft, dass Bitmap
Indices im Main Memory verwaltet werden können.
ƒ Operationen auf Bit-Ebene werden Hardware-seitig gut unterstützt.
ƒ Indices werden auch für Selektionen mit geringerer Selektivität
akzeptabel (ähnlich wie im Information Retrieval).
OHO2002
Kap13-35
Bitstring-Darstellung der Pointerlisten
Bitmap - ein Bit-Spaltenvektor pro Attributwert
πA(R)
TupelNr
3
2
1
2
8
2
2
0
7
5
6
4
1
2
3
4
5
6
7
8
9
10
11
12
OHO2002
V8 V7 V6
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
V5
V4
V3
V2
V1
V0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
Value 2
kommt in
Tupel 6
vor
Kap13-36
Mehrstufigkeit oder Vergröberung durch ClusterBildung
Clusterung der Attributwerte: “Verodern” der Spaltenvektoren
Clusterung der Tupel: “Verodern” der Zeilenvektoren
πA(R)
TupelNr
3
2
1
2
8
2
2
0
7
5
6
4
1
2
3
4
5
6
7
8
9
10
11
12
OHO2002
V8 V7 V6
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
V5
V4
V3
V2
V1
V0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
Kap13-37
Ergebnis im Beispiel
Attribut-Cluster-Nr
1
Tupel-ClusterTupel
-Nr
-Nr
1
2
1
3
4
5
2
6
7
8
9
10
3
11
12
OHO2002
V8 V7 V6
0
2
V5
V4
1
3
V3
V2
V1
V0
1
1
0
1
1
1
0
Attributwer
t 1,2 oder 3
kommt in
Tupel 5,6,7
oder 8 vor
Kap13-38
Literatur
•
Jim Gray et al.: Data Cube: A relational aggregation operatior
generalizing group-by, cross-tab, and sub-totals. In: Data Mining
and Knowlegde Discovery 1, 29-53 (1997).
•
A. Datta and H. Thomas: The cube data model: a conceptual model
and algebra for on-line analytical processing in data warehouses.
Decision Support Systems, 27(3):289--301, 1999.
•
M. Gyssens, Laks Lakshmanan: A foundation for multi-dimensional
databases, VLDB Conference 1996.
•
OLAP Council White Paper.
•
DB Hersteller White Papers im Web suchen, z.B. MSDN Library:
SQL Server 2000 Data Warehouse and OLAP Components.
OHO2002
Kap13-39