1. Einleitung
2. OLAP
2.1. Allgemeines
2.2. Serverarchitekturen
3. Anfrageverarbeitung
3.1. Probleme mit  GROUP BY
3.2. CUBE- und ROLLUP-Operatoren
3.3. ALL-Wert
3.4. Adressierung des Datenwürfels
3.5. Berechnung von cubes und roll-ups
3.6. Unterstützung von CUBE und ROLLUP
4. Verwaltung multidimensionaler Daten
4.1. Speicherung multidimensionaler Daten
4.2. Implementierung des Data Cube
4.3. Laden des Data Cube
5. Der OLAP-Benchmark
5.1. Umgebung
5.2. Struktur der Datenbank
5.3. Datenfiles
5.4. Queries
5.5. Vollständige Offenlegung
6. OLAP-Tool: Seagate Holos
6.1. Holos-Client
6.2. Holos Language
7. Literaturverzeichnis

Data Warehousing und on-line analytic processing (OLAP) sind die grundlegenden Elemente für entscheidungsunterstützende Systeme, die in den letzten Jahren immer mehr in das Zentrum der Datenbank-Industrie gerückt sind.
Nach [CD97] basieren OLTP-Systeme auf  strukturierten, oft wiederholten Tasks mit kurzen, atomaren, isolierten Transaktionen. Diese Transaktionen benötigte detaillierte Daten auf dem neuesten Stand. Sie lesen oder ändern wenige (Dutzend) Datensätze, der Zugriff erfolgt typischerweise über den Primärschlüssel. Operationale Datenbanken tendieren zu Größenordnungen von Hunderten von Megabyte bis in den Gigabytebereich hinein. Das Hauptaugenmerk liegt auf einer guten Throughput-Performance. Konsequenterweise widerspiegelt die das Datenbankdesign die operationale Semantik dieser auf der Datenbank arbeitenden Applikationen.
Data Warehouse-Systeme dagegen sind entscheidungsunterstützende Systeme. Die hier benötigten Daten sollen nicht möglichst detailliert sein, sondern eine Zeit- und Gesamtübersicht ermöglichen. Da Data Warehouses viele Daten (aus verschiedenen Datenbanken) enthalten, sind sie größer als operationale Datenbanken, zu entwickelnde Systeme sind in Größenordnungen von Terrabyte projektiert. Die Arbeitslast besteht größtenteils aus ad-hoc-Queries, komplexe Queries, die auf Millionen von Datensätzen zugreifen. Query-Throughput und Antwortzeit sind hier wichtiger als Transaktions-Throughput.
Um komplexe Datenanalyse und Visualisierung zu ermöglichen, sind Daten im Data Warehouse multidimensional modelliert. Oftmals sind diese Dimensionen hierarchisch geordnet. OLAP-Operationen schließen roll-up- und drill-down-Operationen ein.
Diese Seite gibt einen Überblick über OLAP-Operationen und Serverarchitekturen. Sie geht auf Probleme bei der Aggregation von Daten mittels GROUP BY ein und vermittelt die in [GC96] präsentierten Lösungsansätze unter Zuhilfenahme des CUBE-Operators. Zudem gibt sie einen Überblick über den OLAP-Benchmark APB-1 und stellt (als ein Beispiel für OLAP-Tools) Seagate Holos vor.

2.1. Allgemeines
Datenbanksysteme speichern und verarbeiten Daten in Tabellen. Daher ist eine Benutzersicht immer zweidimensional: eine tabellarische Darstellung, beispielsweise Verkaufszahlen eines Produkts pro Monat.
 

Monat  Produkt 1  Produkt 2  Produkt 3  Produkt 4  ...  Januar            Februar            März            ...           Tabelle1

Für OLAP-Anfragen ist dies jedoch nicht mehr ausreichend, einem Benutzer muß es möglich sein, Daten in mehr als zwei Dimensionen zu verarbeiten. Um solche komplexe Anfragen zu unterstützen, erfolgt die Modellierung von Daten multidimensional. Solche Datenstrukturen nennt man Data Cubes, da sie bei drei Dimensionen als Würfel visualisiert werden können. Als Beispiel die Verkaufszahlen von Produkten pro Region pro Monat oder die Verkaufszahlen der Produkte pro Größe pro Quartal. Jede Dimension entspricht dabei einer Variablen.
 
 

Abbildung 1: Struktur eines Datenwürfels (Graphik nach [TR97])

 
In der Praxis verwendet man natürlich „Würfel" mit sehr viel mehr Dimensionen. Oft sind die-se Dimensionen hierarchisch;  die Zeit z.B. könnte als Tag-Monat-Jahr-Hierar-chie organisiert sein. Typische OLAP-Operationen enthalten roll-up- (Reduzierung der Dimensionen) und drill-down-Operationen (Erhöhung der Anzahl der Dimensionen des Hyperwürfels) entlang einer oder mehrerer Dimensionen.
Versucht man, auf bestehenden operationalen Datenbanken, die auf OLTP-Lasten abgestimmt sind, komplexe OLAP-Queries durchzuführen, erhält man keine befriedigende Performance. Weiterhin benötigt man zur Entscheidungsunterstützung zusätzliche Daten, die in operationalen Datenbanken meist nicht vorhanden sind, z.B. sind zur Trendanalyse historische Daten nötig, während operationale Datenbanken nur aktuelle Daten speichern.
Zudem unterstützen die wenigsten kommerziellen, für OLTP konzipierten Datenbanksysteme multidimensionale Datenmodelle und für OLAP-Operationen benötigten speziellen Datenorganisation, Zugriffs- und Implementierungmethoden.
Nachfolgende Tabelle vergleicht operative und Data Warehouse-Systeme:
 

Operative Systeme Data Warehouse Zweck Unterstützung und Abwicklung der Geschäftsprozesse Informationen für Controlling, dispositive und strategische Entscheidungen Inhalt detaillierte, aktuelle, nicht historisierte Geschäftsdaten vereinheitlichte, detaillierte, verdichtete, historisierte Daten auch aus externen Quellen und umfassende Metadaten Aktualität online, realtime in der Regel älter als ein Tag Modellierung funktionsorientiert  standardisiert, entbenutzertauglich, sachgebietsorientiert  Update laufend und konkurrierend ergänzend, Historisierung von Daten  Abfragen strukturiert im Programmcode der TA-Programme komplexe, wechselnde Fragestellungen und vorgefertigte Standardauswertungen  Daten atomisiert; „record-at-a-time" summiert; viele Datensätze zu einem Zeitpunkt  Tabelle 2 (nach [Me98] und [Pi])

 
2.2. Serverarchitekturen
Wie im letzten Abschnitt gezeigt, sind herkömmliche Datenbanksysteme nicht oder kaum in der Lage, multimensionale Sichten auf Daten zu unterstützen. Jedoch unternehmen viele Anbieter von Datenbanksystemen jetzt Anstrengungen, diese zusätzlichen Anforderungen zu erfüllen. Neben den traditionellen Datenbank-Servern kann man drei Kategorien von Servern unterscheiden, die speziell für entscheidungsunterstützende Systeme entwickelt werden:

• spezialisierte SQL-Server

Ein Beispiel für diese Klasse Server ist Redbrick. Das Hauptaugenmerk hier liegt auf der Bereitstellung einer erweiterten Anfragesprache und der Unterstützung von SQL-Queries über Star- und Snowflake-Schematas.
• ROLAP-Server

Data Warehouse-Systeme können auch auf standardisierten oder erweiterten relationalen Datenbanksystem implementiert werden. In diesem Fall spricht man von relationalen OLAP-Servern (ROLAP).
ROLAP-Server sind Zwischenserver zwischen relationalen Back-End-Servern (auf denen die Daten des Data Warehouse gespeichert sind) und Client-Front-End-Tools. Microstrategy ist ein Beispiel für diese Art von Servern. ROLAP-Server erweitern herkömmliche relationale Server mit spezialisierter Zugriffs- und Implementierungsmethoden sowie SQL-Erweiterungen für eine effiziente Unterstützung multidimensionaler OLAP-Queries.
Die Stärke von ROLAP-Servern ist die Ausnutzung der Skalierbarkeit und der Transaktions-Eigenschaften relationaler Systeme. Allerdings können Unstimmigkeiten zwischen OLAP-Queries und SQL  zu Flaschenhälsen hinsichtlich der Performance von OLAP-Servern  werden.
• MOLAP-Server

Multidimensionale OLAP-Server (MOLAP) unterstützen direkte die multidimensionale Sicht auf Daten durch eine multidimensionale Storage-Engine. Sie speichern Daten direkt in speziellen Datenstrukturen (z.B. Arrays) und implementieren OLAP-Operationen über diesen speziellen Datenstrukturen. Dies ermöglicht die Implementierung multidimensionaler Front-End-Queries auf der Speicherschicht via Direkt-Mapping. Ein Beispiel für diese Art von Server ist Essbase (Arbor).
Dieser Ansatz hat den Vorteil exzellenter Indexeigenschaften, nutzt jedoch den Speicher schlecht aus, speziell bei dünnen Datensätzen. Einige MOLAP-Server versuchen diesen Nachteil durch einen 2-Level-Speicherung zu umgehen und nutzen dabei Index-Strukturen und kleinere Arrays.

Abbildung 2: Vergleich von ROLAP- und MOLAP-Architektur (nach Graphik aus [Da96])

Datenanalysetools verwenden häufig die „dimensionale Reduzierung" (Aggregation), oft durch Summierung von Daten entlang der weggelassenen Dimensionen. Ein Beispiel: Bei der Analyse von PKW-Verkaufszahlen konzentrieren wir uns auf Rolle, die Modell, Jahr und Farbe beim Verkauf spielen. Dazu ignorieren wir die Unterschiede zweier Verkäufe entlang der Dimensionen Datum des Verkaufs oder Händler und analysieren die Verkäufe nur hinsichtlich Verkäufen von Wagen nach Modell, nach Jahr und nach Farbe.

3.1. Probleme mit  GROUP BY
Im SQL-Standard benutzt man den GROUP BY-Operator zur  Aggregationsunterstützung sowie fünf Funktionen: COUNT(), SUM(), MIN(), MAX() und AVG(). Bestimmte häufige Formen der Datenanalyse sind mit diesen SQL-Konstrukten schwierig darzustellen. Dies sind Histogramme, roll-up-Summen und drill-down-Zwischensummen sowie Kreuztabellen.

(1)  Histogramme
Der Standard-SQL-Operator GROUP BY erlaubt keine direkte Konstruktion von Histogrammen. Histogramme müssen indirekt berechnet werden, z.B. durch SQL-Konstrukte mit verschachtelten Queries. Als Beispiel soll eine Query dienen, die auf Tabelle 3 beruht (davon ausgehend, daß eine Funktion Nation() Länge und Breite in den Namen eines Staates umsetzen kann).
 

Zeit Breite Länge  Höhe  (m)  Temperatur  (°C)  Druck  (mb)  1.6.98:1500   37:58:33N   122:45:28W   102 21 1009  ...  7.6.98:1500  34:16:18N  27:05:55W  10 23 1024 Tabelle 3

 

