Verteilte Data Warehouses

Inhaltsverzeichnis

1 Einleitung und Motivation
1.1 Data Warehouses
1.2 Verteilte Data Warehouses

2 Data Warehouse Topologien
2.1 Abgrenzung von Data Warehouses und Data Marts
2.2 Topologien
2.2.1 Zentrales Data Warehouse
2.2.2 Data Warehouse und Data Marts
2.2.3 Verteiltes oder föderiertes Data Warehouse
2.2.4 Hierarchisch verteiltes Data Warehouse
2.3 Gegenüberstellung der Topologien

3 Entwurf des Data Warehouses
3.1 Dimensional Fact Model
3.2 Beispielszenario

4 Komplexe OLAP Abfragen
4.1 MD-Join Operator
4.2 Verteilte Auswertung des MD-Joins
4.3 MD-Joins und Selektionen
4.4 Verschachtelung von MD-Joins
4.4.1 Distributivität des MD-Joins
4.4.2 MD-Join und Equi-Join
4.5 Allgemeiner MD-Join
4.6 Verteilte GMD-Join Auswertung
4.6.1 Skalla
4.7 Kosten für die Übertragung

5 Optimierung verteilter OLAP-Abfragen
5.1 Reduktion unter Berücksichtigung der Fragmentierung
5.2 Von der Fragmentierung unabhängige Reduktion
5.3 Reduktion des Aufwands für die Synchronisation
5.4 Performanzgewinn durch Reduktion

6 Abfragesprachen für OLAP
6.1 Transformation von GMD-Joins in Standard SQL
6.2 Extended Multi-Feature SQL

7 Zusammenfassung

8 Anhang
8.1 Literatur und Quellen
8.2 Abbildungen
8.3 Beispiele
8.4 Definitionen
8.5 Sätze
8.6 Tabellen

1 Einleitung und Motivation

1.1 Data Warehouses

Um langfristige Entscheidungen treffen zu können, muss das Management einer Organisation große Mengen an Daten verarbeiten, die üblicherweise in relationalen Datenbanken (RDBMS) gespeichert sind und SQL als Abfragesprache benutzen. Operative Datenbanken unterstützen diesen Prozess der Entscheidungsfindung allerdings nur ungenügend.

“A Data Warehouse is a subject-oriented, integrated, time variant, and non-volatile collection of Data in support of managements Decision support process”^[1]

Definition 1: Data Warehouse von W.H. Inmon

Ein Data Warehouse soll diese Unzulänglichkeiten der operativen Datenhaltung beheben. Es wird daher auch als Decision Support System (DSS) bezeichnet. Die Eigenschaften eines Data Warehouses sind^[2]:

- Die Daten sind von der operativen Datenhaltung getrennt
- Das Data Warehouse kann eigene Datenstrukturen aufweisen
- Ein Data Warehouse ist kein Produkt sondern ein Informationssystem
- Ein Data Warehouse ist keine Schnittstelle zwischen operativen Datenbanken
- Ein Data Warehouse ist kein Replikat einer operativen Datenbank

Tabelle 1 zeigt die Unterschiede zwischen einem Data Warehouses und einer operativen Datenbank.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Vergleich Data Warehouse mit einer operativen Datenbank^[3]

Zur Findung von strategischen Entscheidungen werden die Daten aus herkömmlichen Datenquellen herausgeholt, transformiert, bereinigt, aggregiert und schließlich redundant im Data Warehouse abgelegt. Abbildung 1 verdeutlicht diesen Prozess, der in regelmäßigen Abständen durchgeführt wird, um die Aktualität der Daten zu gewährleisten.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Transformation von Daten in Information^[4]

