Ein Replikationsschema für multiple Fragmentierungen mit überlappenden Fragmenten Ferdinand Bollwein Lena Wiese Institute of Computer Science Institute of Computer Science University of Göttingen University of Göttingen Goldschmidtstraße 7 Goldschmidtstraße 7 37077 Göttingen, Germany 37077 Göttingen, Germany ferdinand.bollwein@stud.uni- wiese@cs.uni-goettingen.de goettingen.de ABSTRACT Wie15a, Wie15b] untersucht wird. In diesem Artikel werden In diesem Artikel stellen wir ein Replikationsverfahren für wir diese Arbeiten nun erweitern, indem wir beim m-Kopien- verteilte Datenbanksysteme vor, das multiple Fragmentie- Replikationsproblem mehr Fragmentierungen als der Repli- rungen derselben Datentabelle unterstützt. Solche multiplen kationsfaktor zulassen (r > m), sodass einige Replikations- Fragmentierungen können beispielsweise für eine flexible An- bedingungen notwendig und andere optional sind. fragebeantwortung ausgenutzt werden. Die Besonderheit un- seres Ansatzes liegt darin, dass bei der Replikation und Wie- 1.1 Verwandte Arbeiten derherstellung der Tabellen die Überschneidungen von Frag- Fragmentierung relationaler Tabellen ist ein seit langer menten, die aus unterschiedlichen Fragmentierungen entste- Zeit untersuchtes Problem und Teil von Standardlehrbü- hen, berücksichtigt werden, um so die Anzahl der benötig- chern wie [ÖV11]. Einige Ansätze setzen vertikale Fragmen- ten Server zu reduzieren. Wir betrachten insbesondere den tierung um und betrachten Affinität von Attributen (in- Fall, bei dem mehr Fragmentierungen als der gewünschte nerhalb einer vorgegebenen Menge von Anfragen) als Op- Replikationsfaktor existieren, sodass nur ein Teil der Repli- timierungsmerkmal. Eine vergleichende Evaluation mehre- kationsbedingungen notwendigerweise erfüllt werden müssen rer Ansätze zur vertikalen Fragmentierung findet sich in und die restlichen optional sind. [JPPD13]. Im Gegensatz zu diesen Ansätzen setzen wir auf horizontale Fragmentierung für große Datensätze. Mit Be- zug auf horizontale Fragmentierung wird üblicherweise ei- Keywords ne einzige optimale Fragmentierung gesucht. Beispiele da- Behälterproblem mit Konflikten (BPPC), Datenreplikations- für sind [BK15] für Multiple Query Optimization (MQO), problem (DRP), Fragmentierung, Verteilte Datenbanksyste- [CZJM10] zur Partitionierung anhand eines Graphen über me, Ganzzahlige lineare Optimierung einer Menge von Anfragen oder [TPRH16] zur Reduzierung von Abhängigkeiten zwischen Partitionen. Im Gegensatz da- zu toleriert unser Ansatz mehrere Fragmentierungen und 1. EINLEITUNG passt die Replikation den Überlappungen an. Das heißt, die Um große Datenmengen in verteilten Datenbanksystemen existierenden Ansätze zum Finden einer einzelnen horizon- zu speichern, werden diese normalerweise in kleinere Teil- talen Fragmentierung können mit unserem Ansatz kombi- mengen fragmentiert und dann auf mehrere Server verteilt. niert werden. Damit verbessern wir die Laufzeit für Be- Darüber hinaus werden, um bessere Verfügbarkeit und Feh- reichsabfragen durch Vermeiden unnötiger Vereinigungsope- lertoleranz zu garantieren, Kopien der Datensätze erstellt rationen. Zahlreiche Datenbanksysteme bieten zwar die au- und auf unterschiedlichen Servern gespeichert. Bisherige Ar- tomatische Fragmentierung an (so etwa der IBM DB2 Data- beiten zu diesem Thema konzentrieren sich meist nur auf ei- base Advisor [ZRL+ 04], der Vertica DBDesigner [VBC+ 14] ne einzelne optimale Fragmentierung der Daten. In unserem oder Oracles partitioning by reference [ECS+ 08]), jedoch un- Ansatz hingegen betrachten wir multiple Fragmentierungen, terstützen auch sie nur jeweils eine einzige Fragmentierung. um anschließend eine Replikation der Fragmente zu finden, Datenreplikation ist ein zentraler Aspekt in verteilten Da- die Überlappungen berücksichtigt und so die Anzahl der be- tenbanksystemen. Eine Übersicht über Optimierungsstrate- nötigten Server reduziert. Dies kann beispielsweise zur fle- gien und Forschungsfragen für Replikationsverfahren gibt es xiblen Anfragebeantwortung benutzt werden, was in [Wie14, in [KPX+ 11, SPTB14]. Keines dieser Verfahren betrachtet jedoch mehrere Fragmentierungen. Wir benutzen gemeinsa- me Teilfragmente, mit denen eine Fragmentierung aus einer anderen Fragmentierung wiederhergestellt werden kann. 1.2 Übersicht In Abschnitt 2 werden die Hintergründe zu Fragmentie- rung und Datenverteilung beschrieben. Darüber hinaus stel- 28th GI-Workshop on Foundations of Databases (Grundlagen von Daten- banken), 24.05.2015 - 27.05.2015, Nörten-Hardenberg, Germany. len wir das Replikationsproblem für eine einzelne Fragmen- Copyright is held by the author/owner(s). tierung vor. Anschließend erweitern wir in Abschnitt 3 das 33 Ein Replikationsschema für multiple Fragmentierungen mit überlappenden Fragmenten Ill PatientID Diagnosis 8457 Cough K X 2784 Flu min yk (1) 2784 Asthma k=1 2784 brokenLeg K 8765 Asthma X s.d. xik = 1 i = 1, . . . , n (2) 1055 brokenArm k=1 n X Table 1: Beispiel Krankheitstabelle wi xik ≤ W · yk k = 1, . . . , K (3) i=1 Replikationsproblem um multiple Fragmentierungen. Dabei yk ∈ {0, 1} k = 1, . . . , K (4) gehen wir zunächst auf den Fall ein, bei dem der Replikati- xik ∈ {0, 1} i = 1, . . . , n, k = 1, . . . , K (5) onsfaktor der Anzahl der Fragmentierungen entspricht, um In diesem ILP benutzen wir xik als Indikatorvariable, die dann den interessanteren Fall, bei dem die Anzahl der Frag- angibt, ob das Fragment fi dem Server k zugewiesen wird. mentierungen größer als der Replikationsfaktor ist, zu be- Die Bedingung (2) stellt dabei sicher, dass jedes Fragment handeln. Abschnitt 4 schließt den Artikel mit einer Zusam- genau einem Server zugewiesen wird. Hat yk den Wert 1, menfassung und Vorschlägen für zukünftige Arbeiten ab. so bedeutet dies, dass Server k benutzt wird, also mindes- tens ein Fragment darauf gespeichert wird. Durch Gleichung 2. HINTERGRUND (3) wird garantiert, dass die Kapazität der benutzten Server Zunächst werden hier kurz Vorarbeiten zu Fragmentie- nicht überschritten wird. Letztendlich wird in der Zielfunk- rung und Datenverteilung vorgestellt. Desweiteren geben wir tion (1) die Anzahl der belegten Server minimiert. Einblick in das Replikationsproblem für eine einzelne Frag- Das Behälterproblem mit Konflikten (BPPC) ist eine Er- mentierung. Als laufendes Beispiel werden wir im Folgenden weiterung des klassischen Behälterproblems. Dabei wird zu- ein Informationssystem eines Krankenhauses verwenden, bei sätzlich ein Konfliktgraph G = (V, E) betrachtet, bei dem dem die ID der Patienten zusammen mit deren Krankheit die Knoten V der Menge der Objekte entsprechen. In dem gespeichert wird (Tabelle 1). Graph existiert eine Kante (i, j), wenn die beiden Objekte i und j nicht in denselben Behälter gelegt werden dürfen. Um 2.1 Fragmentierung diese Bedingung einzuhalten kann das vorherige ganzzahlige Im Folgenden werden wir ein Datenreplikationsschema für lineare Problem um eine Bedingung erweitert werden: horizontale Fragmentierung vorstellen. Eine wichtige Eigen- xik + xjk ≤ yk k = 1, . . . , K, (6) schaft horizontaler Fragmentierungen ist die Korrektheit. Diese beinhaltet drei Eigenschaften: Da yk höchstens den Wert 1 hat, wird durch Bedingung (6) sichergestellt, dass nur entweder xik oder xjk den Wert 1 • Vollständigkeit: Jedes Tupel der ursprünglichen Daten- hat, falls die Kante (i, j) im Konfliktgraphen existiert und tabelle ist in einem Fragment enthalten. Behälter k benutzt wird. Soll der Behälter k hingegen leer bleiben, so ist yk gleich 0. In diesem Fall müssen auch xik • Rekonstruierbarkeit: Die Vereinigung aller Fragmente und xjk den Wert 0 annehmen. resultiert in der ursprünglichen Datentabelle. In dieser Arbeit werden wir diese Darstellung von (BPPC) • Redundanzfreiheit: Kein Tupel ist in zwei Fragmenten benutzen, um eine m-Kopien-Replikation für eine einzelne gleichzeitig enthalten. Fragmentierung, später aber auch für multiple Fragmentie- rungen, einer Tabelle zu verwirklichen. Wir werden im Folgenden Vollständigkeit und Redundanz- freiheit für unsere intelligente Replikation ausnutzen. 2.3 Replikation für eine Fragmentierung In [Wie15b] wird der Fall einer einzelnen Fragmentierung 2.2 Datenverteilung als Behälterproblem mit m-Kopien-Replikation betrachtet. Dies bedeutet, dass In verteilten Datenbanksystemen werden Datensätze auf für jedes Fragment jeweils m Kopien angelegt werden und verschiedenen Servern gespeichert. Das Datenverteilungspro- diese jeweils auf unterschiedliche Server verteilt werden müs- blem – ohne Replikation – kann daher als Behälterproblem sen. Formal kann das Datenreplikationsproblem mit m Ko- (bin packing problem, BPP) dargestellt werden: pien (m-copy-DRP) folgendermaßen definiert werden: • K Server entsprechen K Behältern Definition 1. Sei m der gewünschte Replikationsfaktor, sei F = {f1 , . . . , fn } eine korrekte Fragmentierung einer Ta- • Jeder Behälter besitzt eine maximale Kapazität W belle. Weiter seien F 1 , . . . , F m die Mengen der Kopien von F . Für jedes Fragment fi ∈ F ist eine Verteilung der m Ko- • n Datensätze entsprechen n Objekten pien fi1 ∈ F 1 , . . . , fim ∈ F m gesucht, sodass die Kopien alle auf unterschiedliche Server verteilt sind. • Jedes Objekt i besitzt ein Gewicht wi ≤ W Dieses Problem entspricht der Lösung eines BPPC Pro- • Die Objekte sollen auf eine minimale Anzahl von Be- blems, bei dem die Bedingungen, dass alle Kopien auf ver- hältern aufgeteilt werden, ohne die maximale Kapazi- schiedene Server verteilt werden, durch Kanten im Konflikt- tät W eines Behälters zu überschreiten graph dargestellt werden. Der Konfliktgraph hat folgende Sm l Form: Die Knotenmenge n  ist V = l=1 F und die Kanten-o BPP kann folgendermaßen als ganzzahliges lineares Pro- 0 gramm dargestellt werden: menge ist E = fil , fil |i = 1, . . . , n; l = 1, . . . , m; l0 < l . 34 Ein Replikationsschema für multiple Fragmentierungen mit überlappenden Fragmenten Respiratory PatientID Diagnosis Dabei argumentieren wir, dass m Kopien eines Tupels für 8457 Cough ein intelligentes Wiederherstellungsverfahren genügen: Je- 2784 Flu des Tupel j soll als Sicherungskopie auf m verschiedenen 2784 Asthma Servern gespeichert sein, diese Kopien dürfen sich jedoch in 8765 Asthma unterschiedlichen Fragmenten befinden. Das bedeutet, dass Fracture PatientID Diagnosis jede Fragmentierung F l aus den Fragmenten einer anderen 0 2784 brokenLeg Fragmentierung F l wiederhergestellt werden kann. 1055 brokenArm Wir unterscheiden im Folgenden drei Fälle: Zuerst neh- men wir an, dass die Anzahl der Fragmentierungen gleich der Table 2: Fragmentierung auf dem Attribut Diagnosis Anzahl der geforderten Kopien ist (r = m). Für den zwei- ten Fall, bei dem die Anzahl der Fragmentierungen kleiner IDlow PatientID Diagnosis als die Anzahl der Kopien ist (r < m), können einige der 2784 Flu Fragmentierungen einfach kopiert werden. Den interessan- 2784 brokenLeg teren Fall, dass die Zahl der Fragmentierungen größer als 2784 Asthma die Zahl der geforderten Kopien ist (r > m), werden wir 1055 brokenArm in einem weiteren Abschnitt behandeln. Zunächst geben wir IDhigh PatientID Diagnosis allerdings eine formale Definition für das Datenreplikations- 8765 Asthma problem mit überlappenden Fragmenten (overlap-DRP): 8457 Cough  Definition 2. Seien F l = f1l , . . . , fnl l für l = 1, . . . , r Table 3: Fragmentierung auf dem Attribut Pati- Fragmentierungen derselben Datentabelle und m der gefor- entID derte Replikationsfaktor. Für jedes Tupel j sind Fragmen- te fil mit 1 ≤ l ≤ m und 1 ≤ il ≤ nl gesucht, sodass j ∈ fi11 ∩ . . . ∩ fim und diese Fragmente müssen auf unter- 3. ÜBERLAPPUNGEN UND MULTIPLE m schiedliche Server verteilt werden. FRAGMENTIERUNGEN Wir werden diese Definition nun an dem Beispiel veran- In diesem Abschnitt werden wir dieses Replikationsschema schaulichen. Dazu nehmen wir an, dass die maximale Kapa- nun auf multiple Fragmentierungen erweitern. Dabei wird ei- zität W der Server 5 Tupel beträgt und setzen einen Repli- nerseits der Speicherbedarf durch eine intelligente Replikati- kationsfaktor 2 voraus. Desweiteren seien Fragmentierungen onsstrategie reduziert und somit die Anzahl der benötigten wie in den Tabellen 2 und 3 gegeben, was zu den Fragmen- Server minimiert und andererseits die Möglichkeit geschaf- ten Respiratory, Fracture, IDhigh, IDlow führt. Im m-copy- fen, durch unterschiedliche Fragmentierungen flexibel auf die Replikationsschema würde jedes Fragment jeweils auf zwei Bedürfnisse des Nutzers zu reagieren. Dies kann, wie bereits Servern gespeichert: Dafür werden mindestens 6 Server be- zuvor erwähnt, zur flexiblen Anfragebeantwortung verwen- nötigt. Mit unserem intelligenten Replikationsschema, das det werden, um mehrere verschiedene Relaxationsattribute Überlappungen von Fragmenten ausnutzt, können wir eine zuzulassen (siehe [Wie14, Wie15a, Wie15b]). Lösung konstruieren, die lediglich 3 Server benötigt: Formal betrachten wir r Fragmentierungen F 1 , . . . , F r der- selben Tabelle. Jede Fragmentierung F l (1 ≤ l ≤ r) be- • Zunächst speichern wir das Fragment Respiratory auf steht aus Fragmenten f1l , . . . , fnl l , wobei nl von der jeweili- Server S1. gen Fragmentierung abhängt. In unserem Beispiel könnte eine Fragmentierung darin be- • Anschließend legen wir das Fragment IDlow auf Server stehen, die Spalte Diagnosis in Atemwegserkrankungen und S2. Knochenbrüche zu unterteilen (Tabelle 2). Zusätzlich könnte man eine weitere Fragmentierung anhand der Spalte Pati- • Die Fragmente Fracture und IDhigh werden zusammen entID erstellen, bei der die IDs in Werte kleiner als 5000 auf Server S3 gespeichert. und Werte größer als 5000 unterteilt werden (Tabelle 3). Dadurch erhalten wir den Replikationsfaktor 2 für jedes Tu- 3.1 Datenreplikation für überlappende Frag- pel und können dennoch jedes Fragment aus den anderen mente zurückgewinnen: Wir stellen nun ein intelligentes Datenreplikationsschema • Fragment Respiratory kann aus den Fragmenten IDlow für multiple Fragmentierungen vor, bei dem die Anzahl der und IDhigh zurückgewonnen werden, denn Respiratory Kopien von Tupeln reduziert werden soll, um so den Ge- = (IDlow ∩ Respiratory) ∪ (IDhigh ∩ Respiratory) samtspeicherbedarf zu minimieren. Bei m-copy-DRP (Abschnitt 2.3) betrachteten wir ledig- • Fragment Fracture kann aus IDlow zurückgewonnen lich disjunkte Fragmente und jeweils m Kopien davon. Diese werden, denn Fracture = (IDlow ∩ Fracture) Annahmen werden nun folgendermaßen verändert: Fragmen- te verschiedener Fragmentierungen dürfen überlappen. Da- • Fragment IDlow kann aus Respiratory und Fracture her ist es im Allgemeinen nicht nötig, m Kopien jedes Frag- rekonstruiert werden, denn IDlow = (IDlow ∩ Respi- ments zu speichern, um jedes Tupel m mal zu replizieren. ratory) ∪ (IDlow ∩ Fracture) Daher schlagen wir, um den Speicherbedarf zu reduzieren, ein intelligentes Replikationsschema vor und fordern, dass • Fragment IDhigh kann aus dem Fragment Respirato- lediglich jedes Tupel m mal repliziert wird und nicht jedes ry zurückgewonnen werden, denn IDhigh = (IDhigh ∩ Fragment. Respiratory) 35 Ein Replikationsschema für multiple Fragmentierungen mit überlappenden Fragmenten Nun werden wir erarbeiten, wie overlap-DRP als erwei- f1 tupleID PatientID Diagnosis tertes BPPC Problem dargestellt werden kann und dazu 1 2784 brokenLeg ein ganzzahliges lineares Programm formulieren. Hierfür be- 2 2784 Flu zeichne J die Anzahl der Tupel der Eingabetabelle, m den 3 8765 Asthma Replikationsfaktor, K die Anzahl der zur Verfügung stehen- 4 8457 Cough den Server und n die Gesamtzahl aller Fragmente aller Frag- mentierungen. Dies führt zu folgendem ganzzahligen linea- Table 4: Fragmentierung auf dem tupleID Attribut ren Programm: auf m verschiedenen Servern gespeichert ist. Diese Beob- K X achtung führt zu folgender Vereinfachung des ganzzahligen min yk (7) linearen Programms: k=1 K X K X minimize yk (16) s.d. xik = 1 i = 1, . . . , n (8) k=1 k=1 K X n X wi xik ≤ W · yk k = 1, . . . , K (9) s.d. xik = 1 i = 1, . . . , n (17) k=1 i=1 n X zjk ≥ xik ∀j : j ∈ fi (10) wi xik ≤ W · yk k = 1, . . . , K (18) X zjk ≤ xik k = 1, . . . , K, j = 1, . . . , J (11) i=1 (i:j∈fi ) xik + xi0 k ≤ yk k = 1, . . . , K, fi ∩ fi0 6= ∅ (19) K X yk ∈ {0, 1} k = 1, . . . , K (20) zjk ≥ m j = 1, . . . , J (12) xik ∈ {0, 1} k = 1, . . . , K, i = 1, . . . , n (21) k=1 yk ∈ {0, 1} k = 1, . . . , K (13) Die Bezeichnungen in dieser Formulierung sind analog zu den vorherigen Formulierungen. Durch die Nebenbedingung xik ∈ {0, 1} k = 1, . . . , K, i = 1, . . . , n (14) (19) wird sichergestellt, dass der Replikationsfaktor m ein- zjk ∈ {0, 1} k = 1, . . . , K, j = 1, . . . , J (15) gehalten wird, da Fragmente, fi und fi0 , deren Schnittmen- ge nicht leer ist, auf unterschiedliche Server verteilt werden In dieser Formulierung verwenden wir die Variablen yk müssen. und xik wie in den vorherigen ILPs. Um die Notation zu vereinfachen benutzen wir i = 1, . . . , n, mit n = |F 1 | + . . . + 3.3 Optionale Konflikte |F m |, nummerieren also alle Fragmente nacheinander von 1 In diesem Abschnitt betrachten wir nun den komplizier- bis n, auch wenn sie aus unterschiedlichen Fragmentierun- teren Fall, bei dem die Anzahl der Fragmentierungen grö- gen stammen. Wir führen zusätzlich K Indikatorvariablen ßer als der geforderte Replikationsfaktor ist (r > m). In zjk für jedes Tupel j ein, mit zjk = 1, falls Tupel j auf diesem Fall müssen, um den Replikationsfaktor einzuhalten, Server k gespeichert wird. Mithilfe von Gleichung (10) er- für jedes Tupel j nur m der r Fragmente, die j beinhalten, reichen wir, dass wenn Fragment fi auf Server k gespeichert auf unterschiedliche Servern verteilt werden. Die restlichen ist und Tupel j in fi enthalten ist, die entsprechende Varia- r − m Fragmente können beliebig, auch auf den bereits be- ble zjk ebenfalls gleich 1 ist. Umgekehrt erreichen wir durch legten Servern, gespeichert werden, was dazu beiträgt, den Bedingung (11), dass wenn kein Fragment, das j enthält, Speicherbedarf zu verringern. auf Server k gespeichert wird, die Variable zjk den Wert 0 Wir werden dies an einem kleinen Beispiel illustrieren. An- annehmen muss. Durch die Nebenbedingung (12) erzwingen genommen wir haben eine Fragmentierung F , die nur das wir den Replikationsfaktor m für jedes Tupel j. Fragment f beinhaltet, eine Fragmentierung F 0 mit Frag- 3.2 Reduktion der Anzahl der Variablen menten f10 und f20 und eine dritte Fragmentierung F 00 mit den Fragmenten f100 und f200 . Dabei überlappt f1 mit allen an- Die Formulierung des ganzzahligen linearen Programms deren vier Fragmenten: f1 ∩ f10 6= ∅, f1 ∩ f20 6= ∅, f1 ∩ f100 6= ∅ im vorherigen Abschnitt ist aufgrund der vielen z-Variablen und f1 ∩ f200 6= ∅. Wir veranschaulichen diese Situation in höchst ineffizient für eine große Anzahl von Tupeln in einer einem leicht modifizierten Beispiel unseres Krankenhaussze- Tabelle. Daher wollen wir nun zeigen, dass es möglich ist, narios in den Tabellen 4, 5 und 6. Für f1 gibt es also 4 sich lediglich auf die x-Variablen zu konzentrieren. Konfliktbedingungen und es ist nicht klar, welche davon ein- Zunächst wird in diesem Abschnitt nur der Fall betrach- gehalten werden sollten, um einerseits 2-Kopien-Replikation tet, bei dem der Replikationsfaktor gleich der Anzahl der für jedes Tupel in f1 sicherzustellen und andererseits die An- Fragmentierungen ist (r = m), mit dem Fall r > m befassen zahl der Server zu minimieren. Betrachten wir das Beispiel wir uns anschließend im nächsten Abschnitt. nun mit konkreten Werten. Wir nehmen eine maximale Ka- Ist der Replikationsfaktor m gleich der Anzahl der Frag- pazität der Server von W = 6 an, das Gewicht von f1 ist mentierungen r, so dürfen Fragmente fi und fi0 nicht auf w1 = 4, die Gewichte von f10 und f20 sind w10 = w20 = 2, demselben Server gespeichert werden, falls fi ∩ fi0 6= ∅ (wir das Gewicht von f100 ist w100 = 1 und das Gewicht von f200 nehmen i < i0 an, um isomorphe Bedingungen zu vermei- ist gleich w200 = 3. Wir diskutieren nun einige Optionen, wie den). Ansonsten kann für alle Tupel j ∈ fi ∩ fi0 der Re- diese Fragmente verteilt werden könnten: plikationsfaktor nicht erreicht werden. Andererseits ist diese Bedingung auch hinreichend, denn aufgrund der r = m Frag- • Angenommen wir speichern f1 auf dem Server S1. Um mentierungen wird dadurch gewährleistet, dass jedes Tupel alle zuvor genannten Konfliktbedingungen einzuhal- 36 Ein Replikationsschema für multiple Fragmentierungen mit überlappenden Fragmenten f10 tupleID PatientID Diagnosis das gemeinsame Teilfragment {t1 } wieder auf, ergibt das die 1 2784 brokenLeg paarweisen Konfliktbedingungen: 2 2784 Flu f20 tupleID PatientID Diagnosis x1k + x01k ≤ 1 3 8765 Asthma x1k + x001k ≤ 1 4 8457 Cough x01k + x001k ≤ 1 Table 5: Fragmentierung auf dem PatientID Attri- Um 2-Kopien-Replikation zu garantieren, muss nur eine die- but ser Bedingungen erfüllt sein. Um dem gerecht zu werden f100 tupleID PatientID Diagnosis führen wir neue c-Indikatorvariablen für jede dieser Bedin- 1 2784 brokenLeg gungen ein: f200 tupleID PatientID Diagnosis x1k + x01k ≤ 1 + c1k 2 8457 Cough x1k + x001k ≤ 1 + c2k 3 2784 Flu 4 8765 Asthma x01k + x001k ≤ 1 + c3k Table 6: Fragmentierung auf dem Diagnosis Attribut Diese Variablen haben die folgende Bedeutung: Sind die c- Variablen gleich 0, dann ist die Konfliktbedingung erfüllt und die beiden Fragmente werden nicht zusammen auf dem- ten, müssen f10 und f20 auf einen zweiten Server S2 selben Server k gespeichert. Ist die c-Variable hingegen gleich gelegt werden und f100 und f200 müssen auf einem drit- 1, ist die Konfliktbedingung nicht erfüllt und die beiden ten Server gespeichert werden. Dies resultiert also in Fragmente können zusammen auf Server k gespeichert wer- einer 3-Kopien-Replikation. den. Um die m-Kopien-Replikation zu erzwingen fordern wir, dass die Summe der c-Variablen höchstens r − m ist, • Angenommen wir fordern lediglich 2-Kopien- was praktisch bedeutet, dass höchstens r − m Bedingungen Replikation. Wir können also versuchen, manche der verletzt werden dürfen und mindestens m Bedingungen er- überlappenden Fragmente auf demselben Server zu spei- füllt werden. In unserem Beispiel führt dies zur Bedingung chern, so lange die Replikationsbedingung erfüllt ist. c1k + c2k + c3k ≤ 1. Dieses Konzept wenden wir nun für Legen wir f1 und f100 auf einen Server S1, so passen f10 beliebige Werte von r und m mit r > m an: und f200 auf einen zweiten Server S2. Fragment f20 muss K X dann auf einem dritten Server S3 gespeichert werden. Wir erzielen also 2-Kopien-Replikation für alle Tupel, min yk (22) benötigen aber dennoch weiterhin drei Server. k=1 K X • Tatsächlich ist es aber auch möglich, die benötigte An- s.d. xlik = 1 i = 1, . . . , nl , (23) zahl der Server auf zwei zu reduzieren, aber dennoch k=1 2-Kopien-Replikation zu erzielen. Hierfür speichern wir l = 1, . . . , r f1 und f10 auf einem Server S1. Auf einem zweiten Ser- n X r X ver S2 ist nun ausreichend Speicherplatz für die rest- wil xlik ≤ W · yk k = 1, . . . , K (24) lichen Fragmente f100 , f20 und f200 vorhanden. i=1 l=1 0 Aus diesem Beispiel wird deutlich, dass die Entscheidung, xli1 k + xli2 k ≤ 1 + csll0 k k = 1, . . . , K, (25) welche Konfliktbedingungen eingehalten werden sollen und l = 1, . . . , r, welche optional sind, sehr schwer ist. Im Folgenden wird nun die Frage beantwortet, wie diese optionalen Konfliktbedin- 0 < l0 < l, 0 gungen in unser ganzzahliges lineares Programm integriert fil2 k ∩ fil1 k ∩ gs 6= ∅, werden können. s = 1, . . . , S Formal gesehen  betrachten wir wiederum r Fragmentie- r X rungen F l = f1l , . . . , fnl l und für jedes Tupel j gibt es csll0 k ≤ r − m k = 1, . . . , K, (26) Fragmente fill für 1 ≤ l ≤ r und 1 ≤ il ≤ nl , sodass l=1 j ∈ fi11 ∩ . . . ∩ firr . Sind fi11 , . . . , firr , Fragmente aus den r 0 m eine zusätzlich Schwierigkeit (über das BPPC) Engineering (ICDE), 2014 IEEE 30th darin liegt, die Überlappungen (nicht-leeren Schnittmengen) International Conference on, pages 1084–1095. zwischen den Fragmenten zu finden. IEEE, 2014. In zukünftigen Arbeiten sollten vor Allem dynamische Ver- [Wie14] Lena Wiese. Clustering-based fragmentation änderungen im Replikationsschema untersucht werden. Hin- and data replication for flexible query zufügen und Entfernen von Daten führt zu Veränderungen answering in distributed databases. Journal of der Größen der Fragmente und daher könnte eine Umvertei- Cloud Computing, 3(1):1–15, 2014. lung der Daten auf den Servern notwendig werden. Zudem beschreiben die Autoren von C-Store [?] die Mög- [Wie15a] Lena Wiese. Horizontal fragmentation and lichkeit verschiedene Projektionen (also vertikale Fragmen- replication for multiple relaxation attributes. In te) in verschiedene Segmente (horizontale Fragmente) auf- Data Science (30th British International zuteilen ohne jedoch ein genaues Verteilungsverfahren anzu- Conference on Databases), pages 157–169. geben. Eine solche Form der hybriden Fragmentierung als Springer, 2015. ILP darzustellen ist eine weitere zukünftige Fragestellung. [Wie15b] Lena Wiese. Ontology-driven data partitioning and recovery for flexible query answering. In Database and Expert Systems Applications, 5. REFERENCES pages 177–191. Springer, 2015. [BK15] Ladjel Bellatreche and Amira Kerkad. Query [ZRL+ 04] Daniel C Zilio, Jun Rao, Sam Lightstone, Guy interaction based approach for horizontal data Lohman, Adam Storm, Christian partitioning. International Journal of Data Garcia-Arellano, and Scott Fadden. Db2 design Warehousing and Mining (IJDWM), advisor: integrated automatic physical database 11(2):44–61, 2015. design. In Proceedings of the Thirtieth international conference on Very large data [CZJM10] Carlo Curino, Yang Zhang, Evan P. C. Jones, bases-Volume 30, pages 1087–1097. VLDB and Samuel Madden. Schism: a workload-driven Endowment, 2004. approach to database replication and partitioning. Proceedings of the VLDB Endowment, 3(1):48–57, 2010. [ECS+ 08] George Eadon, Eugene Inseok Chong, Shrikanth Shankar, Ananth Raghavan, Jagannathan Srinivasan, and Souripriya Das. Supporting table partitioning by reference in oracle. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 1111–1122. ACM, 2008. 38