=Paper=
{{Paper
|id=None
|storemode=property
|title=Die probabilistische Ähnlichkeitsanfragesprache QSQL2
|pdfUrl=https://ceur-ws.org/Vol-733/paper_saretz.pdf
|volume=Vol-733
|dblpUrl=https://dblp.org/rec/conf/gvd/SaretzL11
}}
==Die probabilistische Ähnlichkeitsanfragesprache QSQL2==
https://ceur-ws.org/Vol-733/paper_saretz.pdf
Die probabilistische Ähnlichkeitsanfragesprache QSQL2
Sascha Saretz und Sebastian Lehrack
Brandenburgischer Technische Universität Cottbus
Institut für Informatik
Postfach 10 13 44
D-03013 Cottbus, Germany
{ssaretz, slehrack}@informatik.tu-cottbus.de
ABSTRACT Um die Klassifikation aufzubauen identifizieren wir zwei
Die quantenlogik-basierte probabilistische Ähnlichkeitsan- signifikante Kriterien der Ausdrucksmächtigkeit der Anfra-
fragesprache QSQL2 soll vorgestellt werden. Dabei liegt das gesprache und der darunterliegenden relationalen Datenba-
Hauptaugenmerk auf der Formulierung von Anfragen, wel- sis:
che “unsicher” sind, also nicht nur die traditionelle Boo- (i) das Einbauen von Konzepten der Ungenauigkeit und
lesche Werte wahr und falsch annehmen können. QSQL2 Ähnlichkeit durch Ähnlichkeitsprädikate und
kann Ungenauigkeiten sowohl auf Relationenebene als Ein-
trittswahrscheinlichkeiten, als auch auf Prädikatebene als (ii) Tupel, welche Konfidenzwerte besitzen.
Relevanzwahrscheinlichkeiten modellieren. Zusätzlich bietet Wir benennen die Erfüllung einer dieser beiden Kriterien
die Sprache die Eigenschaft einer Booleschen Algebra, womit mit dem Term unsicher. Dies bedeutet, dass wir sichere oder
bekannte Äquivalenzen für die Anfragen nutzbar sind. unsichere Anfragen auf sicheren oder unsicheren relationa-
len Daten anwenden. Es ist dabei darauf zu achten, dass
1. MOTIVATION die Begriffe sicher und unsicher auch mit anderen Bedeu-
Im traditionellen relationalen Modell von Codd [4] sind tungen genutzt werden. In unserem Zusammenhang nutzen
Tupel entweder in einer Relation enthalten oder nicht. Im wir den Begriff unsicher für den Datenmodellierungsaspekt.
Gegensatz dazu können die Ansätze probabilistischer Daten- Wenn ein Nutzer nicht weiß, welche die korrekte Instanz
banken unpräzisen Daten verarbeiten, wobei jede mit einer oder der richtige Wert seiner Daten ist, kann er diese mit
Eintrittswahrscheinlichkeit annotiert ist. Es ist also unsi- einem Konfidenzwert annotieren, welcher die Eintrittswahr-
cher, ob ein Tupel in einem bestimmten Datenbankzustand scheinlichkeit darstellt.
(mögliche Welt) vorkommt oder nicht [5]. Indem die beiden Klassifikationsdimensionen orthogonal
Ein anderer Typ von Unsicherheiten sind Ähnlichkeitsprä- angewendet werden, erhält man vier Anfrageklassen. Diese
dikate wie “Größe≈1.80m”. Sie drücken unsichere Beziehun- Klassen werden im Folgenden kurz beschrieben.
gen zwischen Tupeln aus.
Dies sind zwei unterschiedliche Arten Unsicherheit zu for- (i) Sichere Anfragen auf sicheren Daten (CQonCD)
malisieren. Unsere Sprache QSQL2 erlaubt es beide Arten Die Klasse CQonCD (Certain Queries on Certain Data) ent-
zu nutzen, was dem Nutzer mehr Freiheiten beim Stellen hält alle Anfragen, welche durch Boolesche Bedingungen auf
von Anfragen bietet. Des Weiteren beachtet die QSQL2 die deterministischen relationalen Daten erzeugt werden. Die-
Gesetze der Booleschen Algebra, womit viele für den Nutzer se Anfragen können durch traditionelle relationale Anfrage-
sehr intuitive Äquivalenzen anwendbar sind. sprachen wie den relationalen Kalkül, die relationale Algebra
Um diese erweiterten Möglichkeiten zu verstehen, betrach- und SQL gestellt werden. Die folgenden drei Klassen enthal-
ten wir im nächsten Abschnitt zunächst eine Klassifikation ten CQonCD vollständig.
von Anfragearten.
(ii) Unsichere Anfragen auf sicheren Daten (UQonCD)
2. ANFRAGETYPEN Die Klasse UQonCD (Uncertain Queries on Certain Data)
Wir wollen zunächst eine Klassifikation unterschiedlicher steht für Anfragen, welche Ungenauigkeiten und Vagheit
Anfrageklassen erstellen. Mit diesen sollen semantische Un- unterstützen indem Ähnlichkeitsprädikate genutzt werden
terschiede zwischen Anfragen deutlich gemacht werden. Die können. Diese Prädikate basieren auf einer sicheren Daten-
Entwicklung dieser Klassifikation ist in [13] zu finden. grundlage. Das Evaluationsergebnis einer solchen Anfrage
kann durch einen score-Wert aus dem Intervall [0, 1] ange-
geben werden, welches den Grad der Erfüllung darstellt.
(iii) Sichere Anfragen auf unsicheren Daten (CQonUD)
Die Anfragen der Klasse CQonUD sind typisch für probabi-
listische Datenbanken mit Possible-Worlds-Semantik (siehe
Abschnitt 3.2). Diese Anfragen nutzen Boolesche Bedingun-
23rd GI-Workshop on Foundations of Databases (Grundlagen von Daten-
banken), 31.05.2011 - 03.06.2011, Obergurgl, Austria. gen auf unsicheren Daten mit einem Konfidenzwert aus dem
Copyright is held by the author/owner(s). Intervall [0, 1].
61
(iv) Unsichere Anfragen auf unsicheren Daten (UQonUD) raum gehört, kann man diese Bedingung als vollständige
Wenn man die Possible-Worlds-Semantik (iii) durch Bedin- Übereinstimmung interpretierten (mit einem Score-Wert von
gungen mit Ähnlichkeitsprädikaten (ii) kombiniert, erhält 1). Im Gegensatz dazu entspricht der rechte Winkel von 90◦
man eine Anfrage einer Klasse mit erweiterter Ausdrucks- zwischen Tupelvektor und Bedingungsraum keiner Überein-
kraft. In UQonUD können Ähnlichkeitsbedingungen auf Da- stimmung, der Score-Wert ist 0.
ten genutzt werden, welche nur in einem bestimmten unsi- In frühreren Arbeiten [12, 11] entwickelten wir eine pro-
cheren Datenbankzustand gegeben sind. Die Klasse UQonUD babilistische Interpretation für unser Retrievalmodell, da-
umfasst die ersten drei Klassen. her kann das geometrische Ähnlichkeitsmaß auch als Wahr-
scheinlichkeit der Relevanz aufgefasst werden. Aus diesem
Grund kann man die folgenden bekannten Auswertungsre-
Wir werden sehen, dass QSQL2 eine Vielzahl von Anfra-
geln für Wahrscheinlichkeiten anwenden, wenn alle beteilig-
gen aus allen vier Klassen auswerten kann und somit eine
ten Teilbedingungen c1 und c2 unabhängig sind:
große Bandbreite für die Nutzung von unsicheren Anfragen
bietet.
evalt (c) := SF(t, c), wenn c atomar ist
3. DATEN- UND ANFRAGEMODELL evalt (c1 ∧c2 ) := evalt (c1 ) ∗ evalt (c2 )
Nun soll das grundlegende Datenmodell der Anfragespra-
che QSQL2 beschrieben werden. Es kombiniert zwei Wahr- evalt (c1 ∨c2 ) := evalt (c1 )+evalt (c2 )−
scheinlichkeitsarten: (i) eine Relevanzwahrscheinlichkeit ge- evalt (c1 ) ∗ evalt (c2 )
gen eine Anfrage und (ii) eine Eintrittswahrscheinlichkeit für
ein Datenobjekt. evalt (¬c) := 1 − evalt (c).
3.1 Relevanzwahrscheinlichkeit Die Berechungsfunktion SF den Ähnlichkeitswert für atoma-
re Ähnlichkeitsbedingungen berechnet, z. B. ‘Ort ≈ Berlin’.
Um die Relevanzwahrscheinlichkeit z. B. einer UQonCD-
Um die Unabhängigkeit der Teilbedingungen zu erhalten
Anfrage auszudrücken, nutzen wir die probabilistische In-
benötigt man die folgende Einschränkung: In einer gültigen
terpretation eines geometrischen Retrievalmodells, welches
Bedingung darf kein Attribut gegen mehr als eine Konstante
auf dem quadrierten Kosinus-Ähnlichkeitsmaß basiert [12].
in unterschiedlichen Ähnlichkeitsprädikaten angefragt wer-
Die Hauptidee unseres Retrievalmodells ist die Anwendung
den. Daher ist die Bedingung ‘Ort≈Berlin ∧ Ort≈München’
von Vektorräumen, welche auch aus der Quantenmechanik
nicht in QSQL2 erlaubt. Die Ähnlichkeitsprädikate ‘Ort ≈
oder Quantenlogik bekannt sind, um Anfrageauswertung in
Berlin’ und ‘Ort ≈ München’ können somit nicht für einen
Datenbanken zu betreiben. Hier wollen wir eine Idee der
festen Ort gleichzeitig zu 1 ausgewertet werden (vollständige
grundlegenden Prinzipien vermitteln. Für diesen Zweck sind
Übereinstimmung), was auch der Intuition entspricht. Diese
Zusammenhänge zwischen Konzepten aus der Anfrageaus-
Einschränkung entspricht der Unabhängigkeitsannahme von
wertung und dem angewandten Retrievalmodell in Tabelle 1
Tupel-unabhängigen bzw. Block-unabhängigen probabilisti-
dargestellt.
schen Datenbanken, welche im folgenden Abschnitt näher
Das Retrievalmodell beschreibt die Auswertung eines ein-
erläutert werden.
zelnen Tupels gegen eine gegebene Ähnlichkeitsanfrage. Wir
beginnen unsere Beschreibung, indem wir uns ein Vektor- 3.2 Eintrittswahrscheinlichkeit
raum vorstellen, welcher die Domäne für ein Tupel ist. Alle
Die Possible-Worlds-Semantik wird von den meisten pro-
Attributwerte eines Tupels werden durch die Richtung ei-
babilistischen Datenbanken genutzt um Anfragen aus der
nes entsprechenden Tupelvektors der Länge 1 ausgedrückt.
Klasse CQonUD zu verarbeiten.
Eine logik-basierte Bedingung korrespondiert zu einem spe-
Als Grundlage dient eine Relation R ⊆ Dom(A1 ) × . . . ×
zifischen Vektorunterraum des Domänen-Vektorraums, auch
Dom(An ) eines Relationenschemas attr(R) = {A1 , . . . , An },
Bedingungsraum genannt.
wobei Ai für ein Attribut steht. Dann definiert jede Tu-
Das Resultat der Auswertung ist festgelegt durch den mi-
pelteilmenge von R einen eigenen Datenbankzustand, auch
nimalen Winkel zwischen Tupelvektor und Bedingungsraum.
Welt von R genannt. Nehmen wir eine ein-attributige Rela-
Der quadrierte Kosinus dieses Winkels ist ein Wert aus dem
tion R = {(1), (2)} an. Für dieses Beispiel sind die möglichen
Intervall [0, 1] und kann daher als Ähnlichkeitsmaß interpre-
Zustände oder möglichen Welten durch Rw1 = {(1), (2)},
tiert werden. Wenn also ein Tupelvektor zum Bedingungs-
Rw2 = {(1)}, Rw3 = {(2)} und Rw4 = {} gegeben. Eine die-
ser möglichen Welten repräsentiert die eine, welche in Real-
Anfrageauswertung CQQL Modell tität vorkommt. Allerdings ist unbekannt, welche dies genau
ist. Um diese Unsicherheit zu meistern, nutzen wir ein Wahr-
Wertebereich Dom(t) ↔ Vektorraum H
scheinlichkeitsmaß über der Menge aller möglichen Welten,
#»
angefragtes Tupel t ↔ Tupelvektor t welches aus einer probabilistischen Tabelle abgeleitet ist.
Bedingung c ↔ Bedingungsraum cs[c] Wir nennen eine Welt mit einer Eintrittswahrscheinlichkeit
höher als 0 eine mögliche Welt oder possible world.
t
Auswertung eval (c) ↔ quadrierter Kosinus des Im Allgemeinen ist die Semantik der genutzten Wahr-
Winkels
#» scheinlichkeitsmaße nicht vordefiniert. Um die Wahrschein-
zwischen t und cs[c]
2 #» lichkeitsberechnung zu vereinfachen nutzen wir die Semantik
(cos (]( t , cs[c]))) der probabilistischen Block-unabhängigen Datenbanken [2]
für QSQL2.
Table 1: Zusammenhänge zwischen Anfrageauswer- In probabilistischen Block-unabhängigen Datenbanken ist
tung und dem Retrieval-Modell CQQL jedes Tupel t mit einem Ereignis E[t] verknüpft, welches das
62
Vorkommen oder das Nichtvorhandensein eines Tupels t in Criminals (crim)
der Realität ausdrückt. Insbesondere unterscheiden wir zwei TID name status sex age height
t1 Bonnie jail female 21 1.63
Arten von Ereignissen und Tupeln. Auf der einen Seite be- t2 Clyde free male 32 1.83
trachten wir Basisereignisse welche von Basistupeln abge- t3 Al free male 47 1.76
leitet sind, welche durch initiale probabilistische Relationen
gegeben sind. Außerdem berücksichtigen wir komplexe Er- Table 2: Deterministische Informationen über regi-
eignisse, welche mit während der Anfrageverarbeitung er- strierte Kriminelle
zeugen komplexen Tupeln verknüpft sind. Diese Ereignisse
bestimmen die Eintrittswahrscheinlichkeit der Ergebnistu- Observation (obs)
pel. TID witness obs_sex obs_age obs_height Pr
Dabei sind Tupel aus einem Block disjunkt zueinander, t4 Amber male 30 1.85 0.3
Tupel aus unterschiedlichen Blöcken sind unabhängig zu ein- t5 Amber male 35 1.90 0.3
ander. Durch diese Vereinfachung erhält man eine relativ t6 Amber female 25 1.70 0.3
einfache Berechnungsvorschrift für komplexe Ereignisse. t7 Mike female 20 1.60 0.7
t8 Carl female 30 1.80 0.9
Wenn die zugrundeliegende Ereignisstruktur unabhängig
ist, kann man die Wahrscheinlichkeiten eines komplexen Er- Table 3: Zeugenaussagen annotiert mit Konfidenz-
eignistupels wie in [8] berechnen: werten
Pr(E[t1 ] ∧ E[t2 ]) := Pr(E[t1 ]) ∗ Pr(E[t2 ])
Pr(E[t1 ] ∨ E[t2 ]) := Pr(E[t1 ]) + Pr(E[t2 ])−
wahrscheinlichkeit aufgefasst werden kann. Wir nehmen an,
Pr(E[t1 ] ∧ E[t2 ]) dass Beobachtungen von unterschiedlichen Zeugen unabhän-
Pr(¬E[t1 ]) := 1 − Pr(E[t1 ]). gig voneinander sind (z. B. die Tupel t6 und t7 ) und dass
die Aussagen eines Zeugen disjunkt sind. Zum Beispiel kann
3.3 Kombinierter Wahrscheinlichkeitsraum nur maximal eins der Tupel t4 , t5 und t6 der Zeugin Amber
Schlussendlich kombinieren wir die eingeführten probabi- der Wahrheit entsprechen.
listischen Modelle, um beliebige Anfragen aus der Klasse
Anfragen bzgl. Klassifikation: Als erstes sollen Bei-
UQonUD verarbeiten zu können. Dies wird getan, indem die
spiele für die Anfrageklassen aus Abschnitt 2 erfolgen. Ein
Wahrscheinlichkeitsräume, welche Relevanz- und Eintritts-
typisches Beispiel für ein CQonCD-Anfrage ist “Bestimme al-
wahrscheinlichkeiten repräsentieren, durch einen Produkt-
le Kriminellen, welche den Status ’free’ haben”. Diese Anfra-
wahrscheinlichkeitsraum vereinigt werden. Die Nutzung ei-
ge ist in QSQL2 und SQL gleich, da keine Ähnlichkeitsprädi-
nes Produktwahrscheinlichkeitraumes kann durch die Klas-
kate oder probabilistischen Relationen benötigt werden (Li-
sifikation der Anfrageklasse UQonUD gerechtfertigt werden.
sting 1).
Wir nehmen also zuerst ein gegebenes Tupel als Daten-
basis an, welches mit einer Eintrittswahrscheinlichkeit an-
Eine UQonCD-Anfrage ist z. B. “Bestimme alle Kriminel-
notiert ist. Dann wenden wir zusätzlich eine Ähnlichkeitsbe-
len, welche den Status ‘free‘ haben und deren Altern un-
dingung an, um eine Relevanzwahrscheinlichkeit auf dieser
gefähr 30 ist”. Listing 2 zeigt das entsprechende Anfrage
Datenbasis zu erzeugen. So verhindern wir das Vermischen
in QSQL2-Syntax. Die Vagheit (“ungefähr”) wird durch ein
oder Überlappen von beiden Eingabewahrscheinlichkeiten.
Ähnlichkeitsprädikat (≈) umgesetzt.
Somit nehmen wir an, dass beide Wahrscheinlichkeitsmaße
unabhängig voneinander und in den kombinierten Produkt-
Als ein komplexeres Beispiel betrachten wir “Bestimme
wahrscheinlichkeitsraum eingebettet sind.
alle Kriminellen, welche möglicherweise beobachtet wurden.
Dies bedeutet, dass das Alter in einem Intervall von zehn
4. ANFRAGEN IN QSQL2 Jahren um das beobachtete Alter liegt und dass das beob-
Um Ideen zu verdeutlichen und Beispielanfragen anzuge- achtete Geschlecht passend ist”. Dieses Beispiel enthält eine
ben wollen wir ein laufendes Beispiel einführen. Es ist ein Boolesche Bedingung, während die Relation Observation
vereinfachter Verbrechenslöser, welcher an ein Beispiel vom probabilistisch ist (Listing 3).
Trio Projekt [15] angelehnt ist. Die Datenwerte sind aus [13].
Es gibt eine deterministische Tabelle Criminals (abgekürzt Als ein Beispiel für eine Anfrage aus der Klasse UQonUD
crim, Tabelle 2), welche ein Dossier von registrierten Kri- wollen wir eine Variante der letzten CQonUD-Anfrage (Li-
minellen enthält. Des Weiteren gibt es eine probabilistische sting 3) betrachten: “Bestimme alle Kriminellen, welche mög-
Tabelle Observations (abgekürzt obs, Tabelle 3) mit Zeugen- licherweise beobachtet wurden. Dies bedeutet, dass das Alter
aussagen und den zugehörigen Konfidenzen. ähnlich zum beobachteten Alter ist und dass das beobach-
Die Datei der Kriminellen enthalt die Attribute name, tete Geschlecht passend ist” (Listing 4). In dieser Anfrage
status, sex, age und height jeder registrierten Person, kommt sowohl ein Ähnlichkeitsprädikat (≈), als auch eine
wobei die Domänen für die Attribute status und sex {free, probabilistische Relation (Observation) vor.
jail, parole} und {female, male} sind.
Die Aufzeichnung der Beobachtungen beinhaltet die Zeu-
genaussagen für ein spezielles Verbrechen, so dass jeder Zeu- SELECT name FROM Criminals C
ge nur genau eine Person mit entsprechenden Geschlecht WHERE C.status = ’free’
(obs_sex), geschätztem Alter (obs_age) und geschätzter
Größe (obs_height) sah. Jedes Aussagentupel in obs ist Listing 1: CQonCD-Anfrage
mit einem Konfidenzwert annotiert, welcher als Eintritts-
63
SELECT name FROM Criminals C SELECT name FROM Criminals C, Observation O
WHERE C.status = ’free’ and C.age ≈ 30 WHERE C.height ≈ O.obs_height and[ 1, 0.5 ]
C.age ≈ O.obs_age
Listing 2: UQonCD-Anfrage
Listing 5: Beispiel für gewichtete Anfrage
SELECT name FROM Criminals C, Observation O
WHERE C.sex = O.sex and C.age > O.obs_age-5
and C.age < O.obs_age+5
5. VERGLEICHBARE ANSÄTZE
In den letzten Jahren wurden viele probabilistische rela-
tionale Datenbankansätze vorgeschlagen [3, 2, 7, 8, 6, 10, 1].
Listing 3: CQonUD-Anfrage
Sie unterstützen alle die Verarbeitung von probabilistischen
relationalen Daten, d.h. Anfragen aus der Klasse CQonUD.
Neben der Berechnungskomplexität ist die Ausdruckskraft
Logische Anfragen: Ein großer Vorteil von QSQL2 ist, ein signifikantes Vergleichsmerkmal. Im Folgenden werden
dass das zugrunde liegende theoretische Fundament eine Boo- drei unterschiedliche Ansätze beschrieben, wie probabilisti-
lesche Algebra bildet, also viele bekannte mathematische sche Datenbanken um Ähnlichkeitsprädikate erweitert wer-
Äquivalenzen wie z. B. Distributivität, Idempotenz und Ab- den können.
sorption erfüllt sind. An dieser Stelle sollen einige dieser
logischen Eigenschaften exemplarisch von QSQL2 für pra- 5.1 Ähnlichkeitsprädikate als Built-In-Prädi-
xisrelevante Anfragen genutzt werden. Wie wir später noch kate
in Abschnitt 5.4 sehen werden, erfüllen z. B. die Fuzzy- Fuhr und Rölleke schlagen vor die Bewertungsfunktion ei-
Datenbanken nicht alle diese logischen Eigenschaften, inso- nes Ähnlichkeitsprädikates durch eine separate probabilisti-
fern sind einige der folgenden Anfragen trotz einfacher Syn- sche Relation umzusetzen [8]. Diese Relation für eine Ähn-
tax nicht selbstverständlich. lichkeitsfunktion (SF-Relation) ersetzt das Ähnlichkeitsprä-
Oft macht es Sinn Implikationen der Form A → B aus- dikat und wird durch ein Join in die Anfrage integriert.
zudrücken, d.h. wenn die erste Aussage wahr ist, muss es Leider gibt es bei diesem Ansatz ein Problem bei der Kon-
die andere auch sein. Durch die bekannte Äquivalenz A → struktion der Ähnlichkeitsfunktion SF. Die Funktion reprä-
B ≡ ¬A ∨ B kann man diesen Junktor auch auf Anfragen sentiert ein Ähnlichkeitsprädikat, aber bzgl. der Auswertung
mit Relevanz- und Eintrittswahrscheinlichkeiten anwenden. ist es kein unabhängiges Konzept, sondern unterliegt den sel-
Analog verhält es sich mit der Äquivalenz A ↔ B. Bei ihr ben Regeln wie alle probabilistische Relationen. So müssen
sind im Booleschen Fall entweder beide Variablen wahr oder die Tupel unabhängige Basisereignisse bilden, damit man
beide sind falsch. Durch die Umformung A ↔ B ≡ A → B geeignete Aggregationsfunktionen anwenden kann. Die Un-
∧ B → A ≡ (¬A ∨ B) ∧ (¬B ∨ A) ≡ (A ∧ B) ∨ (¬A ∧ ¬B) abhängigkeit der Tupel in einer SF-Relation ist aber nicht
kann diese Aussage auch äquivalent in QSQL2 ausgedrückt gegeben. Fuhr und Rölleke schlagen daher vor nur Anfragen
werden. zu nutzen, in denen keine Tupel aus der selben SF-Relation
QSQL2 bietet ebenfalls gewichtete Junktoren. So macht kombiniert werden. Deshalb kann keine SF-Relation mehr
es manchmal Sinn den Einfluss einer Teilbedingung herauf- als einmal in einer Anfrage vorkommen und Projektionen
oder herabzusetzen. In der Sprache gibt es deshalb jeweils können nicht mehr beliebig genutzt werden.
eine gewichtete Konjunktion, ausgedrückt durch and[θ1 , θ2 ],
und eine gewichtete Disjunktion, ausgedrückt mit or[θ1 , θ2 ]. 5.2 Ähnlichkeitsprädikate als Wahrscheinlich-
Die Gewichtsvariablen θi sind reelle Zahlen aus dem Inter-
vall [0, 1], wobei ein Gewicht von 0 überhaupt keinen Einfluss
keit von Relationen
und ein Gewicht von 1 normalen Einfluss bedeutet. Der letzte Ansatz nutzte Ähnlichkeitsprädikate wie proba-
Man könnte sich vorstellen, dass die Identifizierung der bilistische Relationen, welche während der Anfrageauswer-
Verdächtigen durch die Zeugen nicht eindeutig war, weil das tung eingebaut werden. Im Gegensatz dazu schlagen Dalvi
Verbrechen bei Dunkelheit geschehen ist. So kann man fol- und Suciu [6] vor, die Wahrscheinlichkeiten für die genutz-
gende Variante der UQonUD-Anfrage in QSQL2 stellen: “Be- ten Ähnlichkeitsprädiakte vor der eigentlichen Anfrageaus-
stimme alle Kriminellen, welche möglicherweise beobachtet wertung auszuwerten. Die Ergebnisse dieser Vorberechnung
wurden. Dies bedeutet, dass das Alter ähnlich zum beobach- werden als Eintrittswahrscheinlichkeiten den Relationen zu-
teten Alter ist und dass die Größe ähnlich zur beobachteten gewiesen, auf welche die Ähnlichkeitsprädikate verweisen.
Größe ist. Die Relevanz des beobachteten Größe ist doppelt Dieser Ansatz arbeitet nur auf Anfragen mit konjunktiv-
so hoch wie die des geschätzten Alters.” (Listing 5). verknüpften Ähnlichkeitsprädiaten. Schon bei einer einfa-
chen Disjunktion von Ähnlichkeitsprädiaten, welche sich auf
unterschiedliche Relationen beziehen, ist es nicht mehr mög-
lich, die Auswertung der disjunktiven Ähnlichkeitsbedingung
aufzuspalten und hinunter in die entsprechenden Relationen
zu schieben.
SELECT name FROM Criminals C, Observation O
5.3 Ähnlichkeitsprädikate auf Attributebene
WHERE C.sex = O.sex and C.age ≈ O.obs_age In anderen Modellen wie [1, 10] können Wahrscheinlich-
keiten auch auf Attributebene modelliert werden. In diesem
Listing 4: UQonUD-Anfrage Fall ist es möglich, die Auswertung der Ähnlichkeitsprädi-
kate in den abgefragten Attribut vor der eigentlichen An-
64
frageauswertung zu speichern. Wie beim letzten Ansatz aus [5] N. N. Dalvi, C. Ré, and D. Suciu. Probabilistic Databa-
Abschnitt 5.2 funktioniert dies nur bei konjunktiv verknüpf- ses: Diamonds in the Dirt. Commun. ACM, 52(7):86–
ten Ähnlichkeitsprädikaten, weil die Wahrscheinlichkeit ei- 94, 2009.
nes Tupels konjunktiv aus den Wahrscheinlichkeiten der je-
weiligen Attributwerte berechnet wird. Deshalb können nicht [6] N. N. Dalvi and D. Suciu. Efficient query evaluation on
alle komplexen (z. B. disjunktiven) Kombinationen von Ähn- probabilistic databases. VLDB J., 16(4):523–544, 2007.
lichkeitsprädikaten ausgewertet werden. [7] D. Dey and S. Sarkar. A probabilistic relational model
5.4 Fuzzy-Datenbanken and algebra. ACM Trans. Database Syst., 21(3):339–
369, 1996.
Fuzzy-Datenbanken wie FSQL [9] können ebenfalls un-
sichere Anfragen auf einer unsicheren Datengrundlage be- [8] N. Fuhr and T. Rölleke. A Probabilistic Relational Al-
werkstelligen, allerdings sind sie kein probabilistisches Mo- gebra for the Integration of Information Retrieval and
dell. Die entsprechenden Tupel-Konfidenzwerte werden ein- Database Systems. ACM Trans. Inf. Syst., 15(1):32–66,
fach ohne Rücksicht auf die Semantik der Teilbedingungen 1997.
aggregiert. Es findet also keine Überprüfung auf Korrelatio-
nen statt, was das Ergebnis verfälschen kann. [9] J. Galindo, A. Urrutia, and M. Piattini. Fuzzy Databa-
Außerdem bildet die Fuzzylogik [16] keine Boolesche Alge- ses: Modeling, Design and Implementation. Idea Group
bra, da bekannte Äquivalenzen wie Idempotenz und Distri- Publishing, Hershey, USA, 2006.
butibität nicht erfüllt sind. Aufgrund des Fehlens dieser ele-
[10] C. Koch. MayBMS: A system for managing large uncer-
mentaren Eigenschaft sind Fuzzy-Datenbanken für uns nicht
tain and probabilistic databases. Managing and Mining
geeignet. Einen ausführlichen Vergleich zwischen Fuzzy- und
Uncertain Data, 2008.
Quantenlogik wird in [14] gegeben.
Wir fassen zusammen, dass im Gegensatz zu QSQL2 die [11] S. Lehrack, S. Saretz, and I. Schmitt. QSQLp :
anderen Ansätze [8, 6, 1, 10, 9] nicht beliebige, logik-basierte Eine Erweiterung der probabilistischen Many-World-
Ähnlichkeitsbedingungen beherrschen. Semantik um Relevanzwahrscheinlichkeiten. In T. Här-
der, W. Lehner, B. Mitschang, H. Schöning, and
6. ZUSAMMENFASSUNG H. Schwarz, editors, BTW, volume 180 of LNI, pages
In dieser Arbeit wurde die quantenlogik-basierte probabi- 494–513. GI, 2011.
listische Ähnlichkeitsanfragesprache QSQL2 vorgestellt. Ihre
[12] S. Lehrack and I. Schmitt. A Probabilistic Interpre-
Grundlagen wurden kurz dargelegt, ihre Syntax an Beispie-
tation for a Geometric Similarity Measure. In Procee-
len anschaulich gemacht und ihre Besonderheiten demon-
dings of the 11th European Conference on Symbolic and
striert.
Quantitative Approaches to Reasoning with Uncertain-
Im Gegensatz zu probabilistischen Datenbanken ist die In-
ty, ECSQARU ’11, June 2011.
tegration und Nutzung von Ähnlichkeitsprädikaten in mehr
Fällen möglich. Die zusätzlichen Eigenschaften einer Boole- [13] S. Lehrack and I. Schmitt. A unifying probability mea-
schen Algebra wie Idempotenz oder Distributibität ermögli- sure for logic-based similarity conditions on uncertain
chen bessere Resultate als z. B. bei Fuzzylogik-basierte Spra- relational data. In Proceedings of the 1st Workshop on
chen. Das mathematisch Fundament ermöglicht die Inter- New Trends in Similarity Search, NTSS ’11, pages 14–
pretation der Ergebnisse als Wahrscheinlichkeiten, was sie 19, New York, NY, USA, 2011. ACM.
anschaulicher und verständlicher macht.
[14] I. Schmitt, A. Nürnberger, and S. Lehrack. On the
Relation between Fuzzy and Quantum Logic. In Views
Danksagung: Diese Arbeit wurde durch die Förderung on Fuzzy Sets and Systems from Different Perspectives,
SCHM 1208/11 – 1 der Deutschen Forschungsgemeinschaft chapter 5. Springer-Verlag, 2009.
(DFG) unterstützt.
[15] J. Widom. Trio: A system for data, uncertainty, and li-
neage. In Managing and Mining Uncertain Data, pages
Literatur 113–148. Springer, 2008.
[1] P. Agrawal, O. Benjelloun, A. D. Sarma, C. Hayworth,
S. Nabar, T. Sugihara, and J. Widom. Trio: A System [16] L. A. Zadeh. Fuzzy sets. Information and Control,
for Data, Uncertainty, and Lineage. In 32nd Internatio- 8(3):338–353, June 1965.
nal Conference on Very Large Data Bases. VLDB 2006
(demonstration description), September 2006.
[2] D. Barbara, H. Garcia-Molina, and D. Porter. The ma-
nagement of probabilistic data. IEEE Trans. Knowl.
Data Eng., 4(5):487–502, 1992.
[3] R. Cavallo and M. Pittarelli. The theory of probabilistic
databases. In P. M. Stocker, W. Kent, and P. Hammers-
ley, editors, VLDB, pages 71–81. Morgan Kaufmann,
1987.
[4] E. F. Codd. A relational model of data for large shared
data banks. Commun. ACM, 13(6):377–387, 1970.
65