Nach einer Übersicht über die existierenden Data Warehouse Topologien in Abschnitt 2 folgt eine kurze Einführung in den Entwurf multidimensionaler Datenstrukturen (Abschnitt 3). In Abschnitt 4 behandelt komplexe OLAP Abfragen anhand des MD-Join Operators. Weiters werden verschiedene relationale Operatoren in Verbindung mit dem MD-Join und die verteilte Auswertung von MD-Joins erläutert. Anschließend werden einige Reduktionsalgorithmen zur Optimierung verteilter OLAP Abfragen erklärt (Abschnitt 5). In Abschnitt 6 folgt die Realisierung des MD-Joins durch Abfragesprachen auf Basis von Standard SQL und EMF-SQL (Extended Multi-Feature SQL). Letzteres bietet einige Vorteile in der Formulierung von Verschachtelten Aggregaten. Eine Zusammenfassung dieser Arbeit enthält Abschnitt 7.

1.2 Verteilte Data Warehouses

Da die Unternehmensdaten nicht zentral an einem bestimmten Standort vorliegen bzw. nicht zentral gesammelt werden können, sind verteilte Architekturen erforderlich. Für Data Warehouses ist es zweckmäßig die Daten am Ort der Entstehung aus z.B. unterschiedlichen, teilweise heterogenen Informationsquellen zu integrieren. Die entsprechenden Architekturen erläutert der folgende Abschnitt.^[5]

2 Data Warehouse Topologien

2.1 Abgrenzung von Data Warehouses und Data Marts

Ein Data Mart ist jener Teil eines Data Warehouses, der die Daten zu einem bestimmten Gegenstand bzw. Thema enthält. Meist handelt es sich dabei um einen speziellen Problembereich (wie z.B. Marketinganalysen) den ein Data Mart abdeckt. Die Daten kommen hierfür aus verschiedenen Datenquellen.^[6]

2.2 Topologien

2.2.1 Zentrales Data Warehouse

Die Daten werden an zentraler Stelle in einer Datenbank gespeichert. Es gibt nur ein Datenmodell, das für das ganze Unternehmen gilt. Vorteile dieser Art der Datenhaltung sind die zentrale Verwaltung und die hohe Skalierbarkeit des Data Warehouses.

2.2.2 Data Warehouse und Data Marts

Data Marts erlauben im Gegensatz zum Data Warehouse eine engere Sicht auf die Daten. Meist handelt es sich dabei um einen bestimmten Themenbereich, eine Unternehmensfunktion oder eine einzelnes Anwendungsprogramm, den ein Data Mart abdeckt. Das Data Warehouse vereinigt dabei die Data Marts zu einer logischen Einheit. Den genauen Sachverhalt erläutert Abbildung 2. Mit Online Analytical Processing (OLAP) unterstützen Data Warehouses sowie Data Marts erweiterte Analysefunktionen, welche eine logische, mehrdimensionale, hierarchische Sicht auf Daten (z.B. Datenwürfel) zulässt. Anwendungsgebiete sind z.B. das Erstellen von Vorhersagen, Erkennen von Trends und weitere komplexe Analysen.^[7]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Data Warehouse Topologien^[8]

2.2.3 Verteiltes oder föderiertes Data Warehouse

Kennzeichnend für Verteilte Data Warehouses ist, dass sie über Netzwerke verbunden sind, welche die verteilte Verarbeitung von Anfragen bzw. Analysen ermöglichen. Dabei spielt es keine Rolle, ob mehrere einzelne Data Warehouses im Bottom-Up Ansatz zu einem logischen Data Warehouse integriert werden (wenn z.B. zwei Unternehmen fusionieren), oder ob ein Data Warehouse aus physisch verteilten Data Warehouse bzw. Data Marts besteht (Top-Down Ansatz). Letzterer ist zweckmäßig, wenn die Verteilung des Data Warehouses auf mehrere Unternehmensstandorte erfolgen soll. Hier steht also die Integration von Abteilungs-Data-Marts zu einem globalen Schema im Vordergrund. Weitere Gründe für die Verteilung Data Warehouses können Lastverteilung, höhere Skalierbarkeit und höhere Verfügbarkeit der Daten sein.^[9] Beim physischen Entwurf eines solchen Data Warehouses sind die Kosten und der Durchsatz des Netzwerkes sowie die Verteilung bzw. Fragmentierung der Daten auf die einzelnen Rechnersysteme von besonderer Bedeutung. Die Fragmentierung von Relationen behandelt z.B. [DATE00] ausführlich. Speziell auf verteilte Data Warehouses geht [NB99] ein.^[10]