SELECT   day, nation, MAX(Temperatur)
FROM     Wetter
GROUP BY Day(Zeit) AS day,
         Nation(Länge, Breite) AS nation;

Einige SQL-Dialekte erlauben diese Anfrage, Standard-SQL leider nicht: eine Funktion wie z.B. Nation() kann nicht zusammen mit GROUP BY eingesetzt werden. Wir müssen in diesem Fall eine verschachtelte Query benutzen:

SELECT   day, nation, MAX(Temperatur)
FROM     ( SELECT Day(Zeit) AS day,
                  Nation(Länge, Breite) AS nation,
                  Temperatur
           FROM Wetter
         ) AS foo
GROUP BY day, nation;
 

(2)  roll-up und drill-down
Ein noch größeres Problem sind roll-ups mit Summen und drill-downs mit Zwischensummen. Tabelle 4 verdeutlicht das Prinzip: Daten sind nach Modell, dann nach Jahr, dann nach Farbe aggregiert. Die Übersicht zeigt Datenaggregation in drei Leveln. Erhöhung des Level nennt man rolling-up der Daten, Verminderung drilling-down in die Daten. Datenaggregation erzeugt auf jedem verschiedenem Level eine Zwischensumme.
 

Modell   Jahr   Farbe   Verkäufe   nach Modell  nach Jahr  nach Farbe Verkäufe   nach Modell  nach Jahr Verkäufe   nach Modell  Opel  1994  grün 50 weiß 40 90 grün 85 weiß 115 200 290 Tabelle 4

Die Tabelle suggeriert das Anlegen von 2N Spalten für einen roll-up von N Elementen. Allerdings kann man wegen der leeren Felder (NULL-Werte) keinen Schlüssel festlegen und benötigten noch eine weitere Spalte. Die nächste Tabelle ist eine elegante Lösung dieses Problems:
 

Modell  Jahr  Farbe   Verkäufe  Verkäufe   nach Modell  nach Jahr Verkäufe   nach Modell  Opel  1994  grün 50 90 290 Opel 1994 weiß 40 90 290 Opel 1995 grün 85 200 290 Opel 1995 weiß 114 200 290 Tabelle 5

Allerdings muß diese Übersicht wegen der enormen Anzahl von Spalten in den resultierenden Tabellen verworfen werden, müßte man doch 64 Spalten für die Beantwortung einer 6-dimensionalen Query anlegen.
Besser geeignet ist folgender Ansatz, um das exponentielle Anwachsen der Spaltenanzahl zu vermeiden: die Einführung eines Wertes ALL. Tabelle 6 demonstriert diesen Ansatz.
 

Modell  Jahr  Farbe   Verkäufe  Opel  1994  grün 50 Opel 1994 weiß 40 Opel 1994 ALL 90 Opel 1995 grün 85 Opel 1995 weiß 115 Opel 1995 ALL 200 Opel ALL ALL 290 Tabelle 6

Diese Tabelle kann mittels folgender SQL-Query gebildet werden:

SELECT ‘ALL’, ‘ALL’, ‘ALL’, SUM(Verkäufe)
  FROM  Verkäufe
  WHERE  Modell = ‘Opel’
UNION
SELECT Modell, ‘ALL’, ‘ALL’, SUM(Verkäufe)
  FROM  Verkäufe
  WHERE  Modell = ‘Opel’   GROUP BY Modell
UNION
SELECT Modell, Jahr, ‘ALL’, SUM(Verkäufe)
  FROM  Verkäufe
  WHERE  Modell = ‘Opel’   GROUP BY Modell, Jahr
UNION
SELECT Modell, Jahr, Farbe, SUM(Verkäufe)
  FROM  Verkäufe
  WHERE  Modell = ‘Opel’ GROUP BY Modell, Jahr, Farbe;

Dies ist nur ein simpler dreidimensionaler roll-up. Eine Aggregation über N Dimensionen erfordert N solcher UNIONS...
Ein roll-up ist asymmetrisch - in Tabelle 7 sind die Verkäufe nach Jahr, aber nicht die Verkäufe nach Farbe aggregiert. Die fehlenden Zeilen zeigt die nächste Tabelle.
 

Modell   Jahr   Farbe   Verkäufe  Opel ALL grün 135 Opel ALL weiß 155 Tabelle 7

Diese Zeilen können durch Hinzufügen der nachfolgenden Klausel zum obigen SQL-Statements erfaßt werden:

UNION
SELECT Modell, ‘ALL’, Farbe, SUM(Verkäufe)
  FROM Verkäufe
  WHERE Modell = ‘Opel’
  GROUP BY Modell, Farbe;

(3)  Kreuztabellen
Das Ergebnis einer symmetrischen Aggregation ist eine Tabelle, die man Kreuztabelle nennt. Die Tabellen 5 und 6 sind die relationalen Formen einer Kreuztabelle, im Allgemeinen werden Kreuztabellen-Daten in einer kompakteren Form (wie in Tabelle 8) dargestellt.
 

Opel   1994   1995   Total (ALL)  grün 50 85 135 weiß 40 115 155  Total (ALL)  90 200 290 Tabelle 8

Diese Kreuztabelle ist eine zweidimensionale Aggregation. Werden andere PKW-Typen hinzugefügt, wird es eine 3D-Aggregation. Daten über z.B. VW-Produkte fügen eine weitere Kreuztabellen-Ebene hinzu.

3.2. CUBE- und ROLLUP-Operatoren
Die nachfolgende Graphik zeigt das Konzept für Aggregationen bis hinauf zu drei Dimensionen. Das herkömmliche GROUP BY generiert den N-dimensionalen Kern des Datenwürfels. Die N-1 niedrigdimensionierten Aggregationen erscheinen als Punkte, Linien, Ebenen, Würfel oder Hyper-Würfel um den Kern herum.
 

