[zurück] [vorwärts]
 
3. Fragmentierung auf der Anwendungsebene

3.1 Überleitung

Bei der Betrachtung von Disk Arrays ging es schwerpunktmäßig darum, wie Files - die ja beispielsweise auch Relationen einer Datenbank enthalten können - partitioniert und dann auf die einzelnen Platten im Array verteilt, um eine bestmögliche Performance bei gutem Kosten-Leistungsverhältnis zu erreichen. Dies ist eine Technik, wie sie allgemein auf viele Problem bei der Speicherung großer Datenmengen angewendet werden kann, nicht nur bei Datenbanken. Die Anforderungen, die Datenbanken an ein solches Disk Array stellen, wurden schon kurz erwähnt, doch ebenso fand Erwähnung, daß nicht zwangsweise ein Controller eines Disk Arrays die Partitionierung vornehmen muß, sondern daß dies auch durch Software sprich die Anwendungen geschehen kann. So kann man sich vorstellen, daß ein Datenbanksystem mit mehreren Festplatten - die nicht unbedingt ein Disk Array nach der Beschreibung in Punkt 2 bilden müssen - arbeitet, wie z.B. ein verteiltes Datenbanksystem. Sei es nun aus einem Mißverhältnis Größe einer Relation : Plattenplatz oder ebenso wie bei den Disk Arrays aus Optimierungsgründen von Lese- und Schreiboperationen, eventuell ist es auch hier nötig, Relationen zu zerlegen. Geschieht dies auf DBS-Ebene spricht man von Fragmentierung (im Gegensatz zur Partitionierung).

3.2 Ein Algorithmus für horizontale Fragmentierung
 
Da die Extension einer Relation auch als Tabelle betrachtet werden kann, sind logischerweise zwei Arten der Fragmentierung möglich: horizontal und vertikal. Nehmen wir für die folgenden Ausführungen folgende Beispielrelation (Schlüsselattribut):
 

Vortrag
Kennziffer
Autor
Titel
DB 98 00 233 Müller ER-Modell und Relationen
DB 98 01 156 Meier Relationelle Anfragesprachen
DB 98 00 678 Schulze Verteilte Datenbanken
DB 97 34 235 Schmidt Relationenalgebra

Will man diese Relation horizontal fragmentieren, so tut man dies "zwischen" den Tupeln. Wo man die Relation teilt, hängt von bestimmten Bedingungen ab, die entweder in der Relation selbst liegen können (dann handelt es sich um eine Primary horizontal fragmentation) oder in Abhängigkeit von anderen Relationen im Relationenschema stehen können (als Derived horizontal fragmentation bezeichnet) [6].
Egal um welche Fragmentierungsart es sich handelt, zunächst muß immer beachtet werden, wie die einzelnen Relationen der Datenbank miteinander verknüpft sind, z.B. durch Fremdschlüsselbeziehungen. Diese gerichteten Verknüpfungen zweier Relationen über einen Equijoin sollen im Folgenden als Links bezeichnet werden. Die Relation, von der der Link ausgeht (also diejenige, die sozusagen den Fremdschlüssel stellt), wird als Owner des Links bezeichnet, die Relation, auf die der Link verweist (die Relation, die den Fremdschlüssel dann beinhaltet), als Member. Somit lassen sich leicht Beziehungen zwischen Relationen darstellen.
Um eine sinnvolle Fragmentierung durchzuführen, benötigt man weiterhin Informationen über "Nutzung" der in den Relationen gespeicherten Daten. Dies sind vor allem zwei Informationen:

  1. Minterm selectivity

  2. Dies sei die Anzahl der Tupel einer Relation, auf die eine durch Minterm-Prädikate definierten Anfrage erfüllen würden. Ein Minterm-Prädikat ist eine konjunktive (logisch UND) Verknüpfung von einfachen boolschen Ausdrücken wie =, >, <, =<, =>. Da jeder boolsche Ausdruck immer in seine konjunktive Normalform überführt werden kann, schränkt dies die Allgemeingültigkeit nicht ein.
    Beispiel: Für eine Anfrage A: Autor="Müller" ^ Titel="Paralleler Input/Output" wäre die Minterm selectivity sel(A)=0, da kein Tupel das Minterm-Prädikat A erfüllt. Bei einer Anfrage B: Autor="Müller" ^ Titel="ER-Modell und Relationen" bekäme man als Ergebnis sel(B)=1, da ein Tupel B erfüllt.
  3. Zugriffshäufigkeit

  4. Die Frequenz, mit der der Nutzer auf die Daten zugreift. Betrachtet man eine Menge von Anfragen Q={q1, q2, ... ,qq}, so drückt acc(qi) die Zugriffshäufigkeit auf die Daten dieser Anfrage qi in einem bestimmten Zeitabschnitt aus.
