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

Diplomarbeit von Arkadiy Omelchenko

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:

	Kurzfassung	2
	Abstract	2
	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
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	60
4.4.1	CreateRMDwarf Algorithmus und rm-Dwarf	60
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
	Patente	99
	ERKLÄRUNG	100

Textprobe:

Kapitel 2.3.2, Scheduling-Algorithmen: Für das im vorigen Kapitel vorgestellte Szenario wurde eine Reihe von Scheduling-Algorithmen vorgeschlagen und ihre Effizienz wurde gemessen. In diesem Kapitel möchten wir nur die aktuellsten Algorithmen und die früheren Ansätze sehr grob beschreiben, außer h-FCLOS, der zurzeit der beste Scheduling-Algorithmus laut MBL06 ist und somit die Grundlage für unsere weitere Forschung und Verbesserung darstellt. Wir beschreiben h-FCLOS zusammen mit seinem Vorläufer FCLOS detailliert im nächsten Unterkapitel.

Die drahtlose Kommunikation auf der physischen Ebene ist fast immer ein Broadcast. Das bedeutet, dass wenn eine Sendestation innerhalb des drahtlosen Netzwerkes ihre Daten sendet, dann empfangen alle anderen Stationen in ihrer Reichweite die gesendeten Daten.

Im üblichen Fall werden die Daten mit der geeigneten Kennzeichnung eines Empfängers versehen und nur der richtige Empfänger selbst empfängt die Daten, alle weiteren Empfänger ignorieren sie einfach. Aber im Allgemeinen und für unsere Zwecke ist es möglich, dass mehrere Empfänger die Daten bekommen, was einen so genannten Multicast bedeutet. Deswegen kann die Dissemination der Information als eine Kombination von zwei Schemas erfolgen: per Broadcast Pull und/oder Broadcast Push.

Bei Broadcast Pull wird die Information nur nach einer expliziten Klientenanfrage vom Server gesendet. Bei Broadcast Push sendet ein Server die Informationen wiederholt ganz ohne Klientenanforderungen. Man kann beide Schemas kombinieren, indem man die am meisten gefragten Informationen per Broadcast Push und die weniger gefragten per Broadcast Pull sendet.

Die vor kurzem vorgeschlagenen Scheduling-Algorithmen arbeiten nach dem Broadcast Pull Prinzip. Wir betrachten die folgenden Algorithmen: SBS-a [SC02], DV-ES [SSLCR03], STOBS-a [SC04], FCLOS [ML05], h-FCLOS [MBL06].

SBS-a [SC02] (Subsumption-Based Scheduler) war der erste Algorithmus, der speziell für die Dessimination von Cubes konzipiert war und die Ableitbarkeitseigenschaft nutzte. Das Scheduling erfolgt in zwei Schritten. Im ersten Schritt muss man den zu sendenden Sub-Cube bestimmen.

Derjenige Sub-Cube ist zu senden, der die größte total current stretch hat, was die Summe von current stretches ist. Diese beiden Metriken wurden dem LTSF Algorithmus (Longest Total Stretch First) entnommen [AM98]. Der Current stretch einer Anfrage ist das Verhältnis von der Zeit, in der sich Anfrage sich im Server befindet (response time), zu der Zeit, die für die Beantwortung der Anfrage vergehen würde, wenn diese Anfrage eine einzelne Anfrage an den Server wäre (service time).

Im zweiten Schritt ermittelt man auch die Sub-Cubes, die durch die Beantwortung der Anfrage mit dem im ersten Schritt gewählten Sub-Cube auch automatisch bedient werden und löscht diese Anfragen aus der Warteschlange. In diesem Schritt nutzt man die Ableitbarkeitseigenschaft von Sub-Cubes, die vom ausgewählten Sub-Cube unter Berücksichtigung des speziellen Parameters a ableitbar sind. Dieser Parameter a steuert die ableitbare Anfragemenge, indem man die Unterschiede zwischen der Dimensionalität (Anzahl der Dimensionen) des zu sendenden Sub-Cube und den Dimensionalitäten der ableitbaren Sube-Cubes betrachtet. Bei a=0 würde man keine weiteren ableitbaren Sub-Cubes finden, bei a=1 wären es alle möglichen ableitbaren Sub-Cubes. Dieser Schritt setzt voraus, dass die Klienten über diese Optimierung Bescheid wissen und ihre ursprünglich angeforderten Sub-Cubes aus dem gesendeten Sub-Cube lokal ableiten. Die Sub-Cubes werden als Summary Tables zu Klienten gesendet.