Abbildung 3: CUBE-Operator (nach Graphik aus [GC96])

 
Die Generierung eines Datenwürfels erfordert die Generierung der Allmenge (Menge aller Teilmengen) der aggregierten Spalten. Der CUBE-Operator ersetzt dabei den SQL-GROUP BY-Operator (GROUP BY und ROLL UP sind Spezialfälle des CUBE-Operators). [GC96] schlägt deshalb eine Syntax-Erweiterung zu SQL vor. Die momentane GROUP BY-Syntax:

 GROUP BY
   {<column name> [collate clause] ,...}

Für die Unterstützung von Histogrammen und anderen Aggregationen soll die Syntax erweitert werden:

 GROUP BY <aggregation list>
 <aggregation list> ::=
   { ( <column name> | <expression> )
     [ AS <correlation name> ]
     [ <collate clause> ]
       ,...}

Diese Erweiterung ist unabhängig vom CUBE-Operator. Sie behebt einige schon vorher existierende Probleme mit GROUP BY. Viele Systeme erlauben diese Erweiterung bereits.
Nun kann der SQL-GROUP BY-Operator erweitert werden:

 GROUP BY <aggregation list>
 <aggregation list> ::=
   { ( <column name> | <expression> )
       [ AS <correlation name> ]
       [ <collate clause> ]
   ,...}
       [ WITH ( CUBE | ROLLUP ) ]
 
 

Verkäufe   Modelle  Jahr  Farbe   Verkäufe  Opel  1990  rot 5 Opel 1990 weiß 87 Opel 1990 blau 62 Opel 1991 rot 54 Opel 1991 weiß 95 Opel 1991 blau 49 Opel 1992 rot 31 Opel 1992 weiß 54 Opel 1992 blau 71 VW 1990 rot 64 VW 1990 weiß 62 VW 1990 blau 63 VW 1991 rot 52 VW 1991 weiß 9 VW 1991 blau 55 VW 1992 rot 27 VW 1992 weiß 62 VW 1992 blau 39 Tabelle 9

Data Cube   Modell  Jahr  Farbe   Verkäufe  Opel  1990  blau 62 Opel 1990 rot 5 Opel 1990 weiß 95 Opel 1990 ALL 154 Opel 1991 blau 49 Opel 1991 rot 54 Opel 1991 weiß 95 Opel 1991 ALL 198 Opel 1992 blau 71 Opel 1992 rot 31 Opel 1992 weiß 54 Opel 1992 ALL 156 Opel ALL blau 182 Opel ALL rot 90 Opel ALL weiß 236 Opel ALL ALL 508 VW 1990 blau 63 VW 1990 rot 64 VW 1990 weiß 62 VW 1990 ALL 189 VW 1991 blau 55 VW 1991 rot 52 VW 1991 weiß 9 VW 1991 ALL 116 VW 1992 blau 39 VW 1992 rot 27 VW 1992 weiß 62 VW 1992 ALL 128 VW ALL blau 157 VW ALL rot 143 VW ALL weiß 133 VW ALL ALL 433 ALL 1990 blau 125 ALL 1990 rot 69 ALL 1990 weiß 149 ALL 1990 ALL 343 ALL 1991 blau 106 ALL 1991 rot 104 ALL 1991 weiß 110 ALL 1991 ALL 314 ALL 1992 blau 110 ALL 1992 rot 58 ALL 1992 weiß 116 ALL 1992 ALL 284 ALL ALL blau 339 ALL ALL rot 233 ALL ALL weiß 369 ALL ALL ALL 941 Tabelle 10

Der CUBE-Operator erzeugt aus Tabelle 9 die Tabelle 10 mit allen diesen aggregierten Werten:

  SELECT Modell, Jahr, Farbe, SUM(Verkäufe) AS Verkäufe
    FROM Verkäufe
    WHERE Modell IN (‘Opel, ‘VW’) AND Jahr BETWEEN 1990 AND 1992
    GROUP BY Modell, Jahr, Farbe WITH CUBE;

3.3. ALL-Wert
Wird der ALL-Wert wirklich benötigt? Jeder ALL-Wert repräsentiert einen Set - einen Set, über die die Aggregation berechnet wird. In den Tabelle 6 und 7 z.B. sind die Sets:

  Modell.ALL = ALL(Modell) = {Opel, VW}
  Jahr.ALL = ALL(Jahr) = {1990, 1991, 1992}
  Farbe.ALL = ALL(Farbe) = {rot, weiß, blau}

In der Realität führt das in die Welt verschachtelter Relationen - Relationen können Werte sein. Das ist ein wichtiger Schritt für relationale Systeme.
Man kann jeden ALL-Wert als kontext-sensitives Token ansehen, der ein Set repräsentiert. Den ALL-Wert als korrespondierendes Set anzusehen, definiert die Semantik des relationalen Operators (z.B. equals und IN). Eine Funktion ALL() generiert ein Set, welches mit den Werten wie im obigen Beispiel assoziiert werden kann. ALL() auf  andere Werte angewendet liefert NULL zurück.
Nach [GC96] wirkt sich die Einführung von ALL auf viele Aspekte von SQL aus, einige davon sind:

• ALL wird ein neues Schlüsselwort
• ALL [NOT] ALLOWED ist der column-Syntaxdefinition und den column-Attributen im Systemkatalog hinzuzufügen

