Inkrementelle Wartung materialisierter Sichten


Bachelorarbeit, 2008

47 Seiten, Note: 1,3


Leseprobe

Inhaltsverzeichnis

1 EINLEITUNG
1.1 Themengrundlage
1.2 Problemstellung
1.3Ziel und Ausrichtung der Arbeit
1.4Struktur der Arbeit
1.5Nomenklatur und Annahmen
1.6Definition der verwendeten Beispielsicht

2 GRUNDLAGEN - MATERIALISIERTE SICHTEN
2.1Unterschiede zwischen nicht materialisierten und materialisierten Sichten
2.2 Anwendung mit Vor- und Nachteilen

3 KLASSIFIZIERUNG VON ASPEKTEN DER SICHTWARTUNG
3.1 Uberblick
3.2 Wartungsverfahren
3.2.1Vollstandige Aktualisierung
3.2.2 Inkrementelle Aktualisierung
3.3 Wartungszeitpunkt
3.3.1Sofortige Aktualisierung
3.3.2Transaktionsbasierte Aktualisierung
3.3.3 Verzogerte Aktualisierung

4 INKREMENTELLE WARTUNGSVERFAHREN
4.1Relevante und irrelevante Veranderungen auf Basistabellen
4.1.1Relevanz und deren Uberprufbarkeit
4.1.2Irrelevante Veranderungen durch INSERT Anweisungen
4.1.3Irrelevante Veranderungen durch DELETE Anweisungen
4.1.4Verfahren zum Filtern relevanter Veranderungen
4.1.5Verwandte Literatur
4.2Wartungsverfahren fur einfache Sichtdefinitionen
4.2.1SELECT Sichtdefinitionen
4.2.2PROJECT Sichtdefinitionen
4.2.3INNER JOIN Sichtdefinitionen
4.2.3.1Veranderungen einer Basisrelation
4.2.3.2Veranderungen mehrerer Basisrelationen
4.2.4OUTER JOIN Sichtdefinitionen
4.2.4.1Allgemeines Wartungsschema
4.2.4.2Berechnung der direkten Veranderungen
4.2.4.3Berechnung der indirekten Veranderungen
4.2.4.4Offene Fragen
4.3Wartungsverfahren fur kombinierte Sichtdefinitionen
4.4Weitere Moglichkeiten zur Effizienzsteigerung
4.5 Fazit und offene Fragen

5 VERZOGERTE WARTUNGSSTRATEGIE
5.1 Allgemeines Wartungsschema
5.2 Grundlagen
5.2.1 Annahmen
5.2.2Transaktionen unter Snapshot Isolation und Tupelversionierung
5.2.3Wartungsauftrage
5.3 Berechnen von Sichtveranderungen
5.3 Redundante Sichtveranderungen
5.3.1 Entstehung
5.3.2 Umgehen redundanter Wartungsoperationen
5.4Weitere Moglichkeiten zur Effizienzsteigerung
5.5 Verwandte Literatur
5.6 Fazit & Offene Fragen

6 KOMBINIERBARKEIT DER ASPEKTE DER SICHTWARTUNG

7ZUSAMMENFASSUNG

LITERATURVERZEICHNIS

ANHANG A

Kurzzusammenfassung

Um die Anfrageausfuhrung in Datenbanksystemen zu optimieren, konnen materialisierte Sichten eingesetzt werden. Dabei mussen Veranderungen ihrer Basisrelationen jedoch auf die Sichten ubertragen werden, um ihre Zustande konsistent zu halten. Die vorliegende Arbeit fokussiert das Sichtwartungsproblem und betrachtet dessen orthogonale Aspekte, welche die Art und Weise und den Zeitpunkt der Wartung betreffen, sowie die Vor- und Nachteile ihrer Anwendung. Die inkrementelle, verzogerte Wartungsstrategie steht dabei im Mittelpunkt der Darstellung. Bereits vor der Anwendung eines Wartungsalgorithmus’ konnen die fur eine Sicht irrelevanten Veranderungen ihrer Basisrelationen von der Wartung ausgeschlossen werden. Je nach Sichtdefinition existieren anschliebend unterschiedliche Verfahren, welche miteinander kombiniert, die inkrementelle Wartung materialisierter SPJ und SPOJ Sichten erlauben. Ein verzogerter Wartungszeitpunkt ermoglicht zudem die Entkopplung des Wartungsprozesses von der verandernden Transaktion, sodass diese nicht die Wartungskosten tragen muss. Mit dem in dieser Arbeit vorgestellten Algorithmen und Verfahren konnen irrelevante und redundante Veranderungen vor der stattfindenden Sichtwartung entfernt werden, weshalb eine inkrementelle, verzogerte Wartungsstrategie eine effiziente Aktualisierung materialisierter Sichten erlaubt.

1 Einleitung

1.1 Themengrundlage