DV-ES [SSLCR03] (Dwarf-Views and Extraction-Subsumption) ist der Algorithmus, der die Prinzipien von SBS-a für das Scheduling nutzt. Der Unterschied besteht darin, dass der Server anstatt nur Summary Tables (wie in SBS-a) auch die spezielle Data-Cube-Datenstruktur Dwarf senden kann. Man nimmt diejenige Datenstruktur, die die kleinere Größe hat. Wir betrachten Dwarfs ausführlich in Kapitel 3.2 Dwarf-Technologie.

Hier reicht es aus zu sagen, dass Dwarfs eine sehr komprimierte Datenstruktur für das Speichern von Cubes ist. Sie sind so kompakt, dass einige Sub-Cubes genauso groß wie die Summary Tables sind oder noch kleiner. Die Klienten müssen beide Datenstrukturen empfangen und verarbeiten können.

STOBS-a [SC04] (Summary Tables On-Demand Broadcast Scheduler) hat einen ähnlichen zweit-schrittigen Scheduling-Prozess wie in SBS-a, aber mit einigen Unterschieden. Den größten Unterschied gibt es im ersten Schritt, wo man eine andere Metrik für die Auswahl des zu sendenden Sub-Cube nimmt. Für jede Anforderung wird die Metrik berechnet, mit R – Anzahl der Anforderungen nach dem Sub-Cube, W – die Zeit des Eintreffens der ersten Anforderung nach dem Sub-Cube, S – die Größe der Summary Table für den Sub-Cube.

Man sendet den Sub-Cube mit dem größten Wert der Metrik. Der zweite Schritt ist fast derselbe wie in SBS-a, nur mit dem kleinen Unterschied in der Definition von a, was aber dasselbe Prinzip darstellt. Man sendet wie in SBS-a die Summary Tables als die physische Repräsentation eines Sub-Cube.

Die beiden Algorithmen FCLOS [ML05] (Force Clustering OLAP Scheduler) und h-FCLOS [MBL06] (hybrid-FCLOS) haben im Wesentlichen vieles gemeinsam, deswegen beschreiben wir sie beide in diesem Unterkapitel.

Der Scheduling-Prozess erfolgt ähnlich wie in allen anderen vorgestellten Algorithmen in zwei Schritten. Der zweite Schritt ist derselbe mit der Definition von a aus STOBS-a, wo man die ableitbaren Sub-Cubes aus der Warteschlange entfernt.

Der erste Schritt nutzt ganz unterschiedliche Metriken. Für alle in der Warteschlange stehenden Anforderungen berechnet der Scheduler die sogenannte Sub-Cube Metrik SM: , mit R – Anzahl der Anforderungen nach dem Sub-Cube. W – Zeit, die die Anforderung in der Warteschlange verbringt, D – Anzahl der Dimensionen im Sub-Cube.

Nach der Berechung von SM bildet der Scheduler aus Sub-Cubes in der Warteschlange alle möglichen Broadcast Cluster (BCL). Diese bildet man auf folgende Weise: jeder Cluster besteht aus einem Vaterknoten (parent node) und aus allen von ihm ableitbaren Kinderknoten. Aus Effizienzgründen möchte man die Anzahl der Kinderknoten verkleinern, was in dem Algorithmus mit dem Parameter a geschieht: vereinfacht ist diese Zahl gleich der Anzahl der Pfade in DCL oder hDCL, die man beginnend aus dem Vaterknoten auf der Suche nach Kinderknoten nehmen kann. Zum Beispiel für a=1 würde der Cluster für den Vaterknoten PT die Kinderknoten P und T enthalten, und für a=2 auch den Knoten “–“ dazu.