• die Verwendung von NULL anstelle von ALL
• keine Implementierung der Funktion ALL()
• die Implementierung einer Funktion GROUPING() zur Unterscheidung zwischen NULL und ALL

  SELECT Modell, Jahr, Farbe, SUM(Verkäufe),
    GROUPING(Modell),
    GROUPING(Jahr),
    GROUPING(Farbe)
  FROM Verkäufe
  GROUP BY CUBE Modell, Jahr, Farbe;

Wo vorher der ALL-Wert erschien, steht jetzt als korrespondierender Wert NULL im Datenfeld und TRUE im korrespondierenden Gruppenfeld. Als Beispiel, die globale Summe aus Tabelle 10 stellt sich als Tupel

  (NULL, NULL, NULL, 941, TRUE, TRUE, TRUE)

dar, anstelle des Tupels

  (ALL, ALL, ALL, 941)

mit dem „realen" CUBE-Operator.

3.4. Adressierung des Datenwürfels
Im letzten Abschnitt wurde die Berechnung von Datnwürfels besprochen. Dieser Abschnitt beschäftigt sich mit Erweiterungen der SQL-Syntax zum Zweck des leichten Zugriffs auf Elemente des Datenwürfels.
Die allgemeinsten Anfragen sind die nach Prozenten der Gesamtsumme. In SQL wird dies als verschachtelte SQL-Query realisiert:

  SELECT Modell, Jahr, Farbe, SUM(Verkäufe),
         SUM(Verkäufe)/
            (SELECT SUM(Verkäufe)
             FROM Verkäufe
             WHERE Modell IN {‘Opel’, ‘VW’}
                   AND Jahr BETWEEN 1990 AND 1992
            )
  FROM   Verkäufe
  WHERE  Modell IN {‘Opel’,’VW’}
         AND Jahr BETWEEN 1990 AND 1992
  GROUP BY CUBE Modell, Jahr, Farbe;

[GC96] empfiehlt folgende Syntaxvereinfachung:

  SELECT Modell, Jahr, Farbe, SUM(Verkäufe) AS total,
         SUM(Verkäufe) / total(ALL, ALL, ALL)
  FROM   Verkäufe
  WHERE  Modell IN {‘Opel’, ‘VW’}
         AND Jahr BETWEEN 1990 AND 1992
 GROUP BY CUBE Modell, Jahr, Farbe;

Der nächste Schritt ist die des Indizierung eines Wertes. Der momentane Ansatz, um eine Feld aus einem 2D-Würfel zu lesen

  SELECT  v
  FROM cube
  WHERE row = :i AND column = :j

sollte ersetzt werden durch

  cube.v(:i, :j)

Mit dieser Erweiterung der SQL-Syntax sollte es sehr einfach sein, Super-Super-Aggregationen aus dem Basis-Würfel zu berechnen.

3.5. Berechnung von cubes und roll-ups
CUBE und ROLLUP verallgemeinern Aggregationen und GROUP BY, so daß all die Technologien für die Berechnung solcher Resultate ebenfalls auf die Berechnung des Kerns eines Würfels angewendet werden können [Gr93]. Die Basistechnik für die Berechnung eines ROLLUPs ist das Sortieren der Tabelle auf dem Aggregations-Attributen und die darauffolgende Berechnung der Aggregationsfunktion. Ist das ROLLUP-Resultat klein genug, um in den Hauptspeicher zu passen, kann es durch Scannen des Input-Sets und Anwendung jedes Datensatzes auf den im Speicher befindlichen ROLLUP berechnet werden. Nach [Gr93] sind die Basistechniken zur Berechnung von Aggregationen:

• Minimalisierung von Datenbewegungen und Prozesskosten, Aggregate auf dem niedrigsten verfügbaren Systemlevel berechnen
• Wenn möglich, Arrays oder Hashing nutzen, um die Aggregationsspalten im Speicher zu organisieren; Speichern eines Aggregations-Wertes für jedes Array oder jeden Hash-Eintrag
• Sind die Aggregations-Werte große Strings, erscheint eine Hash-Symbol-Tafel ratsam, die jedem String einen Integer-Wert zuweist. Auf diese Art können Aggregations-Werte kleingehalten werden. Die Werte werden dichter und können so als N-dimensionales Array gespeichert werden
• Wenn die Anzahl der Aggregations-Werte zu groß ist, um in den Speicher zu passen, benutze man Sortierung oder Hybrid-Hashing, um die Daten nach Werten zu ordnen und mit einem sequentiellen Scan zu aggregieren
• Sind die Daten über viele Platten oder Knoten verteilt, empfiehlt sich eine parallele Aggregation jeder Partition mit nachfolgender Vereinigung

3.6. Unterstützung von CUBE und ROLLUP
Stand der Unterstützung: Microsoft SQL Server 6.5 unterstützt CUBE und ROLLUP jetzt ca. zwei Jahre. Es existieren Anwendungen, die diese Funktionen in Triggern nutzen, um bei Änderung in darunterliegenden Tabellen den Datenwürfel automatisch upzudaten.
 

4.1. Speicherung multidimensionaler Daten
Nach [DN97] sind zwei Ansätze denkbar, um multidimensionale Daten für OLAP-Anfragen zu speichern: relationale Tabellen oder Arrays. Beide Ansätze haben Vor- und Nachteile (und führen immer wieder zu Debatten zwischen ROLAP und MOLAP-Anbietern). Einige der Vorteile des MOLAP-Ansatzes:

• dichte Arrays können im Arrayformat kompakter als in Tabellen gespeichert werden
• der Zugriff auf die gespeicherten Daten ist einfacher als bei Tabellen

• dünne Daten können in Tabellen kompakter gespeichert werden (es werden nur die Zellengespeichert, die tatsächlich Daten enthalten)
• Nutzung der Möglichkeiten von SQL