Zu Beginn der 80er Jahre loste das relationale Datenbankmodell die bisher vorherrschenden hierarchischen und netzwerkartigen Datenorganisationsmodelle auf dem Markt ab. So wurde beispielsweise die IT von Konzernen oder mittelstandigen Unternehmen zur Verwaltung von Kundendaten auf Datenbanksysteme umgestellt. Mit zunehmender Grobe der zu verwaltenden Datenmengen und deren dezentralen Speicherung wurden zentrale Datenlager geschaffen, welche heute als Data-Warehouses bekannt sind. In ihnen werden aktuelle und historische Datenbestande heterogener Quellsysteme integriert, analysiert und ausgewertet. Damit speichern Data-Warehouses nicht nur Daten fur Unternehmen, sondern helfen auch bei der betriebswirtschaftlichen Entscheidungsfindung, indem beispielsweise Kunden-, Markt- oder Trendanalysen durchgefuhrt werden konnen [Le02]. Nicht nur mit zunehmenden Datenmengen und der Nutzung verteilter Systeme, sondern auch mit ansteigender Komplexitat der an ein Verwaltungssystem gestellten Anfragen, wurden neue Techniken notig, um die Anfrageausfuhrung schneller und effizienter zu gestalten. Die Verwendung von materialisierten Sichten in Datenbanksystemen tragt zu dieser Anfrageoptimierung bei.

1.2 Problemstellung

Bei der Verwendung von materialisierten Sichten anstelle von nicht materialisierten Sichten, wie in Kapitel 2.1 definiert, kommen verschiedene Fragestellungen auf, welche in die folgenden drei Kernfelder kategorisiert werden konnen.

Fragestellungen, wie die Wartung materialisierter Sichten effizient gestaltet werden kann, werden unter dem Begriff der Sichtwartung (englisch: view maintenance) zusammengefasst. Wenn sich Daten in den Basistabellen andern, z. B. durch das Einfugen neuer Tupel oder durch das Aktualisieren von Attributen, so mussen moglicherweise auch die auf ihnen definierten materialisierte Sichten verandert werden, was eine Wartung erzwingt. Das heibt, die Veranderungen auf den Basisrelationen mussen auf die Sichten ubertragen werden, um diese korrekt und konsistent und damit nutzbar zu halten [RG02]. Zu den Problemstellungen hierbei zahlen, auf welche Art und Weise die Wartung materialisierter Sichten geschehen kann, d.h. welches Verfahren benutzt werden soll, und zu welchem Zeitpunkt die Aktualisierung stattfinden kann.

Eine weiteres Problem ist die Sichtauswahl (englisch: view selection). Dabei sei eine Menge N von nicht materialisierten Sichten gegeben. Welche M Sichten (M^N) aus N sollten materialisiert werden, um eine optimale Balance zwischen Anfrage- und Aktualisierungskosten zu gewahrleisten? Zur Verdeutlichung betrachte man ein Datenbanksystem, in welchem alle Sichten materialisiert sind. In diesem Fall ware zwar die Anfragezeit optimiert, die Kosten fur die Wartung der Sichten jedoch sehr hoch. Wurden im Gegenteil alle Sichten virtuell gehalten, so stiegen die Kosten der Anfrageausfuhrung durch die Berechnungskosten stark an. Die Problematik besteht hierbei also in der Kernfrage, einen Algorithmus zu finden, welcher eine Menge von Sichten zur Materialisierung auswahlt, um damit die Summe der Anfrage- und Aktualisierungskosten zu minimieren [ZYY01].

Eine weitere Problemstellung der Sichtwartung ist die Sichtdefinition[1] (englisch: view definition). Sie beinhaltet die Frage, welche Sichten materialisiert werden sollten [RG02] und wie sie zu definieren sind, damit die Ausfuhrung einer Menge von Anfragen an ein Datenbanksystem effizient ist, d.h. die Antwortzeit gering, aber die Sichtwartungskosten niedrig sind.

1.3Ziel und Ausrichtung der Arbeit

Unter den drei, oben genannten Problemstellungen im Zusammenhang mit der Verwendung von materialisierten Sichten in Datenbanksystemen fokussiert diese Arbeit das Sichtwartungsproblem. Das Ziel der vorliegenden Arbeit ist die Darstellung der orthogonalen Aspekte Wartungsverfahren und Wartungszeitpunkt materialisierter Sichten, um eine Klassifizierung und Einordnung verschiedener Ansatze in der Problemstellung der Sichtwartung vorzunehmen. Welche Verfahren zur Wartung materialisierter Sichten existieren? Wann kann die Aktualisierung von Sichten stattfinden? Worin bestehen jeweils die Vor- und Nachteile der verschiedenen Ansatze?

Der Fokus der Arbeit liegt anschlieftend auf der ausfuhrlichen Darstellung, sowie Verbindung und Bewertung inkrementeller Wartungsverfahren mit der verzogerten Aktualisierungsstrategie. Welche Algorithmen und Ansatze zur inkrementellen Wartung von materialisierten Sichten existieren? Inwieweit unterscheiden sich die Verfahren je nach gegebener Sichtdefinition? Wie konnen sie miteinander verknupft werden, um die Wartung kombinierter Sichtdefinitionen zu ermoglichen? Wie konnen materialisierte Sichten aktualisiert werden, ohne dass Updates auf Basistabellen die Aktualisierungskosten tragen mussen?

Aspektubergreifend soll am Ende der vorliegenden Arbeit die Frage beantwortet werden, welche verschiedenen Verfahren und Zeitpunkte miteinander kombiniert werden konnen, um die Wartung materialisierter Sichten effizient zu gestalten.

