Bucket-Algorithmus

Der Eimeralgorithmus bzw. Bucket-Algorithmus ist im Rahmen der Informationsintegration ein Algorithmus zur effizienten Zusammenstellung von Sichten auf lokale Datenquellen (Local-as-View), die für eine Anfrage an das integrierte Gesamtsystem kombiniert werden müssen. Der Algorithmus wurde 1996 von Levy, Rajaraman und Ordille vorgestellt.

Grundsätzlich wächst die Anzahl der zu prüfenden Kombinationen exponentiell und das Problem der Prüfung NP-vollständig. Durch geschickte Vorauswahl lässt sich die Anzahl der Kombinationen jedoch reduzieren. Die Grundidee des Bucket-Algorithmus ist, dass jede Relation der Anfrage einen Bucket (Eimer) erhält. In jeden Eimer werden alle Sichten hinzugefügt, die für die Relation nutzbar sind. Geprüft werden nun nur alle Kombinationen von Anfrageumschreibungen, die aus jedem Bucket genau eine Sicht enthalten.

Ob eine Sicht für eine Relation nutzbar ist, hängt von ihren Teilzielen ab. Dabei müssen alle Anfrageattribute vorkommen und die Prädikate passend sein. Eine Sicht kann durchaus mehrfach in einem Bucket auftauchen, wenn sie zur Erfüllung mehrerer Teilziele passt.

Es lässt sich zeigen, dass der Bucket-Algorithmus immer eine Umschreibung der Anfrage ermittelt, die ein vollständiges Ergebnis liefert. Eine Erweiterung des Algorithmus ermittelt nur die besten Anfragepläne, so dass nicht alle Teilpläne ausgeführt werden müssen.

Alternativen zum Bucket-Algorithmus sind der Inverse-Rules-Algorithmus oder der MiniCon-Algorithmus.

Beispiel

Gegeben sei ein globales Schema mit folgenden Relationen:

• Adresse: Ausweisnummer, Ort
• Person: Ausweisnummer, Name, Alter

sowie drei lokale Datenquellen mit folgenden Schemata:

• Q1: Ausweisnummer, Name, Ort
• Q2: Name, Ausweisnummer, Alter
• Q3: Ausweisnummer, Alter, Beruf

sowie drei Quellen, deren lokale Schemata als Sichten auf das globale Schema formuliert sind (siehe Beispiel unter Local-as-View):

CREATE VIEW S1 AS SELECT Person.Ausweisnummer, Person.Name, Adresse.Ort FROM Person, Adresse WHERE Person.Ausweisnummer = Adresse.Ausweisnummer

CREATE VIEW S2 AS SELECT Ausweisnummer, Name, Alter FROM Person

CREATE VIEW S3 AS SELECT Ausweisnummer, NULL, Alter FROM Person

Nun soll die folgende Anfrage auf das globale Schema umformuliert werden:

• SELECT Person.Alter, Adresse.Ort FROM Person, Adresse WHERE Person.Ausweisnummer=Adresse.Ausweisnummer

Die Anfrage lässt sich etwas übersichtlicher in Prolog (Programmiersprache) formulieren

Q(Alter,Ort) :- Person(Ausweisnummer,_,Alter), Adresse(Ausweisnummer, Ort).

Nun werden zwei Buckets für die beiden in der Anfrage vorkommenden Relationen gebildet und mit den Sichten gefüllt, die für diese Relation nutzbar sind.

1. Bucket (Person): S1, S2, S3
2. Bucket (Adresse): S1

Es ergeben sich folgende Kombinationen

• S1 und S1
• S1 und S2
• S1 und S3

Die Views S1, S2 und S3 in Prolog-Schreibweise:

S1(Ausweisnummer, Name, Ort) :- Person(Ausweisnummer, Name, _), Adresse(Ausweisnummer, Ort)

S2(Ausweisnummer, Name, Alter) :- Person(Ausweisnummer, Name, Alter)

S3(Ausweisnummer, Alter) :- Person(Ausweisnummer, _, Alter)

Die Kombination von S1 mit S1 kann die Anfrage nicht beantworten, da der Kopf von S1 nicht das Anfrageattribut 'Alter' enthält. Es bleiben also zur Beantwortung der Anfrage die beiden anderen Kombinationen, die vereinigt werden. Es ergibt sich als Umschreibung der Anfrage:

SELECT S2.Alter, S1.Ort FROM S1, S2 
WHERE S1.Ausweisnummer=S2.Ausweisnummer
UNION
SELECT S3.Alter, S1.Ort FROM S1, S3 
WHERE S1.Ausweisnummer=S3.Ausweisnummer

Literatur

• Alon Levy: Answering queries using views: a survey. In: VLDB Journal 10, S. 270-294, 2001
• Alon Levy, Anand Rajaraman, Joann Ordille: Querying heterogeneous information sources using source descriptions. In: Proceedings of the 22nd VLDB Conference, Bombay, India. 1996