=Paper= {{Paper |id=Vol-1594/paper7 |storemode=property |title=Ein Replikationsschema für multiple Fragmentierungen mit überlappenden Fragmenten |pdfUrl=https://ceur-ws.org/Vol-1594/paper7.pdf |volume=Vol-1594 |authors=Ferdinand Bollwein,Lena Wiese |dblpUrl=https://dblp.org/rec/conf/gvd/BollweinW16 }} ==Ein Replikationsschema für multiple Fragmentierungen mit überlappenden Fragmenten== https://ceur-ws.org/Vol-1594/paper7.pdf

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 fü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 unterstützt. Solche multiplen kationsfaktor zulassen (r > m), sodass einige Replikations-
Fragmentierungen können beispielsweise fü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 Überschneidungen von Frag- Fragmentierung relationaler Tabellen ist ein seit langer
menten, die aus unterschiedlichen Fragmentierungen entste- Zeit untersuchtes Problem und Teil von Standardlehrbü-
hen, berücksichtigt werden, um so die Anzahl der benötig- chern wie [ÖV11]. Einige Ansätze setzen vertikale Fragmen-
ten Server zu reduzieren. Wir betrachten insbesondere den tierung um und betrachten Affinität von Attributen (in-
Fall, bei dem mehr Fragmentierungen als der gewünschte nerhalb einer vorgegebenen Menge von Anfragen) als Op-
Replikationsfaktor existieren, sodass nur ein Teil der Repli- timierungsmerkmal. Eine vergleichende Evaluation mehre-
kationsbedingungen notwendigerweise erfüllt werden müssen rer Ansätze zur vertikalen Fragmentierung findet sich in
und die restlichen optional sind. [JPPD13]. Im Gegensatz zu diesen Ansätzen setzen wir auf
horizontale Fragmentierung für große Datensätze. Mit Be-
zug auf horizontale Fragmentierung wird üblicherweise ei-
Keywords ne einzige optimale Fragmentierung gesucht. Beispiele da-
Behälterproblem mit Konflikten (BPPC), Datenreplikations- für sind [BK15] für Multiple Query Optimization (MQO),
problem (DRP), Fragmentierung, Verteilte Datenbanksyste- [CZJM10] zur Partitionierung anhand eines Graphen über
me, Ganzzahlige lineare Optimierung einer Menge von Anfragen oder [TPRH16] zur Reduzierung
von Abhängigkeiten zwischen Partitionen. Im Gegensatz da-
zu toleriert unser Ansatz mehrere Fragmentierungen und
1. EINLEITUNG passt die Replikation den Überlappungen an. Das heißt, die
Um große Datenmengen in verteilten Datenbanksystemen existierenden Ansätze zum Finden einer einzelnen horizon-
zu speichern, werden diese normalerweise in kleinere Teil- talen Fragmentierung können mit unserem Ansatz kombi-
mengen fragmentiert und dann auf mehrere Server verteilt. niert werden. Damit verbessern wir die Laufzeit für Be-
Darüber hinaus werden, um bessere Verfügbarkeit und Feh- reichsabfragen durch Vermeiden unnötiger Vereinigungsope-
lertoleranz zu garantieren, Kopien der Datensä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, terstü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 Überlappungen berücksichtigt und so die Anzahl der be- tenbanksystemen. Eine Übersicht über Optimierungsstrate-
nötigten Server reduziert. Dies kann beispielsweise zur fle- gien und Forschungsfragen fü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 Hintergründe zu Fragmentie-
rung und Datenverteilung beschrieben. Darü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 fü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 für multiple Fragmentierungen mit ü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 zunä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 größ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 Vorschlägen für zukü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 Kapazität der benutzten Server
Zunächst werden hier kurz Vorarbeiten zu Fragmentie- nicht ü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 für eine einzelne Frag- Das Behälterproblem mit Konflikten (BPPC) ist eine Er-
mentierung. Als laufendes Beispiel werden wir im Folgenden weiterung des klassischen Behälterproblems. Dabei wird zu-
ein Informationssystem eines Krankenhauses verwenden, bei sä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 Behälter gelegt werden dürfen. Um
2.1 Fragmentierung diese Bedingung einzuhalten kann das vorherige ganzzahlige
Im Folgenden werden wir ein Datenreplikationsschema fü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 höchstens den Wert 1 hat, wird durch Bedingung (6)
sichergestellt, dass nur entweder xik oder xjk den Wert 1
• Vollständigkeit: Jedes Tupel der ursprünglichen Daten- hat, falls die Kante (i, j) im Konfliktgraphen existiert und
tabelle ist in einem Fragment enthalten. Behälter k benutzt wird. Soll der Behälter k hingegen leer
bleiben, so ist yk gleich 0. In diesem Fall müssen auch xik
• Rekonstruierbarkeit: Die Vereinigung aller Fragmente und xjk den Wert 0 annehmen.
resultiert in der ursprünglichen Datentabelle. In dieser Arbeit werden wir diese Darstellung von (BPPC)
• Redundanzfreiheit: Kein Tupel ist in zwei Fragmenten benutzen, um eine m-Kopien-Replikation für eine einzelne
gleichzeitig enthalten. Fragmentierung, später aber auch für multiple Fragmentie-
rungen, einer Tabelle zu verwirklichen.
Wir werden im Folgenden Vollständigkeit und Redundanz-
freiheit fü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 Datensätze auf für jedes Fragment jeweils m Kopien angelegt werden und
verschiedenen Servern gespeichert. Das Datenverteilungspro- diese jeweils auf unterschiedliche Server verteilt werden müs-
blem – ohne Replikation – kann daher als Behä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 Behältern Definition 1. Sei m der gewünschte Replikationsfaktor,
sei F = {f1 , . . . , fn } eine korrekte Fragmentierung einer Ta-
• Jeder Behälter besitzt eine maximale Kapazität W belle. Weiter seien F 1 , . . . , F m die Mengen der Kopien von
F . Für jedes Fragment fi ∈ F ist eine Verteilung der m Ko-
• n Datensä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 Lösung eines BPPC Pro-
• Die Objekte sollen auf eine minimale Anzahl von Be- blems, bei dem die Bedingungen, dass alle Kopien auf ver-
hältern aufgeteilt werden, ohne die maximale Kapazi- schiedene Server verteilt werden, durch Kanten im Konflikt-
tät W eines Behälters zu ü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 für multiple Fragmentierungen mit überlappenden Fragmenten

Respiratory PatientID Diagnosis Dabei argumentieren wir, dass m Kopien eines Tupels für
8457 Cough ein intelligentes Wiederherstellungsverfahren genügen: Je-
2784 Flu des Tupel j soll als Sicherungskopie auf m verschiedenen
2784 Asthma Servern gespeichert sein, diese Kopien dü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 Fä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). Für den zwei-
ten Fall, bei dem die Anzahl der Fragmentierungen kleiner
IDlow PatientID Diagnosis als die Anzahl der Kopien ist (r < m), können einige der
2784 Flu Fragmentierungen einfach kopiert werden. Den interessan-
2784 brokenLeg teren Fall, dass die Zahl der Fragmentierungen größer als
2784 Asthma die Zahl der geforderten Kopien ist (r > m), werden wir
1055 brokenArm in einem weiteren Abschnitt behandeln. Zunächst geben wir
IDhigh PatientID Diagnosis allerdings eine formale Definition für das Datenreplikations-
8765 Asthma problem mit überlappenden Fragmenten (overlap-DRP):
8457 Cough
Definition 2. Seien F l = f1l , . . . , fnl l für l = 1, . . . , r
Table 3: Fragmentierung auf dem Attribut Pati- Fragmentierungen derselben Datentabelle und m der gefor-
entID derte Replikationsfaktor. Für jedes Tupel j sind Fragmen-
te fil mit 1 ≤ l ≤ m und 1 ≤ il ≤ nl gesucht, sodass
j ∈ fi11 ∩ . . . ∩ fim und diese Fragmente mü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- zität W der Server 5 Tupel beträ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 benötigten wie in den Tabellen 2 und 3 gegeben, was zu den Fragmen-
Server minimiert und andererseits die Möglichkeit geschaf- ten Respiratory, Fracture, IDhigh, IDlow führt. Im m-copy-
fen, durch unterschiedliche Fragmentierungen flexibel auf die Replikationsschema würde jedes Fragment jeweils auf zwei
Bedürfnisse des Nutzers zu reagieren. Dies kann, wie bereits Servern gespeichert: Dafür werden mindestens 6 Server be-
zuvor erwähnt, zur flexiblen Anfragebeantwortung verwen- nötigt. Mit unserem intelligenten Replikationsschema, das
det werden, um mehrere verschiedene Relaxationsattribute Überlappungen von Fragmenten ausnutzt, können wir eine
zuzulassen (siehe [Wie14, Wie15a, Wie15b]). Lösung konstruieren, die lediglich 3 Server benötigt:
Formal betrachten wir r Fragmentierungen F 1 , . . . , F r der-
selben Tabelle. Jede Fragmentierung F l (1 ≤ l ≤ r) be- • Zunächst speichern wir das Fragment Respiratory auf
steht aus Fragmenten f1l , . . . , fnl l , wobei nl von der jeweili- Server S1.
gen Fragmentierung abhängt.
In unserem Beispiel könnte eine Fragmentierung darin be- • Anschließend legen wir das Fragment IDlow auf Server
stehen, die Spalte Diagnosis in Atemwegserkrankungen und S2.
Knochenbrüche zu unterteilen (Tabelle 2). Zusätzlich kö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 größer als 5000 unterteilt werden (Tabelle 3).
Dadurch erhalten wir den Replikationsfaktor 2 für jedes Tu-
3.1 Datenreplikation für überlappende Frag- pel und können dennoch jedes Fragment aus den anderen
mente zurückgewinnen:
Wir stellen nun ein intelligentes Datenreplikationsschema • Fragment Respiratory kann aus den Fragmenten IDlow
für multiple Fragmentierungen vor, bei dem die Anzahl der und IDhigh zurü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 zurückgewonnen
lich disjunkte Fragmente und jeweils m Kopien davon. Diese werden, denn Fracture = (IDlow ∩ Fracture)
Annahmen werden nun folgendermaßen verändert: Fragmen-
te verschiedener Fragmentierungen dürfen überlappen. Da- • Fragment IDlow kann aus Respiratory und Fracture
her ist es im Allgemeinen nicht nö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 zurückgewonnen werden, denn IDhigh = (IDhigh ∩
Fragment. Respiratory)

35
Ein Replikationsschema für multiple Fragmentierungen mit ü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. Hierfür be- 2 2784 Flu
zeichne J die Anzahl der Tupel der Eingabetabelle, m den 3 8765 Asthma
Replikationsfaktor, K die Anzahl der zur Verfügung stehen- 4 8457 Cough
den Server und n die Gesamtzahl aller Fragmente aller Frag-
mentierungen. Dies fü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 fü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
mü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 grö-
gen stammen. Wir führen zusätzlich K Indikatorvariablen ßer als der geforderte Replikationsfaktor ist (r > m). In
zjk für jedes Tupel j ein, mit zjk = 1, falls Tupel j auf diesem Fall müssen, um den Replikationsfaktor einzuhalten,
Server k gespeichert wird. Mithilfe von Gleichung (10) er- fü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 können beliebig, auch auf den bereits be-
ble zjk ebenfalls gleich 1 ist. Umgekehrt erreichen wir durch legten Servern, gespeichert werden, was dazu beiträgt, den
Bedingung (11), dass wenn kein Fragment, das j enthä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 fü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 ü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
höchst ineffizient für eine große Anzahl von Tupeln in einer einem leicht modifizierten Beispiel unseres Krankenhaussze-
Tabelle. Daher wollen wir nun zeigen, dass es möglich ist, narios in den Tabellen 4, 5 und 6. Für f1 gibt es also 4
sich lediglich auf die x-Variablen zu konzentrieren. Konfliktbedingungen und es ist nicht klar, welche davon ein-
Zunä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 fü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 nächsten Abschnitt. nun mit konkreten Werten. Wir nehmen eine maximale Ka-
Ist der Replikationsfaktor m gleich der Anzahl der Frag- pazität der Server von W = 6 an, das Gewicht von f1 ist
mentierungen r, so dü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 für alle Tupel j ∈ fi ∩ fi0 der Re- diese Fragmente verteilt werden kö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 gewährleistet, dass jedes Tupel alle zuvor genannten Konfliktbedingungen einzuhal-

36
Ein Replikationsschema für multiple Fragmentierungen mit ü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 erfüllt sein. Um dem gerecht zu werden
f100 tupleID PatientID Diagnosis führen wir neue c-Indikatorvariablen fü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 erfüllt
und die beiden Fragmente werden nicht zusammen auf dem-
ten, mü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 müssen auf einem drit- 1, ist die Konfliktbedingung nicht erfüllt und die beiden
ten Server gespeichert werden. Dies resultiert also in Fragmente kö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 höchstens r − m ist,
• Angenommen wir fordern lediglich 2-Kopien- was praktisch bedeutet, dass höchstens r − m Bedingungen
Replikation. Wir können also versuchen, manche der verletzt werden dürfen und mindestens m Bedingungen er-
überlappenden Fragmente auf demselben Server zu spei- füllt werden. In unserem Beispiel führt dies zur Bedingung
chern, so lange die Replikationsbedingung erfüllt ist. c1k + c2k + c3k ≤ 1. Dieses Konzept wenden wir nun fü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 für alle Tupel, min yk (22)
benötigen aber dennoch weiterhin drei Server. k=1
K
X
• Tatsächlich ist es aber auch möglich, die benö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. Hierfü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 fü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 können.
s = 1, . . . , S
Formal gesehen betrachten wir wiederum r Fragmentie- r
X
rungen F l = f1l , . . . , fnl l und für jedes Tupel j gibt es
csll0 k ≤ r − m k = 1, . . . , K, (26)
Fragmente fill für 1 ≤ l ≤ r und 1 ≤ il ≤ nl , sodass l=1
j ∈ fi11 ∩ . . . ∩ firr . Sind fi11 , . . . , firr , Fragmente aus den r 0 m eine zusätzlich Schwierigkeit (über das BPPC)
Engineering (ICDE), 2014 IEEE 30th
darin liegt, die Überlappungen (nicht-leeren Schnittmengen)
International Conference on, pages 1084–1095.
zwischen den Fragmenten zu finden.
IEEE, 2014.
In zukünftigen Arbeiten sollten vor Allem dynamische Ver-
[Wie14] Lena Wiese. Clustering-based fragmentation
änderungen im Replikationsschema untersucht werden. Hin-
and data replication for flexible query
zufügen und Entfernen von Daten führt zu Veränderungen
answering in distributed databases. Journal of
der Größen der Fragmente und daher kö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 Mö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 zukü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.