Auf die Sichtwartung in Data-Warehouses wird in der vorliegenden Arbeit nicht eingegangen, da sie sich aufgrund der Dezentralisierung und Quellenentkopplung der Daten von den in dieser Arbeit beschriebenen, traditionellen Wartungsalgorithmen unterscheiden. Der interessierte Leser sei hierfur auf [Zh+95] oder [ZGW97] verwiesen.

1.4 Struktur der Arbeit

Eine grundlegende Definition materialisierter Sichten und die Darstellung wesentlicher Vor- und Nachteile ihrer Anwendung, fasst Kapitel 2 zusammen. In Kapitel 3 werden mogliche Wartungsverfahren (vollstandig oder inkrementell) und Wartungszeitpunkte (sofort, transaktionsbasiert oder verzogert) klassifiziert. Aufbauend auf dieser Einteilung der Sichtwartungsaspekte stellt Kapitel 4 verschiedene Algorithmen und Verfahren zur inkrementellen Wartung einfacher materialisierter Sichtdefinitionen vor, welche zum Ende hin miteinander kombiniert werden, sodass eine effiziente Wartung von zusammengesetzten Sichtausdrucken moglich ist. Kapitel 5 demonstriert die Anwendung eines verzogerten Sichtwartungszeitpunktes zur weiteren Leistungsverbesserung. In Kapitel 6 werden die einzelnen Wartungsaspekte miteinander kombiniert und deren Performance und Anwendbarkeit betrachtet. Kapitel 7 fasst die Inhalte der beleuchteten Aspekte und deren Ergebnisse zusammen.

1.5 Nomenklatur und Annahmen

Zur Vorstellung verschiedener Wartungsverfahren werden Sichtausdrucke mit relationaler Algebra definiert. R und S seien beliebige Relationen (dazu zahlen auch materialisierte Sichten selbst). In der gesamten Arbeit wird angenommen, dass weder in Relationen, noch in anderen,

Abbildung in dieser Leseprobe nicht enthalten[1]

Dabei konnen Ausdrucke der Form [Abbildung in dieser Leseprobe nicht enthalten] mit Verbundbedingungen[Abbildung in dieser Leseprobe nicht enthalten]unter Verwendung des kartesischen Produktes zu [Abbildung in dieser Leseprobe nicht enthalten]umgeformt werden. Die vorliegende Arbeit beschrankt die Verbundbedingung J auf Gleichheitsausdrucke. 1st die Verbundbedingung mit J(X) definiert, so ist eine Gleichheitsbedingung auf Attributen der Menge X symbolisiert.

Weitere, in dieser Arbeit verwendete Operatoren und Symbole sind:

Abbildung in dieser Leseprobe nicht enthalten

Ein Tupel r1 subsumiert ein Tupel r2 in R, wenn r1 mit r2 in alien Attributen, auf denen r2 nicht NULL ist, ubereinstimmt aber r1 insgesamt weniger NULL Werte auf den Attributen a(R) annimmt als r2 [Ga94].

Es werden Veranderungsoperationen auf einer Relation R durch Einfuge-, Losch- und Modifizierungsanweisungen, ausgedruckt mit den Anweisungen INSERT([Abbildung in dieser Leseprobe nicht enthalten] ), DELETE([Abbildung in dieser Leseprobe nicht enthalten]) und entsprechend MODIFY(R, P, F), betrachtet. Dabei sei P eine Bedingung, welche alle auf R zu verandernden Tupel selektiert und F die auf sie angewandte Modifikationsfunktion.

Alle Tupel einer beliebigen Relation R und den zugehorigen Tabellen [Abbildung in dieser Leseprobe nicht enthalten] und [Abbildung in dieser Leseprobe nicht enthalten] seien jeweils um eine ACTION Spalte erganzt, in welcher die durchzufuhrende Aktualisierung vermerkt ist. Dabei steht INSERT fur ein einzufugendes, DELETE fur ein zu loschendes und OLD fur ein unverandertes, altes Tupel. Fur alle p auf R eingefugten Tupel [Abbildung in dieser Leseprobe nicht enthalten]gilt [Abbildung in dieser Leseprobe nicht enthalten]ACTION = INSERT und entsprechend [Abbildung in dieser Leseprobe nicht enthalten].ACTION = DELETE[Abbildung in dieser Leseprobe nicht enthalten] fur alle q von [Abbildung in dieser Leseprobe nicht enthalten] geloschten Tupel [Abbildung in dieser Leseprobe nicht enthalten] Eine MODIFY-Veranderung kann durch eine Losch-Einfuge-Abfolge und deshalb in [Abbildung in dieser Leseprobe nicht enthalten] mit zwei korrespondierenden Tupeln dargestellt werden. Der Datensatz mit dem alten, zu modifizierenden Wert wird geloscht und ein Tupel mit dem neuen, modifizierten Wert eingefugt.

