Das Auffinden von semantisch verwandten Daten in großen Datenmengen ist aufwa¨ndig und daher zur Laufzeit einer Anfrage nur schwierig durchzufu¨hren. In diesem Artikel stellen wir ein Verfahren vor, dass Datentabellen anhand einer Ontologie in semantisch zusammenha¨ngende Cluster aufteilt. Dadurch ergibt sich eine Ontologie-basierte Fragmentierung der Tabelle, die eine flexible Anfragebeantwortung unterstu¨tzt. Bei mehreren derartigen Fragmentierungen u¨berschneiden sich Fragmente; dies wird fu¨r ein intelligentes Replikationsverfahren ausgenutzt, um die Anzahl der Replikaserver zu reduzieren.
• Lastverteilung: Datenbankanfragen ko¨nnen auf mehrere Server verteilt und damit parallelisiert werden. • Verfu¨gbarkeit: Durch die Lastverteilung erho¨ht sich die Verfu¨gbarkeit des Gesamtsystems, da einzelne Anfragen seltener verzo¨gert werden mu¨ssen.
Ein geeignetes Verfahren zur Fragmentierung (auch: Partitionierung oder Sharding) der Daten in Teilmengen ist daher notwendig. Die ga¨ngigen Fragmentierungsverfahren (Round-Robin, Hash-basiert, Intervall-basiert) ignorieren jedoch semantische Zusammenha¨nge der Daten.
Aus Gru¨nden der Ausfallsicherheit ist zusa¨tzlich noch die Replikation von Daten (also die Spiegelung desselben Datensatzes auf mehreren Servern) erforderlich. Dies gilt insbesondere fu¨r Hauptspeicherdatenbanken, die nicht u¨ber einen Hintergrundspeicher verfu¨gen. In dieser Arbeit stellen wir
Verfahren zur Ontologie-basierten Fragmentierung und zur intelligenten Replikation vor, womit folgende Eigenschaften sichergestellt werden: 1.1
Übersicht
Abschnitt 2 beschreibt den Hintergrund zu flexibler Anfragebeantwortung, Fragmentierung und Datenverteilung. Abschnitt 3 stellt die Ontologie-basierte Fragmentierung inklusive Clustering, Fragmentverteilung und Anfragebeantwortung vor. Abschnitt 4 beschreibt darauf aufbauend ein Replikationsverfahren mit u¨berlappenden Fragmenten. Ein Wiederherstellungsverfahren anhand des Replikationsverfahrens wird in Abschnitt 5 dargestellt. Es folgt ein Verfahren fu¨r abgeleitete Fragmentierungen in Abschnitt 6 und abschließend eine Zusammenfassung in Abschnitt 7. 2.
Wir stellen hier kurz Vorarbeiten zu flexibler Anfragebeantwortung, Fragmentierung und Datenverteilung vor. 2.1
Flexible Anfragebeantwortung ist ein intelligentes Verfahren, um Datenbanknutzern Antworten zu liefern, die zwar nicht exakt der Anfrage entsprechen, die jedoch dennoch interessante 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]: • Anti-Instantiation: Ein Term (eine Variable mit mehreren Vorkommen oder eine Konstante) wird durch eine neue Variable ersetzt.
Diese Operatoren ko¨nnen auch kombiniert werden [IW11].
Diese syntaktischen A¨ nderungen ko¨nnen aber zu weit gehen und zu viele Antworten produzieren – insbesondere beim Ersetzen von Konstanten durch neue Variablen in der AntiInstantiation. Daher ist es wichtig, dass die Werte, die der neuen Variable zugewiesen werden ko¨nnen, beschra¨nkt werden: es sollen nur semantisch a¨quivalente oder semantisch nah verwandte Werte zugelassen werden. Diese semantische A¨ hnlichkeit kann anhand einer Ontologie oder Taxonomie von Werten bestimmt werden. Fu¨r Einzelrechner wurden bereits vor einiger Zeit Verfahren vorgeschlagen – ohne jedoch verteilte Datenspeicherung mit einzubeziehen. CoBase [CYC+96] und [SHL07] zum Beispiel benutzten sogenannte Abstraktionshierarchien, um einzelne Werte zu generalisieren. Auch fu¨r XML-Anfragen wurden Verfahren entwickelt [HTGC10].
Ein grundlegendes Problem ist dabei jedoch, dass die Bestimmung von a¨hnlichen Werten zur Laufzeit (wa¨hrend der Anfragebeantwortung) viel zu ineffizient ist [BDIW14]. Dieses Problem wird durch das hier vorgestellte Fragmentierungsverfahren gelo¨st. 2.2
Im relationalen Modell gibt es die Theorie der Datenfragmentierung, die sich aufgrund des strikten Tabellenformats aufteilen la¨sst in horizontale und vertikale Fragmentierung (siehe zum Beispiel [ O¨V11]): • Vertikale Fragmentierung: Fragmente entsprechen Teilmengen von Attributen (also Tabellenspalten). Die Eintra¨ge in den Fragmenten, die zur selben Tabellenzeile geho¨ren, mu¨ssen durch einen Tuple-Identifikator verbunden werden. Vertikale Fragmentierung entspricht einer Projektion auf der Tabelle. • Horizontale Fragmentierung: Fragmente sind Teilmengen von Tupeln (also Tabellenzeilen). Eine horizontale Fragmentierung entspricht einer Selektion auf der Tabelle. • Abgeleitete Fragmentierung: Eine bereits bestehende ”prima¨re“ horizontale Fragmenation of einer Tabelle induziert eine horizontale Fragmentierung einer weiteren Tabelle; dazu wird der Semi-JOIN auf beiden Tabellen ausgefu¨hrt.
Drei grundlegende Eigenschaften sind wichtig fu¨r Fragmentierungen: • Vollsta¨ndigkeit: Keine Daten du¨rfen wa¨hrend der Fragmentierung verloren gehen. Bei vertikaler Fragmentierung ist jede Spalte in einem Fragment enthalten; bei horizontaler Fragmentierung ist jede Zeile in einem Fragment enthalten. • Rekonstruierbarkeit: Daten aus den Fragmenten ko¨nnen wieder zur Originaltabelle zusammengefu¨gt werden. Bei vertikaler Fragmentierung wird der JOINOperator benutzt (basierend auf einem zusa¨tzlich eingefu¨gten Tupel-Identifikator), um die Spalten zu verbinden. Bei horizontaler Fragmentierung wird der Vereinigungsoperator zum Zusammenfu¨hren der Fragmente verwendet. • Redundanzfreiheit: Um Duplizieren von Daten zu vermeiden, sollen einzelne Datensa¨tze nur einem Fragment zugewiesen werden. Bei vertikaler Fragmentierung ist jede Spalte nur in einem Fragment enthalten (abgesehen vom Tupel-Identifikator). Bei horizontaler Fragmentierung ist jede Zeile in nur einem Fragment enthalten.
In anderen, nicht-relationalen Datenmodellen (Schlu¨sselWert-Speicher, Dokumentdatenbanken oder Spaltenfamiliendatenbanken) gibt es Fragmentierung meist u¨ber den Zugriffsschlu¨ssel entweder Hash-basiert [KLL+97] oder basierend auf Intervallen. Jedoch unterstu¨tzt keines dieser Verfahren die flexible Anfragebeantwortung; im Gegensatz dazu hat das im Folgenden vorgestellte Fragmentierungsverfahren den Vorteil, dass eine relaxierte Bedingung aus nur einem Fragment beantwortet werden kann. 2.3
In einem verteilten Datenbanksystem mu¨ssen Daten auf die verschiedenen Server verteilt werden. Wichtige Eigenschaften sind • Datenlokalita¨t: Daten, auf die innerhalb einer Anfrage oder Transaktion zugegriffen wird, sollten mo¨glichst auf einem Server sein. Dadurch verringert sich die Anzahl der kontaktierten Server und somit auch die Dauer der Anfragebeantwortung. Außerdem kann so die Parallelisierung der Anfragebeantwortung verbessert werden, da die anderen Server neue Anfragen annehmen ko¨nnen. • Lastverteilung: Daten sollen so verteilt werden, dass parallele Anfragen mo¨glichst auch von verschiedenen Servern beantwortet werden ko¨nnen, damit nicht einzelne Server unter Lastspitzen (”hot spots“) leiden. Einige Arbeiten befassen sich mit horizontaler Fragmentierung und Verteilung; jedoch unterstu¨tzen diese nur exakte Anfragebeantwortung und keine flexible Anfragebeantwortung wie in unserem Ansatz. Die meisten Ansa¨tze gehen von einer vorgebenen Menge von Anfragen oder Transaktionen aus (”workload“) und optimieren die Lokalita¨t der Daten, die innerhalb der Anfrage beziehungsweise Transaktion beno¨tigt werden. Dies ist fu¨r die Anwendung der flexiblen Anfragebeantwortung jedoch nicht anwendbar, da hier auch Werte zuru¨ckgegeben werden, die nicht explizit in einer Anfrage auftauchen.
[CZJM10] stellen Tupel als Knoten eines Graphen dar. Fu¨r eine vorgegebene Menge von Transaktionen fu¨gen sie Hyperkanten in den Graph ein, wenn die Tupel in derselben Transaktion beno¨tigt werden. Mit einem Graphpartitionierungsalgorithmus wird dann eine Datenfragmentierung ermittelt, die Zahl der zerschnittenen Kanten minimiert. In einer zweiten Phase benutzen die Autoren einen Klassifizierer aus dem Maschinellen Lernen, der eine Intervallbasierte Fragmentierung herleitet. Experimentell vergleichen sie dann das Graph-basierten mit Intervall-basierten und Hash-basierten Verfahren. Im Gegensatz zu unserem Ansatz wenden sie jedoch volle Replikation an, bei der alle Server alle Daten vorhalten; dies ist wenig realistisch in großen verteilten Systemen. Zudem vergleichen sie drei verschiedene Arten von Lookup-Tabellen, die Tupel-Identifikatoren fu¨r jedes Fragment abspeichern: Indexe, Bitarrays und Bloomfilter. Bei der Analyse unseres Systems stellt sich jedoch heraus, dass Lookup-Tabellen ineffizienter sind als das Einfu¨hren einer zusa¨tzlichen Spalte mit der Cluster-ID in anderen Fragmentierungen.
Auch [QKD13] modellieren das Fragmentierungsproblem durch Minimierung zerschnittener Hyperkanten in einem Graphen. Zur Verbesserung der Effizienz komprimieren sie den Graphen und erhalten so Gruppen von Tupeln. Die Autoren kritisieren dabei auch den tupelweisen Ansatz von [CZJM10] als unpraktisch fu¨r große Tupelmengen. Die Autoren vergleichen ihren Ansatz mit zufa¨lligen und tupelweisen Fragmentierungen und betrachten auch A¨ nderungen der vorgegebenen Transaktionen.
[TCJM12] gehen von drei existierenden Fragmentierungen aus: Hash-basiert, Intervall-basiert und Lookup-Tabellen auf einzelnen Zugriffsschlu¨sseln. Sie vergleichen diese drei bezu¨glich Kommunikationskosten und Anfragendurchsatz. Zur Effiziensteigerung analysieren sie diverse Komprimierungstechniken. Sie beschreiben Hash-basierte Fragmentierung als zu ineffizient. Die Autoren beschreiben jedoch nicht, wie die Fragmentierungen fu¨r die Lookup-Tabellen berechnet werden; im Gegensatz dazu stellen wir ein Ontologie-basiertes Fragmentierungsverfahren vor.
Im Gegensatz zu den meisten anderen Ansa¨tzen gehen wir nicht von einer vorgegebenen Menge von Anfragen oder Transaktionen aus sondern schlagen ein allgemein anwendbares Clusteringverfahren vor, dass die flexible Anfragebeantwortung zum Auffinden semantisch a¨hnlicher Antworten ermo¨glicht. Unsere Ergebnisse zeigen, dass Lookup-Tabellen (selbst wenn sie auf allen Servern repliziert werden) fu¨r unseren Ansatz zu ineffizient sind, dadurch dass viele JOINOperationen durchgefu¨hrt werden mu¨ssen.
Unser Verfahren der Ontologie-basierten Fragmentierung beruht darauf, dass • zur Anti-Instantiierung ein Attribut (also eine Tabellenspalte) ausgewa¨hlt wird. • ein Clusteringverfahren auf dieser Tabellenspalte ausgefu¨hrt wird, um die a¨hnlichen Werte innerhalb dieser Spalte zu gruppieren. • anhand der Cluster die Tabelle zeilenweise fragmentiert wird.
Wie in Abbildung 1 dargestellt werden dann die Anfragen so weitergeleitet, dass zu einer Konstante aus der Originalanfrage das semantisch a¨hnlichste Fragment ermittelt wird und anschließend alle Werte des Fragments als relevante Antworten zuru¨ckgeliefert werden. Daher werden zum Beispiel bei einer Anfrage nach Husten auch die a¨hnlichen Werte Asthma und Bronchitis gefunden. 3.1
Zu dem zur Anti-Instantiierung ausgewa¨hlten Attribut A in der gegebenen Tabelle F werden alle in der Tabelle vorhandenen Werte (die sogenannte aktive Doma¨ne) ausgelesen durch Projektion πA(F ). Anhand einer gegebenen Ontologie werden A¨ hnlichkeitswerte sim zwischen jeweils zwei Termen a, b ∈ πA(F ) bestimmt im Wertebereich 0 (keine A¨ hnlichkeit) bis 1 (volle A¨ hnlichkeit). Dazu gibt es verschiedene Metriken, die meist auf der Berechnung von Pfaden zwischen den Termen in der Ontologie beruhen [Wie14, Wie13]. user query rewrite & redirect
Fragment 1: cough, bronchitis, asthma Fragment 2: brokenLeg, brokenArm cluster & fragment Ein Clustering-Verfahren benutzt diese A¨ hnlichkeitswerte um Cluster zu bestimmen (in Anlehnung an [Gon85]). Dazu wird in jedem Cluster ein prototypisches Element head bestimmt, das das jeweilige Cluster repra¨sentiert. Zusa¨tzlich gibt es einen Schwellenwert α und das Verfahren unterteilt Cluster solange in Teilcluster, bis fu¨r jedes Element innerhalb eines Clusters die A¨ hnlichkeit zu head mindestens α ist. Das heißt, fu¨r jedes Cluster ci und head i ∈ ci gilt fu¨r jeden anderen Wert a ∈ ci (mit a 6= head i), dass sim(a, head i) ≥ α. Dieses Verfahren wird in Auflistung 1 dargestellt.
Listing 1 Clustering procedure Input: Set πA(F ) of values for attribute A, similarity threshold α Output: A set of clusters c1, . . . , cf 1: Let c1 = πA(F ) 2: Choose arbitrary head 1 ∈ c1 3: simmin = min{sim(a, head1) | a ∈ c1; a 6= head 1} 4: i = 1 5: while simmin < α do 6: Choose head i+1 ∈ S1≤j≤i{b | b ∈ cj ; b 6= head j ; sim(b, headj ) = simmin } 7: ci+1 = {head i+1} ∪ S1≤j≤i{c | c ∈ cj; c 6= head j; sim(c, headj ) ≤ sim(c, headi+1)} 8: i = i + 1 9: simmin = min{sim(d, headj ) | d ∈ cj; d 6= head j ; 1 ≤ j ≤ i} 10: end while
Zum Beispiel kann eine Taxonomie wie in Abbildung 2 benutzt werden, um die Tabellenspalte aus Abbildung 1 zu clustern. 3.2
Ein Clustering der aktiven Doma¨ne von A induziert eine horizontale Fragmentierung der Tabelle F in Fragmente Fi ⊆ F . Jede aktive Doma¨ne eines Fragments Fi entspricht genau den Werten in einem Cluster: ci = πA(Fi). Die grundlegenden Eigenschaften einer Fragmentierung (Vollsta¨ndigkeit, Rekonstruierbarkeit, Redundanzfreiheit) sollen auch bei einer Clustering-basierten Fragmentierung gelten. Auch das Clustering muss vollsta¨ndig sein: bei einer aktiven Doma¨ne πA(F ) muss dann fu¨r ein Clustering C = c1, . . . , cn gelten, dass es die ganze aktive Doma¨ne umfasst und kein Wert verloren geht: c1 ∪ . . . ∪ cn = πA(F ). Die Eigenschaften einer Clustering-basierten Fragmentierung werden in Definition 1 zusammengefasst.
Definition 1 (Clustering-bas. Fragmentierung). Fu¨r ein Attribut A einer Tabelle F (eine Menge von Tupeln t) und ein Clustering C = {c1, . . . cn} der aktiven Doma¨ne πA(F ) und fu¨r head i ∈ ci gibt es eine Menge von Fragmenten {F1, . . . , Fn} (definiert u¨ber denselben Attributen wie F ), so dass folgende Eigenschaften gelten: • Horizontale Fragmentierung: fu¨r jedes Fragment Fi gilt
Fi ⊆ F • Clustering: fu¨r jedes Fi gibt es in Cluster ci ∈ C so dass ci = πA(Fi) • Schwellenwert: fu¨r jedes a ∈ ci (wobei a 6= head i) gilt sim(a, head i) ≥ α • Vollsta¨ndigkeit: fu¨r jedes Tupel t in F gibt es ein Fragment Fi, in dem t enthalten ist • Rekonstruierbarkeit: F = F1 ∪ . . . ∪ Fn • Redundanzfreiheit: fu¨r jedes i 6= j, Fi ∩ Fj = ∅ (oder auch ci ∩ cj = ∅) 3.3
In verteilten Datenbanken mu¨ssen Fragmente verschiedenen Servern zugewiesen werden. Dieses Fragmentverteilungsproblem kann als ein Bin-Packing-Problem dargestellt werden: • K Server entsprechen K Bins • Jedes Bin hat maximale Kapazita¨t W • n Fragmente entsprechen n Objekten • Jedes Objekt/Fragment hat ein Gewicht (oder Kapizita¨tsverbrauch) wi ≤ W • alle Objekte mu¨ssen auf mo¨glichst wenig Bins verteilt werden, wobei die Gewichtsgrenze W beachtet werden muss.
Dieses Bin-Packing-Problem kann auch als Problem der ganzzahligen linearen Optimierung dargestellt werden: s.t.
Dabei entspricht xik einer Bina¨rvariable die dann wahr (1) ist, wenn Fragment/Objekt i Server/Bin k zugewiesen wird; und yk bedeutet, dass Server/Bin k belegt ist (also nicht leer). Gleichung (1) fordert, dass die Anzahl der belegten Server minimiert wird; Gleichung (2) erzwingt, dass jedes Fragment einem Server zugewiesen wird; Gleichung (3) bedeutet, dass die Kapazita¨tsgrenzen nicht u¨berschritten werden; die letzten beiden Gleichungen stellen sicher, dass die Variablen bina¨r sind.
Zusa¨tzlich ko¨nnen noch die Eigenschaften der Datenlokalita¨t und der Lastverteilung optimiert werden. Datenverteilung mit einer guten Datenlokalita¨t platziert die Fragmente zusammen auf einen Server, die ha¨ufig gemeinsam innerhalb einer Datenbanktransaktion (oder auch innerhalb einer Anfrage) benutzt werden. Lastverteilung sorgt dafu¨r, dass alle Server ungefa¨hr dieselbe Anzahl von Anfragen beantworten mu¨ssen. 3.4
Fu¨r die Durchfu¨hrung des Clustering, der Fragmentverteilung und der Anfrageumschreibung und -umleitung werden ein paar Metadaten beno¨tigt.
Eine Tabelle root speichert einen Identifikator fu¨r jedes Cluster (Spalte ID), den Namen des Fragments (Name), den Repra¨sentaten des Clusters (Head), die Gro¨ße des Clusters (S) sowie den Server (Host), auf dem das Fragment gespeichert wird. Eine Beispieltabelle sieht dann so aus: ROOT ID Name Head S Host 101 Respiratory Flu 4 S1 107 Fracture brokenArm 2 S2
Eine Tabelle similarities speichert die A¨ hnlichkeiten aller Werte des betrachteten Attributes zu den jeweiligen head Werten der Cluster. 3.5
Fu¨r die flexible Anfragebeantwortung wird die Konstante im entsprechenden Attribut A in der Anfrage anti-instantiiert und die entstehende Anfrage dann aus dem semantisch a¨hnlichsten Fragment beantwortet.
Als Beispiel betrachten wir eine Anfrage nach Husten in einer Tabelle ill mit Patienten IDs und Krankheiten: SELECT patientid, disease FROM ill WHERE disease=’cough’
U¨ ber die Tabelle similarities wird das Fragment Fi ausgewa¨hlt, dessen head am a¨hnlichsten zu der anti-instantiierten Konstante (im Beispiel cough) ist.
SELECT TOP 1 root.name FROM root, similarities WHERE similarities.term=’cough’ AND similarities.head = root.head ORDER BY similarities.sim DESC
Der Name der Originaltabelle F wird durch den Namen des Fragmentes Fi ersetzt und die gea¨nderte Anfrage an den entsprechenden Server gesendet. Dadurch werden alle Werte aus dem Fragment als relevante Antworten zuru¨ckgeliefert. Als Beispiel sei der Fragmentname Respiratory. Daher wird die Anfrage gea¨ndert zu:
SELECT patientid, disease FROM respiratory und and den entsprechenden Server (hier S1) weitergeleitet.
A¨ hnliches gilt beim Einfu¨gen neuer Zeilen:
INSERT INTO ill VALUES (349, ’asthma’) wird umgeschrieben zu:
INSERT INTO respiratory VALUES (349, ’asthma’). Auch das Lo¨schen von Werten wird so umgesetzt: DELETE FROM ill WHERE disease=’cough’ wird zu:
DELETE FROM respiratory WHERE mesh=’cough’
Bisherige Replikationsverfahren kopieren die vorhandenen Fragmente auf andere Server; bei einer m-fachen Replikation verteilen sich so m verschiedene Kopien jedes Fragments auf m verschiedenen Servern. Dabei wird davon ausgegangen, dass die Fragmentierung redundanzfrei ist und sich die Fragmente daher nicht u¨berschneiden: jedes Tupel ist in genau einem Fragment enthalten.
Bei der Ontologie-basierten Fragmentierung kann es jedoch sein, dass mehrere Attribute zur Anti-Instantiierung ausgewa¨hlt werden. Dadurch ergeben sich mehrere Fragmentierungen derselben Tabelle. Fragmente aus unterschiedlichen Fragmentierungen u¨berschneiden sich deswegen. Bei α redundanzfreien Fragmentierungen ist daher jedes Tupel in α verschiedenen Fragmenten enthalten.
Beispielsweise kann unsere Beispieltabelle anhand eines Clusterings der Krankheitsdiagnose fragmentiert werden; so ergeben sich zwei Fragemente: Respiratory und Fracture.
Respiratory PatientID Disease 8457 Cough 2784 Flu 2784 Asthma 8765 Asthma Fracture PatientID Diagnosis 2784 brokenLeg 1055 brokenArm
Zum Zweiten kann dieselbe Tabelle auch anhand der IDs der Patienten fragmentiert werden.
IDlow PatientID Diagnosis 2784 Flu 2784 brokenLeg 2784 Asthma 1055 brokenArm IDhigh PatientID Diagnosis 8765 Asthma 8457 Cough
Dabei gilt, dass Respiratory ∩ IDlow 6= ∅, Respiratory ∩ IDhigh 6= ∅ und Fracture ∩ IDlow 6= ∅.
Im Sinne der Minimierung der benutzten Server sollten nicht alle α Fragmentierungen m-fach kopiert werden, da dies zu α · m Kopien jedes Tupels fu¨hrt, obwohl m Kopien ausreichen wu¨rden. Das bedeutet, dass das hier vorgestellte Verfahren weniger Speicherplatzbedarf hat als eine konventionelle Replikation aller ontologie-basierter Fragmente.
Um eine m-fache Replikation pro Tupel zu erreichen, werden daher die U¨ berschneidungen beru¨cksichtigt. Wir gehen im Folgenden (ohne Beschra¨nkung der Allgemeinheit) davon aus, dass α = m – andernfalls werden einige Fragmentierungen dupliziert bis die entsprechende Anzahl erreicht ist. Damit ist also jedes Tupel in m Fragmenten enthalten.
Das Fragmentverteilungsproblem la¨sst sich daher
erweitern um die Bedingung, dass u¨berlappende Fragmente (i ∩
i0 6= ∅) auf verschiedenen Server platziert werden (Gleichung
(9)). Im Beispiel kann also Fracture nicht mit IDlow auf
einem Server platziert werden; jedoch ko¨nnen Fracture und
IDhigh auf demselben Server liegen. Generell handelt es
sich dann dabei um ein Bin Packing Problem with Conflicts
(6)
(7)
(8)
(9)
(
Um diese Konflikte (u¨berlappende Fragmente) zu identifizieren werden Fragmente aus verschiedenen Fragmentierungen verglichen. Im Beispiel gibt es Fragmente ci mit einer Cluster-ID (Fragmentierung wie im obigen Beispiel u¨ber den Werten der Krankheiten) und Fragmente rj mit einer RangeID (Fragmentierung u¨ber den Werten der Patienten-ID): SELECT DISTINCT clusterid, rangeid
FROM ci JOIN rj ON (rj.tupleid=ci.tupleid) fu¨r jedes Cluster-Fragment ci und jedes Range-Fragment rj. Danach wird das resultierende BPPC gelo¨st und die Fragmente auf entsprechend viele Server verteilt mittels:
ALTER TABLE ci MOVE TO ’severname’ PHYSICAL. 5.
Passend zum Replikationsverfahren mu¨ssen im Falle eines Serverausfalls einige Fragmente wiederhergestellt werden. Dazu werden der Originaltabelle Spalten fu¨r die jeweiligen Cluster-Identifikatoren hinzugefu¨gt. Anhand der IDs ko¨nnen die entsprechenden Fragmente rekonstruiert werden: INSERT INTO ci SELECT * FROM rj WHERE clusterid=i Alternativ ist die Erstellung einer sogenannten LookupTabelle [TCJM12] mo¨glich, die zu jeder Cluster-ID die beteiligten Tupelidentifikatoren abspeichert. Diese beno¨tigt jedoch einen JOIN-Operator:
INSERT INTO ci SELECT * FROM ill JOIN lookup ON (lookup.tupleid= rj.tupleid)
WHERE lookup.clusterid=i Die Lookup-Tabelle hat sich daher als ineffizienter herausgestellt.
Wenn auf mehrere Tabellen innerhalb einer Anfrage zugegriffen wird und diese Tabellen Join-Attribute gemeinsam haben, kann durch abgeleitete Fragmentierung die Datenlokalita¨t fu¨r die Anfragen erho¨ht werden. Zum Beispiel sei zusa¨tzlich zur Tabelle ill eine Tabelle info gegeben, die zu jeder Patienten-ID Adressangaben entha¨lt. Eine mo¨gliche Anfrage wa¨re daher, die Angaben zu Krankheiten und Adressen zu kombinieren:
SELECT a.disease, a.patientid, b.address FROM ill AS a,info AS b WHERE disease=’cough’ AND b.patientid= a.patientid
Anhand der vorgegebenen prima¨ren Fragmentierung der Tabelle ill wird dann auch die Tabelle info fragmentiert, zum Beispiel fu¨r das Fragment Respiratory: INSERT INTO inforesp SELECT a.patientid, b.address FROM respiratory AS a, info AS b WHERE b.patientid = a.patientid
Daher kann dann im Folgenden auch die Anfrage, die Angaben zu Krankheiten und Adressen kombiniert, entsprechend umgeschrieben werden:
SELECT a.disease, a.patientid, b.address FROM respiratory AS a
JOIN inforesp AS b ON (a.patientid=b.patientid)
Flexible Anfragebeantwortung unterstu¨tzt Benutzer bei der Suche nach relevanten Informationen. In unserem Verfahren wird auf eine Ontologie zuru¨ckgegriffen aufgrund derer semantisch a¨hnliche Werte in einem Cluster zusammengefasst werden ko¨nnen. Eine Fragmentierung der Originaltabelle anhand der Cluster ermo¨glichst ein effizientes Laufzeitverhalten der flexiblen Anfragebeantwortung. Durch einige Metadaten (Root-Tabelle, Similarities-Tabelle, zusa¨tzliche Spalte fu¨r Cluster-ID) werden alle typischen Datenbankoperationen unterstu¨tzt.
Zuku¨nftig soll insbesondere das dynamische Anpassen der Fragmente untersucht werden: da sich durch Einfu¨gungen und Lo¨schungen die Gro¨ßen der Fragmente stark a¨ndern ko¨nnen, mu¨ssen zur Laufzeit Fragmente verschoben werden, sowie gegebenenfalls zu kleine Fragmente in ein gro¨ßeres vereinigt werden beziehungsweise zu große Fragmente in kleinere aufgespalten werden.