Hierarchische physische Data-Cube-Strukturen in einem mobilen Data-Warehouse

Omelchenko, Arkadiy

Hierarchische physische Data-Cube-Strukturen in einem mobilen Data-Warehouse

Zusammenfassung

Inhaltsangabe:Einleitung:
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 unternehmerischen Alltag. 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, sowie mit den für die Übertragung eingesetzten physischen Data-Cube-Datenstrukturen.
Wir entwickelten dabei eine neue Datenstruktur m-Dwarf, die speziell für den mOLAP konzipiert ist. Sie speichert keine Aggregatinformationen 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 wesentlich verbessert. Wir haben diesem neuen Algorithmus den Namen FCLOSmD (FCLOS with m-Dwarfs) gegeben. Mit FCLOSmD wird im mOLAP die durchschnittliche Wartezeit um 40%, der durchschnittliche Energieverbrauch um 40% und das generierte Datenvolumen um 30% verringert. Inhaltsverzeichnis:Inhaltsverzeichnis:
Kurzfassung2
Abstract2
Inhaltsverzeichnis3
Abbildungsverzeichnis6
Tabellenverzeichnis7
Vorwort8
1.Einführung9
1.1Grundlagen9
1.2Problembeschreibung9
1.3Unsere Ziele und unser Beitrag10
1.4Überblick11
2.Grundlagen von Data-Warehousing, OLAP und mOLAP13
2.1Data-Warehousing13
2.1.1Einführung13
2.1.2Terminologie und Definitionen14
2.1.3Architektur eines Data-Warehouse14
2.1.4Datenmodellierung für Data-Warehouses16
2.1.5ROLAP and MOLAP18
2.2OLAP18
2.2.1Data-Cube und der cube-Operator19
2.2.2DCL und hDCL23
2.3mOLAP27
2.3.1Architektur27
2.3.2Scheduling-Algorithmen29
2.3.3FCLOS und h-FCLOS31
3.Physische Data-Cube-Datenstrukturen34
3.1Stand der Dinge und Related Work34
3.1.1ROLAP34
3.1.2MOLAP35
3.1.3Index-Strukturen35
3.1.4View Materialisierung38
3.1.5Data-Cube-Datenstrukturen39
3.2Dwarf-Technologie44
3.2.1Dwarf44
3.2.2Hierarchical Dwarf (h-Dwarf)51
3.2.3Coarse-grained Dwarf (cg-Dwarf) und Fully coarse-grained Dwarf (fcg-Dwarf)52
3.2.4Persistenz von Dwarfs, h-Dwarfs und cg-Dwarfs54
4.Mobile Dwarf (m-Dwarf)56
4.1Motivation56
4.2Kompromiss in mOLAP56
4.3Struktur des m-Dwarf58
4.4Erzeugen des m-Dwarf60
4.4.1CreateRMDwarf Algorithmus […]

Leseprobe

Inhaltsverzeichnis

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.

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

(FCLOS with m-Dwarfs) gegeben. Mit FCLOS

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

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

to this new algorithm (FCLOS with m-

Dwarfs). With FCLOS

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

Inhaltsverzeichnis

-3-

Inhaltsverzeichnis

Kurzfassung... 1

Abstract... 1

Inhaltsverzeichnis ... 3

Abbildungsverzeichnis... 6

Tabellenverzeichnis ... 7

Vorwort... 8

Einführung ... 9

1.1 Grundlagen ... 9

1.2 Problembeschreibung ... 9

1.3

Unsere Ziele und unser Beitrag ... 10

1.4 Überblick ... 11

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

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

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

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

Test- und Simulationsergebnisse der Dwarf-Technologie und m-Dwarfs

in mOLAP ... 78

6.1

Größenverhältnisse der verschiedenen Dwarfs ... 78

6.2 Simulationsergebnisse

mOLAP ... 89

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

(FCLOS with m-Dwarfs) genutzt. Der FCLOS

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

-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-

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-

$70

Product

Store

Time

Price

Facts

Faktentabelle

$40

$50

CodeId

Details

Seiten
Erscheinungsform: Originalausgabe
Jahr: 2007
ISBN (eBook): 9783836605427
DOI: 10.3239/9783836605427
Dateigröße: 1.5 MB
Sprache: Deutsch
Institution / Hochschule: Freie Universität Berlin – Mathematik und Informatik, Informatik
Erscheinungsdatum: 2007 (September)
Note: 1,3
Schlagworte: olap mobile computing abfrageverarbeitung dwarf create rmdwarf fclosmd data warehouse data-cube-struktur

Autor

Arkadiy Omelchenko (Autor:in)

Hierarchische physische Data-Cube-Strukturen in einem mobilen Data-Warehouse

Zusammenfassung

Leseprobe

Inhaltsverzeichnis

Details

Autor

Arkadiy Omelchenko (Autor:in)