In allgemeiner Mengendarstellung[Abbildung in dieser Leseprobe nicht enthalten]sind alle auf R eingefugten Tupel[Abbildung in dieser Leseprobe nicht enthalten] mit[Abbildung in dieser Leseprobe nicht enthalten]ACTION = INSERT mit „I“ und alle q von R geloschten Tupel[Abbildung in dieser Leseprobe nicht enthalten] mit [Abbildung in dieser Leseprobe nicht enthalten].ACTION = DELETE mit „D“ gekennzeichnet. Alle Tupel □ pG^R mit □rJ-.ACTION = INSERT sind Tupel AqGAR. Entsprechend sind Tupel [Abbildung in dieser Leseprobe nicht enthalten] pG [Abbildung in dieser Leseprobe nicht enthalten] mit [Abbildung in dieser Leseprobe nicht enthalten].ACTION = DELETE Tupel [Abbildung in dieser Leseprobe nicht enthalten] Dies gilt fur Basisrelationen als auch fur materialisierte Sichten R.

Auf Grundlage der Tupelmarkierung durch das ACTION Attribut und der oben definierten Ausdrucke konnen noch folgende Operatoren fur eine beliebige Relation R definiert werden.

[Abbildung in dieser Leseprobe nicht enthalten][3]

Materialisierte Sichten sind in dieser Arbeit jeweils auf n Basisrelationen R1, _, Rn definiert. Alle Veranderungen AR; und VR; einer Basisrelation RJ seit der letzten Wartung einer auf ihr definierten Sicht V sind in der entsprechenden Veranderungstabelle [Abbildung in dieser Leseprobe nicht enthalten] gespeichert. Es gilt [Abbildung in dieser Leseprobe nicht enthalten]Da Veranderungen □R; immer sofort auf RJ ubertragen werden, gelten zusatzlich [Abbildung in dieser Leseprobe nicht enthalten] disjunkt) und [Abbildung in dieser Leseprobe nicht enthalten] Damit lasst sich [Abbildung in dieser Leseprobe nicht enthalten]definieren.[4]

Zu jedem Tupel [Abbildung in dieser Leseprobe nicht enthalten]wird in der zusatzlichen Spalte TN die Transaktionsnummer der verandernden Transaktion und mit der Operationsnummer ON die das jeweilige Tupel erzeugende Operation innerhalb der Transaktion notiert.[5]

1.6 Definition derverwendeten Beispielsicht

Mehrere der in dieser Arbeit vorgestellten Algorithmen zur inkrementellen Wartung materialisierter Sichten sollen anhand der Beispielsicht V1 verdeutlicht werden, welche auf den Basisrelationen R = {A,B} und S = {C,D,E} definiert ist. Die Inhalte dieser Relationen und die daraus resultierende Sicht sind in Abbildung 1 dargestellt. Werden nicht alle hier festgelegten Bedingungen von V1 zur spateren Veranschaulichung spezieller Verfahren benotigt, so werden neue Sichtdefinitionen Vi (i = 2, 3, 4, 5) erzeugt, welche V1 ahneln aber weiterhin auf R und S, wie hier definiert, basieren.

Abbildung in dieser Leseprobe nicht enthalten

2 Grundlagen - materialisierte Sichten

2.1 Unterschiede zwischen nicht materialisierten und materialisierten Sichten

Nicht materialisierte Sichten sind virtuelle Tabellen, d.h. die Ergebnismenge bei Auswertung ihrer Sichtdefinition auf gespeicherten Basisrelationen wird nicht physisch als Tabelle abgespeichert, sondern bei jeder Verwendung, zum Beispiel bei einer AnfTage an die Sicht, neu berechnet [GM95]. Somit kann eine nicht materialisierte Sicht auch als Name fur eine Anfragedefinition bezeichnet werden, unter welchem man diese aufrufen und benutzen kann. Im Gegensatz dazu sind materialisierte Sichten[4] Relationen mit einer Extension. Die Ergebnismenge ihrer Sichtdefinition bei Auswertung auf einem konkreten Datenbankzustand wird als eigenstandige Tabelle abgespeichert [BLT86]. In [GM95] vergleichen die Autoren materialisierte Sichten mit einem Cache, also Kopien von Anfrageergebnissen, auf welche schnell zugegriffen werden kann. Materialisierte Sichten tragen auch den von IBM gepragten Namen Automatic Summary Tables (kurz: ASTs) [Le+01], wohingegen Sie bei Microsoft als Indexed Views bezeichnet werden [Ha05].

2.2 Anwendung mit Vor- und Nachteilen

Wie einleitend bereits erwahnt, finden materialisierte Sichten z.B. Anwendung in verteilten Datenbanksystemen. Dies bringt den Vorteil, dass Daten aus verschiedenen Datenbanken integriert werden konnen, ohne dass die Basistabellen erneut, komplett in einer zentralen Datenbank abgespeichert werden mussen. Damit wird die redundante Datenspeicherung vermieden. Anfragen an das System konnen mithilfe von materialisierten Sichten beantwortet werden, sodass der Zugriff auf ferne, dezentrale Basistabellen nicht stattfinden muss. Durch die Vorberechnung und Speicherung von Anfrageergebnissen wird die Ausfuhrungszeit von Anfragen an das Datenbanksystem verbessert [Bu+99].