2.2.4 Hierarchisch verteiltes Data Warehouse

Im Gegensatz zum Föderierten Data Warehouse ist diese Topologie hierarchisch organisiert. Dieser Ansatz ist vor allem für landesweite Unternehmen oder Länder übergreifende Konzerne gedacht. Hierbei kann die Analyse der Daten auf verschiedenen Hierarchiestufen angefangen von einer Abteilung bis zum gesamten Konzern erfolgen. Da der Schwerpunkt der Analyse auf den Daten in unmittelbarer Umgebung zum Standort liegt, d.h. die Bezirksleitung greift auf die Bezirksdaten - die Konzernleitung auf die Daten der höchsten Hierarchiestufe usw. zu, ist dieser Ansatz gegenüber den bisher gezeigten am zweckmäßigsten. Ausgehend von den Data-Marts in den Filialen über die Data Warehouses in den Zwischenschichten bis zum konzernweiten Data Warehouse entsteht diese Topologie im Bottom-Up Ansatz. Ziel ist es, die jeweils darunter liegenden Data Warehouses in eine globale Sicht bzw. ein globales Schema zu integrieren.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Hierarchisch verteiltes Data Warehouse

2.3 Gegenüberstellung der Topologien

Tabelle 2 zeigt in einer Gegenüberstellung der vorgestellten Data Warehouses Topologien die jeweiligen Vor- bzw. Nachteile in den einzelnen Merkmalen.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: Gegenüberstellung der Topologien

In Abhängigkeit von der vorliegenden Problemstellung ist die jeweils zweckmäßigste Architektur zu wählen. Bereits in der Designphase ist auf die Skalierbarkeit Rücksicht zu nehmen, da Unternehmen wachsen und möglicherweise mit anderen Unternehmen fusionieren.

3 Entwurf des Data Warehouses

Das Hauptmerkmal von OLAP ist die mehrdimensionale Sicht auf die Daten. Konzeptuell wird durch das Dimensional Fact Model die klassische Datenmodellierung um multidimensionale Aspekte erweitert.

3.1 Dimensional Fact Model

Im Dimensional Fact Model sind folgende Begriffe relevant:

- Fakten (facts): Menge von Kennzahlen, die mit den Dimensionen in Beziehung stehen
- Kennzahlen (measures): Kernpunkt der Analyse, wie z.B. Umsätze, Verkäufe
- Dimensionen (dimensions): Die Analyse der Kennzahlen erfolgt im Kontext der Dimensionen, wie z.B. Produkt, Datum, Filiale
- Hierarchien (hierarchies) von Dimensionen: Zum Verändern der Aggregationsstufe (Granularität) der Analyse, wie z.B. Filiale – Stadt – Land

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Dimensionen und Hierarchien^[11]

3.2 Beispielszenario

Für alle nachfolgenden Algorithmen soll folgende Relation als Beispiel dienen, die Verkäufe enthält. In weiterer Folge werden Tupel mit Nr. = n als Tupel n bezeichnet.

Abbildung in dieser Leseprobe nicht enthalten

Relation 1: Verkäufe

4 Komplexe OLAP Abfragen