• „Chunking" Arrays: Dieser Ansatz beruht auf eine Zerteilung großer Arrays in kleinere (engl.: chunk - Brocken). Dabei wird ein n-dimensionales Array in kleinere n-dimensionale Chunks zerteilt und jedes dieser Teile als eigenes Objekt auf der Platte gespeichert.
• gepackte Arrays: Dichte Arrays (mehr als 40% der Zellen gefüllt) werden ohne Kompression gespeichert. Bei weniger als 40% kommt eine sogenannte „chunk-offset"-Kompression zum Einsatz. Bei dieser Methode wird ein Paar (Offset im Chunk, Datum) gespeichert, wobei die Adress-Indizees i, j, k des Datum im Würfel in einen Offset vom Beginn des Chunks umgewandelt werden.

• Physische Materialisierung des gesamten Würfels: Dieser Ansatz liefert die besten Antwortzeiten auf Queries, ist aber für große Data Cubes keine gängige Alternative, da der benötigte Speicherplatz hoch wird.
• Keine Vorberechnung: In diesem Fall wird jede Zelle des Würfels bei Bedarf berechnet. Es wird kein zusätzlicher Speicherplatz benötigt, hinsichtlich einer schnellen Antwortzeit jedoch birgt dieser Ansatz erhebliche Nachteile
• Nur einige Teile des Würfels materialisieren. In Data Cubes sind die Werte vieler Zellen aus dem Inhalt anderer Zellen berechenbar. Je mehr Zellen vorberechnet werden, um so besser wird die Query-Performance. Es kann jedoch ausreichend sein, nur einen kleinen Teil des Würfels vorzuberechnen.

Der Algorithmus kann nun wie folgt definiert werden:

  S = {top view}
  for i=1 to k do
  begin
    Wähle die Sicht v Ï S so, daß B(v,S) maximal ist;
    S = S union {v};
  end;
  Resultat S ist die „gierige" Auswahl;

4.3. Laden des Data Cube
In [ZDN97] werden zwei Algorithmen zur Berechnung von Sub-Aggregates im Datenwürfel vorgestellt:

• Basic Array Cubing: Dieser Algorithmus minimiert den Speicherbedarf während der Berechnung. Wenn z.B. das Array die Dimensionen ABC hat, berechnet der Algorithmus AB aus ABC, liest danach ABC erneut, um AC zu berechnen, anschliessen wird ABC ein drittes Mal gelesen und BC berechnet.
• Multi-Way Array: Hierbei handelt es sich um eine modifizierte Variante des ersten Algorithmus, hinsichtlich I/O minimiert. Dabei werden die „Kinder" in einem einzigen Durchlauf erstellt. Da der Speicherbedarf bei diesem Algorithmus hoch ist, wird neben der Standard-Algorithmus ein zweiter mit einem geringeren Speicherbedarf vorgestellt.

Die Entwicklung des OLAP-Benchmarks, des Analytic Processing Benchmark (APB-1) wurde vom OLAP-Council gefördert. Der Benchmark simuliert realistische OLAP-Business-Situationen, die auf Server-basierter Software laufen. Das Ziel des APB-1 ist die Messung der gesamten OLAP-Performance eines Servers, weniger die Performance spezieller Teilaufgaben. Die (sorgfältig ausgewählten) Operationen des Benchmarks sollen häufige Operationen in der Praxis widerspiegeln und so sicherstellen, daß die Ergebnisse des Benchmarks praxisrelevant sind. Diese Operationen umfassen:

• umfangreiche Laden von Daten aus in- und externen Quellen
• inkrementelles Laden von Daten aus operationalen Systemen
• Aggregationen
• Datenumverteilung entsprechend dem Business-Modell
• Zeitreihenanalysen
• Queries mit einem hohen Komplexitätsgrad
• drill-down durch Hierarchien
• ad-hoc-Queries
• multiple Online-Sessions

• Laden der Daten in das System
• Ausführung der Berechnungen
• Durchführung der Queries

5.2. Struktur der Datenbank
Die logische Datenbankstruktur besteht aus sechs Dimensionen: Zeit, Szenario, Maßstab sowie drei Aggregations-Dimensionen zur Definition der Datenbankgröße (Produkt, Kunde und Kanal).

• Produkt: Die Produkt-Dimension hat die meistens Einträge. Die Anzahl der Einträge in der Dimension Produkt ist zehnmal so hoch wie die der Dimension Kunde. Die minimale Anzahl der Einträge ist 10.000. Die Produkthierarchie erstreckt sich über sieben Level und ist als Baumstruktur organisiert, dabei enthalten die Blätter 90% der Einträge. Die Levelnamen der Produkthierarchie:
• Top
• Division
• Line
• Family
• Group
• Class
• Code

• Kunde: Die Anzahl der Kunden ist die hundertfache der Anzahl der Kanäle, das Minimum liegt bei 1.000. Die Hierarchie erstreckt sich über drei Level, der unterste enthält 90% der Einträge. Die Namen der Level:
• Top
• Retailer
• Store

• Kanal: die Anzahl der Einträge hier ist die geringste; die Anzahl der Kanäle ist ein Eingabeparameter des Programms APB1GEN (Beschreibung siehe unten). Das Minimum liegt bei zehn, und die Hierarchie umfaßt zwei Level:
•  Top
•  Base