An sich gesehen, ist eine Primary horizontal Fragmentation eine bzw. mehrere Selektion(en) auf eine bestehende Relation der Datenbank. Bedingung sei, daß die Selektionsbedingung ein Minterm-Prädikat ist. So ließe sich unser Beispiel wie folgt Fragmentieren (ich nutze SQL, um die Formelzeichen der Relationen-Algebra zu umgehen):
SELECT *
FROM Vortrag
WHERE Kennziffer<="DB98 00 250" und

SELECT *
FROM Vortrag
WHERE Kennzeifer>"DB98 00 250"

So wäre Vortrag in seiner jetzigen Form in zwei Relationen fragmentiert. Problematisch würde es, wenn die Domäne von Kennziffer ins Unendliche anwachsen würde; wo müßten die Bereichsgrenzen gesetzt werden, um die Relation gleichmäßig zu fragmentieren? Hier ist es notwendig, theoretisch unendliche Domänen so zu begrenzen, daß alle Anwendungsanforderungen erfüllt sind und doch eine "ordentliche" Fragmentierung möglich ist.
Somit kann man nun sagen, daß ein horizontales Fragment einer Relation alle Tupel enthält, die ein Minterm-Prädikat aus der Selektionsbedingung erfüllen. Dadurch gibt es genausoviele Fragmente (dann auch als Minterm-Fragment bezeichnet), wie es Minterm-Prädikate gibt. Es gilt also nur einen Algorithmus zu finden, der die einfachen boolschen Ausdrücke, aus denen die Minterm-Prädikate bestehen, bestimmt, und zwar so, daß letztere vollständig und minimal sind. Vollständigkeit bedeutet hier, daß die Wahrscheinlichkeit für zwei Tupel aus einem beliebigen Minterm-Fragment, daß sich aus den gefunden einfachen boolschen Ausdrücken ergibt, gelesen zu werden, immer gleich ist. Dies ist offensichtlich eine Grundvoraussetzung für eine optimale Primary horizontal Fragmentation. Mit Minimalität ist in diesem Zusammenhang gefordert, daß jeder gefundene einfache boolsche Ausdruck auch Einfluß auf das Ergebnis der Fragmentierung haben muß. Kann ein Ausdruck weggelassen werden, und das Ergebnis der Fragmentierung bleibt dennoch gleich (der Ausdruck ist also nicht relevant), so war das Minterm-Prädikat nicht minimal. Nun kann man einen Algorithmus entwickeln, der aus einer gegebenen Menge von einfachen boolschen Ausdrücken eine vollständige und minimale Menge generiert [6].
 
 Eingabe: R: Relation; Pr: Menge einfacher boolscher Prädikate
 Ausgabe: Pr': Menge einfacher boolscher Prädikate
 es sei:  F: Menge von Minterm-Fragmenten
 begin
  Finde ein pi aus Pr so daß pi R nach FRCM partitioniert
  Pr' <- Pi
  Pr  <- Pr - pi
  F   <- fi
  do
    begin
       Finde ein pj aus Pr so daß pj ein fk nach FRCM partitioniert
       Pr' <- Pr' + pj
       Pr  <- Pr - pj
       F   <- F + fj
       if es existiert ein pk aus Pr' das nicht relevant ist then
         begin
            Pr' <- Pr' - Pk
            F   <- F - fk         
       end-if
     begin-end     
   until Pr' vollständig ist
end.

Der Algorithmus beginnt, einen einfachen boolschen Ausdruck aus der gegebenen Menge zu finden, der die zu fragementierende Relation R so partitioniert, daß mindestens zwei Fragmente entstehen, die von mindestens einer Anwendung, die auf die Relation zugreift, unterschiedlich gelesen werden; mit anderen Worten: es wird ein relevanter einfacher boolscher Ausdruck gesucht. (Wenn also z.B. jede Anwendung bei jeder Leseoperation auf jedes Fragment wäre diese Regel verletzt.) Dies ist Voraussetzung, um später eine vollständige und minimale Ergebnismenge zu erhalten (als Fundamental rule of completeness and minimality (FRCM) [6] bezeichnet).
Dieser gefundene einfache boolsche Ausdruck wird der Ergebnismenge hinzugefügt und von der gegebenen Menge abgezogen. Das zugehörige Fragment der Relation wird zu der Ergebnisfragmentmenge addiert. Nun beginnt eine do-until-Schleife, weiterer einfache boolsche Ausdrücke aus der gegebenen Menge zu finden, so daß bereits ermittelte Fragmente weiter partitioniert werden können, ohne die Fundamental rule of completeness and minimality zu verletzen. Gefundene Ausdrücke werden der Ergebnismenge hinzugefügt und von der gegebenen Menge abgezogen; weiterhin wird die Ergebnisfragmentmenge um das neue gefundene Fragment erweitert. Die auf diese Weise erweiterte Ergebnismenge wird daraufhin kontrolliert, daß sie minimal ist. Ist sie das nicht (wird also ein nichtrelevanter einfacher boolscher Ausdruck gefunden), wird dieser zusammen mit dem zugehörigen Fragment aus den Ergebnismengen (Ausdruck und Fragment) entfernt. Die Schleife wird beendet, wenn die Ergebnismenge vollständig ist.
Um nun zum eigentlichen Fragmentierungsschritt zu gelangen, muß diese gefundene vollständige und minimale Menge von einfachen boolschen Ausdrücken in eine Menge von Minterm-Prädikaten überführt werden, anhand derer dann die Fragmentierung durchgeführt wird. Zu achten ist bei dieser Überführung nur darauf, daß die Menge recht stark anwachsen kann, hier also eine Reduzierung nötig ist, vornehmlich durch Ausmerzung von Prädikaten, die sich gegenseitig aufheben. So entsteht folgender Algorithmus für die Primary horizontal Fragmentation:
 

Eingabe: Ri: Relation; Pri: Menge von einfachen boolschen Ausdrücken
Ergebnis: Mi: Menge von Minterm-Fragementen
Begin
  Pr'i <- COM_MIN(Ri,Pri)
  Berechne die Menge Mi der Minterm-Prädikate
  Berechne die Menge Ii der Folgerungen aus jedem pi aus Pr'i
  for each mi aus Mi do
    if mi einer Folgerung aus I logisch entgegenwirkt then
      Mi <- Mi - mi
    end-if
   end-for
end.
 
Mit der Prozedur COM_MIN ist der oben beschriebene Algorithmus zur Überführung einfacher boolscher Ausdrücke gemeint. Ein Beispiel zur Funktion der Menge I: wenn wir als Ergebnis aus diesem Algorithmus die Menge Pr erhalten, als boolsche Ausdrücke p:att = wert_1 und q:att = wert_2 enthält, und die Domäne von att nur zwei Werte enthält, dann läßt sich folgern, daß wenn att einen der beiden Werte angenommen hat, es nicht gleichzeitig den anderen annehmen kann. Ergibt nun die Berechnung der Minterm-Prädikate, daß es nach ihnen doch so seien soll, können diese Prädikate gleich gelöscht werden.
Bei einer Derived horizontal fragmentation nun kommt es auf die Verknüpfung zwischen den Relationen an; hier hilft der eingeführte Begriff des Links (Erinnerung: ein Equijoin). Diesen kann man auch als Semijoin darstellen, welches insofern wichtig ist, daß wir die Member-Relation unseres Links entsprechend der Owner-Relation fragmentieren, aber diese Fragmentierung nur aufgrund der Attribute der Member-Relation durchführen wollen. Somit kann man eine Derived horizontal fragmentation als den Semijoin der Member-Relation mit jeden Primary horizontal fragment definieren. Ein entsprechender Algorithmus bräuchte also nur die Fragmente der Owner-Relation, die Member-Relation an sich und die Prädikate des Semijoins. Schwierigkeiten entstehen nur, wenn eine Relationen an mehreren Links partizipiert. Dann muß entschieden werden, welcher Link benutzt wird, um die Relation zu Fragmentieren. Zum einen kann man danach gehen, welche Relationen/Links von seiten der Anwendungen mehr genutzt werden. Hier sind Beobachtungen der Zugriffshäufigkeiten nötig. Zum anderen kann man aber auch eine Entscheidung danach treffen, welche Fragmentierung für den späteren Join besser geeignet scheint. Dies ist gerade für die Parallelisierung in verteilten Datenbanken wichtig; so ist es günstig, die Fragmentierung so zu wählen, daß beim Join zwischen den verlinkten Relationen jeweiligen zu joinenden Fragmente (man joint also nicht zwei komplette Relationen, sondern nur die entsprechenden Fragmente paarweise) an der gleichen Stelle im verteilten System liegen.
Nun gilt es nur noch, die Fragmentierung auf ihre Korrektheit zu überprüfen. Zunächst die Vollständigkeit: dies ist bei der Primary horizontal fragmentation einfach, denn wenn die Prädikate, nach denen fragmentiert wurde, vollständig sind, ist es auch die Fragmentierung. Für die Derived horizontal fragmentation gilt dies, wenn die Tupel eines jeden Fragments der Member-Relation auch in der Owner-Relation vorhanden sind. Außerdem gilt die Fragmentation als korrekt, wenn die Ausgangsrelation aus den Fragmenten durch Vereinigung wieder rekonstruierbar sind. Ein dritter Faktor für die Korrektheit ist die Disjunktheit der Fragmente. Bei der Primary horizontal fragmentation ist dies automatisch der Fall, solange die Minterm-Prädikate sich gegenseitig ausschließen. Für die Derived horizontal fragmentation gilt dies auf jeden Fall dann, wenn oben beschriebene Konstellation der zu joinenden Fragmente von Owner- und Member-Relation eingehalten wird.

3.3 Ein Algorithmus für vertikale Fragmentierung

Die vertikale Fragmentierung zerlegt eine Relation nun nicht entlang ihrer Tupel, sondern entlang der Attribute, die Tupel werden also sozusagen zerschnitten. Es entstehen also Fragmente, die jeweils eine Teilmenge der Attribute der Ausgangsrelation enthalten, und dazu den Primärschlüssel der Relation, um alle Fragmente später wieder zusammenfügen zu können. Man erhält also kleinere Relationen, die - so das Ziel der vertikalen Fragmentierung - auf solche Art (im günstigsten Fall) fragmentiert sind, daß Anwendungen nur auf ein Fragment zugreifen müssen, um die Nutzeranfragen zu beantworten. So sind weniger Lese- und Schreibzugriffe auf die Platte nötig und der Speicherbedarf ist ebenfalls geringer. Es ist also deutlich, daß erneut die Anforderungen der Anwendungen eine entscheidende Rolle bei der Ausführung der vertikalen Fragmentierung spielen. Ein Algorithmus für die vertikale Fragmentierung könnte wir folgt aussehen [6]. Die zum Verständnis nötigen Erläuterungen folgen.
 

input: CA: clustered affinity matrix; R: Relation
output: F: Menge von Fragmenten
begin
   Berechne CTQn-1
   Berechne CBQn-1
   Berechne COQn-1
   best <- CTQn-1 * CBQn-1 - (COQn-1)2
   do                             {Ermittle beste Partitionierung}
      begin
        for I from n - 2 to 1 by -1 do
        begin
            Berechne CTQI
            Berechne CBQI
            Berechne COQI
            z <- CTQI * CBQI - COQI2
            if z > best then
            begin
              best <- z
              Speichere die shift position
            end-if
        end-for
        call SHIFT(CA)
      end-begin
    until keine SHIFTs mehr möglich
    Rekonstruiere die Matrix anhand der shift position
    R1 <- ¶TA(R) U K {K ist die Menge der Primärschlüssel-Attribute von R}
    R2 <- ¶BA(R) U K
    F  <- {R1,R2}
 end.
 
Der Algorithmus erhält als Eingabe die Relation, die fragmentiert werden soll, und eine Clustered Affinity Matrix (CA). Diese soll dazu dienen, die oben erwähnte Anwendungsorientiertheit der Fragmentierung zu ermöglichen. Um zur CA zu gelangen, benötigt man zuerst Informationen darüber, wie sich zwei Attribute in bezug auf die Menge möglicher Anwendungen (und deren Anfragen) verhalten. Diese Information wird mit dem Attribute affinity measure (aff) ausgedrückt. Die aff-Funktion liefert für zwei Attribute einer Relation eine Maßzahl, die umso größer ist, je häufiger eine Anfrage auf beide zu messenden Attribute zugreift (genaue Formeln finden sich in [6]). Da immer zwei Attribute im Vergleich stehen, kann für diese eine zweidimensionale Matrix - die Attribute Affinity Matrix (AA) - mit den errechneten Werten erstellt werden. Wie die Namensähnlichkeit zwischen AA und CA schon andeutet, gelangt man zur CA durch Clustering der AA. Der zugehörige Algorithmus [6] läuft in drei Schritten ab:
  1. Initialisierung: Auswahl einer beliebigen Spalte aus der AA und Kopierung dieser in die CA
  2. Iterationsschritt: Jede verbleibende Spalte in der AA wird nacheinander in jede noch freie Spalte der CA eingesetzt; schlußendlich wird aber nur die Positionierung beibehalten, für die das sog. Global affinity measure den höchsten Wert liefert. Das Global affinity measure bildet sich aus der Summe über alle Attributpaare der Relation, für die ihr aff gebildet wird und mit der Summe aller aff’s eines jeden Attributpaarteiles mit den Nachbarn des anderen Attributpaarteiles multipliziert wird. So gelangen Spalten mit Attributen, auf die Anwendungen "ähnlich" zugreifen, in direkte Nachbarschaft, ein Vorteil für die anwendungsorientierte Fragmentierung.
  3. Ordnen der Zeilen: Die Zeilen werden so geordnet, daß ihre relative Position den relativen Positionen der Spalten entsprechen. (Wenn die CA beispielsweise beschriftet werden sollte, entspräche dann die Beschriftung der Spalten denen der Zeilen.)
Anhand dieser CA kann man nun den Punkt finden, an dem unsere Relation den Anforderungen nach bestmöglich partitioniert werden kann. Lokalisiert man diesen Splitting Point auf der Diagonalen der CA, teilt man auch die Attribute in zwei Teile, nämlich die Menge, die sich links oberhalb des Splitting Points befindet (Top Attributes) und die, die rechts unterhalb liegt (Bottom Attributes). Genauso lassen sich die Anwendungen aufteilen, nämlich in diejenigen, die nur auf die Top Attributes zugreifen, diejenigen, die nur auf die Bottom Attributes zugreifen, und diejenigen, die auf beide Menge zugreifen. Der beste Splitting Point ist nun der, der die Mengen der Anwendungen, die nur auf eine der beiden Attributmengen zugreifen, maximiert und die Menge mit den Anwendungen mit Zugriff auf beide Attributmengen minimiert. Die Werte CTQ (für die Top Attributes), CBQ (für die Bottom Attributes) und COQ (für alle Attribute) beinhalten die Anzahl der Zugriffe auf Attribute seitens der Anwendungen aufgeteilt nach Top, Bottom und beide. Aufgabe des Algorithmus ist es nun, einen Punkt zu finden, an dem die Gleichung:
z = CTQ * CBQ -COQ2
maximal wird, welches der Fall ist, wenn CTQ und CBQ möglichst gleich groß sind (wegen der Disjunktheit der Mengen).
Der Algorithmus durchläuft die CA von hinten und berechnet zunächst für die vorletzte Spalte (das vorletzte Attribut) den genannten z-Wert (natürlich geht es nicht für die letzte Spalte, da es dort keine Bottom Attributes gäbe). Dieser Wert wird in best gespeichert. Nun beginnt die Iteration; die Matrix wird Spaltenweise rückwärts durchlaufen und für jede Spalte wird der z-Wert kalkuliert und mit dem bisherigen Maximum in best verglichen. Ist er höher, wird er zum neuen Maximum, und gleichzeitig wird die shift position gespeichert. Nach dem Durchlaufen der matrix muß nämlich eine Shift-Operation über die Matrix durchgeführt werden, bei der die 1. Spalte links zur letzten Spalte rechts und die oberste Zeile zur untersten wird. Dies ist notwendig, weil andernfalls nur eine Partitionierung entlang der Diagonalen der CA möglich wäre und nicht an einem beliebigen Punkt in der Matrix. Durch die Shift-Operation entsteht in der linken oberen Ecke der Matrix ein Block mit den Attributen, die später ein Fragment bilden sollen und so leicht zu identifizieren sind. Die Iteration endet, wenn alle möglichen shift positionen getestet wurden. Da die Position, die mit dem maximalen z-Wert zusammenhängt, gespeichert wurde, kann der Algorithmus die zugehörige Matrix rekonstruieren. Die beiden Fragmente können nun durch zwei einfache Projektionen (durch ¶ dargestellt) über die Top und Bottom Attribute erzeugt werden. Sie müssen noch mit dem Primärschlüssel(n) von der Ursprungsrelation vereinigt werden (zwecks evtl. späterer Rekonstruktion) und können dann vom Algorithmus als Ergebnis ausgegeben werden.
Zuletzt noch ein Blick auf die Korrektheit des Algorithmus: Die Vollständigkeit ist gewährleistet, da jedes Attribut der Ursprungsrelation einem der beiden Fragmente zugeordnet wird. Die Ursprungsrelation läßt sich außerdem durch eine Join-Operation rekonstruieren; solange die Fragmente vollständig sind und die Primärschlüsselattribute vorhanden sind, ist auch dies korrekt möglich. Auch die Disjunktheit ist erfüllt, sieht man einmal von den in allen Tupel replizierten Primärschlüsselattribtuten ab (es ist also nicht im strenge Sinne disjunkt, aber für diesen Fall reicht es).