OLAP ermöglicht die Analyse der im Data Warehouse angesammelten Daten unter verschiedenen Blickwinkeln. Mittels OLAP Werkzeugen können Abfragen interaktiv an das Data Warehouse gestellt werden. OLAP Abfragen verwenden grundsätzlich Gruppierungen (GROUP BY) und Aggregatfunktionen wie SUM, AVG, MIN und MAX um nur die wichtigsten zu nennen. Dabei passiert es häufig, dass die Gruppierungen für das gewünschte Ergebnis schwierig zu formulieren sind. Ein Beispiel soll dies verdeutlichen.

Beispiel 1: Verschiedene Aggregationsebenen

Aus einer Verkaufsrelation soll für alle möglichen Kombinationen aus Produkt und Filiale der Umsatz ausgegeben werden. Es sind 2 n = 4 Abfragen nötig, wobei n die Zahl der Gruppierungsttribute ist. Dies ergibt sich daraus, dass jedes Gruppierungsattribut in einer Teilanfrage entweder berücksichtigt wird oder nicht (= 2 mögliche Zustände). Die Vereinigung der Einzelergebnisse bildet das Gesamtergebnis (Relation 2).^[12]

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3: SQL Abfragen

Abbildung in dieser Leseprobe nicht enthalten

Relation 2: Kombinationen von Produkt und Filiale

Leere Felder in Produkt und/oder Filiale entsprechen der ALL-Ebene. Welche Abfrage welches Ergebnis liefert ist in der Spalte Abf.Nr. ersichtlich.

Noch komplexer wird es, falls Aggregate verschachtelt vorkommen. In diesem Fall entstehen Abfragen die kaum noch zu verstehen und daher schwer wartbar bzw. optimierbar sind. Einen Lösungsansatz für diese Probleme verspricht der MD-Join, dem die strikte Trennung von Gruppen und Aggregaten zugrunde liegt.^[13]

4.1 MD-Join Operator

Durch die strikte Trennung von Gruppen und Aggregaten ermöglicht der MD-Join eine sehr feine Abstimmung von beiden bei der Formulierung von Abfragen. Dieser Vorteil kommt besonders gut zum Tragen, wenn nur ganz bestimmte Kombinationen von Gruppen (z.B. nur Filiale 1 und 3) oder benutzerdefinierte Aggregate (z.B. das Produkt, welches in den 10 vorhergehenden Tagen am häufigsten pro Filiale verkauft wurde) berechnet werden sollen.

Der MD-Join geht von zwei Relationen, der Bezugswerte-Relation (base values relation) und der Detailrelation (detail relation), aus. Die Bezugswerte (= Gruppen) bestimmen die Anzahl der Tupel in der Ergebnistabelle. Aus der Detailrelation werden die Aggregate berechnet.

Abbildung in dieser Leseprobe nicht enthalten

Definition 2: MD-Join

Abbildung in dieser Leseprobe nicht enthalten

Satz 1: MD-Join in relationaler Algebra

Optisch lässt sich der MD-Join in relationaler Algebra, wie in Abbildung 5 gezeigt, in vier Quadranten einteilen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: Optische Darstellung der Auswertung des MD-Joins

Verbal lässt sich der MD-Joins in relationaler Algebra folgendermaßen beschreiben. [Abbildung in dieser Leseprobe nicht enthalten][Abbildung in dieser Leseprobe nicht enthalten][Abbildung in dieser Leseprobe nicht enthalten]liefert den Join der Bezugswerte-Relation mit der Detailrelation über die Bedingung[Abbildung in dieser Leseprobe nicht enthalten]. Der erste Teil [Abbildung in dieser Leseprobe nicht enthalten] ([Abbildung in dieser Leseprobe nicht enthalten] stellt den Aggregationsoperator^[14] dar) des Gesamtausdrucks berechnet die Aggregate über die Attribute cn aus R. Das Schema der Aggregation entspricht dem Ergebnisschema, es enthält also alle Attribute aus B inklusive der Aggregationsfunktionen. Der hintere Teil ([Abbildung in dieser Leseprobe nicht enthalten][Abbildung in dieser Leseprobe nicht enthalten][Abbildung in dieser Leseprobe nicht enthalten]) liefert jene Tupel aus B, die beim ersten Join nicht enthalten sind. [Abbildung in dieser Leseprobe nicht enthalten] ist eine Relation mit einem Tupel, welches die Initialwerte der Aggregationsfunktionen enthält (z.B. 0 bei SUM und COUNT oder NULL bei AVG). Über das kartesische Produkt werden beide Relationen zusammengefügt. Das Schema entspricht wiederum dem Ergebnisschema, also allen Attributen aus B inklusive den Initialwerten der Aggregationsfunktionen. Schließlich entspricht die Vereinigung beider Teilrelationen dem MD-Join. Im Endergebnis sind alle Tupel aus B enthalten. Es handelt sich daher um einen Outer-Join.