• Zeit: die Zeit umfaßt zwei Jahre (1995 und 1996) mit je zwölf Monatseinträgen. Die Zeit-Hierarchie schließt Vierteljahr-, Jahr- und Jahr-zu-Datum-Aggregationen ein. Als aktueller Monat dient der Juni 1996. Zeitperioden vor diesem Monat gelten als „historisch", Perioden danach als zukünftige.
• Szenario: Es existieren drei Basiswerte in dieser Dimension: zwei sind Input von Datenfiles, der dritte ist aus den anderen beiden modelliert. Die Input-Szenarien umfassen Gegenwart und Budget, das modellierte Szenario enthält Vorhersagen.
• Maßstab: Diese Dimension enthält zehn Einträge; fünf Input und fünf berechnete.

Die Input- Einträge sind:
• verkaufte Einheiten: nach Produkt, Kunde, Kanal, Zeit und Szenario
• Einnahmen: nach Produkt, Kunde, Kanal, Zeit und Szenario
• Inventar: nach Produkt, Kunde und Zeit
• Standard-Produktkosten: nach Produkt, Zeit und Szenario (SPK)
• Standard-Vertriebskosten: nach Kunde, Zeit und Szenario (SVK)
die berechneten:
• durchschnittlicher Verkaufspreis = Einnahmen / verkaufte Einheiten
• Kosten = verkaufte Einheiten * (SPK + SVK)
• Gewinn = Einnahmen - Kosten
• Gewinn in % = Gewinn / Einnahmen
• smoothes sales = 6-Monats-Durchschnitt der Einnahmen

5.4. Queries
OLAP-Queries sind ad-hoc-Queries und sehr dynamisch. Die benötigten Informationen umfassen alle vorhandenen Daten.
Der APB-1 umfaßt folgende Queries:

• Kanal-Verkaufs-Analyse: Die Query zeigt aktuelle verkaufte Einheiten, Einnahmen und den durchschnittlichen Verkaufspreis für einen angegebenen Kanal. Produkt, Kunde, Kanal und Zeitperiode variieren bei jeder Ausführung der Query.
• Kunden-Gewinn-Analyse: Diese Query zeigt aktuelle Verkäufe, Kosten und Gewinn für einen angegebenen Kunden. Produkt, Kunde und Zeitperiode variieren bei jeder Ausführung der Query.
• Produkt-Inventory-Analyse: Diese Query zeigt aktuelle Verkäufe, Kosten und Bestand für ein gegebenes Produkt ungeachtet des Kanals. Produkt und Kunde variieren bei jeder Ausführung der Query.
• Zeitreihen-Analyse: Die Query zeigt aktuelle Verkäufe und einen Sechs-Monats-Durchschnitt für einen angegebenen Kunden und eine Gruppe von Zeitintervallen über alle Kanäle. Produkt, Kunde und Zeitperiode variieren bei jeder Ausführung der Query.
• Kundenbudget: Diese Query zeigt das Kundenbudget über alle Kanäle für alle Monate des Jahres 1996. Der Kunde variiert bei jeder Ausführung der Query.
• Produktbudget: Diese Query zeigt das Produktbudget für eine angegebene Zeitperiode im Jahr 1996. Das Produkt variiert bei jeder Ausführung der Query.
• Vorhersage-Analyse: Diese Query zeigt die Kanalvorhersage für eine angegebene Zeitperiode im Jahr 1996. Produkt, Kunde, Kanal und Zeitperiode variieren bei jeder Ausführung der Query.
• Budget-Performance: Die Query vergleicht die Budget-Performance des aktuellen mit der des vergangenen Jahres für den aktuellen Monat und aktuellem Jahr-zu-Datum. Produkt und Kunde variieren bei jeder Ausführung der Query.
• Vorhersage-Performance: Diese Query vergleicht die vorhergesagte Performance des letzten Monats mit aktuellen dieses Monate für den aktuellen Monat und aktuellem Jahr-zu-Tag. Produkt und Kunde variieren bei jeder Ausführung der Query.
• ad-hoc: Beantwortet ad-hoc-Queries auf der Datenbank. Maßstab, Szenario, Produkt, Kunde Kanal und Zeitperiode variieren bei jeder Ausführung der Query.

• 10% Kanal-Verkaufs-Analyse
• 10% Kunden-Gewinn-Analyse
• 15% Produkt-Bestands-Analyse
• 3% Zeitreihen-Analyse
• 5% Kundenbudget
• 5% Produktbudget
• 15% Vorhersage-Analyse
• 20% Budget-Performance
• 15% Vorhersage-Performance
• 2% ad-hoc

1. Ausführung von APB1GEN zum Anlegen der Hierarchiefiles und historischen Daten
2. Datenbankinitialisierung und Laden der historischen Daten
3. Ausführung von APB1GEN zum Anlegen der inkrementellen Datenfiles
4. inkrementelles Laden und Vorberechnung
5. Ausführung von APB1GEN zum Anlegen der Query-Datenfiles
6. Query-Ausführung

5.5. Vollständige Offenlegung
Bei jeder Publikation von Ergebnissen des APB-1-Benchmarks ist von Seiten des OLAP-Councils eine vollständige Offenlegung gefordert. Folgende Informationen müssen veröffentlicht werden:

• der Audit-Report
• das Datenbankschema
• der benötigter Code zum Laden der Daten
• der benötigter Code zur Vorberechnung
• die Anzahl der Nutzer
• die Größe jedes einzelnen  Benchmark-Datenfiles
• Datenbankgröße
• Datenbank-Serversoftware
• Datenbank-Tuning-Parameter
• Hardware-Plattform und Konfiguration (CPU, Speicher)
• Betriebssystem und Konfigurationsparameter