3.4 Allokation

Sind die Relationen ersteinmal fragmentiert, gilt es, sie günstig zu speichern. Dies ist vor allem bei verteilten Systemen wichtig, um folgende Aspekte zu berücksichtigen:

  1. Geringe Kosten. Darin fließen ein die Kosten des Speicherns eines Fragments an einem Netzwerkknoten, die Kosten für Anfragen an ein Fragment von einem Netzwerkknoten, die Update-Kosten eines Fragments an allen Netzwerkknoten, an denen es gespeichert ist, und natürlich die Kosten für die Datenübertragung.
  2. Hohe Geschwindigkeit. Die Zeit zur Beantwortung einer Anfrage muß minimiert und die der Datendurchsatz des System muß maximiert werden.
Um eine Allokationsentscheidung zu treffen, die beiden Punkten gerecht wird, benötigt man verschiedene Informationen: Mit diesen Informationen kann man eine Allokationsentscheidung treffen, die hinsichtlich der Antwortzeit auf eine Anfrage, der Speicherauslastung und der Prozessornutzlast die Gesamtkosten minimiert. Die Gesamtkosten setzen sich aus den Kosten für die Anfrageabarbeitung und die Speicherung der Fragmente zusammen. Die Speicherkosten verhalten sich proportional zu der Speicherplatzbelegung der einzelnen Fragmente. Schwieriger wird die Festlegung, was die Anfragebearbeitung kostet; man kann diese Kosten zum einen in Kosten für die eigentliche Bearbeitung im Prozessor und zum anderen in die Kosten für den Datentransfer aufteilen. Bei letzterem ist zu beachten, daß bei der Existenz mehrere Kopien eines Fragments im verteilten System die Abarbeitung einer Anfrage nur auf ein Fragment zugreifen muß, die Abarbeitung eines Updates jedoch dazu führt, daß alle Kopien angesprochen werden müssen. Unter der Beachtung der Bedingungen, daß der Speicherbedarf eines Fragments nicht den freien Speicherplatz an einem Netzwerkknoten und der Bedarf an Prozessorzeit für die Abarbeitung einer Anfrage nicht die Kapazität des Prozessors an einem Netzwerkknoten übersteigen darf, kann man dann die Fragmente im System verteilen. (Angaben zu genauerer Literatur zu diesem Problem finden sich in [6].)


Erstellt: 11.01.1998
Zuletzt geändert: 11.01.1998
Autor: Gerrit Gragert