In diesem Artikel stellen wir ein Replikationsverfahren fu¨r verteilte Datenbanksysteme vor, das multiple Fragmentierungen derselben Datentabelle unterstu¨tzt. Solche multiplen Fragmentierungen ko¨nnen beispielsweise fu¨r eine flexible Anfragebeantwortung ausgenutzt werden. Die Besonderheit unseres Ansatzes liegt darin, dass bei der Replikation und Wiederherstellung der Tabellen die U¨ berschneidungen von Fragmenten, die aus unterschiedlichen Fragmentierungen entstehen, beru¨cksichtigt werden, um so die Anzahl der beno¨tigten Server zu reduzieren. Wir betrachten insbesondere den Fall, bei dem mehr Fragmentierungen als der gewu¨nschte Replikationsfaktor existieren, sodass nur ein Teil der Replikationsbedingungen notwendigerweise erfu¨llt werden mu¨ssen und die restlichen optional sind.
Um große Datenmengen in verteilten Datenbanksystemen zu speichern, werden diese normalerweise in kleinere Teilmengen fragmentiert und dann auf mehrere Server verteilt. Daru¨ber hinaus werden, um bessere Verfu¨gbarkeit und Fehlertoleranz zu garantieren, Kopien der Datensa¨tze erstellt und auf unterschiedlichen Servern gespeichert. Bisherige Arbeiten zu diesem Thema konzentrieren sich meist nur auf eine einzelne optimale Fragmentierung der Daten. In unserem Ansatz hingegen betrachten wir multiple Fragmentierungen, um anschließend eine Replikation der Fragmente zu finden, die U¨ berlappungen beru¨cksichtigt und so die Anzahl der beno¨tigten Server reduziert. Dies kann beispielsweise zur flexiblen Anfragebeantwortung benutzt werden, was in [Wie14, 1.1
Fragmentierung relationaler Tabellen ist ein seit langer Zeit untersuchtes Problem und Teil von Standardlehrbu¨chern wie [ O¨V11]. Einige Ansa¨tze setzen vertikale Fragmentierung um und betrachten Affinita¨t von Attributen (innerhalb einer vorgegebenen Menge von Anfragen) als Optimierungsmerkmal. Eine vergleichende Evaluation mehrerer Ansa¨tze zur vertikalen Fragmentierung findet sich in [JPPD13]. Im Gegensatz zu diesen Ansa¨tzen setzen wir auf horizontale Fragmentierung fu¨r große Datensa¨tze. Mit Bezug auf horizontale Fragmentierung wird u¨blicherweise eine einzige optimale Fragmentierung gesucht. Beispiele dafu¨r sind [BK15] fu¨r Multiple Query Optimization (MQO), [CZJM10] zur Partitionierung anhand eines Graphen u¨ber einer Menge von Anfragen oder [TPRH16] zur Reduzierung von Abha¨ngigkeiten zwischen Partitionen. Im Gegensatz dazu toleriert unser Ansatz mehrere Fragmentierungen und passt die Replikation den U¨ berlappungen an. Das heißt, die existierenden Ansa¨tze zum Finden einer einzelnen horizontalen Fragmentierung ko¨nnen mit unserem Ansatz kombiniert werden. Damit verbessern wir die Laufzeit fu¨r Bereichsabfragen durch Vermeiden unno¨tiger Vereinigungsoperationen. Zahlreiche Datenbanksysteme bieten zwar die automatische Fragmentierung an (so etwa der IBM DB2 Database Advisor [ZRL+04], der Vertica DBDesigner [VBC+14] oder Oracles partitioning by reference [ECS+08]), jedoch unterstu¨tzen auch sie nur jeweils eine einzige Fragmentierung.
Datenreplikation ist ein zentraler Aspekt in verteilten Datenbanksystemen. Eine U¨ bersicht u¨ber Optimierungsstrategien und Forschungsfragen fu¨r Replikationsverfahren gibt es in [KPX+11, SPTB14]. Keines dieser Verfahren betrachtet jedoch mehrere Fragmentierungen. Wir benutzen gemeinsame Teilfragmente, mit denen eine Fragmentierung aus einer anderen Fragmentierung wiederhergestellt werden kann. 1.2
Übersicht
In Abschnitt 2 werden die Hintergru¨nde zu Fragmentierung und Datenverteilung beschrieben. Daru¨ber hinaus stellen wir das Replikationsproblem fu¨r eine einzelne Fragmentierung vor. Anschließend erweitern wir in Abschnitt 3 das
Zuna¨chst werden hier kurz Vorarbeiten zu Fragmentierung und Datenverteilung vorgestellt. Desweiteren geben wir Einblick in das Replikationsproblem fu¨r eine einzelne Fragmentierung. Als laufendes Beispiel werden wir im Folgenden ein Informationssystem eines Krankenhauses verwenden, bei dem die ID der Patienten zusammen mit deren Krankheit gespeichert wird (Tabelle 1). 2.1
Im Folgenden werden wir ein Datenreplikationsschema fu¨r horizontale Fragmentierung vorstellen. Eine wichtige Eigenschaft horizontaler Fragmentierungen ist die Korrektheit. Diese beinhaltet drei Eigenschaften: • Vollsta¨ndigkeit : Jedes Tupel der urspru¨nglichen Datentabelle ist in einem Fragment enthalten. • Rekonstruierbarkeit : Die Vereinigung aller Fragmente resultiert in der urspru¨nglichen Datentabelle. • Redundanzfreiheit: Kein Tupel ist in zwei Fragmenten gleichzeitig enthalten.
Wir werden im Folgenden Vollsta¨ndigkeit und Redundanzfreiheit fu¨r unsere intelligente Replikation ausnutzen. 2.2
In verteilten Datenbanksystemen werden Datensa¨tze auf verschiedenen Servern gespeichert. Das Datenverteilungsproblem – ohne Replikation – kann daher als Beha¨lterproblem (bin packing problem, BPP) dargestellt werden: • K Server entsprechen K Beha¨ltern • Jeder Beha¨lter besitzt eine maximale Kapazita¨t W • n Datensa¨tze entsprechen n Objekten • Jedes Objekt i besitzt ein Gewicht wi ≤ W • Die Objekte sollen auf eine minimale Anzahl von Beha¨ltern aufgeteilt werden, ohne die maximale Kapazita¨t W eines Beha¨lters zu u¨berschreiten BPP kann folgendermaßen als ganzzahliges lineares Programm dargestellt werden:
In diesem ILP benutzen wir xik als Indikatorvariable, die angibt, ob das Fragment fi dem Server k zugewiesen wird. Die Bedingung (2) stellt dabei sicher, dass jedes Fragment genau einem Server zugewiesen wird. Hat yk den Wert 1, so bedeutet dies, dass Server k benutzt wird, also mindestens ein Fragment darauf gespeichert wird. Durch Gleichung (3) wird garantiert, dass die Kapazita¨t der benutzten Server nicht u¨berschritten wird. Letztendlich wird in der Zielfunktion (1) die Anzahl der belegten Server minimiert.
Das Beha¨lterproblem mit Konflikten (BPPC) ist eine Erweiterung des klassischen Beha¨lterproblems. Dabei wird zusa¨tzlich ein Konfliktgraph G = (V, E) betrachtet, bei dem die Knoten V der Menge der Objekte entsprechen. In dem Graph existiert eine Kante (i, j), wenn die beiden Objekte i und j nicht in denselben Beha¨lter gelegt werden du¨rfen. Um diese Bedingung einzuhalten kann das vorherige ganzzahlige lineare Problem um eine Bedingung erweitert werden: xik + xjk ≤ yk sbeeillFe. =W{efit1e,r. .s.e,iefnn}Fe1i,n.e. .k,oFrrmekdteieFMraegnmgeenntideerurnKgoepiineenr vToanF . Fu¨r jedes Fragment fi ∈ F ist eine Verteilung der m Kopien fi1 ∈ F 1, . . . , fim ∈ F m gesucht, sodass die Kopien alle auf unterschiedliche Server verteilt sind.
Dieses Problem entspricht der Lo¨sung eines BPPC Problems, bei dem die Bedingungen, dass alle Kopien auf verschiedene Server verteilt werden, durch Kanten im Konfliktgraph dargestellt werden. Der Konfliktgraph hat folgende Form: Die Knotenmenge ist V = Sm l=1 F l und die Kantenmenge ist E = n fil, fil0 |i = 1, . . . , n; l = 1, . . . , m; l0 < lo.
ÜBERLAPPUNGEN UND MULTIPLE
In diesem Abschnitt werden wir dieses Replikationsschema nun auf multiple Fragmentierungen erweitern. Dabei wird einerseits der Speicherbedarf durch eine intelligente Replikationsstrategie reduziert und somit die Anzahl der beno¨tigten Server minimiert und andererseits die Mo¨glichkeit geschaffen, durch unterschiedliche Fragmentierungen flexibel auf die Bedu¨rfnisse des Nutzers zu reagieren. Dies kann, wie bereits zuvor erwa¨hnt, zur flexiblen Anfragebeantwortung verwendet werden, um mehrere verschiedene Relaxationsattribute zuzulassen (siehe [Wie14, Wie15a, Wie15b]).
Formal betrachten wir r Fragmentierungen F 1, . . . , F r derselben Tabelle. Jede Fragmentierung F l (1 ≤ l ≤ r) besteht aus Fragmenten f1l, . . . , f nll , wobei nl von der jeweiligen Fragmentierung abha¨ngt.
In unserem Beispiel ko¨nnte eine Fragmentierung darin bestehen, die Spalte Diagnosis in Atemwegserkrankungen und Knochenbru¨che zu unterteilen (Tabelle 2). Zusa¨tzlich ko¨nnte man eine weitere Fragmentierung anhand der Spalte PatientID erstellen, bei der die IDs in Werte kleiner als 5000 und Werte gro¨ßer als 5000 unterteilt werden (Tabelle 3). 3.1
Wir stellen nun ein intelligentes Datenreplikationsschema fu¨r multiple Fragmentierungen vor, bei dem die Anzahl der Kopien von Tupeln reduziert werden soll, um so den Gesamtspeicherbedarf zu minimieren.
Bei m-copy-DRP (Abschnitt 2.3) betrachteten wir lediglich disjunkte Fragmente und jeweils m Kopien davon. Diese Annahmen werden nun folgendermaßen vera¨ndert: Fragmente verschiedener Fragmentierungen du¨rfen u¨berlappen. Daher ist es im Allgemeinen nicht no¨tig, m Kopien jedes Fragments zu speichern, um jedes Tupel m mal zu replizieren. Daher schlagen wir, um den Speicherbedarf zu reduzieren, ein intelligentes Replikationsschema vor und fordern, dass lediglich jedes Tupel m mal repliziert wird und nicht jedes Fragment.
Dabei argumentieren wir, dass m Kopien eines Tupels fu¨r ein intelligentes Wiederherstellungsverfahren genu¨gen: Jedes Tupel j soll als Sicherungskopie auf m verschiedenen Servern gespeichert sein, diese Kopien du¨rfen sich jedoch in unterschiedlichen Fragmenten befinden. Das bedeutet, dass jede Fragmentierung F l aus den Fragmenten einer anderen Fragmentierung F l0 wiederhergestellt werden kann.
Wir unterscheiden im Folgenden drei Fa¨lle: Zuerst nehmen wir an, dass die Anzahl der Fragmentierungen gleich der Anzahl der geforderten Kopien ist (r = m). Fu¨r den zweiten Fall, bei dem die Anzahl der Fragmentierungen kleiner als die Anzahl der Kopien ist (r < m), ko¨nnen einige der Fragmentierungen einfach kopiert werden. Den interessanteren Fall, dass die Zahl der Fragmentierungen gro¨ßer als die Zahl der geforderten Kopien ist (r > m), werden wir in einem weiteren Abschnitt behandeln. Zuna¨chst geben wir allerdings eine formale Definition fu¨r das Datenreplikationsproblem mit u¨berlappenden Fragmenten (overlap-DRP):
Definition 2. Seien F l = f1l, . . . , f nll fu¨r l = 1, . . . , r Fragmentierungen derselben Datentabelle und m der geforderte Replikationsfaktor. Fu¨r jedes Tupel j sind Fragmente fil l ≤ nl gesucht, sodass j ∈ fi1m∩it. .1. ∩≤fimlm ≤unmd duinesde 1Fr≤agmi ente mu¨ssen auf unter1 schiedliche Server verteilt werden.
Wir werden diese Definition nun an dem Beispiel veranschaulichen. Dazu nehmen wir an, dass die maximale Kapazita¨t W der Server 5 Tupel betra¨gt und setzen einen Replikationsfaktor 2 voraus. Desweiteren seien Fragmentierungen wie in den Tabellen 2 und 3 gegeben, was zu den Fragmenten Respiratory, Fracture, IDhigh, IDlow fu¨hrt. Im m-copyReplikationsschema wu¨rde jedes Fragment jeweils auf zwei Servern gespeichert: Dafu¨r werden mindestens 6 Server beno¨tigt. Mit unserem intelligenten Replikationsschema, das U¨ berlappungen von Fragmenten ausnutzt, ko¨nnen wir eine Lo¨sung konstruieren, die lediglich 3 Server beno¨tigt: • Zuna¨chst speichern wir das Fragment Respiratory auf
Server S1. • Anschließend legen wir das Fragment IDlow auf Server
S2. • Die Fragmente Fracture und IDhigh werden zusammen auf Server S3 gespeichert.
Dadurch erhalten wir den Replikationsfaktor 2 fu¨r jedes Tupel und ko¨nnen dennoch jedes Fragment aus den anderen zuru¨ckgewinnen: • Fragment Respiratory kann aus den Fragmenten IDlow und IDhigh zuru¨ckgewonnen werden, denn Respiratory = (IDlow ∩ Respiratory ) ∪ (IDhigh ∩ Respiratory ) • Fragment Fracture kann aus IDlow zuru¨ckgewonnen werden, denn Fracture = (IDlow ∩ Fracture) • Fragment IDlow kann aus Respiratory und Fracture rekonstruiert werden, denn IDlow = (IDlow ∩ Respiratory) ∪ (IDlow ∩ Fracture) • Fragment IDhigh kann aus dem Fragment Respiratory zuru¨ckgewonnen werden, denn IDhigh = (IDhigh ∩ Respiratory ) Nun werden wir erarbeiten, wie overlap-DRP als erweitertes BPPC Problem dargestellt werden kann und dazu ein ganzzahliges lineares Programm formulieren. Hierfu¨r bezeichne J die Anzahl der Tupel der Eingabetabelle, m den Replikationsfaktor, K die Anzahl der zur Verfu¨gung stehenden Server und n die Gesamtzahl aller Fragmente aller Fragmentierungen. Dies fu¨hrt zu folgendem ganzzahligen linearen Programm:
K min X yk
k=1
In dieser Formulierung verwenden wir die Variablen yk
und xik wie in den vorherigen ILPs. Um die Notation zu
vereinfachen benutzen wir i = 1, . . . , n, mit n = |F 1| + . . . +
|F m|, nummerieren also alle Fragmente nacheinander von 1
bis n, auch wenn sie aus unterschiedlichen
Fragmentierungen stammen. Wir fu¨hren zusa¨tzlich K Indikatorvariablen
zjk fu¨r jedes Tupel j ein, mit zjk = 1, falls Tupel j auf
Server k gespeichert wird. Mithilfe von Gleichung (
Die Formulierung des ganzzahligen linearen Programms im vorherigen Abschnitt ist aufgrund der vielen z-Variablen ho¨chst ineffizient fu¨r eine große Anzahl von Tupeln in einer Tabelle. Daher wollen wir nun zeigen, dass es mo¨glich ist, sich lediglich auf die x-Variablen zu konzentrieren.
Zuna¨chst wird in diesem Abschnitt nur der Fall betrachtet, bei dem der Replikationsfaktor gleich der Anzahl der Fragmentierungen ist (r = m), mit dem Fall r > m befassen wir uns anschließend im na¨chsten Abschnitt.
Ist der Replikationsfaktor m gleich der Anzahl der Fragmentierungen r, so du¨rfen Fragmente fi und fi0 nicht auf demselben Server gespeichert werden, falls fi ∩ fi0 6= ∅ (wir nehmen i < i0 an, um isomorphe Bedingungen zu vermeiden). Ansonsten kann fu¨r alle Tupel j ∈ fi ∩ fi0 der Replikationsfaktor nicht erreicht werden. Andererseits ist diese Bedingung auch hinreichend, denn aufgrund der r = m Fragmentierungen wird dadurch gewa¨hrleistet, dass jedes Tupel
2784 2784 8765 8457
brokenLeg Flu Asthma Cough auf m verschiedenen Servern gespeichert ist. Diese Beobachtung fu¨hrt zu folgender Vereinfachung des ganzzahligen linearen Programms:
In diesem Abschnitt betrachten wir nun den komplizierteren Fall, bei dem die Anzahl der Fragmentierungen gro¨ßer als der geforderte Replikationsfaktor ist (r > m). In diesem Fall mu¨ssen, um den Replikationsfaktor einzuhalten, fu¨r jedes Tupel j nur m der r Fragmente, die j beinhalten, auf unterschiedliche Servern verteilt werden. Die restlichen r − m Fragmente ko¨nnen beliebig, auch auf den bereits belegten Servern, gespeichert werden, was dazu beitra¨gt, den Speicherbedarf zu verringern.
Wir werden dies an einem kleinen Beispiel illustrieren. Angenommen wir haben eine Fragmentierung F , die nur das Fragment f beinhaltet, eine Fragmentierung F 0 mit Fragmenten f10 und f20 und eine dritte Fragmentierung F 00 mit den Fragmenten f100 und f200. Dabei u¨berlappt f1 mit allen anderen vier Fragmenten: f1 ∩ f10 6= ∅, f1 ∩ f20 6= ∅, f1 ∩ f100 6= ∅ und f1 ∩ f200 6= ∅. Wir veranschaulichen diese Situation in einem leicht modifizierten Beispiel unseres Krankenhausszenarios in den Tabellen 4, 5 und 6. Fu¨r f1 gibt es also 4 Konfliktbedingungen und es ist nicht klar, welche davon eingehalten werden sollten, um einerseits 2-Kopien-Replikation fu¨r jedes Tupel in f1 sicherzustellen und andererseits die Anzahl der Server zu minimieren. Betrachten wir das Beispiel nun mit konkreten Werten. Wir nehmen eine maximale Kapazita¨t der Server von W = 6 an, das Gewicht von f1 ist w1 = 4, die Gewichte von f10 und f20 sind w10 = w20 = 2, das Gewicht von f100 ist w100 = 1 und das Gewicht von f200 ist gleich w200 = 3. Wir diskutieren nun einige Optionen, wie diese Fragmente verteilt werden ko¨nnten: • Angenommen wir speichern f1 auf dem Server S1. Um alle zuvor genannten Konfliktbedingungen einzuhal
Aus diesem Beispiel wird deutlich, dass die Entscheidung, welche Konfliktbedingungen eingehalten werden sollen und welche optional sind, sehr schwer ist. Im Folgenden wird nun die Frage beantwortet, wie diese optionalen Konfliktbedingungen in unser ganzzahliges lineares Programm integriert werden ko¨nnen.
Formal gesehen betrachten wir wiederum r Fragmentierungen F l = f1l, . . . , f nll und fu¨r jedes Tupel j gibt es Fragmente fill fu¨r 1 ≤ l ≤ r und 1 ≤ il ≤ nl, sodass j ∈ fi1 ∩ . . . ∩ firr . Sind fi11 , . . . , firr , Fragmente aus den r 1 unterschiedlichen Fragmentierungen, so definieren wir den Begriff des gemeinsamen Teilfragments als den Durchschnitt fi1 ∩. . .∩firr . In unserem Beispiel ergeben sich folgende nicht1 leere gemeinsame Teilfragmente: f1 ∩ f10 ∩ f100 = {t1} f1 ∩ f10 ∩ f200 = {t2} f1 ∩ f20 ∩ f200 = {t3, t4} Fu¨r solche nichtleeren gemeinsamen Teilfragmente erha¨lt man paarweise Konfliktbedingungen der Form xilk + xil0 k ≤ yk fu¨r 1 ≤ l ≤ r und 0 < l0 < l. Greifen wir das Beispiel fu¨r das gemeinsame Teilfragment {t1} wieder auf, ergibt das die paarweisen Konfliktbedingungen: Um 2-Kopien-Replikation zu garantieren, muss nur eine dieser Bedingungen erfu¨llt sein. Um dem gerecht zu werden fu¨hren wir neue c-Indikatorvariablen fu¨r jede dieser Bedingungen ein: x1k + x01k ≤ 1 x1k + x010k ≤ 1 x01k + x010k ≤ 1 x1k + x01k ≤ 1 + c1k x1k + x010k ≤ 1 + c2k x01k + x010k ≤ 1 + c3k Diese Variablen haben die folgende Bedeutung: Sind die cVariablen gleich 0, dann ist die Konfliktbedingung erfu¨llt und die beiden Fragmente werden nicht zusammen auf demselben Server k gespeichert. Ist die c-Variable hingegen gleich 1, ist die Konfliktbedingung nicht erfu¨llt und die beiden Fragmente ko¨nnen zusammen auf Server k gespeichert werden. Um die m-Kopien-Replikation zu erzwingen fordern wir, dass die Summe der c-Variablen ho¨chstens r − m ist, was praktisch bedeutet, dass ho¨chstens r − m Bedingungen verletzt werden du¨rfen und mindestens m Bedingungen erfu¨llt werden. In unserem Beispiel fu¨hrt dies zur Bedingung c1k + c2k + c3k ≤ 1. Dieses Konzept wenden wir nun fu¨r beliebige Werte von r und m mit r > m an: Da wir r Fragmentierungen der Form F l = {f1l, . . . , f nll } fu¨r l = 1, . . . , r betrachten, gibt es die Indikatorvariablen xlik, die angeben, ob Fragment i aus der Fragmentierung l auf Server k gespeichert werden. Jedes Fragment fil besitzt ein l gewisses Gewicht wi. Mit S bezeichnen wir die Gesamtzahl der nichtleeren gemeinsamen Teilfragmente und mit gs fu¨r s = 1, . . . , S die Teilfragmente selbst. Die Bedingungen (25) und (26) garantieren zusammen, dass mindestens m Fragmente jedes gemeinsamen Teilfragments gs auf unterschiedlichen Servern gespeichert werden.
In diesem Artikel haben wir das Datenreplikationsproblem fu¨r multiple Fragmentierungen betrachtet. Um Speicherplatz zu sparen, wurde ein intelligentes Replikationsschema vorgestellt, bei dem unno¨tige Kopien von Tupeln vermieden werden. Anschließend haben wir das Problem als ganzzahliges lineares Programm formuliert und dabei versucht die Anzahl der Variablen zu reduzieren, um eine bessere Lo¨sbarkeit zu ermo¨glichen.
Solche multiplen Fragmentierungen ko¨nnten beispielsweise benutzt werden, um Datenbankanfragen flexibel zu beantworten. Diese Anwendung wurde bereits in vorherigen Arbeiten fu¨r ein einzelnes Relaxationsattribut (eine einzelne Fragmentierung) behandelt, la¨sst sich aber auf natu¨rliche Art und Weise auf mehrere Relaxationsattribute erweitern.
Eine genaue Komplexita¨tsanalyse des Verfahrens kann noch vorgenommen werden. Es wird aber deutlich, dass fu¨r den Fall r > m eine zusa¨tzlich Schwierigkeit (u¨ber das BPPC) darin liegt, die U¨ berlappungen (nicht-leeren Schnittmengen) zwischen den Fragmenten zu finden.
In zuku¨nftigen Arbeiten sollten vor Allem dynamische Ver¨anderungen im Replikationsschema untersucht werden. Hinzufu¨gen und Entfernen von Daten fu¨hrt zu Vera¨nderungen der Gro¨ßen der Fragmente und daher ko¨nnte eine Umverteilung der Daten auf den Servern notwendig werden.
Zudem beschreiben die Autoren von C-Store [?] die Mo¨glichkeit verschiedene Projektionen (also vertikale Fragmente) in verschiedene Segmente (horizontale Fragmente) aufzuteilen ohne jedoch ein genaues Verteilungsverfahren anzugeben. Eine solche Form der hybriden Fragmentierung als ILP darzustellen ist eine weitere zuku¨nftige Fragestellung.