Als Beispiel für OLAP-Werkzeuge dient hier das Programm Holos der Firma Seagate Software Inc., das bei der R+V-Versicherung eingesetzt wird, als Referenzmaterial diente dabei [Se97].
Seagate Software bezeichnet Holos als „Operational Business Intelligence System". Es ist ein „Executiv Information System" - es kann hochwertige, gut präsentierte Informationen liefern: nützlich für Manager. Es ist ein Entscheidungsunterstützungssystem - Holos erlaubt die Modellierung von Geschäftsfällen, das Testen alternativer Szenarien und die statistische Vorhersage solcher Systeme. Holos ist ein OLAP-Tool - es liefert multidimensionale Queries, Reports und Analysen. Und es ist eine wichtige Komponente des Data Warehousing - es ermöglicht Zugriffe ins Data Warehouse auf etablierter relationaler Basis.
Holos ist ein Client-Server-System. Die Server-Komponenten bieten Möglichkeiten für Datenzugriff, Modellierung, multidimensionale Operationen und Reports an. Als Client können sowohl der Holos-Client als auch Java-fähige Browser oder ODBC-fähige Client-Applikationen (z.B. Visual Basic oder Delphi) verwendet werden: Holos stellt Schnittstellen für den Zugriff auf seine multidimensionalen Daten für ODBC-Anwendungen bereit.
Holos läuft auf über einem Dutzend Serversystemen, z.B. IBM RS/6000 AIX, HP 9000/800 HP-UX, Sun-4 SunOS oder Windows NT. Als Clients werden derzeit Windows 3.1 und 3.11, Windows 95, Windows NT und Macintosh System 7.0 unterstützt. HOLOS arbeitet  mit einer breiten Palette an Datenbanksystemen zusammen, als Beispiel seien hier Informix, Ingres, ORACLE und Sybase genannt.

6.1. Holos-Client
Der Holos-Client bietet eine produktive und leicht zu benutzende Arbeitsumgebung. Er umfaßt folgende Komponenten:

• Application Manager: Ein graphisches Tool zur Erstellung und Entwicklung von Holos-Applikationen. Er bietet eine hierarchische Sicht auf die Struktur der Applikation und ermöglicht eine einfache point-and-click-Bearbeitung vielerlei Elemente: Holos-Language-Quellcode, Reports, Datenfilter, Nutzerdialoge u.v.m.
• Report Designer und Report Viever: Ein Report kann Graphiken, Datenbank-Queries, Navigationshilfen (z.B. für drill-down) oder Live-Links zu anderen Applikationen enthalten. Der Designer ermöglicht die interaktive und graphische Erstellung von Reports über eine volle Kontrolle von Farben, Fonts, Layout und Hintergrund.
• Worksheet: Hierbei handelt es sich um eine tabellenkalkulationsartige Sicht auf multidimensionale Daten ohne die 2- oder 3-dimensionalen Einschränkungen der meisten Tabellenkalkulationen.
• Datenfilter
• Dialog-Designer zum Erstellen von Dialogboxen. Es werden alle gängigen Windows- und Macintosh-Dialogelemente unterstützt.
• Desktop-Designer: Verwaltung des Desktop der Applikation: startet Holos- und andere Windows- oder Macintosh-Anwendungen, erlaubt den Zugriff auf alle Tools des Holos-Client und verwaltet ein Hilfesystem.
• Texteditor
• Datenzugriff: kreiert Holos-Strukturen oder Dimensionen auf flachen Dateien oder Datenbanktabellen, ein SQL-Select-Builder ist ebenfalls vorhanden.
• Multimedia: ermöglicht Einbindung von Audio, Video, graphischen und Text-Daten.
• Hilfesystem

• CD97:

Chudhuri S., Dayal U.: An Overview of Data Warehousing and OLAP Technology. 1997
• Da96:

Darling, C.D.: Think Outside the OLAP Box. http://www.datamation/com/PlugIn/issues/1996/april15/04beval1.html
• DN97:

Deshpande P.M., Naughton J.F., Ramasamy K., Shukla A., Tufte K., Zhao Y.: Cubing Algorithms, Storage Estimation, and Storage and Processing Alternatives für OLAP. Dutch Engineers Bulletin 20(1), 3/97
• GC96:

Gray J., Chaudhuri S., Bosworth A., Layman A., Reichard D., Venkatrao M., Pellow F., Pirahesh H.: Data Cube: A Relational Aggregation Operator. Generalizing Group-By, Cross-Tab and Sub-Totals. Data Mining and Knowledge Discovery 1, 29-53, 1997
• Gr93:

Graefe, C.J.: Query evaluation techniques for large databases. ACM Computing Surveys 25.2, 73-170, 1993
• HRU96:

Harinarayan V., Rajaraman A., Ullman J.D.: Implementing Data Cubes Efficiently. Proc. SIGMOD Conference, 1996
• Me98:

Mertens, Peter: Konzeptionen für ein Data Warehouse. Unternehmensdatenmodell als Basis. Datenbank Fokus, Januar 1998
• OL96:

OLAP Council: OLAP Benchmark Study, 1996
• Pi:

Pilot Software: An Introduction to OLAP. http://www.pilotsw.com/olap/olap.html
• Se97:

Seagate Software: Seagate Holos. Informationsbroschüre. United Kingdom, 1997
• TR97:

Tresch M., Rys M.: Data Warehousing Architektur für Online Analytical Processing. Theorie und Praxis der Wirtschaftsinformatik 195(34), Mai 1997
• ZDN97:

Zhao Y., Deshpance P.M., Naughton J.F.: An Array-Based Algorithm for Simultaneous Multidimensopnal Aggregates. Proc. SIGMOD Conference, Tucson, Arizona, 1997 (SIGMOD Record 26(2))

 

[ Michael Müller ] [ 5.6.98 ]