Arkadiy Omelchenko
Hierarchische physische Data-Cube-Strukturen in einem mobilen Data-Warehouse
ISBN: 978-3-8366-0542-7
Druck Diplomica® Verlag GmbH, Hamburg, 2007
Zugl. Freie Universität Berlin, Berlin, Deutschland, Diplomarbeit, 2007
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden, und die Diplomarbeiten Agentur, die
Autoren oder Übersetzer übernehmen keine juristische Verantwortung oder irgendeine
Haftung für evtl. verbliebene fehlerhafte Angaben und deren Folgen.
© Diplomica Verlag GmbH
http://www.diplom.de, Hamburg 2007
Printed in Germany
Kurzfassung
-1-
Kurzfassung
Die Entscheidungsunterstützung in den modernen Unternehmen mit ihren immensen
Informationsmengen ist ohne das Konzept eines Data-Warehouse und OLAP nicht mehr
vorstellbar. Außerdem werden die mobilen Geräte wie PDAs oder Notebooks mit ihren
Möglichkeiten der drahtlosen Kommunikation immer beliebter in dem unternehmeri-
schen Alltag. Daher befassen wir uns in unserer Arbeit ausführlich mit dem mobile O-
LAP (kurz mOLAP), wo die mobilen Klienten die OLAP-Dienste durch eine drahtlose
Verbindung in Anspruch nehmen, sowie mit den für die Übertragung eingesetzten phy-
sischen Data-Cube-Datenstrukturen. Wir entwickelten dabei eine neue Datenstruktur m-
Dwarf, die speziell für den mOLAP konzipiert ist. Sie speichert keine Aggregatinforma-
tionen und ist somit sehr kompakt. Sie ist um 30-35 % kleiner als fcg-Dwarfs und um
40% kleiner als Summary Tables im Durchschnitt über ein hDCL. Mit dem Einsatz der
m-Dwarfs haben wir den besten existierenden Scheduling-Algorithmus h-FCLOS we-
sentlich verbessert. Wir haben diesem neuen Algorithmus den Namen FCLOS
mD
(FCLOS with m-Dwarfs) gegeben. Mit FCLOS
mD
wird im mOLAP die durchschnittli-
che Wartezeit um 40%, der durchschnittliche Energieverbrauch um 40% und das gene-
rierte Datenvolumen um 30% verringert.
Schlagwörter: OLAP, mobile OLAP, mOLAP, dwarf, mobile dwarf, m-dwarf, FCLOS,
h-FCLOS, FCLOS
mD
Abstract
The decision support in the modern businesses with their immense information amount
is not more imaginable without the concept of the data warehouse and OLAP. The mo-
bile devices like PDAs or notebooks are becoming more and more popular in the busi-
ness workaday usage. That why we concern ourselves in our work in detail with the
mobile OLAP (mOLAP for short), where the mobile clients take the OLAP services over
the wireless connection, and with the transmitting of the used physical data cube struc-
tures. Thereby we developed one new data structure m-Dwarf that is especially designed
for mOLAP. It saves no aggregate information and thus is very compact. It is 30-35%
smaller than the fcg-Dwarfs and 40% smaller than the summary tables in average over
an hDCL. By the m-Dwarfs usage we substantially improved the best scheduling algo-
rithm h-FCLOS. We gave the name FCLOS
mD
to this new algorithm (FCLOS with m-
Dwarfs). With FCLOS
mD
the average access time is decreased at 40%, the average en-
ergy consumption at 40% and the generated traffic at 30% in the mOLAP.
Keywords: OLAP, mobile OLAP, mOLAP, dwarf, mobile dwarf, m-dwarf, FCLOS,
h-FCLOS, FCLOS
mD
Inhaltsverzeichnis
-3-
Inhaltsverzeichnis
Kurzfassung... 1
Abstract... 1
Inhaltsverzeichnis ... 3
Abbildungsverzeichnis... 6
Tabellenverzeichnis ... 7
Vorwort... 8
1
Einführung ... 9
1.1 Grundlagen ... 9
1.2 Problembeschreibung ... 9
1.3
Unsere Ziele und unser Beitrag ... 10
1.4 Überblick ... 11
2
Grundlagen von Data-Warehousing, OLAP und mOLAP... 13
2.1 Data-Warehousing... 13
2.1.1 Einführung... 13
2.1.2 Terminologie und Definitionen ... 14
2.1.3 Architektur
eines
Data-Warehouse... 14
2.1.4 Datenmodellierung für Data-Warehouses ... 16
2.1.5 ROLAP and MOLAP ... 18
2.2 OLAP... 18
2.2.1 Data-Cube und der cube-Operator... 19
2.2.2 DCL und hDCL ... 23
2.3 mOLAP... 27
2.3.1 Architektur... 27
2.3.2 Scheduling-Algorithmen ... 29
2.3.3 FCLOS
und
h-FCLOS ... 31
3
Physische Data-Cube-Datenstrukturen... 34
3.1
Stand der Dinge und Related Work... 34
3.1.1 ROLAP ... 34
3.1.2 MOLAP ... 35
3.1.3 Index-Strukturen... 35
3.1.4 View
Materialisierung ... 38
3.1.5 Data-Cube-Datenstrukturen... 39
Inhaltsverzeichnis
-4-
3.2 Dwarf-Technologie... 44
3.2.1 Dwarf ... 44
3.2.2 Hierarchical Dwarf (h-Dwarf) ... 51
3.2.3 Coarse-grained Dwarf (cg-Dwarf) und Fully coarse-grained Dwarf (fcg-
Dwarf)... 52
3.2.4 Persistenz von Dwarfs, h-Dwarfs und cg-Dwarfs ... 54
4
Mobile Dwarf (m-Dwarf) ... 56
4.1 Motivation ... 56
4.2
Kompromiss in mOLAP... 56
4.3 Struktur
des
m-Dwarf ... 58
4.4
Erzeugen des m-Dwarf ... 61
4.4.1 CreateRMDwarf Algorithmus und rm-Dwarf ... 61
4.4.2 CreateMDwarf Algorithmus ... 62
4.5 Persistenz
von
m-Dwarfs... 63
5
Implementierung ... 64
5.1
Einführung und Programmdesign... 64
5.2 Test-Datenbasis ... 68
5.3
Implementierung von Dwarfs... 69
5.3.1 MemoryDwarf ... 69
5.3.2 PersistentDwarf ... 71
5.4
Implementierung von h-Dwarfs ... 73
5.4.1 HierarchicalMemoryDwarf ... 73
5.4.2 HierarchicalPersistentDwarf... 74
5.5
Implementierung von cg-Dwarfs... 75
5.6
Implementierung von fcg-Dwarfs ... 75
5.7
Implementierung von m-Dwarfs and rm-Dwarfs ... 76
6
Test- und Simulationsergebnisse der Dwarf-Technologie und m-Dwarfs
in mOLAP ... 78
6.1
Größenverhältnisse der verschiedenen Dwarfs ... 78
6.2 Simulationsergebnisse
in
mOLAP ... 89
7
Zusammenfassung und Ausblick ... 93
7.1 Unser
Beitrag... 93
7.2 Schlussfolgerungen... 94
7.3 Zukünftige
Aktivitäten ... 94
Literaturverzeichnis ... 95
Literatur ... 95
Inhaltsverzeichnis
-5-
Patente... 99
Abbildungsverzeichnis
-6-
Abbildungsverzeichnis
Abbildung 2-1: Typische Architektur eines Data-Warehouse... 15
Abbildung 2-2: Relationen des Sternschemas ... 17
Abbildung 2-3: Die Faktentabelle Facts... 19
Abbildung 2-4: DCL für den Beispiel-Data-Cube... 25
Abbildung 2-5: Zusammenhang zwischen DCL und Summary Tables ... 26
Abbildung 2-6: Zusammenhang zwischen hDCL und Summary Tables ... 27
Abbildung 2-7: mOLAP-Architektur... 28
Abbildung 2-8: (h-)FCLOS Algorithmus in Aktion (für =1) ... 32
Abbildung 3-1: Ein Bitmap-Index für die Spalte Gender in einer Datenbanktabelle ... 36
Abbildung 3-2: Der schematische Aufbau eines B-Baums ... 37
Abbildung 3-3: Ein R-Baum... 37
Abbildung 3-4: Ein Cube Tree (in der Mitte) ... 39
Abbildung 3-5: BUC Prozessbaum... 40
Abbildung 3-6: Ein H-Tree... 41
Abbildung 3-7: Ein Star-Tree ... 42
Abbildung 3-8: Ein statistic tree... 42
Abbildung 3-9: Ein Condensed Cube ... 43
Abbildung 3-10: Dwarf für die Faktentabelle Facts... 45
Abbildung 3-11: CreateDwarfCube Algorithmus ... 48
Abbildung 3-12: SuffixCoalesce Algorithmus... 49
Abbildung 3-13: Hierarchical Dwarf (h-Dwarf)... 51
Abbildung 3-14: Coarse-grained Dwarf mit G
min
= 2... 53
Abbildung 3-15: Fully coarse-grained Dwarf (mit G
min
= )... 53
Abbildung 3-16: Konzeptionelle Persistenz eines Dwarf... 54
Abbildung 3-17: Die Dwarf Datei schematisch... 55
Abbildung 3-18: Die Dwarf-Datei für die Faktentabelle Facts... 55
Abbildung 4-1: m-Dwarf ohne Optimierung von Knotenseparatoren... 59
Abbildung 4-2: m-Dwarf ... 60
Abbildung 4-3: CreateRMDwarf Algorithmus... 61
Abbildung 4-4: rm-Dwarf ... 62
Abbildung 4-5: CreateMDwarf Algorithmus ... 63
Abbildung 4-6: m-Dwarf File ... 63
Abbildung 5-1: Allgemeines Klassendiagramm... 67
Abbildung 5-2: Verschiedene Datenbankschemas mit Beispiel-Daten ... 68
Abbildung 5-3: Klassendiagram für MemoryDwarf ... 70
Abbildung 5-4: Klassendiagramm für PersistentDwarf ... 72
Abbildung 5-5: Klassendiagramm für HierarchicalMemoryDwarf ... 73
Abbildung 5-6: Klassendiagramm für HierarchicalPersistentDwarf ... 74
Tabellenverzeichnis
-7-
Abbildung 5-7: Klassendiagramm für FullyCoarseGrainedDwarf... 76
Abbildung 5-8: Klassendiagramm für MobileDwarf und RequestableMobileDwarf... 77
Abbildung 6-1: Größen der Strukturen in hDCL für einen synthetischen Dataset mit
100.000 Tupeln, 4 Dimensionen, 80-20 Distribution ... 80
Abbildung 6-2: Größen der Strukturen (ohne den h-Dwarf) in hDCL für einen
synthetischen Dataset mit 100.000 Tupeln, 4 Dimensionen, 80-20
Distribution ... 81
Abbildung 6-3: Größenersparnis der m-Dwarfs gegenüber den fcg-Dwarfs in hDCL
für einen synthetischen Dataset mit 1.000.000 Tupeln, 6 Dimensionen, 80-
20 Verteilung der Dimensionswerte ... 84
Abbildung 6-4: Größenersparnis der m-Dwarfs gegenüber den Summary Tables in
hDCL für einen synthetischen Dataset mit 1.000.000 Tupeln, 6
Dimensionen, 80-20 Verteilung der Dimensionswerte... 85
Abbildung 6-5: Größenersparnis der m-Dwarfs gegenüber den fcg-Dwarfs in hDCL .. 87
Abbildung 6-6: Größenersparnis der m-Dwarfs gegenüber den Summary Tables in
hDCL... 88
Abbildung 6-7: Durchschnittliche Wartezeit nach einer Anforderung für den realen
Dataset... 90
Abbildung 6-8: Die durchschnittlich durch die mobilen Klienten verbrauchte
Leistung in der Zeitspanne von der Anforderung bis zum Erhalt eines Cube
für den realen Dataset ... 91
Abbildung 6-9: Das vom System generierte Datenvolumen durchschnittlich für jede
Anforderung ... 92
Tabellenverzeichnis
Tabelle 2-1: Tabellarische Repräsentation eines Data-Cube ... 21
Tabelle 2-2: Summary Table für Listing 2-3 ... 23
Tabelle 6-1: Einige experimentelle Ergebniswerte für die synthetischen Datasets
mit einer variablen Anzahl der Tupel ... 82
Tabelle 6-2: Einige experimentelle Ergebniswerte für die synthetischen Datasets
mit einer variablen Verteilung der Dimensionswerte ... 83
Tabelle 6-3: Einige experimentelle Ergebniswerte für die synthetischen Datasets
mit einer variablen Anzahl der Dimensionen ... 83
Tabelle 6-4: Einige experimentelle Ergebniswerte für den realen Dataset mit 918
843 Tupeln ... 86
Tabelle 6-5: Die Simulationsparameter ... 89
Vorwort
-8-
Vorwort
Beim Vorwort möchte ich mich bei allen bedanken, die mich bei dieser Arbeit unter-
stützt haben. Ich danke meinen Prüfern Herrn Prof. Dr. Hans-Joachim Lenz und Herrn
Prof. Dr.-Ing. Jochen Schiller für ihre Veranstaltungen, die ich immer mit Interesse be-
sucht habe und bei denen ich immer Spaß am Informatikstudium hatte. Ich danke mei-
nem unmittelbaren Betreuer am Fachbereich, Herrn Ilias Michalarias, für seine auf-
merksame Führung, Betreuung und für seine Unterstützung mit den nötigen Informatio-
nen. Für seine Ratschläge danke ich sehr meinen Freunden Valeri Felberg und Bernhard
Häring. Und last but not least danke ich meiner Freundin Lilia für ihre Geduld und ihre
Unterstützung während der langen Stunden, die ich mit dieser Arbeit verbrachte.
Einführung
-9-
1 Einführung
1.1 Grundlagen
Die Entscheidungsunterstützung in den modernen Unternehmen mit ihren immensen
Informationsmengen ist ohne das Konzept eines Data-Warehouse und OLAP nicht mehr
vorstellbar. Ein Data-Warehouse ist dabei eine dedizierte, auf die analytischen Zwecke
orientierte Datenbank und OLAP stellt die nötigen Dienste für eine flexible und an-
spruchsvolle Datenanalyse bereit.
Außerdem werden die mobilen Geräte wie PDAs oder Notebooks mit ihren Möglichkei-
ten der drahtlosen Kommunikation immer beliebter in dem unternehmerischen Alltag.
Solche Geräte sind schon seit langem in ihrer Leistungsfähigkeit so fortgeschritten, dass
sie für die gehobenen Anforderungen der analytischen OLAP-Anwendungen bereit
sind. Daher befassen wir uns in unserer Arbeit ausführlich mit dem mobile OLAP (kurz
mOLAP), wo die mobilen Klienten die OLAP-Dienste durch eine drahtlose Verbindung
in Anspruch nehmen. Genauer gesagt geht es um die Datenstrukturen, die die angefor-
derten und zu übertragenden Daten repräsentieren. Solche Daten liegen in OLAP-
Anwendungen in der Form der Data-Cubes vor, deswegen liegt der Focus unserer Ar-
beit auf den Data-Cube-Datenstrukturen in mOLAP.
1.2 Problembeschreibung
Das Anwendungsszenario in mOLAP sieht eine Menge von Nutzern vor, die mit mobi-
len Geräten (Klienten) ausgestattet sind, und einen OLAP-Server, der allen Nutzern
seine analytischen OLAP-Dienste zur Verfügung stellt. Alle Klienten befinden sich in-
nerhalb einer Broadcast-Domäne eines drahtlosen Gateway, das die Anforderungen der
Klienten nach einem Sub-Cube zum OLAP-Server weiterleitet. Der Server beantwortet
die Anforderungen der Klienten, indem er die angeforderten Sub-Cubes zurücksendet.
Ein realistisches Beispiel wäre eine Börsenhalle, in der die mit PDAs und Notebooks
ausgestatteten Broker den OLAP-Server nach den analytischen Informationen (wie z.B.
Zahlen zu Aktienverkäufen oder statistische Trends in Verkaufsvorgängen) permanent
anfragen. Die Klienten bekommen eine Antwort in der Form eines Data-Cubes, und
danach können sie den Data-Cube ,,offline" analysieren.
Die Herausforderung bei diesem Szenario ist die effiziente Bedienung der Klienten. Die
Effizienz wird gemessen als die Zeit der Anfragebeantwortung, als Leistungsverbrauch
der mobilen Geräte und als vom System generierte Datenvolumen. Entscheidend für die
gesamte Systemeffizienz sind die Scheduling-Algorithmen, die die Art und die Reihen-
Einführung
-10-
folge der Klientenbedienung bestimmen. Zusätzlich spielen die Data-Cube-
Datenstrukturen, die die übertragenen Sub-Cubes physisch repräsentieren, eine wichtige
Rolle dabei.
1.3 Unsere Ziele und unser Beitrag
Wir haben in unserer Arbeit mehrere Ziele gesetzt. Das erste Ziel war die Untersuchung
der existierenden Scheduling-Algorithmen und Data-Cube-Datenstrukturen für den
mOLAP. Unseren Ausgangspunkt stellte der Algorithmus h-FCLOS dar, der zurzeit die
beste Effizienz aufweist. Bei den Data-Cube-Datenstrukturen haben wir auch ,,den bes-
ten" für die weiteren Untersuchungen genommen: den Dwarf, der eine sehr kompri-
mierte aber effizient berechenbare Data-Cube-Datenstruktur aufweist. Wir haben die
weiteren mit dem Dwarf zusammenhängenden Datenstrukturen wie hierarchical
Dwarfs (h-Dwarf), coarse-grained Dwarfs (cg-Dwarf) und fully coarse-grained Dwarfs
(fcg-Dwarf) erforscht.
Das zweite Ziel war die weitere Verbesserung des mOLAP, was uns mit der Entde-
ckung einer an Dwarf angelehnten Datenstruktur, eines mobile Dwarf (kurz m-Dwarf),
gelang. Ein m-Dwarf ist eine speziell für den mOLAP entwickelte Datenstruktur, die
keine vorgerechneten Aggregatwerte in sich speichert. Die fehlenden Aggregatwerte
kann ein mobiler Klient selbst durch seine eigene Rechenleistung nach dem Erhalt des
m-Dwarfs schnell nachrechnen. Wir stellen einen Algorithmus zum Berechnen eines m-
Dwarf sowie eine weitere Datenstruktur requestable mobile Dwarf (rm-Dwarf) vor. Ein
rm-Dwarf ist eine temporäre Datenstruktur für die Berechnung eines m-Dwarf auf der
Serverseite, kann aber für die spätere Nachberechung der Aggregatwerte auf der Klien-
tenseite genutzt werden. Dank der fehlenden Aggregatwerte und der Besonderheiten
seiner Struktur wurde der m-Dwarf dabei um 40% kleiner als Summary Tables im
Durchschnitt über alle hDCL-Knoten.
Durch seine kompakte Größe ist ein m-Dwarf zum Übertragen durch einen relativ lang-
samen drahtlosen Link besser geeignet als die anderen Strukturen. Diese Eigenschaft
haben wir bei der Realisierung unseres neuen Scheduling-Algorithmus FCLOS
mD
(FCLOS with m-Dwarfs) genutzt. Der FCLOS
mD
Algorithmus ist dabei die Modifizie-
rung des h-FCLOS um die m-Dwarfs, die man komplett anstatt der Summary Tables
oder Dwarfs an die Klienten schickt. Das bedeutet, dass nur die Selecting Component
der h-FCLOS modifiziert wurde, aber die Scheduling-Funktion der FCLOS unverändert
blieb.
Um die realen Angaben zu den Effizienzergebnissen zu bekommen, haben wir alle mit
der Dwarf-Technologie zusammenhängenden Datenstrukturen sowie den m-Dwarf imp-
lementiert und ihre Größen für die verschiedenen synthetischen Datasets und einen rea-
len Dataset berechnet. Mit diesen realen Größenwerten haben wir die Effizienz der ge-
Einführung
-11-
samten mOLAP durch eine Simulation des mOLAP für die früheren Scheduling-
Algorithmen und unseren neuen FCLOS
mD
-Algorithmus mit den variablen Parametern
des Systems gemessen.
Die Ergebnisse zeigen eindeutig, dass die Nutzung der m-Dwarfs im Gegensatz zu den
anderen Dwarf-Arten oder Summary Tables die gesamte Effizienz des Systems bei allen
Parametern verbessert: die durchschnittliche Antwortzeit und der Energieverbrauch
wurden um 40% und das generierte Datenvolumen um 30% reduziert. Insgesamt ist
unser Fazit, dass solche Data-Cube-Datenstrukturen bei den bestehenden relativ kleinen
Bandbreiten der drahtlosen Netwerke und der relativ hohen Rechenleistung der mobilen
Geräte vorteilhafter sind, wenn sie ohne vorgerechnete Aggregatwerte übertragen wer-
den. Man bekommt die Antworten schneller, mit weniger Energieverbrauch und weni-
ger Traffic. Eine andere Alternative, wo die Data-Cube-Datenstrukturen alle Aggregat-
werte (z.B. Dwarfs oder h-Dwarfs) oder einige Aggregatwerte (z.B. fcg-Dwarfs) in sich
speichern, ist natürlich möglich, ist aber für die mOLAP-Architektur insgesamt ineffi-
zient. Diese Alternative kann für die bestimmten Anwendungsfälle angewendet werden,
wo man eine schlechtere Systemeffizienz in Kauf nimmt.
1.4 Überblick
Wir stellen die Grundlagen des erwähnten Konzeptes des Data-Warehousing im Kapitel
2 ,,Grundlagen von Data-Warehousing, OLAP und mOLAP" vor. Dabei werden Sie die
Architektur eines Data-Warehouse, seine konkrete Realisierung mit einem Sternschema,
den OLAP mit dem Data-Cube kennenlernen. In diesem Kapitel betrachten wir auch
den mOLAP mit den dazu gehörigen Scheduling-Algorithmen: die früher vorgeschlage-
nen Scheduling-Algorithmen in einem Überblick und mehr detailliert den Algorithmus
h-FCLOS, der zurzeit die beste Effizienz aufweist. Bei unseren Beschreibungen nutzen
wir durchgehend ein konkretes Beispiel, damit der Leser besser die vorgestellten Inhalte
nachvollziehen kann.
Im Kapitel 3 ,,Physische Data-Cube-Datenstrukturen" lernen Sie mehrere Datenstruk-
turen kennen, die für die Repräsentation der Data-Cubes vorgeschlagen werden. Im ei-
nen Übersichtskapitel geht es um den Stand der Dinge und Related Work bei den ver-
schiedenen Vorschlägen zur Implementierung eines Data-Cube sowie den für OLAP
relevanten Datenstrukturen. Dann erzählen wir ausführlich über die Dwarf-Technologie
und über die dazu gehörigen Data-Cube-Datenstrukturen: Dwarfs, h-Dwarfs, cg-Dwarfs
und fcg-Dwarfs. Wir berichten über die Persistenz dieser Dwarf-Strukturen am Ende
des Kapitels.
Unsere Erfindung m-Dwarf wird von uns im Kapitel 4 ,,Mobile Dwarf (m-Dwarf)" vor-
gestellt. Wir sprechen über die Motivation und die Gründe, die uns zum Entwickeln
Einführung
-12-
dieser Datenstruktur bewegten. Dann werden wir den Algorithmus zum Erzeugen der
m-Dwarfs angeben und sprechen kurz über seine Persistenz.
Die Implementierungsaspekte unseres Programms zum Berechnen der unterschiedlichen
Dwarfs kann man im Kapitel 5 ,,Implementierung" erfahren. Wir gehen dabei nicht tief
ins Detail, sondern geben die Beschreibungen auf der Ebene der Klassendiagramme zu
den relevanten Klassen und Methoden des Programms.
Die Resultate unserer Simulationen mit den implementierten Datenstrukturen sind im
Kapitel 6 ,,Test- und Simulationsergebnisse der Dwarf-Technologie und m-Dwarfs in
mOLAP" zu finden. Hier präsentieren wir zum ersten die Angaben zu den Größen der
Strukturen und zum zweiten die erzielten Ergebnisse einer simulierten mOLAP-
Umgebung.
Das Kapitel 7 ,,Zusammenfassung und Ausblick" dient als ein kurzer Bericht über die
gemachte Arbeit und die gewonnenen Resultate. Wir machen auch Angaben über die
zukünftigen Forschungsaktivitäten in unserem Bereich.
Grundlagen von Data-Warehousing, OLAP und mOLAP
-13-
2
Grundlagen von Data-Warehousing, OLAP und
mOLAP
In diesem Kapitel stellen wir die Informationen bereit, die als Grundlagen für die weite-
ren Ausführungen dienen sollen. Im Allgemeinen geht es um Data-Warehousing, das
die gesamten Technologien zur Unterstützung von Datenanalysen umfasst. Online Ana-
lytical Processing (OLAP) ist eine wichtiger Teil von Data-Warehousing, mit dem man
Datenanalysen durchführen kann. Mobile OLAP (kurz mOLAP) ist ein Spezialfall von
OLAP, wenn die analysierenden OLAP-Klienten mobil sind.
2.1 Data-Warehousing
2.1.1 Einführung
Im mittleren und höheren Management eines Unternehmens existiert immer ein großer
Bedarf an Informationen, die es bei den täglichen unternehmerischen Entscheidungen
unterstützen können. Seit der Erfindung von Datenbanken kann man solche Informatio-
nen leicht in den operationalen Datenbanken ablegen und nutzen. Das hat man auch
ursprünglich auf diese Weise getan und macht es bis zum heutigen Tag für einfachere
Analysen. Aber man hat ziemlich früh festgestellt, dass das Bereitstellen von analyti-
schen Informationen in operativen Datenbanken im Allgemeinen nicht die beste und
effektivste Lösung ist. Man kann viele Gründe dafür nennen, unter anderen die folgen-
den:
Die analytischen Datenbanktransaktionen und -anfragen unterscheiden sich sehr
stark in ihrer Struktur von Transaktionen im operativen Geschäft. Die operativen
Transaktionen betreffen meistens wenige Zeilen in den Datenbanktabellen, sind
sowohl lesend als auch schreibend und machen wenig Gebrauch von aggregier-
ten Werten. Im Unterschied dazu sind die analytischen Transaktionen meistens
Anfragen, die ausschließlich lesend sind, die aber eine riesige Anzahl von Zeilen
auslesen und große Mengen von aggregierten Werten berechnen müssen.
Die Datenbasis für die Analyse muss eine sehr große Menge an ,,historischen"
Daten beinhalten, wobei für das operative Geschäft nur die aktuellen ,,jungen"
Daten relevant sind.
In einem großen Unternehmen sind die operationalen Daten auf mehrere Daten-
banken verteilt, aber die Informationen für die Analyse muss man aus allen die-
sen Datenbanken berücksichtigen.
Grundlagen von Data-Warehousing, OLAP und mOLAP
-14-
Aus diesen und anderen Gründen besteht schon seit langem weitgehender Konsens, dass
man die operationalen und analytischen Anwendungen nicht auf derselben Datenbasis
durchführt, sondern die Daten voneinander trennt. Das führte zum Aufbau einer speziel-
len dedizierten Datenbank, eines so genannten ,,Data-Warehouse", das einzig und allein
für den analytischen Bedarf eines Unternehmens konzipiert ist. Als Data-Warehousing
bezeichnen wir sowohl alle Technologien und Prozesse, die zum Aufbau eines Data-
Warehouse notwendig sind, als auch alle von einem Data-Warehouse bereitgestellten
Dienste.
2.1.2 Terminologie und Definitionen
Der Begriff ,,Data-Warehouse" stammt von W.H. Inmon [In92]. Er charakterisiert ein
Data-Warehouse als ,,eine subjektorientierte, integrierte, nicht flüchtige, zeitvariierende
Datensammlung zur Unterstützung von Managemententscheidungen". Sie werden ein-
gesetzt um die Daten für fortgeschrittene Analyse, Wissensgewinnung und Entschei-
dungsfindung bereitzustellen.
Man unterscheidet mehrere Anwendungstypen, die von Data-Warehouses unterstützt
werden: OLAP, DSS und Data-Mining. OLAP (Online Analytical Processing) ist ein
Begriff, mit dem man die Analyse komplexer Daten aus dem Data-Warehouse be-
schreibt. Wir stellen OLAP detailliert im eigenen Kapitel 2.2 vor. DSS (Decision-
Support Systems) liefern auch die Daten für den analytischen Bedarf der führenden
Entscheidungsträger, aber auf allgemeinerem Niveau für komplexe und wichtige Ent-
scheidungen. Bei Data-Mining handelt es sich um den Prozess der Gewinnung neuen
Wissens mittels vorhandener Daten.
Die in der Einführung erwähnten traditionellen Datenbanken bieten im Gegensatz zu
den Data-Warehouses die OLTP-Dienste an. OLTP (Online Transactional Proces-
sing) nennt man den Prozess, bei dem man die in der Datenbank modellierte Abbildung
einer realen Weltsituation aufrechterhält. Das schließt die Einfügung, Aktualisierung
und Löschung der Daten ein, sowie alle Anfragen, die diesen Prozess unterstützen.
Man unterscheidet deswegen konzeptionell die Anwendungen, die es mit dem operati-
ven Geschäft und den traditionellen Datenbanken zu tun haben (OLTP-
Anwendungen), von denen, die die Analyse von Daten mit Zugriffen auf ein Data-
Warehouse (OLAP-Anwendungen) erfordern.
2.1.3 Architektur eines Data-Warehouse
Eine typische Data-Warehouse-Architektur ist in Abbildung 2-1 dargestellt. Hier ist
nicht die innere Architektur sondern vielmehr das Zusammenspiel mit den operationa-
len Datenbanken und anderen Dateneingaben gezeigt. Wir betrachten einen allgemeinen
Grundlagen von Data-Warehousing, OLAP und mOLAP
-15-
Fall, von dem man je nach Einsatzbereich und Technologien mehr oder weniger abwei-
chen kann.
Abbildung 2-1: Typische Architektur eines Data-Warehouse
Die Datenquellen für ein Data-Warehouse sind normalerweise die operationalen Daten-
banken eines Unternehmens, aber auch andere externe Datenquellen.
Bevor man die Daten aus den Datenquellen in einem Data-Warehouse ablegen kann, ist
ein komplexer Datenverarbeitungsprozess notwendig. Man bezeichnet diesen Prozess
als einen ETL-Prozess. ETL ist ein englisches Akronym für Extraction, Transformati-
on and Loading, was einen normalen Prozessablauf des ETL-Prozesses darstellt: man
extrahiert zuerst die Daten aus den Datenquellen (Extraction), man macht die notwen-
digen Bereinigungen und Umformatierungen der Daten (Transformation) und lädt letzt-
endlich die bereinigten Daten in das Data-Warehouse (Loading). Alle diese Schritte
sind notwendig, weil normalerweise mehrere Datenquellen für den Aufbau eines unter-
nehmerischen Data-Warehouse benötigt werden und diese Inkonsistenzen verschiedener
Art aufweisen können: die Datenbank-Schemas und Datentypen können sich unter-
scheiden, die Daten können fehlen oder fehlerhaft sein und vieles mehr.
Bis zu 80% der gesamten Entwicklungszeit eines Data-Warehouse werden für diesen
Schritt gebraucht [In05], was meistens unterschätzt wird. Das liegt hauptsächlich an
fehlender Automatisierung der Entwicklung des ETL-Prozesses trotz fortgeschrittener
ETL-Tools, die diese Arbeit unterstützen. Eine solche Automatisierung bleibt noch eine
offene Forschungsrichtung der Wissenschaft.
Die Bereinigung der Daten durch den ETL-Prozess kann auch dafür eingesetzt werden,
dass die Daten in den operationalen Datenbanken durch den ETL-Prozess mit den rich-
Grundlagen von Data-Warehousing, OLAP und mOLAP
-16-
tigen Werten gefüllt oder aktualisiert werden. Das bezeichnet man als Backflushing,
was durch einen Rückpfeil in der Abbildung dargestellt ist.
Wie oft der ETL-Prozess abläuft (täglich, wöchentlich, monatlich) hängt im Wesentli-
chen von den Anforderungen der Nutzer an die Aktualität der Daten ab. Es kann ein
Mal pro Tag erfolgen, in der Zeit, wenn die Auslastung der Datenbankquellen am ge-
ringsten ist meistens in der Nacht. Oder es kann mehrmals pro Tag erfolgen, zum Bei-
spiel für ein international tätiges Unternehmen jedes Mal, wenn eine regionale Ge-
schäftsfiliale die Daten bereitstellt. Das Laden erfolgt meist im Batchmodus ohne Inter-
aktion mit dem Benutzer.
Nachdem die Daten in das Data-Warehouse durch den ETL-Prozess geladen wurden,
kann man die vor kurzem erwähnten analytischen Dienste OLAP, DSS oder Data Mi-
ning für die externen Klienten durch die geeigneten Schnittstellen bereitstellen. Diese
Dienste können neue Informationen generieren, die auch per Backflushing zurück in die
Datenquellen übertragen werden, was mit Rückpfeilen von den Diensten zu den Daten-
quellen dargestellt ist.
Wir haben das Data-Warehouse absichtlich als einen riesigen Zylinder dargestellt, weil
es sich bei einem unternehmensweiten Data-Warehouse tatsächlich um die Datenmen-
gen handelt, die im Allgemeinen um eine Größenordung (manchmal auch zwei) größer
als die Quelldatenbanken sind. Hunderte von Gigabytes bis zu 10 Terabyte müssen
die Data-Warehouse-Anwendungen verwalten können. Die gezeigten Metadata spielen
dabei eine wesentliche Rolle: im Metadata-Bereich werden alle Systeminformationen
gespeichert, die unterstützenden Informationen für den ETL-Prozess und auch weitere
Informationen wie z.B. für die Datenstrukturen im Data-Warehouse.
2.1.4 Datenmodellierung für Data-Warehouses
Als Datenbankschema für die Data-Warehouses hat sich das so genannte Sternschema
(engl. star schema) durchgesetzt. Dieses Schema besteht aus einer in der Mitte stehen-
den Faktentabelle und mehreren Dimensionstabellen, die um die Faktentabelle herum
stehen. Diese Verteilung der Tabellen ergibt den Namen ,,Stern" für dieses Schema und
ist in der Abbildung 2-2 zusammen mit einigen Beispieldaten dargestellt.
Grundlagen von Data-Warehousing, OLAP und mOLAP
-17-
Abbildung 2-2: Relationen des Sternschemas
In unserem Beispiel ist die Tabelle Facts die Faktentabelle und alle weiteren sind die
Dimensionstabellen. In der Faktentabelle stehen die Tupel, die die Fakten darstellen.
Die Tupel bestehen aus zwei Teilen:
1. der erste Teil besteht aus den Attributen mit Fremdschlüsseln zu den Dimensi-
onstabellen, den so genannten Dimensionen (engl. dimensions) (im Beispiel
sind es die Attribute Product, Store und Time). Sie bilden alle zusammen den
Primärschlüssel der Faktentabelle.
2. der zweite Teil besteht aus den Attributen mit so genannten Kennzahlen (engl.
Measures), die gemessene oder beobachtete Werte zu den mit Dimensionswer-
ten festgestellten Fakten beinhalten. In unserem Beispiel gibt es eine einzige
Kennzahl in dem Attribut Price, die die Summe der Preise eines verkauften
Produkts X in einem bestimmten Geschäft Y an einem bestimmten Tag Z dar-
stellt. Die Summe ist eine so genannte Aggregatfunktion, die immer zu einem
Attribut mit Kennzahlen gehört. Außer der Summe (SUM) gibt es weitere Ag-
gregatfunktionen wie AVG, COUNT, MIN oder MAX.
Wir geben für das Beispiel ganz wenige Tupel an. In der Realität kann die Faktentabelle
Millionen von Tupel enthalten, je nach Verdichtungsgrad der geladenen Daten. Die Di-
mensionstabellen enthalten dagegen sehr viel weniger Tupel. Für eine Tabelle mit Pro-
dukten eines Handelsunternehmens könnte man sich beispielsweise ein Hundert Tau-
1
2
1
$70
Product
Store
Time
Price
Facts
Faktentabelle
1
3
2
$40
2
1
3
$50
1
10
CodeId
Category
Product
Dimensionstabelle
2
20
1
2007
Day
Year
Time
Dimensionstabelle
2
2007
3
2007
StoreId
Store
Dimensionstabelle
1
2
3
Grundlagen von Data-Warehousing, OLAP und mOLAP
-18-
send Produkte vorstellen, die Zeit-Tabelle mit Detaillierungsgrad 1 Tag würde 365 Tu-
pel pro Jahr enthalten.
Die Dimensionstabellen sind im Sternschema nicht normalisiert. Im Beispiel sieht man
es an der Tabelle Time, wo die folgende funktionale Abhängigkeit gilt: Day
Year.
Damit erhält diese Tabelle die Klassifizierung in der Zeitdimension. Wenn man die
Dimensionstabellen normalisieren würde, würde man zu einem anderem Schema kom-
men, dem so genannten Schneeflockenschema (engl. snow flake schema). Dieses
Schema ist trotz der Normalisierung eher unüblich für Data-Warehouses, weil die Nor-
malisierung die Leistungsfähigkeit wegen notwendiger Joins verschlechtert. Man ver-
letzt bewusst die Normalform in einem Data-Warehouse. Zum einen werden die Daten
nur selten und nur durch den ETL-Prozess kontrolliert verändert und zum anderen fällt
der durch die Denormalisierung erhöhte Speicherbedarf kaum ins Gewicht, weil die
Dimensionstabellen relativ klein sind.
2.1.5 ROLAP and MOLAP
In diesem Kapitel beschreiben wir sehr grob und kurz die interne Architektur eines Da-
ta-Warehouse. Es gibt zwei nebeneinander stehende und konkurrierende Ansätze für die
Architektur und Implementierung eines Data-Warehouse:
1. ROLAP (Relational OLAP): Wie im vorigen Kapitel vorgestellt, wird das Da-
ta-Warehouse auf der Basis eines relationalen Datenmodells mit einem (oder
mehreren) Sternschemas realisiert. Alle OLAP Operationen werden bei dieser
Implementierung in die geeigneten SQL-Anfragen transparent für den Nutzer
überführt.
2. MOLAP (Multidimensional OLAP): Bei diesem Ansatz werden die Daten nicht
in den Tabellen einer relationaler Datenbank abgespeichert sondern in speziel-
len proprietären, mehrdimensionalen Datenstrukturen. Ein einfacher Fall sol-
cher Strukturen wären die mehrdimensionalen Arrays.
Es gibt auch einige Implementierungen, die die besten Seiten der beiden Ansätze zu
vereinen versuchen und beide Techniken zusammen nutzen.
2.2 OLAP
Wir haben im Kapitel 2.1.2 kurz die Definition von OLAP vorgestellt, als einen Teil
von Data-Warehousing. Unter OLAP versteht man einen wichtigen Dienst eines Data-
Warehouse, mit dem man Analysen von Daten durchführen kann. Hier gehen wir auf
die Beschreibung von OLAP und ihren Diensten näher ein.
Grundlagen von Data-Warehousing, OLAP und mOLAP
-19-
2.2.1 Data-Cube und der cube-Operator
Einen zentralen und grundlegenden Begriff in OLAP stellt Data-Cube (oder kurz und
einfach Cube) und cube-Operator dar. Wir möchten diese beiden Begriffe durch ein
Beispiel verdeutlichen. Betrachten Sie noch einmal die Faktentabelle Facts in der
Abbildung 2-3, die wir aus dem Sternschema aus der Abbildung 2-2 ohne Dimensions-
tabellen übernommen haben.
Abbildung 2-3: Die Faktentabelle Facts
Jetzt versuchen wir einige mögliche analytische Anfragen zur Faktentabelle vorzustel-
len. Wir bekommen Anfragen folgender Art:
1. Welche Summe wurde von Produkt 1 im Geschäft 2 am Tag mit dem Identifi-
kator 1 verkauft?
2. Wie hoch sind die Umsätze für die Verkäufe insgesamt, gruppiert nach Produk-
ten (über alle Geschäfte und Zeiten)?
3. Wie hoch sind die Umsätze insgesamt (über alle Produkte, Geschäfte und Zei-
ten)?
Wie man sieht, kann die erste Anfrage direkt aus der Faktentabelle ausgelesen werden,
wobei die beiden anderen Anfragen eine geeignete Aggregation über die Dimensions-
werte mit einem passenden SQL-Ausdruck benötigen.
Für die zweite Anfrage braucht man den folgenden SQL-Ausdruck:
SELECT
Product
,
'ALL',
'ALL',
sum
(
Price
)
FROM
Facts
GROUP
BY
Product
wo man über die Dimension Product aggregiert. Anschließend liest man das Tupel für
das Produkt 1 aus der vom Ausdruck gelieferten Relation für die Beantwortung der
zweiten Anfrage.
Die dritte Anfrage kann man ähnlich der zweiten beantworten mit dem Unterschied,
dass man über alle Dimensionen mit dem folgenden SQL-Ausdruck aggregieren muss:
SELECT
'ALL',
'ALL',
'ALL',
sum
(
Price
)
FROM
Facts
1
2
1
$70
Product
Store
Time
Price
Facts
Faktentabelle
1
3
2
$40
2
1
3
$50
Grundlagen von Data-Warehousing, OLAP und mOLAP
-20-
Man summiert damit alle Preise in der Faktentabelle auf und bekommt die Antwort auf
die dritte Anfrage.
Wenn man sich alle möglichen analytischen Anfragen zu der Faktentabelle vorstellt,
kommt man zu dem Ergebnis, dass man die Aggregationen über alle möglichen Kombi-
nationen der Dimensionen braucht. Genau das macht einen Data-Cube aus: das sind
alle Werte vom Resultat einer Vereinigung der Aggregationen über alle möglichen
Kombinationen der Dimensionen [GBLP96]. Für unsere Beispiel-Faktentabelle sieht ein
Data-Cube bildender SQL-Ausdruck wie folgt aus:
(
SELECT
Product
,
Store
,
Time
,
sum
(
Price
)
FROM
Facts
GROUP
BY
Product
,
Store
,
Time
)
UNION
(
SELECT
Product
,
Store
,
'ALL',
sum
(
Price
)
FROM
Facts
GROUP
BY
Product
,
Store
)
UNION
(
SELECT
Product
,
'ALL',
Time
,
sum
(
Price
)
FROM
Facts
GROUP
BY
Product
,
Time
)
UNION
(
SELECT
'ALL',
Store
,
Time
,
sum
(
Price
)
FROM
Facts
GROUP
BY
Store
,
Time
)
UNION
(
SELECT
Product
,
'ALL',
'ALL',
sum
(
Price
)
FROM
Facts
GROUP
BY
Product
)
UNION
(
SELECT
'ALL',
Store
,
'ALL',
sum
(
Price
)
FROM
Facts
GROUP
BY
Store
)
UNION
(
SELECT
'ALL',
'ALL',
Time
,
sum
(
Price
)
FROM
Facts
GROUP
BY
Time
)
UNION
(
SELECT
'ALL',
'ALL',
'ALL',
sum
(
Price
)
FROM
Facts
)
Listing 2-1: Der Data-Cube bildende SQL-Ausdruck
Man sieht, dass dieser Ausdruck aus 2
D
Unteranfragen besteht, wobei D die Anzahl der
Dimensionen in der Faktentabelle ist. Man bezeichet jede dieser Unteranfragen als
einen Group-By, weil es sich dabei um eine Aggregation mit der Group-By Klausel
handelt. In unserem Fall gibt es 8 solche Group-Bys.
Das Resultat der SQL-Anfrage aus Listing 2-1 ist in der Tabelle 2-1 dargestellt.
Grundlagen von Data-Warehousing, OLAP und mOLAP
-21-
Product
Store
Time
Price
1 2
1
$70
1 3
2
$40
2 1
3
$50
1 2
ALL
$70
1 3
ALL
$40
2 1
ALL
$50
1 ALL
1
$70
1 ALL
2
$40
2 ALL
3
$50
ALL 2 1
$70
ALL 3 2
$40
ALL 1 3
$50
1 ALL
ALL
$110
2 ALL
ALL
$50
ALL 1 ALL
$50
ALL 2 ALL
$70
ALL 3 ALL
$40
ALL ALL
1
$70
ALL ALL
2
$40
ALL ALL
3
$50
ALL ALL
ALL
$160
Tabelle 2-1: Tabellarische Repräsentation eines Data-Cube
Die Tabelle 2-1 zeigt uns in einer tabellarischen Form, was man unter einem Data-Cube
und seinem Inhalt versteht. An der Stelle sei bemerkt, dass in der Praxis die Faktenta-
bellen Millionen von Tupel enthalten und aus mehr als nur drei Dimensionen und einer
Kennzahl bestehen, was theoretisch zu sehr großen Data-Cubes und zu sehr langen Cu-
be-Berechnungen führt. Deswegen wurden mehrere Ansätze und Datenstrukturen vor-
geschlagen, um diesen Prozess effizienter zu gestalten. Wir betrachten solche Ansätze
und Datenstrukturen in Kapitel 3 ,,Physische Data-Cube-Datenstrukturen" sowie im
nächsten Kapitel 2.2.2 ,,DCL und hDCL".
Wie man in Listing 2-1 sieht, ist es ziemlich mühsam, einen Cube manuell zu berech-
nen. Man müsste solche lange SQL-Ausdrücke per Hand eingeben. Seit dem Standard
SQL-99 ist es möglich, die Tabelle 2-1 mit einem einzigen SQL cube-Operator
[GBLP96] zu bekommen ohne alle Kombinationen von Dimensionsspalten einzugeben.
Der cube-Operator zu der Beispiel-Faktentabelle ist in Listing 2-2 gezeigt. Zum anderen
bietet der cube-Operator eine effizientere Ausführung, indem die stärker verdichteten
Aggregate auf den weniger starken aufbauen. Man kann verschiedene Aggregationen in
einem Durchgang berechnen, so dass die Faktentabelle Facts nur einmal eingelesen
werden muss.
SELECT
Product
,
Store
,
Time
,
sum
(
Price
)
FROM
Facts
GROUP
BY
CUBE (Product
,
Store
,
Time)
Listing 2-2: Der Cube-Operator zu der Beispiel-Faktentabelle
Ende der Leseprobe aus 102 Seiten
- nach oben
Details
- Arbeit zitieren
- , 2007, Hierarchische physische Data-Cube-Strukturen in einem mobilen Data-Warehouse, Hamburg, Bedey Media GmbH, https://www.diplom.de/document/229009
Ähnliche Arbeiten
Deutschlands größter Sharing Community
Jetzt Zusammenfassungen, Skripte und Klausuren kostenlos downloaden!
Uniturm.de
Ihre Vorteile als Autor
Geld verdienen Für jedes verkaufte Exemplar erhalten Sie Autorenhonorar - bis zu 40%.Kostenlose Buchveröffentlichung
Als eBook-Studie im Original und / oder auf Wunsch zusätzlich als hochwertiges Fachbuch in unserem renommierten Buchverlag.
Renommee als Fachbuchautor
Präsentieren Sie sich als Fachfrau oder Fachmann in Ihrem Fachgebiet und machen Sie sich bekannt.
Persönliche Betreuung
Unser Lektorat wird Sie persönlich betreuen und ist auch telefonisch unter 040-655992-14 erreichbar.
Weltweit im Buchhandel
Ihr Buch ist weltweit im Buchhandel und Online-Buchhandel wie z.B. amazon erhältlich.
Jetzt Autor werden!
Kommentare