Folgender Algorithmus ermöglicht die vereinfachte Auswertung des MD-Joins für algebraische und distributive Aggregatfunktionen wie AVG, COUNT, SUM, usw. Die einzelnen Arbeitsschritte sind durchnummeriert.

Abbildung in dieser Leseprobe nicht enthalten

Algorithmus 1: Auswertung des MD-Joins

Beispiel 2: Kombinationen aus Produkt und Filiale

Beispiel 1 soll mit allen Kombinationen aus Produkt und Filiale mittels MD-Join ausgewertet werden. Dazu ist Algorithmus 1 zu verwenden. Die Bezugswerte-Relation enthält die gewünschten Gruppen.

Abbildung in dieser Leseprobe nicht enthalten

Relation 3: Bezugswerte (B)

Abbildung in dieser Leseprobe nicht enthalten

Relation 4: Verkäufe (R)

Arbeitsschritt 1 besteht aus dem Durchlaufen der Bezugswerte-Relation und dem Wiederholen der Arbeitsschritte 2 und 3. Die Arbeitsschritte 2 und 3 werden anhand von Tupel 2 (b) von B demonstriert.

Arbeitsschritt 2: Für alle Zeilen r in R prüfe, ob die Bedingung [Abbildung in dieser Leseprobe nicht enthalten] in Bezug auf r und b erfüllt ist.

Arbeitsschritt 3: Bedingung[Abbildung in dieser Leseprobe nicht enthalten] (B.Produkt = R.Produkt AND B.Filiale = R.Filiale) ist für Tupel 6 und 10 von R erfüllt. Tupel b wird dem Ergebnis hinzugefügt und das Aggregat SUM(Preis*Menge) = (6 * 5 + 1 * 7) = 37 berechnet.

Abbildung in dieser Leseprobe nicht enthalten

Relation 5: Ergebnis für Tupel 2

Relation 5 stellt das Ergebnis (E) bzw. das Ergebnistupel (e) des MD-Joins dar. Einzelne Vergleiche in der Bedingung [Abbildung in dieser Leseprobe nicht enthalten] mit der ALL-Ebene eines Attributs in B sind immer erfüllt.

Beispiel 3: Kreuztabelle

Darstellung der Umsätze pro Produkt und Filiale als Kreuztabelle für die Filialen 1 und 2. Die Bezugswerte-Relation besteht nur aus dem Attribut Produkt.

Abbildung in dieser Leseprobe nicht enthalten

Relation 6: Bezugswerte (B)

[...]

---

^[1] PR03, Einführung, Folie 6

^[2] JO98, Seite 42f

^[3] IBM98, Seite 40

^[4] IBM98, Seite 41

^[5] IBM98, Seite 41

^[6] BCCFP01, Seite 453

^[7] JO98, Seite 47

^[8] ZZTH00, Seite 2

^[9] CD97

^[10] ZZTH00, Seite 2 f

^[11] PR03: Konzeptueller Entwurf, Folie 3

^[12] RSC98, Seite 267

^[13] CAJK01

^[14] PR03, Anfragesprachen, Folie 22 ff