Materialisierte Sichten werden i. A. bevorzugt in solchen Datenbanksystemen verwendet, in denen eine Vielzahl gleicher oder ahnlicher Anfragen auf denselben Relationen bei weitgehend stabiler Datenbasis vorkommt. Haufig gestellte Anfragen werden materialisiert, um ihre standige, komplette Neuberechnung zu vermeiden. Zudem kann eine bereits existierende Sicht zur Erzeugung weiterer Sichten benutzt werden, wodurch die erneute Berechnung von Teilergebnissen eingespart wird. Materialisierte Sichten reduzieren somit den Berechnungsaufwand und verbessern die Effizienz der Anfrageausfuhrung, indem Anfrageergebnisse gespeichert und damit teure Plattenzugriffe, infolge mehrfacher Datenabfragungen aus unterschiedlichen Relationen, reduziert werden. Deshalb werden sie vor allem in solchen Systemen implementiert, die eine schnelle Antwortzeit fur haufig gestellte Anfragen verlangen. Dabei sind bestandig verwendete, komplexe Aggregations- und Verbundanfragen haufig Kandidaten fur eine Materialisierung [Ha05].

Des Weiteren bietet die Materialisierung von Sichten den Vorteil des Datenschutzes, indem uber die Sichtdefinition dem Benutzer nur bestimmte Informationen sichtbar gemacht werden konnen. Dadurch kann die Veranderung schutzenswerter Daten verhindert und die Fehlerhaufigkeit herabgesetzt werden. Konkret konnen so z.B. Anwendungen im Bankwesen oder dem Einzelhandel durch den Einsatz materialisierter Sichten effizienter und fehlerfreier ausgefuhrt werden [Mu95].

Im Gegenteil dazu kann die Benutzung materialisierter Sichten in solchen Fallen von Nachteil sein, in denen Basisrelationen standigen Anderungen unterliegen. Dadurch vermehrt entstehende Wartungskosten fur die Aktualisierung der Basistabellen und der dazugehorigen Sichten konnen die Vorteile der Materialisierung ubersteigen. Ein weiterer Nachteil bei der Verwendung materialisierter Sichten besteht im moglichen Anstieg der benotigten Speicherkapazitat [Bu+99, Ha95]. Zusammenfassend stellt die Entscheidung uber die Materialisierung von Sichten in einem Datenbanksystem gewissermaben einen Zielkonflikt zwischen dem Erreichen schneller Antwortzeiten bei der Anfrageausfuhrung und dem Reduzieren von Wartungskosten dar.

3 Klassifizierung von Aspekten der Sichtwartung

3.1 Uberblick

Veranderungen auf Basisrelationen konnen[7], abhangig von der Sichtdefinition, Aktualisierungen der auf ihnen definierten, materialisierten Sichten implizieren. Werden diese nicht durchgefuhrt, kann eine Sicht V inkonsistent werden. Sie Auswertung ihrer Sichtdefinition auf den neuen Zustanden ihrer Basisrelationen stimmt dann nicht mehr mit ihrem aktuellen, unaktualisierten Sichtzustand uberein. Das heibt, sobald sich die Inhalte der Basistabellen, auf denen V definiert ist, verandern, mussen diese Anderungen auch auf V abgebildet werden.

Der Prozess der Aktualisierung von materialisierten Sichten als Reaktion auf Updates auf die zugrunde liegenden Basisrelationen wird als Sichtwartung bezeichnet [GM95]. Dabei ist neben der Art und Weise der Wartung ist auch der Wartungszeitpunkt ein bedeutsamer Leistungsaspekt. Beide Ansatze werden im Folgenden kategorisiert.

3.2 Wartungsverfahren

3.2.1 Vollstandige Aktualisierung

Das Wartungsverfahren der vollstandigen Aktualisierung, auch Rematerialisierung genannt, umfasst das ganzliche Loschen veralteter materialisierter Sichten mit anschliebender, kompletter Neuberechnung infolge jeglicher Anderungen von Daten auf zugrunde liegenden Basistabellen. Dieses Vorgehen ist zumeist nicht effizient, kann jedoch in Systemen sinnvoll sein, in denen Basistabellen permanenten, groben Anderungen unterliegen, beispielsweise dann, wenn auf Basisrelationen mehr als 50% der Menge der bereits in ihnen vorhandenen Datensatze eingefugt werden [Ho01]. Die Entscheidung uber die Nutzung dieses Aktualisierungsverfahrens hangt deshalb stark vom Anwendungsszenario und der Komplexitat der Sichtdefinition ab, ist jedoch im Allgemeinen dann sinnvoll, wenn die Kosten der kompletten Neuberechnung der Sicht geringer sind als bei einer inkrementellen Wartung.

