=Paper= {{Paper |id=Vol-1366/paper4.pdf |storemode=property |title=Ontologie-basierte Fragmentierungs- und Replikationsverfahren für verteilte Datenbanksysteme |pdfUrl=https://ceur-ws.org/Vol-1366/paper4.pdf |volume=Vol-1366 |dblpUrl=https://dblp.org/rec/conf/gvd/Wiese15 }} ==Ontologie-basierte Fragmentierungs- und Replikationsverfahren für verteilte Datenbanksysteme== https://ceur-ws.org/Vol-1366/paper4.pdf

Ontologie-basierte Fragmentierungs- und
Replikationsverfahren für verteilte Datenbanksysteme

Lena Wiese
Forschungsgruppe Knowledge Engineering
Institut für Informatik
Georg-August-Universität Göttingen
wiese@cs.uni-goettingen.de

ABSTRACT Verfahren zur Ontologie-basierten Fragmentierung und zur
Das Auffinden von semantisch verwandten Daten in großen intelligenten Replikation vor, womit folgende Eigenschaften
Datenmengen ist aufwändig und daher zur Laufzeit einer sichergestellt werden:
Anfrage nur schwierig durchzuführen. In diesem Artikel stel- • durch die Fragmentierung wird ein Verfahren der fle-
len wir ein Verfahren vor, dass Datentabellen anhand einer xiblen Anfragebeantwortung unterstützt, die dem An-
Ontologie in semantisch zusammenhängende Cluster auf- frager auch relevante verwandte Werte als Antworten
teilt. Dadurch ergibt sich eine Ontologie-basierte Fragmen- zurückliefert.
tierung der Tabelle, die eine flexible Anfragebeantwortung
unterstützt. Bei mehreren derartigen Fragmentierungen über- • durch die Fragmentierung wird eine Lastverteilung auf
schneiden sich Fragmente; dies wird für ein intelligentes Re- mehrere Server möglich.
plikationsverfahren ausgenutzt, um die Anzahl der Replika-
server zu reduzieren. • durch die Fragmentierung wird die Anzahl der kontak-
tierten Server pro Anfrage reduziert und damit eine
bessere Parallelisierung möglich.
Keywords
Verteiltes Datenbanksystem, Replikation, Ontologie, Frag- • durch die intelligente Replikation wird die Anzahl der
mentierung, flexible Anfragebeantwortung benötigten Replikaserver reduziert.

1. EINLEITUNG 1.1 Übersicht
Abschnitt 2 beschreibt den Hintergrund zu flexibler Anfra-
Die Verwaltung von großen Datenmengen in Datenbanken
gebeantwortung, Fragmentierung und Datenverteilung. Ab-
erfordert die Verteilung der Daten auf mehrere Datenbank-
schnitt 3 stellt die Ontologie-basierte Fragmentierung inklu-
Server. Dies bietet mehrere Vorteile:
sive Clustering, Fragmentverteilung und Anfragebeantwor-
• Lastverteilung: Datenbankanfragen können auf mehre- tung vor. Abschnitt 4 beschreibt darauf aufbauend ein Repli-
re Server verteilt und damit parallelisiert werden. kationsverfahren mit überlappenden Fragmenten. Ein Wie-
derherstellungsverfahren anhand des Replikationsverfahrens
• Verfügbarkeit: Durch die Lastverteilung erhöht sich die wird in Abschnitt 5 dargestellt. Es folgt ein Verfahren für
Verfügbarkeit des Gesamtsystems, da einzelne Anfra- abgeleitete Fragmentierungen in Abschnitt 6 und abschlie-
gen seltener verzögert werden müssen. ßend eine Zusammenfassung in Abschnitt 7.
Ein geeignetes Verfahren zur Fragmentierung (auch: Par-
titionierung oder Sharding) der Daten in Teilmengen ist 2. HINTERGRUND
daher notwendig. Die gängigen Fragmentierungsverfahren Wir stellen hier kurz Vorarbeiten zu flexibler Anfragebe-
(Round-Robin, Hash-basiert, Intervall-basiert) ignorieren je- antwortung, Fragmentierung und Datenverteilung vor.
doch semantische Zusammenhänge der Daten.
Aus Gründen der Ausfallsicherheit ist zusätzlich noch die 2.1 Flexible Anfragebeantwortung
Replikation von Daten (also die Spiegelung desselben Da- Flexible Anfragebeantwortung ist ein intelligentes Verfah-
tensatzes auf mehreren Servern) erforderlich. Dies gilt insbe- ren, um Datenbanknutzern Antworten zu liefern, die zwar
sondere für Hauptspeicherdatenbanken, die nicht über einen nicht exakt der Anfrage entsprechen, die jedoch dennoch in-
Hintergrundspeicher verfügen. In dieser Arbeit stellen wir teressante Informationen für den Benutzer darstellen. Dabei
gibt es syntaktische und semantische Ansätze.
Zum einen gibt es syntaktische Änderungen, die Teile der
Anfrage verändern. Dazu zählen [Mic83]:
• Dropping Conditions: Selektionsbedingungen werden
aus der Originalanfrage entfernt.
• Goal Replacement: einige Bedingungen der Originalan-
27th GI-Workshop on Foundations of Databases (Grundlagen von Daten-
banken), 26.05.2015 - 29.05.2015, Magdeburg, Germany. frage werden anhand einer Ableitungsregel durch an-
Copyright is held by the author/owner(s). dere Bedingungen ersetzt.

12
• Anti-Instantiation: Ein Term (eine Variable mit meh- • Redundanzfreiheit: Um Duplizieren von Daten zu ver-
reren Vorkommen oder eine Konstante) wird durch ei- meiden, sollen einzelne Datensätze nur einem Frag-
ne neue Variable ersetzt. ment zugewiesen werden. Bei vertikaler Fragmentie-
Diese Operatoren können auch kombiniert werden [IW11]. rung ist jede Spalte nur in einem Fragment enthalten
Diese syntaktischen Änderungen können aber zu weit ge- (abgesehen vom Tupel-Identifikator). Bei horizontaler
hen und zu viele Antworten produzieren – insbesondere beim Fragmentierung ist jede Zeile in nur einem Fragment
Ersetzen von Konstanten durch neue Variablen in der Anti- enthalten.
Instantiation. Daher ist es wichtig, dass die Werte, die der In anderen, nicht-relationalen Datenmodellen (Schlüssel-
neuen Variable zugewiesen werden können, beschränkt wer- Wert-Speicher, Dokumentdatenbanken oder Spaltenfamili-
den: es sollen nur semantisch äquivalente oder semantisch endatenbanken) gibt es Fragmentierung meist über den Zu-
nah verwandte Werte zugelassen werden. Diese semantische griffsschlüssel entweder Hash-basiert [KLL+ 97] oder basie-
Ähnlichkeit kann anhand einer Ontologie oder Taxonomie rend auf Intervallen. Jedoch unterstützt keines dieser Ver-
von Werten bestimmt werden. Für Einzelrechner wurden fahren die flexible Anfragebeantwortung; im Gegensatz dazu
bereits vor einiger Zeit Verfahren vorgeschlagen – ohne je- hat das im Folgenden vorgestellte Fragmentierungsverfahren
doch verteilte Datenspeicherung mit einzubeziehen. CoBase den Vorteil, dass eine relaxierte Bedingung aus nur einem
[CYC+ 96] und [SHL07] zum Beispiel benutzten sogenannte Fragment beantwortet werden kann.
Abstraktionshierarchien, um einzelne Werte zu generalisie-
ren. Auch für XML-Anfragen wurden Verfahren entwickelt 2.3 Datenverteilung
[HTGC10]. In einem verteilten Datenbanksystem müssen Daten auf
Ein grundlegendes Problem ist dabei jedoch, dass die Be- die verschiedenen Server verteilt werden. Wichtige Eigen-
stimmung von ähnlichen Werten zur Laufzeit (während der schaften sind
Anfragebeantwortung) viel zu ineffizient ist [BDIW14]. Die-
ses Problem wird durch das hier vorgestellte Fragmentie- • Datenlokalität: Daten, auf die innerhalb einer Anfra-
rungsverfahren gelöst. ge oder Transaktion zugegriffen wird, sollten möglichst
auf einem Server sein. Dadurch verringert sich die An-
2.2 Fragmentierung zahl der kontaktierten Server und somit auch die Dauer
Im relationalen Modell gibt es die Theorie der Datenfrag- der Anfragebeantwortung. Außerdem kann so die Par-
mentierung, die sich aufgrund des strikten Tabellenformats allelisierung der Anfragebeantwortung verbessert wer-
aufteilen lässt in horizontale und vertikale Fragmentierung den, da die anderen Server neue Anfragen annehmen
(siehe zum Beispiel [ÖV11]): können.
• Vertikale Fragmentierung: Fragmente entsprechen Teil- • Lastverteilung: Daten sollen so verteilt werden, dass
mengen von Attributen (also Tabellenspalten). Die Ein- parallele Anfragen möglichst auch von verschiedenen
träge in den Fragmenten, die zur selben Tabellenzeile Servern beantwortet werden können, damit nicht ein-
gehören, müssen durch einen Tuple-Identifikator ver- zelne Server unter Lastspitzen ( hot spots“) leiden.
bunden werden. Vertikale Fragmentierung entspricht ”
einer Projektion auf der Tabelle. Einige Arbeiten befassen sich mit horizontaler Fragmentie-
rung und Verteilung; jedoch unterstützen diese nur exakte
• Horizontale Fragmentierung: Fragmente sind Teilmen- Anfragebeantwortung und keine flexible Anfragebeantwor-
gen von Tupeln (also Tabellenzeilen). Eine horizontale tung wie in unserem Ansatz. Die meisten Ansätze gehen von
Fragmentierung entspricht einer Selektion auf der Ta- einer vorgebenen Menge von Anfragen oder Transaktionen
belle. aus ( workload“) und optimieren die Lokalität der Daten, die
”
innerhalb der Anfrage beziehungsweise Transaktion benötigt
• Abgeleitete Fragmentierung: Eine bereits bestehende
werden. Dies ist für die Anwendung der flexiblen Anfrage-
primäre“ horizontale Fragmenation of einer Tabelle
” beantwortung jedoch nicht anwendbar, da hier auch Werte
induziert eine horizontale Fragmentierung einer wei-
zurückgegeben werden, die nicht explizit in einer Anfrage
teren Tabelle; dazu wird der Semi-JOIN auf beiden
auftauchen.
Tabellen ausgeführt.
[CZJM10] stellen Tupel als Knoten eines Graphen dar.
Drei grundlegende Eigenschaften sind wichtig für Fragmen- Für eine vorgegebene Menge von Transaktionen fügen sie
tierungen: Hyperkanten in den Graph ein, wenn die Tupel in dersel-
ben Transaktion benötigt werden. Mit einem Graphpartitio-
• Vollständigkeit: Keine Daten dürfen während der Frag-
nierungsalgorithmus wird dann eine Datenfragmentierung
mentierung verloren gehen. Bei vertikaler Fragmentie-
ermittelt, die Zahl der zerschnittenen Kanten minimiert.
rung ist jede Spalte in einem Fragment enthalten; bei
In einer zweiten Phase benutzen die Autoren einen Klas-
horizontaler Fragmentierung ist jede Zeile in einem
sifizierer aus dem Maschinellen Lernen, der eine Intervall-
Fragment enthalten.
basierte Fragmentierung herleitet. Experimentell vergleichen
• Rekonstruierbarkeit: Daten aus den Fragmenten kön- sie dann das Graph-basierten mit Intervall-basierten und
nen wieder zur Originaltabelle zusammengefügt wer- Hash-basierten Verfahren. Im Gegensatz zu unserem Ansatz
den. Bei vertikaler Fragmentierung wird der JOIN- wenden sie jedoch volle Replikation an, bei der alle Server
Operator benutzt (basierend auf einem zusätzlich ein- alle Daten vorhalten; dies ist wenig realistisch in großen ver-
gefügten Tupel-Identifikator), um die Spalten zu ver- teilten Systemen. Zudem vergleichen sie drei verschiedene
binden. Bei horizontaler Fragmentierung wird der Ver- Arten von Lookup-Tabellen, die Tupel-Identifikatoren für je-
einigungsoperator zum Zusammenführen der Fragmen- des Fragment abspeichern: Indexe, Bitarrays und Bloomfil-
te verwendet. ter. Bei der Analyse unseres Systems stellt sich jedoch her-

13
aus, dass Lookup-Tabellen ineffizienter sind als das Einfüh- Fragment 1:
cough,
ren einer zusätzlichen Spalte mit der Cluster-ID in anderen bronchitis, Table column:
Fragmentierungen. query
asthma cough,
rewrite & cluster & brokenLeg,
Auch [QKD13] modellieren das Fragmentierungsproblem fragment
user redirect bronchitis,
durch Minimierung zerschnittener Hyperkanten in einem Gra- brokenArm,
Fragment 2:
phen. Zur Verbesserung der Effizienz komprimieren sie den brokenLeg,
asthma
Graphen und erhalten so Gruppen von Tupeln. Die Autoren brokenArm
kritisieren dabei auch den tupelweisen Ansatz von [CZJM10]
als unpraktisch für große Tupelmengen. Die Autoren verglei-
Figure 1: Fragmentation and query rewriting
chen ihren Ansatz mit zufälligen und tupelweisen Fragmen-
tierungen und betrachten auch Änderungen der vorgegebe-
Diseases
nen Transaktionen.
[TCJM12] gehen von drei existierenden Fragmentierungen Disease,
Injuries Wound
aus: Hash-basiert, Intervall-basiert und Lookup-Tabellen auf Respiratory Tract
einzelnen Zugriffsschlüsseln. Sie vergleichen diese drei be- Disorder, Diseases, Respiratory
züglich Kommunikationskosten und Anfragendurchsatz. Zur Fracture
Respiration Bronchial Tract Infections
Effiziensteigerung analysieren sie diverse Komprimierungs-
Fracture Tibial
techniken. Sie beschreiben Hash-basierte Fragmentierung als Cough Asthma Influenza
of ulna Fractures
zu ineffizient. Die Autoren beschreiben jedoch nicht, wie die
Fragmentierungen für die Lookup-Tabellen berechnet wer-
den; im Gegensatz dazu stellen wir ein Ontologie-basiertes Figure 2: Beispieltaxonomie für Krankendaten
Fragmentierungsverfahren vor.
Im Gegensatz zu den meisten anderen Ansätzen gehen
Ein Clustering-Verfahren benutzt diese Ähnlichkeitswerte
wir nicht von einer vorgegebenen Menge von Anfragen oder
um Cluster zu bestimmen (in Anlehnung an [Gon85]). Da-
Transaktionen aus sondern schlagen ein allgemein anwend-
zu wird in jedem Cluster ein prototypisches Element head
bares Clusteringverfahren vor, dass die flexible Anfragebe-
bestimmt, das das jeweilige Cluster repräsentiert. Zusätz-
antwortung zum Auffinden semantisch ähnlicher Antworten
lich gibt es einen Schwellenwert α und das Verfahren un-
ermöglicht. Unsere Ergebnisse zeigen, dass Lookup-Tabellen
terteilt Cluster solange in Teilcluster, bis für jedes Element
(selbst wenn sie auf allen Servern repliziert werden) für un-
innerhalb eines Clusters die Ähnlichkeit zu head mindes-
seren Ansatz zu ineffizient sind, dadurch dass viele JOIN-
tens α ist. Das heißt, für jedes Cluster ci und head i ∈ ci
Operationen durchgeführt werden müssen.
gilt für jeden anderen Wert a ∈ ci (mit a 6= head i ), dass
sim(a, head i ) ≥ α. Dieses Verfahren wird in Auflistung 1
3. ONTOLOGIE-BASIERTE FRAGMENTIE- dargestellt.
RUNG
Unser Verfahren der Ontologie-basierten Fragmentierung Listing 1 Clustering procedure
beruht darauf, dass Input: Set πA (F ) of values for attribute A, similarity thres-
• zur Anti-Instantiierung ein Attribut (also eine Tabel- hold α
lenspalte) ausgewählt wird. Output: A set of clusters c1 , . . . , cf
1: Let c1 = πA (F )
• ein Clusteringverfahren auf dieser Tabellenspalte aus- 2: Choose arbitrary head 1 ∈ c1
geführt wird, um die ähnlichen Werte innerhalb dieser 3: sim min = min{sim(a, head1 ) | a ∈ c1 ; a 6= head 1 }
Spalte zu gruppieren. 4: i = 1
• anhand der Cluster die Tabelle zeilenweise fragmen- 5: while sim min < α do S
tiert wird. 6: Choose head i+1 ∈ 1≤j≤i {b | b ∈ cj ; b 6= head j ;
sim(b, headj ) = sim min } S
Wie in Abbildung 1 dargestellt werden dann die Anfra- 7: ci+1 = {head i+1 } ∪ 1≤j≤i {c | c ∈ cj ; c 6= head j ;
gen so weitergeleitet, dass zu einer Konstante aus der Ori-
sim(c, headj ) ≤ sim(c, headi+1 )}
ginalanfrage das semantisch ähnlichste Fragment ermittelt
8: i=i+1
wird und anschließend alle Werte des Fragments als rele-
9: sim min = min{sim(d, headj ) | d ∈ cj ; d 6= head j ; 1 ≤
vante Antworten zurückgeliefert werden. Daher werden zum
j ≤ i}
Beispiel bei einer Anfrage nach Husten auch die ähnlichen
10: end while
Werte Asthma und Bronchitis gefunden.
3.1 Clustering Zum Beispiel kann eine Taxonomie wie in Abbildung 2
Zu dem zur Anti-Instantiierung ausgewählten Attribut A benutzt werden, um die Tabellenspalte aus Abbildung 1 zu
in der gegebenen Tabelle F werden alle in der Tabelle vor- clustern.
handenen Werte (die sogenannte aktive Domäne) ausgelesen
durch Projektion πA (F ). Anhand einer gegebenen Ontologie 3.2 Fragmentierung
werden Ähnlichkeitswerte sim zwischen jeweils zwei Termen Ein Clustering der aktiven Domäne von A induziert ei-
a, b ∈ πA (F ) bestimmt im Wertebereich 0 (keine Ähnlich- ne horizontale Fragmentierung der Tabelle F in Fragmente
keit) bis 1 (volle Ähnlichkeit). Dazu gibt es verschiedene Me- Fi ⊆ F . Jede aktive Domäne eines Fragments Fi entspricht
triken, die meist auf der Berechnung von Pfaden zwischen genau den Werten in einem Cluster: ci = πA (Fi ). Die grund-
den Termen in der Ontologie beruhen [Wie14, Wie13]. legenden Eigenschaften einer Fragmentierung (Vollständig-

14
keit, Rekonstruierbarkeit, Redundanzfreiheit) sollen auch bei Dabei entspricht xik einer Binärvariable die dann wahr (1)
einer Clustering-basierten Fragmentierung gelten. Auch das ist, wenn Fragment/Objekt i Server/Bin k zugewiesen wird;
Clustering muss vollständig sein: bei einer aktiven Domäne und yk bedeutet, dass Server/Bin k belegt ist (also nicht
πA (F ) muss dann für ein Clustering C = c1 , . . . , cn gelten, leer). Gleichung (1) fordert, dass die Anzahl der belegten
dass es die ganze aktive Domäne umfasst und kein Wert ver- Server minimiert wird; Gleichung (2) erzwingt, dass jedes
loren geht: c1 ∪ . . . ∪ cn = πA (F ). Die Eigenschaften einer Fragment einem Server zugewiesen wird; Gleichung (3) be-
Clustering-basierten Fragmentierung werden in Definition 1 deutet, dass die Kapazitätsgrenzen nicht überschritten wer-
zusammengefasst. den; die letzten beiden Gleichungen stellen sicher, dass die
Variablen binär sind.
Definition 1 (Clustering-bas. Fragmentierung). Zusätzlich können noch die Eigenschaften der Datenloka-
Für ein Attribut A einer Tabelle F (eine Menge von Tupeln lität und der Lastverteilung optimiert werden. Datenvertei-
t) und ein Clustering C = {c1 , . . . cn } der aktiven Domäne lung mit einer guten Datenlokalität platziert die Fragmente
πA (F ) und für head i ∈ ci gibt es eine Menge von Fragmen- zusammen auf einen Server, die häufig gemeinsam innerhalb
ten {F1 , . . . , Fn } (definiert über denselben Attributen wie F ), einer Datenbanktransaktion (oder auch innerhalb einer An-
so dass folgende Eigenschaften gelten: frage) benutzt werden. Lastverteilung sorgt dafür, dass alle
Server ungefähr dieselbe Anzahl von Anfragen beantworten
• Horizontale Fragmentierung: für jedes Fragment Fi gilt müssen.
Fi ⊆ F
• Clustering: für jedes Fi gibt es in Cluster ci ∈ C so 3.4 Metadaten
dass ci = πA (Fi ) Für die Durchführung des Clustering, der Fragmentvertei-
lung und der Anfrageumschreibung und -umleitung werden
• Schwellenwert: für jedes a ∈ ci (wobei a 6= head i ) gilt ein paar Metadaten benötigt.
sim(a, head i ) ≥ α Eine Tabelle root speichert einen Identifikator für jedes
Cluster (Spalte ID), den Namen des Fragments (Name), den
• Vollständigkeit: für jedes Tupel t in F gibt es ein Frag-
Repräsentaten des Clusters (Head), die Größe des Clusters
ment Fi , in dem t enthalten ist
(S) sowie den Server (Host), auf dem das Fragment gespei-
• Rekonstruierbarkeit: F = F1 ∪ . . . ∪ Fn chert wird. Eine Beispieltabelle sieht dann so aus:
ROOT ID Name Head S Host
• Redundanzfreiheit: für jedes i 6= j, Fi ∩ Fj = ∅ (oder 101 Respiratory Flu 4 S1
auch ci ∩ cj = ∅) 107 Fracture brokenArm 2 S2
Eine Tabelle similarities speichert die Ähnlichkeiten al-
3.3 Fragmentverteilung ler Werte des betrachteten Attributes zu den jeweiligen head -
In verteilten Datenbanken müssen Fragmente verschie- Werten der Cluster.
denen Servern zugewiesen werden. Dieses Fragmentvertei-
lungsproblem kann als ein Bin-Packing-Problem dargestellt 3.5 Anfragebeantwortung
werden: Für die flexible Anfragebeantwortung wird die Konstante
im entsprechenden Attribut A in der Anfrage anti-instantiiert
• K Server entsprechen K Bins und die entstehende Anfrage dann aus dem semantisch ähn-
lichsten Fragment beantwortet.
• Jedes Bin hat maximale Kapazität W
Als Beispiel betrachten wir eine Anfrage nach Husten in
• n Fragmente entsprechen n Objekten einer Tabelle ill mit Patienten IDs und Krankheiten:
SELECT patientid, disease
• Jedes Objekt/Fragment hat ein Gewicht (oder Kapizi- FROM ill WHERE disease=’cough’
tätsverbrauch) wi ≤ W Über die Tabelle similarities wird das Fragment Fi ausge-
wählt, dessen head am ähnlichsten zu der anti-instantiierten
• alle Objekte müssen auf möglichst wenig Bins verteilt
Konstante (im Beispiel cough) ist.
werden, wobei die Gewichtsgrenze W beachtet werden
SELECT TOP 1 root.name
muss.
FROM root, similarities
Dieses Bin-Packing-Problem kann auch als Problem der WHERE similarities.term=’cough’
ganzzahligen linearen Optimierung dargestellt werden: AND similarities.head = root.head
ORDER BY similarities.sim DESC
Der Name der Originaltabelle F wird durch den Namen
K
X des Fragmentes Fi ersetzt und die geänderte Anfrage an den
minimize yk (1) entsprechenden Server gesendet. Dadurch werden alle Werte
k=1
aus dem Fragment als relevante Antworten zurückgeliefert.
K
X Als Beispiel sei der Fragmentname Respiratory. Daher wird
s.t. xik = 1, i = 1, . . . , n (2) die Anfrage geändert zu:
k=1
SELECT patientid, disease FROM respiratory
n
X und and den entsprechenden Server (hier S1) weitergeleitet.
wi xik ≤ W yk , k = 1, . . . , K (3) Ähnliches gilt beim Einfügen neuer Zeilen:
i=1
INSERT INTO ill VALUES (349, ’asthma’)
yk ∈ {0, 1} k = 1, . . . , K (4) wird umgeschrieben zu:
xik ∈ {0, 1} k = 1, . . . , K, i = 1, . . . , n (5) INSERT INTO respiratory VALUES (349, ’asthma’).

15
Auch das Löschen von Werten wird so umgesetzt: (BPPC):
DELETE FROM ill WHERE disease=’cough’
wird zu: K
X
DELETE FROM respiratory WHERE mesh=’cough’ minimize yk (6)
k=1

4. INTELLIGENTE REPLIKATION
K
X
s.t. xik = 1, i = 1, . . . , n (7)
Bisherige Replikationsverfahren kopieren die vorhandenen k=1
Fragmente auf andere Server; bei einer m-fachen Replikati- n
X
on verteilen sich so m verschiedene Kopien jedes Fragments wi xik ≤ W yk , k = 1, . . . , K (8)
auf m verschiedenen Servern. Dabei wird davon ausgegan- i=1
gen, dass die Fragmentierung redundanzfrei ist und sich die xik + xi0 k ≤ yk k = 1, . . . , K, i ∩ i0 6= ∅ (9)
Fragmente daher nicht überschneiden: jedes Tupel ist in ge-
nau einem Fragment enthalten. yk ∈ {0, 1} k = 1, . . . , K (10)
Bei der Ontologie-basierten Fragmentierung kann es je- xik ∈ {0, 1} k = 1, . . . , K, i = 1, . . . , n (11)
doch sein, dass mehrere Attribute zur Anti-Instantiierung
Um diese Konflikte (überlappende Fragmente) zu identifi-
ausgewählt werden. Dadurch ergeben sich mehrere Fragmen-
zieren werden Fragmente aus verschiedenen Fragmentierun-
tierungen derselben Tabelle. Fragmente aus unterschiedli-
gen verglichen. Im Beispiel gibt es Fragmente ci mit einer
chen Fragmentierungen überschneiden sich deswegen. Bei α
Cluster-ID (Fragmentierung wie im obigen Beispiel über den
redundanzfreien Fragmentierungen ist daher jedes Tupel in
Werten der Krankheiten) und Fragmente rj mit einer Range-
α verschiedenen Fragmenten enthalten.
ID (Fragmentierung über den Werten der Patienten-ID):
Beispielsweise kann unsere Beispieltabelle anhand eines
SELECT DISTINCT clusterid, rangeid
Clusterings der Krankheitsdiagnose fragmentiert werden; so
FROM ci JOIN rj ON (rj .tupleid=ci .tupleid)
ergeben sich zwei Fragemente: Respiratory und Fracture.
Respiratory PatientID Disease für jedes Cluster-Fragment ci und jedes Range-Fragment rj .
Danach wird das resultierende BPPC gelöst und die Frag-
8457 Cough
mente auf entsprechend viele Server verteilt mittels:
2784 Flu
ALTER TABLE ci MOVE TO ’severname’ PHYSICAL.
2784 Asthma
8765 Asthma
Fracture PatientID Diagnosis 5. WIEDERHERSTELLUNG
2784 brokenLeg Passend zum Replikationsverfahren müssen im Falle ei-
1055 brokenArm nes Serverausfalls einige Fragmente wiederhergestellt wer-
Zum Zweiten kann dieselbe Tabelle auch anhand der IDs den. Dazu werden der Originaltabelle Spalten für die jewei-
der Patienten fragmentiert werden. ligen Cluster-Identifikatoren hinzugefügt. Anhand der IDs
IDlow PatientID Diagnosis können die entsprechenden Fragmente rekonstruiert werden:
2784 Flu INSERT INTO ci SELECT * FROM rj WHERE clusterid=i
2784 brokenLeg Alternativ ist die Erstellung einer sogenannten Lookup-
2784 Asthma Tabelle [TCJM12] möglich, die zu jeder Cluster-ID die be-
1055 brokenArm teiligten Tupelidentifikatoren abspeichert. Diese benötigt je-
IDhigh PatientID Diagnosis doch einen JOIN-Operator:
8765 Asthma INSERT INTO ci SELECT * FROM ill JOIN lookup
8457 Cough ON (lookup.tupleid= rj .tupleid)
Dabei gilt, dass Respiratory ∩ IDlow 6= ∅, Respiratory WHERE lookup.clusterid=i
∩ IDhigh 6= ∅ und Fracture ∩ IDlow 6= ∅. Die Lookup-Tabelle hat sich daher als ineffizienter heraus-
Im Sinne der Minimierung der benutzten Server sollten gestellt.
nicht alle α Fragmentierungen m-fach kopiert werden, da
dies zu α · m Kopien jedes Tupels führt, obwohl m Kopien 6. DATENLOKALITÄT FÜR ABGELEITE-
ausreichen würden. Das bedeutet, dass das hier vorgestellte
Verfahren weniger Speicherplatzbedarf hat als eine konven- TE FRAGMENTIERUNGEN
tionelle Replikation aller ontologie-basierter Fragmente. Wenn auf mehrere Tabellen innerhalb einer Anfrage zu-
Um eine m-fache Replikation pro Tupel zu erreichen, wer- gegriffen wird und diese Tabellen Join-Attribute gemeinsam
den daher die Überschneidungen berücksichtigt. Wir gehen haben, kann durch abgeleitete Fragmentierung die Datenlo-
im Folgenden (ohne Beschränkung der Allgemeinheit) davon kalität für die Anfragen erhöht werden. Zum Beispiel sei zu-
aus, dass α = m – andernfalls werden einige Fragmentie- sätzlich zur Tabelle ill eine Tabelle info gegeben, die zu jeder
rungen dupliziert bis die entsprechende Anzahl erreicht ist. Patienten-ID Adressangaben enthält. Eine mögliche Anfra-
Damit ist also jedes Tupel in m Fragmenten enthalten. ge wäre daher, die Angaben zu Krankheiten und Adressen
Das Fragmentverteilungsproblem lässt sich daher erwei- zu kombinieren:
tern um die Bedingung, dass überlappende Fragmente (i ∩ SELECT a.disease, a.patientid, b.address
i0 6= ∅) auf verschiedenen Server platziert werden (Gleichung FROM ill AS a,info AS b WHERE disease=’cough’
(9)). Im Beispiel kann also Fracture nicht mit IDlow auf ei- AND b.patientid= a.patientid
nem Server platziert werden; jedoch können Fracture und Anhand der vorgegebenen primären Fragmentierung der
IDhigh auf demselben Server liegen. Generell handelt es Tabelle ill wird dann auch die Tabelle info fragmentiert,
sich dann dabei um ein Bin Packing Problem with Conflicts zum Beispiel für das Fragment Respiratory:

16
INSERT INTO inforesp Distributed caching protocols for relieving hot
SELECT a.patientid, b.address spots on the world wide web. In Proceedings of
FROM respiratory AS a, info AS b the twenty-ninth annual ACM symposium on
WHERE b.patientid = a.patientid Theory of computing, pages 654–663. ACM,
Daher kann dann im Folgenden auch die Anfrage, die An- 1997.
gaben zu Krankheiten und Adressen kombiniert, entspre- [Mic83] Ryszard S. Michalski. A theory and
chend umgeschrieben werden: methodology of inductive learning. Artificial
SELECT a.disease, a.patientid, b.address Intelligence, 20(2):111–161, 1983.
FROM respiratory AS a [ÖV11] M. Tamer Özsu and Patrick Valduriez.
JOIN inforesp AS b ON (a.patientid=b.patientid) Principles of Distributed Database Systems,
Third Edition. Springer, Berlin/Heidelberg,
7. ZUSAMMENFASSUNG UND AUSBLICK Germany, 2011.
Flexible Anfragebeantwortung unterstützt Benutzer bei [QKD13] Abdul Quamar, K. Ashwin Kumar, and Amol
der Suche nach relevanten Informationen. In unserem Ver- Deshpande. Sword: scalable workload-aware
fahren wird auf eine Ontologie zurückgegriffen aufgrund de- data placement for transactional workloads. In
rer semantisch ähnliche Werte in einem Cluster zusammen- Giovanna Guerrini and Norman W. Paton,
gefasst werden können. Eine Fragmentierung der Original- editors, Joint 2013 EDBT/ICDT Conferences,
tabelle anhand der Cluster ermöglichst ein effizientes Lauf- pages 430–441, New York, NY, USA, 2013.
zeitverhalten der flexiblen Anfragebeantwortung. Durch ei- ACM.
nige Metadaten (Root-Tabelle, Similarities-Tabelle, zusätzli- [SHL07] Myung Keun Shin, Soon-Young Huh, and
che Spalte für Cluster-ID) werden alle typischen Datenbank- Wookey Lee. Providing ranked cooperative
operationen unterstützt. query answers using the metricized knowledge
Zukünftig soll insbesondere das dynamische Anpassen der abstraction hierarchy. Expert Systems with
Fragmente untersucht werden: da sich durch Einfügungen Applications, 32(2):469–484, 2007.
und Löschungen die Größen der Fragmente stark ändern [TCJM12] Aubrey Tatarowicz, Carlo Curino, Evan P. C.
können, müssen zur Laufzeit Fragmente verschoben werden, Jones, and Sam Madden. Lookup tables:
sowie gegebenenfalls zu kleine Fragmente in ein größeres ver- Fine-grained partitioning for distributed
einigt werden beziehungsweise zu große Fragmente in klei- databases. In Anastasios Kementsietsidis and
nere aufgespalten werden. Marcos Antonio Vaz Salles, editors, IEEE 28th
International Conference on Data Engineering
8. REFERENCES (ICDE 2012), pages 102–113, Washington, DC,
[BDIW14] Maheen Bakhtyar, Nam Dang, Katsumi Inoue, USA, 2012. IEEE Computer Society.
and Lena Wiese. Implementing inductive [Wie13] Lena Wiese. Taxonomy-based fragmentation for
concept learning for cooperative query anti-instantiation in distributed databases. In
answering. In Data Analysis, Machine Learning 3rd International Workshop on Intelligent
and Knowledge Discovery, pages 127–134. Techniques and Architectures for Autonomic
Springer, 2014. Clouds (ITAAC’13) collocated with IEEE/ACM
[CYC+ 96] Wesley W. Chu, Hua Yang, Kuorong Chiang, 6th International Conference on Utility and
Michael Minock, Gladys Chow, and Chris Cloud Computing, pages 363–368, Washington,
Larson. CoBase: A scalable and extensible DC, USA, 2013. IEEE.
cooperative information system. JIIS, [Wie14] Lena Wiese. Clustering-based fragmentation
6(2/3):223–259, 1996. and data replication for flexible query
[CZJM10] Carlo Curino, Yang Zhang, Evan P. C. Jones, answering in distributed databases. Journal of
and Samuel Madden. Schism: a workload-driven Cloud Computing, 3(1):1–15, 2014.
approach to database replication and
partitioning. Proceedings of the VLDB
Endowment, 3(1):48–57, 2010.
[Gon85] Teofilo F. Gonzalez. Clustering to minimize the
maximum intercluster distance. Theoretical
Computer Science, 38:293–306, 1985.
[HTGC10] J. Hill, J. Torson, Bo Guo, and Zhengxin Chen.
Toward ontology-guided knowledge-driven xml
query relaxation. In Computational
Intelligence, Modelling and Simulation
(CIMSiM), pages 448–453, 2010.
[IW11] Katsumi Inoue and Lena Wiese. Generalizing
conjunctive queries for informative answers. In
Flexible Query Answering Systems, pages 1–12.
Springer, 2011.
[KLL+ 97] David Karger, Eric Lehman, Tom Leighton,
Rina Panigrahy, Matthew Levine, and Daniel
Lewin. Consistent hashing and random trees: