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 aufwändig und daher zur Laufzeit einer sichergestellt werden: Anfrage nur schwierig durchzuführen. In diesem Artikel stel- • durch die Fragmentierung wird ein Verfahren der fle- len wir ein Verfahren vor, dass Datentabellen anhand einer xiblen Anfragebeantwortung unterstützt, die dem An- Ontologie in semantisch zusammenhängende Cluster auf- frager auch relevante verwandte Werte als Antworten teilt. Dadurch ergibt sich eine Ontologie-basierte Fragmen- zurückliefert. tierung der Tabelle, die eine flexible Anfragebeantwortung unterstützt. Bei mehreren derartigen Fragmentierungen über- • durch die Fragmentierung wird eine Lastverteilung auf schneiden sich Fragmente; dies wird für ein intelligentes Re- mehrere Server mö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 möglich. Keywords Verteiltes Datenbanksystem, Replikation, Ontologie, Frag- • durch die intelligente Replikation wird die Anzahl der mentierung, flexible Anfragebeantwortung benö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 können auf mehre- tung vor. Abschnitt 4 beschreibt darauf aufbauend ein Repli- re Server verteilt und damit parallelisiert werden. kationsverfahren mit überlappenden Fragmenten. Ein Wie- derherstellungsverfahren anhand des Replikationsverfahrens • Verfügbarkeit: Durch die Lastverteilung erhöht sich die wird in Abschnitt 5 dargestellt. Es folgt ein Verfahren für Verfügbarkeit des Gesamtsystems, da einzelne Anfra- abgeleitete Fragmentierungen in Abschnitt 6 und abschlie- gen seltener verzögert werden mü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 gä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 Zusammenhänge der Daten. Aus Gründen der Ausfallsicherheit ist zusä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 für Hauptspeicherdatenbanken, die nicht über einen nicht exakt der Anfrage entsprechen, die jedoch dennoch in- Hintergrundspeicher verfügen. In dieser Arbeit stellen wir teressante Informationen für den Benutzer darstellen. Dabei gibt es syntaktische und semantische Ansätze. Zum einen gibt es syntaktische Änderungen, die Teile der Anfrage verändern. Dazu zä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 Datensätze nur einem Frag- ne neue Variable ersetzt. ment zugewiesen werden. Bei vertikaler Fragmentie- Diese Operatoren können auch kombiniert werden [IW11]. rung ist jede Spalte nur in einem Fragment enthalten Diese syntaktischen Änderungen kö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 (Schlüssel- neuen Variable zugewiesen werden können, beschränkt wer- Wert-Speicher, Dokumentdatenbanken oder Spaltenfamili- den: es sollen nur semantisch äquivalente oder semantisch endatenbanken) gibt es Fragmentierung meist über den Zu- nah verwandte Werte zugelassen werden. Diese semantische griffsschlüssel entweder Hash-basiert [KLL+ 97] oder basie- Ähnlichkeit kann anhand einer Ontologie oder Taxonomie rend auf Intervallen. Jedoch unterstützt keines dieser Ver- von Werten bestimmt werden. Fü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 für XML-Anfragen wurden Verfahren entwickelt 2.3 Datenverteilung [HTGC10]. In einem verteilten Datenbanksystem müssen Daten auf Ein grundlegendes Problem ist dabei jedoch, dass die Be- die verschiedenen Server verteilt werden. Wichtige Eigen- stimmung von ähnlichen Werten zur Laufzeit (während der schaften sind Anfragebeantwortung) viel zu ineffizient ist [BDIW14]. Die- ses Problem wird durch das hier vorgestellte Fragmentie- • Datenlokalität: Daten, auf die innerhalb einer Anfra- rungsverfahren gelöst. ge oder Transaktion zugegriffen wird, sollten mö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 lässt in horizontale und vertikale Fragmentierung den, da die anderen Server neue Anfragen annehmen (siehe zum Beispiel [ÖV11]): können. • Vertikale Fragmentierung: Fragmente entsprechen Teil- • Lastverteilung: Daten sollen so verteilt werden, dass mengen von Attributen (also Tabellenspalten). Die Ein- parallele Anfragen möglichst auch von verschiedenen träge in den Fragmenten, die zur selben Tabellenzeile Servern beantwortet werden können, damit nicht ein- gehören, mü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 unterstü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 Ansätze gehen von Fragmentierung entspricht einer Selektion auf der Ta- einer vorgebenen Menge von Anfragen oder Transaktionen belle. aus ( workload“) und optimieren die Lokalität der Daten, die ” innerhalb der Anfrage beziehungsweise Transaktion benötigt • Abgeleitete Fragmentierung: Eine bereits bestehende werden. Dies ist für die Anwendung der flexiblen Anfrage- primäre“ horizontale Fragmenation of einer Tabelle ” beantwortung jedoch nicht anwendbar, da hier auch Werte induziert eine horizontale Fragmentierung einer wei- zurückgegeben werden, die nicht explizit in einer Anfrage teren Tabelle; dazu wird der Semi-JOIN auf beiden auftauchen. Tabellen ausgeführt. [CZJM10] stellen Tupel als Knoten eines Graphen dar. Drei grundlegende Eigenschaften sind wichtig für Fragmen- Für eine vorgegebene Menge von Transaktionen fügen sie tierungen: Hyperkanten in den Graph ein, wenn die Tupel in dersel- ben Transaktion benötigt werden. Mit einem Graphpartitio- • Vollständigkeit: Keine Daten dürfen wä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 kön- sie dann das Graph-basierten mit Intervall-basierten und nen wieder zur Originaltabelle zusammengefü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 zusätzlich ein- alle Daten vorhalten; dies ist wenig realistisch in großen ver- gefü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 für je- einigungsoperator zum Zusammenfü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 Einfüh- Fragment 1: cough, ren einer zusä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 für große Tupelmengen. Die Autoren verglei- Figure 1: Fragmentation and query rewriting chen ihren Ansatz mit zufälligen und tupelweisen Fragmen- tierungen und betrachten auch Ä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 Zugriffsschlüsseln. Sie vergleichen diese drei be- Disorder, Diseases, Respiratory zü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 für die Lookup-Tabellen berechnet wer- den; im Gegensatz dazu stellen wir ein Ontologie-basiertes Figure 2: Beispieltaxonomie für Krankendaten Fragmentierungsverfahren vor. Im Gegensatz zu den meisten anderen Ansätzen gehen Ein Clustering-Verfahren benutzt diese Ä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 repräsentiert. Zusätz- antwortung zum Auffinden semantisch ähnlicher Antworten lich gibt es einen Schwellenwert α und das Verfahren un- ermöglicht. Unsere Ergebnisse zeigen, dass Lookup-Tabellen terteilt Cluster solange in Teilcluster, bis für jedes Element (selbst wenn sie auf allen Servern repliziert werden) für un- innerhalb eines Clusters die Ähnlichkeit zu head mindes- seren Ansatz zu ineffizient sind, dadurch dass viele JOIN- tens α ist. Das heißt, für jedes Cluster ci und head i ∈ ci Operationen durchgeführt werden müssen. gilt fü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) ausgewä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 geführt wird, um die ä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 ä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 zurückgeliefert werden. Daher werden zum j ≤ i} Beispiel bei einer Anfrage nach Husten auch die ä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 ausgewä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 Domäne) ausgelesen durch Projektion πA (F ). Anhand einer gegebenen Ontologie 3.2 Fragmentierung werden Ähnlichkeitswerte sim zwischen jeweils zwei Termen Ein Clustering der aktiven Domäne von A induziert ei- a, b ∈ πA (F ) bestimmt im Wertebereich 0 (keine Ähnlich- ne horizontale Fragmentierung der Tabelle F in Fragmente keit) bis 1 (volle Ähnlichkeit). Dazu gibt es verschiedene Me- Fi ⊆ F . Jede aktive Domä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 (Vollständig- 14 keit, Rekonstruierbarkeit, Redundanzfreiheit) sollen auch bei Dabei entspricht xik einer Binärvariable die dann wahr (1) einer Clustering-basierten Fragmentierung gelten. Auch das ist, wenn Fragment/Objekt i Server/Bin k zugewiesen wird; Clustering muss vollständig sein: bei einer aktiven Domäne und yk bedeutet, dass Server/Bin k belegt ist (also nicht πA (F ) muss dann für ein Clustering C = c1 , . . . , cn gelten, leer). Gleichung (1) fordert, dass die Anzahl der belegten dass es die ganze aktive Domä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 Kapazitätsgrenzen nicht überschritten wer- zusammengefasst. den; die letzten beiden Gleichungen stellen sicher, dass die Variablen binär sind. Definition 1 (Clustering-bas. Fragmentierung). Zusätzlich können noch die Eigenschaften der Datenloka- Für ein Attribut A einer Tabelle F (eine Menge von Tupeln lität und der Lastverteilung optimiert werden. Datenvertei- t) und ein Clustering C = {c1 , . . . cn } der aktiven Domäne lung mit einer guten Datenlokalität platziert die Fragmente πA (F ) und für head i ∈ ci gibt es eine Menge von Fragmen- zusammen auf einen Server, die häufig gemeinsam innerhalb ten {F1 , . . . , Fn } (definiert über denselben Attributen wie F ), einer Datenbanktransaktion (oder auch innerhalb einer An- so dass folgende Eigenschaften gelten: frage) benutzt werden. Lastverteilung sorgt dafür, dass alle Server ungefähr dieselbe Anzahl von Anfragen beantworten • Horizontale Fragmentierung: für jedes Fragment Fi gilt müssen. Fi ⊆ F • Clustering: für jedes Fi gibt es in Cluster ci ∈ C so 3.4 Metadaten dass ci = πA (Fi ) Für die Durchführung des Clustering, der Fragmentvertei- lung und der Anfrageumschreibung und -umleitung werden • Schwellenwert: für jedes a ∈ ci (wobei a 6= head i ) gilt ein paar Metadaten benötigt. sim(a, head i ) ≥ α Eine Tabelle root speichert einen Identifikator für jedes Cluster (Spalte ID), den Namen des Fragments (Name), den • Vollständigkeit: für jedes Tupel t in F gibt es ein Frag- Repräsentaten des Clusters (Head), die Größ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: fü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 Ähnlichkeiten al- 3.3 Fragmentverteilung ler Werte des betrachteten Attributes zu den jeweiligen head - In verteilten Datenbanken müssen Fragmente verschie- Werten der Cluster. denen Servern zugewiesen werden. Dieses Fragmentvertei- lungsproblem kann als ein Bin-Packing-Problem dargestellt 3.5 Anfragebeantwortung werden: Fü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 ähn- lichsten Fragment beantwortet. • Jedes Bin hat maximale Kapazitä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’ tätsverbrauch) wi ≤ W Über die Tabelle similarities wird das Fragment Fi ausge- wählt, dessen head am ähnlichsten zu der anti-instantiierten • alle Objekte müssen auf mö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 geänderte Anfrage an den minimize yk (1) entsprechenden Server gesendet. Dadurch werden alle Werte k=1 aus dem Fragment als relevante Antworten zurückgeliefert. K X Als Beispiel sei der Fragmentname Respiratory. Daher wird s.t. xik = 1, i = 1, . . . , n (2) die Anfrage geä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) Ähnliches gilt beim Einfü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 Lö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 ü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 (überlappende Fragmente) zu identifi- ausgewä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 überschneiden sich deswegen. Bei α Cluster-ID (Fragmentierung wie im obigen Beispiel über den redundanzfreien Fragmentierungen ist daher jedes Tupel in Werten der Krankheiten) und Fragmente rj mit einer Range- α verschiedenen Fragmenten enthalten. ID (Fragmentierung ü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 für jedes Cluster-Fragment ci und jedes Range-Fragment rj . Danach wird das resultierende BPPC gelö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 mü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 für die jewei- der Patienten fragmentiert werden. ligen Cluster-Identifikatoren hinzugefügt. Anhand der IDs IDlow PatientID Diagnosis kö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] möglich, die zu jeder Cluster-ID die be- 1055 brokenArm teiligten Tupelidentifikatoren abspeichert. Diese benö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 führt, obwohl m Kopien 6. DATENLOKALITÄT FÜR ABGELEITE- ausreichen wü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 Überschneidungen berücksichtigt. Wir gehen haben, kann durch abgeleitete Fragmentierung die Datenlo- im Folgenden (ohne Beschränkung der Allgemeinheit) davon kalität für die Anfragen erhöht werden. Zum Beispiel sei zu- aus, dass α = m – andernfalls werden einige Fragmentie- sätzlich zur Tabelle ill eine Tabelle info gegeben, die zu jeder rungen dupliziert bis die entsprechende Anzahl erreicht ist. Patienten-ID Adressangaben enthält. Eine mögliche Anfra- Damit ist also jedes Tupel in m Fragmenten enthalten. ge wäre daher, die Angaben zu Krankheiten und Adressen Das Fragmentverteilungsproblem lässt sich daher erwei- zu kombinieren: tern um die Bedingung, dass ü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 können Fracture und Anhand der vorgegebenen primä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 fü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 [ÖV11] M. Tamer Ö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 unterstü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 zurückgegriffen aufgrund de- data placement for transactional workloads. In rer semantisch ähnliche Werte in einem Cluster zusammen- Giovanna Guerrini and Norman W. Paton, gefasst werden können. Eine Fragmentierung der Original- editors, Joint 2013 EDBT/ICDT Conferences, tabelle anhand der Cluster ermö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, zusätzli- [SHL07] Myung Keun Shin, Soon-Young Huh, and che Spalte für Cluster-ID) werden alle typischen Datenbank- Wookey Lee. Providing ranked cooperative operationen unterstützt. query answers using the metricized knowledge Zukünftig soll insbesondere das dynamische Anpassen der abstraction hierarchy. Expert Systems with Fragmente untersucht werden: da sich durch Einfügungen Applications, 32(2):469–484, 2007. und Löschungen die Größen der Fragmente stark ändern [TCJM12] Aubrey Tatarowicz, Carlo Curino, Evan P. C. können, müssen zur Laufzeit Fragmente verschoben werden, Jones, and Sam Madden. Lookup tables: sowie gegebenenfalls zu kleine Fragmente in ein größ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: 17