Des Weiteren bietet die Strategie der vollstandigen Rematerialiserung einen Ansatzpunkt fur die gemeinsame, gleichzeitige Wartung mehrerer Sichten. Das als MQO-Technik (englisch: mass/mw/h-gwery oph'wzzah'ow tecAwz'gwej bezeichnete Verfahren hat die Optimierung von Anfragemengen, welche gemeinsame Unterausdrucke besitzen, zum Ziel [Ro+00]. Durch das Erzeugen von Vorganger - Nachfolger Beziehungen zwischen unterschiedlichen Anfragedefinitionen kann der Gesamtberechnungsaufwand einer Menge von Anfragen minimiert werden. Es werden eine oder mehrere gemeinsam und wiederholt nutzbare Basisanfragen generiert, sodass einzelne Anfrageteile verschiedener Sichten nicht isoliert mehrfach berechnet werden mussen. Die MQO-Technik findet in der Sichtwartung Anwendung [Zh+07, Le+01], indem durch sie beispielsweise das wiederholte Lesen grober Basistabellen zur Berechnung einer Vielzahl von darauf definierten Sichten oder das mehrfache Ausfuhren von Verbundoperationen reduziert und dadurch die gemeinsame Wartungszeit verringert werden.

3.2.2 Inkrementelle Aktualisierung

Um eine Sicht V nicht von Grunde auf neu zu berechnen, bedient man sich inkrementeller Aktualisierungsverfahren. Dazu zahlen Algorithmen, welche nur die Veranderungen der Basisrelationen auf V nachvollziehen. Die Idee dabei ist, dass zumeist nur Teile und nicht der gesamten Inhalt einer Sicht infolge von Veranderungen auf den Basistabellen betroffen sind und deshalb gewartet werden mussen [GM95]. Der neue Zustand einer Sicht [Abbildung in dieser Leseprobe nicht enthalten] kann deshalb aus ihrem alten Zustand [Abbildung in dieser Leseprobe nicht enthalten] und den durchzufuhrenden Veranderungen durch eingefugte Tupel AR bzw. geloschte Tupel[Abbildung in dieser Leseprobe nicht enthalten] (mit 1 <i<n) auf einer ihrer Basisrelationen Ri, ...,Rn berechnet werden. Damit lasst sich die Definition der inkrementellen Wartung einer materiellen Sicht V allgemein mit Gleichung (1) beschreiben, wobei V[ARi] die Sichtdefinition V darstellt, in welcher die Basisrelation RI durch die Einfuge-Modifizierungen AR ersetzt wird. Analog gilt dies fur [Abbildung in dieser Leseprobe nicht enthalten] und[Abbildung in dieser Leseprobe nicht enthalten].[6]

Abbildung in dieser Leseprobe nicht enthalten

Andert sich der Zustand einer Sicht V infolge von Veranderungen [Abbildung in dieser Leseprobe nicht enthalten]auf mehr als einer Basisrelation R, so symbolisieren AV und VV die notwendiger Weise auf V einzufugenden bzw. zu loschenden Tupel. Die beiden Mengen werden in der Sichtveranderungsmenge [Abbildung in dieser Leseprobe nicht enthalten] zusammengefasst. Fur Tupel[Abbildung in dieser Leseprobe nicht enthalten]gilt [Abbildung in dieser Leseprobe nicht enthalten]mit[Abbildung in dieser Leseprobe nicht enthalten] wenn □v.ACTION = INSERT. Analog gilt[Abbildung in dieser Leseprobe nicht enthalten] wenn[Abbildung in dieser Leseprobe nicht enthalten]. Die inkrementelle Wartung von V lasst sich mit der allgemeinen Form in (2) definieren. Die Tupel[Abbildung in dieser Leseprobe nicht enthalten]werden jeweils aufVA angewandt, d.h. die Menge AV zum alten Sichtzustand VA hinzugefugt und [Abbildung in dieser Leseprobe nicht enthalten] geloscht.

Abbildung in dieser Leseprobe nicht enthalten

Die inkrementelle Wartung materialisierter Sichten bietet sich besonders bei einfacheren Sichtdefinitionen, wie in dieser Arbeit betrachtet, und kleineren Anderungen an ihren Basisrelationen an [Le02].

3.3 Wartungszeitpunkt

3.3.1 Sofortige Aktualisierung

Wird eine materialisierte Sicht innerhalb der sie verandernden Transaktion aktualisiert, so wird die sofortige Aktualisierungsstrategie (englisch: immediate re/resR) gebraucht. Dabei wird die Sicht direkt mit der Veranderungsoperation auf den Basistabellen gewartet [RG02], sodass nachfolgende Operationen innerhalb der Transaktion auch immer einen konsistenten Sichtzustand sehen (z.B. eine nachfolgende READ Operation) [Le02]. Nachteil dieser Wartungsstrategie ist jedoch die Notwendigkeit des Ro//6acAs der durchgefuhrten Aktualisierungen auf der Sicht, falls die Transaktion scheitert. Zudem erhohen die durchzufuhrenden Wartungsschritte an Basisrelationen und materialisierten Sichten die Ausfuhrungszeit einer verandernden Transaktion [RG02].

Beispielhaft sei hier das IBM-Datenbankmanagementsystem DB2 genannt, welches dem Benutzer mit den Schlusselworten REFRESH IMMEDIATE in der Sichtdefinition erlaubt die sofortige Aktualisierungsstrategie zu verwenden [IBM06].

3.3.2 Transaktionsbasierte Aktualisierung

Im Vergleich zur sofortigen Aktualisierungsstrategie konnen Veranderungen auf Basisrelationen auch erst bei erfolgreicher Beendigung der Veranderungstransaktion auf eine Sicht ubertragen werden (englisch: on commit refresh). Durch diese Strategie entfallt die Notwendigkeit eines Rollbacks der Sichtwartung bei nicht erfolgreich abgeschlossenen Transaktionen. Allerdings ist es moglich, dass Operationen innerhalb der Transaktion eventuell inkonsistent gewordene Sichtinhalte lesen und verarbeiten [Le02]. Da Veranderungen an den aktualisierten Basistabellen und an den materialisierten Sichten, welche diese Tabellen in ihrer Sichtdefinition referenzieren, durchgefuhrt werden mussen, kann jedoch auch hier die Beendigung der Transaktion langer dauern [Ho01].

Als Beispiel sei Oracle9i genannt, welches die transaktionsbasierte Aktualisierung von materialisierten Sichten unterstutzt. Der Benutzer kann diesen Wartungszeitpunkt in der Sichtdefinition uber die Klausel REFRESH ON COMMIT festsetzen [Ho01].

3.3.3 Verzogerte Aktualisierung

Bei der verzogerten Aktualisierungsstrategie ([Abbildung in dieser Leseprobe nicht enthalten]) werden materialisierten Sichten veranderungsentkoppelt aktualisiert, d. h. Anderungsvorgange auf den Basisrelationen werden in einem Log zwischengespeichert und nicht direkt mit der verandernden Transaktion, sondern spater auf die Sicht ubertragen. Es gibt drei verschiedene, nachstehend erlauterte Strategien der verzogerten Aktualisierung. Bei der erzwungenen Aktualisierung [Abbildung in dieser Leseprobe nicht enthalten] werden materialisierte Sichten aktualisiert, sobald eine festgelegte Anzahl von Veranderungen an den ihnen zugrund liegenden Basisrelationen vorgenommen wurde [RG02].

Die periodische Aktualisierung (englisch: periodic re/resh) wartet materialisierte Sichten in bestimmten Zeitabstanden, beispielsweise taglich oder wochentlich [RG02].

Die trage Aktualisierungsstrategie (englisch: lazy re/resh) zogert die Wartung einer Sicht V bis zu einem Zeitpunkt t heraus, an dem der Benutzer die Aktualisierung von V explizit anweist, dem Datenbankmanagementsystem freie Zyklen zur Wartung zur Verfugung stehen oder V zur Auswertung einer Anfrage benotigt wird [ZLE07]. Dazu werden alle durchzufuhrenden Aktualisierungen an V bis zum Zeitpunkt t zwischengespeichert und erst in t auf die Sicht abgebildet.

Der Vorteil von verzogerten Aktualisierungsstrategien ist die Moglichkeit der Bundelung von durchzufuhrenden Sichtaktualisierungen [ZLE07]. Des Weiteren tragen Anderungsoperationen nicht die Kosten fur die anschliebende Sichtwartung, wodurch sich die Ausfuhrungsgeschwindigkeit von Anderungsoperationen verbessert. Nachteilig ist jedoch, dass die erzwungene und periodische Aktualisierungsstrategie inkonsistente Sichtzustande erzeugen konnen. Dadurch besteht die Moglichkeit, dass Anfragen auf der Grundlage inkorrekter, nicht aktueller Datenbestande ausgewertet werden.

DB2 erlaubt dem Benutzer die Verwendung der tragen Aktualisierungsstrategie durch den Einsatz des Schlusselwortes REFRESH DEFERRED in der Sichtdefinition. Damit kann eine materialisierte Sicht jederzeit mit der Anweisung REFRESH TABLE aktualisiert werden [Me05].

4 Inkrementelle Wartungsverfahren

4.1Relevante und irrelevante Veranderungen auf Basistabellen

Bevor die inkrementelle Wartung einer Sicht erfolgt, scheint es sinnvoll, nur die Veranderungen auf den Basistabellen in die Berechnungen einzubeziehen, die auch eine Veranderung auf den auf ihnen definierten Sichten bewirken. Die nachstehend prasentierte Methode kombiniert Ansatzpunkte aus [BLT86] und [BCL89] auf Grundlage des in [RH80] begrundeten Verfahrens zur Uberprufung der Erfullbarkeit von Booleschen Ausdrucken. Dabei werden Veranderungen INSERT[Abbildung in dieser Leseprobe nicht enthalten] und/oder DELETE[Abbildung in dieser Leseprobe nicht enthalten]

4.1.1 Relevanz und deren Uberprufbarkeit

Eine Veranderung U = DR; von eingefugten und/oder geloschten Tupeln auf einer Basisrelation [Abbildung in dieser Leseprobe nicht enthalten] ist fur die auf ihr definierte ^uatenalisierte Sicht[Abbildung in dieser Leseprobe nicht enthalten] dann irrelevant, wenn U den Sichtzustand, unabhangig vom Datenbankzustand, nicht verandert [BCL89]. D. h. der neu berechnete Sichtzustand VN ist nach der Anwendung des Sichtausdrucks auf den neuen Zustand der Relationen [Abbildung in dieser Leseprobe nicht enthalten] unverandert und exakt derselbe, wie vor der Veranderung, also[Abbildung in dieser Leseprobe nicht enthalten]

Ist eine Veranderung[Abbildung in dieser Leseprobe nicht enthalten] nicht irrelevant fur V, so wird sie als relevant bezeichnet. Dies bedeutet jedoch nicht sofort, dass U sich definitiv auf den aktuellen Sichtzustand auswirkt. Ob Einfuge- oder Loschvorgange auf den Basisrelationen tatsachlich zur Wartung von V fuhren, hangt von der jeweiligen Datenbankinstanziierung, also vom Inhalt der Basisrelationen ab.

Um festzustellen, ob [Abbildung in dieser Leseprobe nicht enthalten] eine relevante oder irrelevante Veranderung ist, wird die Erfullbarkeit der Selektionsbedingung P, wie in den nachsten beiden Abschnitten verdeutlicht, getestet. Eine Bedingung kann entweder zu TRUE oder FALSE ausgewertet werden, nachdem all ihre Attribute a(P) durch passende Werte ersetzt wurden. Werden nicht alle, sondern nur einige Attributnamen aus P durch entsprechende Werte eines Tupels [Abbildung in dieser Leseprobe nicht enthalten] ersetzt, so spricht man von der Substitution[Abbildung in dieser Leseprobe nicht enthalten]. Hierbei werden die Attribute [Abbildung in dieser Leseprobe nicht enthalten] durch die jeweils in Dr; gegebenen Werte ersetzt, sodass eine Bedingung mit weniger Variablen entsteht [BCL89]. Bei einer Substitution gilt demnach #(a(P[Dr;])) < #(a(P)).

Der Boolesche Ausdruck, definiert durch P, heibt gultig, wenn er immer zu TRUE ausgewertet wird; erfullbar, wenn er fur mindestens eine Kombination von Werten fur seine Attribute zu TRUE ausgewertet werden kann und unerfullbar, wenn er niemals zu TRUE ausgewertet werden kann [BCL89].

4.1.2 Irrelevante Veranderungen durch INSERT Anweisungen

Es sei[Abbildung in dieser Leseprobe nicht enthalten] eine Basisrelation der Sicht V und[Abbildung in dieser Leseprobe nicht enthalten][Abbildung in dieser Leseprobe nicht enthalten] die Menge der p auf [Abbildung in dieser Leseprobe nicht enthalten] eingefugten Tupel. Bei einer Veranderung[Abbildung in dieser Leseprobe nicht enthalten]ist ein Tupel [Abbildung in dieser Leseprobe nicht enthalten]genau dann irrelevant fur eine Sicht[Abbildung in dieser Leseprobe nicht enthalten] wenn die substituierte Selektionsbedingung [Abbildung in dieser Leseprobe nicht enthalten]unabhangig vom Datenbankzustand unerfullbar ist [BCL89]. Daher muss durch U keine Wartung von V aufgrund einzufugender Tupel[Abbildung in dieser Leseprobe nicht enthalten] erfolgen. Ist[Abbildung in dieser Leseprobe nicht enthalten]unerfullbar, so ist die gesamte Veranderung U irrelevant fur V.

[...]


[1] Abweichend von der hier genannten Problemstellung der Sichtdefinition, bezeichnet das Wort Sichtdefmition im Folgenden immer den Sichtausdruck, d.h. die einer materialisierten Sicht zugrunde liegende AnfTage, welche sie definiert.

[2] Fur eine ausfuhrlichere Beschreibung sei auf [Ga94] verwiesen.

[3] Aus Grunden der Lesbarkeit wird im Zusammenhang mit der Berechnung von □ V, auf Grundlage von Veranderungen □R; und dem alten Zustand R;A, im Folgenden nur R; anstelle von R;A geschrieben. Bezeichnet R; in Gleichungen etwas anderes als den Zustand R;A, so ist dies explizit erwahnt.

[4] Sofern nicht explizit angegeben, bezieht sich die alleinige Bezeichnung SicAt im Folgenden immer auf eine materialisierte Sicht.

[5] Auf die Moglichkeit, dass Veranderungen der Basisrelationen keine Veranderungen auf einer materialisierten Sicht hervorrufen, wird in Kapitel 4.1 eingegangen.

[6] Auf Besonderheiten, die bei einigen Sichtdefinitionen, wie beispielsweise bei PROJECT Sichten, beachtet werden mussen und unter denen die Berechnung von VN von der allgemeinen Definition aus (1) abweicht, wird in Kapitel 4.2 eingegangen.

Ende der Leseprobe aus 47 Seiten

Details

Titel
Inkrementelle Wartung materialisierter Sichten
Hochschule
Humboldt-Universität zu Berlin  (Institut für Informatik)
Note
1,3
Autor
Jahr
2008
Seiten
47
Katalognummer
V192518
ISBN (eBook)
9783656175759
ISBN (Buch)
9783656175636
Dateigröße
1099 KB
Sprache
Deutsch
Anmerkungen
Schlagworte
Datenbanken, Materialisierte Sichten, Views, Wartung, Inkrementell
Arbeit zitieren
Peggy Werner (Autor:in), 2008, Inkrementelle Wartung materialisierter Sichten, München, GRIN Verlag, https://www.grin.com/document/192518

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Inkrementelle Wartung materialisierter Sichten



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden