Die quantenlogik-basierte probabilistische Ähnlichkeitsanfragesprache QSQL2 soll vorgestellt werden. Dabei liegt das Hauptaugenmerk auf der Formulierung von Anfragen, welche “unsicher” sind, also nicht nur die traditionelle Boolesche Werte wahr und falsch annehmen können. QSQL2 kann Ungenauigkeiten sowohl auf Relationenebene als Eintrittswahrscheinlichkeiten, als auch auf Prädikatebene als Relevanzwahrscheinlichkeiten modellieren. Zusätzlich bietet die Sprache die Eigenschaft einer Booleschen Algebra, womit bekannte Äquivalenzen für die Anfragen nutzbar sind.
Wir wollen zunächst eine Klassifikation unterschiedlicher
Anfrageklassen erstellen. Mit diesen sollen semantische
Unterschiede zwischen Anfragen deutlich gemacht werden. Die
Entwicklung dieser Klassifikation ist in [
Wir werden sehen, dass QSQL2 eine Vielzahl von Anfragen aus allen vier Klassen auswerten kann und somit eine große Bandbreite für die Nutzung von unsicheren Anfragen bietet.
Nun soll das grundlegende Datenmodell der Anfragesprache QSQL2 beschrieben werden. Es kombiniert zwei Wahrscheinlichkeitsarten: (i) eine Relevanzwahrscheinlichkeit gegen eine Anfrage und (ii) eine Eintrittswahrscheinlichkeit für ein Datenobjekt. 3.1
Um die Relevanzwahrscheinlichkeit z. B. einer
UQonCDAnfrage auszudrücken, nutzen wir die probabilistische
Interpretation eines geometrischen Retrievalmodells, welches
auf dem quadrierten Kosinus-Ähnlichkeitsmaß basiert [
Das Retrievalmodell beschreibt die Auswertung eines einzelnen Tupels gegen eine gegebene Ähnlichkeitsanfrage. Wir beginnen unsere Beschreibung, indem wir uns ein Vektorraum vorstellen, welcher die Domäne für ein Tupel ist. Alle Attributwerte eines Tupels werden durch die Richtung eines entsprechenden Tupelvektors der Länge 1 ausgedrückt. Eine logik-basierte Bedingung korrespondiert zu einem spezifischen Vektorunterraum des Domänen-Vektorraums, auch Bedingungsraum genannt.
Das Resultat der Auswertung ist festgelegt durch den
minimalen Winkel zwischen Tupelvektor und Bedingungsraum.
Der quadrierte Kosinus dieses Winkels ist ein Wert aus dem
Intervall [
angefragtes Tupel t
Auswertung evalt(c) ↔ ↔ ↔ ↔
Vektorraum H
# Tupelvektor t Bedingungsraum cs[c] quadrierter Kosinus Winkels # zwischen# t und cs[c] (cos2(]( t , cs[c]))) raum gehört, kann man diese Bedingung als vollständige Übereinstimmung interpretierten (mit einem Score-Wert von 1). Im Gegensatz dazu entspricht der rechte Winkel von 90◦ zwischen Tupelvektor und Bedingungsraum keiner Übereinstimmung, der Score-Wert ist 0.
In frühreren Arbeiten [
evalt(c1) ∗ evalt(c2) evalt(¬c) := 1 − evalt(c).
Die Berechungsfunktion SF den Ähnlichkeitswert für atomare Ähnlichkeitsbedingungen berechnet, z. B. ‘Ort ≈ Berlin’.
Um die Unabhängigkeit der Teilbedingungen zu erhalten benötigt man die folgende Einschränkung: In einer gültigen Bedingung darf kein Attribut gegen mehr als eine Konstante in unterschiedlichen Ähnlichkeitsprädikaten angefragt werden. Daher ist die Bedingung ‘Ort≈Berlin ∧ Ort≈München’ nicht in QSQL2 erlaubt. Die Ähnlichkeitsprädikate ‘Ort ≈ Berlin’ und ‘Ort ≈ München’ können somit nicht für einen festen Ort gleichzeitig zu 1 ausgewertet werden (vollständige Übereinstimmung), was auch der Intuition entspricht. Diese Einschränkung entspricht der Unabhängigkeitsannahme von Tupel-unabhängigen bzw. Block-unabhängigen probabilistischen Datenbanken, welche im folgenden Abschnitt näher erläutert werden. 3.2
Die Possible-Worlds-Semantik wird von den meisten probabilistischen Datenbanken genutzt um Anfragen aus der Klasse CQonUD zu verarbeiten.
Als Grundlage dient eine Relation R ⊆ Dom(A1) × . . . × Dom(An) eines Relationenschemas attr(R) = {A1, . . . , An}, wobei Ai für ein Attribut steht. Dann definiert jede Tupelteilmenge von R einen eigenen Datenbankzustand, auch Welt von R genannt. Nehmen wir eine ein-attributige Relation R = {(1), (2)} an. Für dieses Beispiel sind die möglichen Zustände oder möglichen Welten durch Rw1 = {(1), (2)}, Rw2 = {(1)}, Rw3 = {(2)} und Rw4 = {} gegeben. Eine dieser möglichen Welten repräsentiert die eine, welche in Realtität vorkommt. Allerdings ist unbekannt, welche dies genau ist. Um diese Unsicherheit zu meistern, nutzen wir ein Wahrscheinlichkeitsmaß über der Menge aller möglichen Welten, welches aus einer probabilistischen Tabelle abgeleitet ist. Wir nennen eine Welt mit einer Eintrittswahrscheinlichkeit höher als 0 eine mögliche Welt oder possible world.
Im Allgemeinen ist die Semantik der genutzten
Wahrscheinlichkeitsmaße nicht vordefiniert. Um die
Wahrscheinlichkeitsberechnung zu vereinfachen nutzen wir die Semantik
der probabilistischen Block-unabhängigen Datenbanken [
In probabilistischen Block-unabhängigen Datenbanken ist jedes Tupel t mit einem Ereignis E[t] verknüpft, welches das Vorkommen oder das Nichtvorhandensein eines Tupels t in der Realität ausdrückt. Insbesondere unterscheiden wir zwei Arten von Ereignissen und Tupeln. Auf der einen Seite betrachten wir Basisereignisse welche von Basistupeln abgeleitet sind, welche durch initiale probabilistische Relationen gegeben sind. Außerdem berücksichtigen wir komplexe Ereignisse, welche mit während der Anfrageverarbeitung erzeugen komplexen Tupeln verknüpft sind. Diese Ereignisse bestimmen die Eintrittswahrscheinlichkeit der Ergebnistupel.
Dabei sind Tupel aus einem Block disjunkt zueinander, Tupel aus unterschiedlichen Blöcken sind unabhängig zu einander. Durch diese Vereinfachung erhält man eine relativ einfache Berechnungsvorschrift für komplexe Ereignisse.
Wenn die zugrundeliegende Ereignisstruktur unabhängig
ist, kann man die Wahrscheinlichkeiten eines komplexen
Ereignistupels wie in [
Pr(E[t1] ∧ E[t2]) := Pr(E[t1]) ∗ Pr(E[t2]) Pr(E[t1] ∨ E[t2]) := Pr(E[t1]) + Pr(E[t2])−
Pr(E[t1] ∧ E[t2])
Pr(¬E[t1]) := 1 − Pr(E[t1]). 3.3
Schlussendlich kombinieren wir die eingeführten probabilistischen Modelle, um beliebige Anfragen aus der Klasse UQonUD verarbeiten zu können. Dies wird getan, indem die Wahrscheinlichkeitsräume, welche Relevanz- und Eintrittswahrscheinlichkeiten repräsentieren, durch einen Produktwahrscheinlichkeitsraum vereinigt werden. Die Nutzung eines Produktwahrscheinlichkeitraumes kann durch die Klassifikation der Anfrageklasse UQonUD gerechtfertigt werden.
Wir nehmen also zuerst ein gegebenes Tupel als Datenbasis an, welches mit einer Eintrittswahrscheinlichkeit annotiert ist. Dann wenden wir zusätzlich eine Ähnlichkeitsbedingung an, um eine Relevanzwahrscheinlichkeit auf dieser Datenbasis zu erzeugen. So verhindern wir das Vermischen oder Überlappen von beiden Eingabewahrscheinlichkeiten. Somit nehmen wir an, dass beide Wahrscheinlichkeitsmaße unabhängig voneinander und in den kombinierten Produktwahrscheinlichkeitsraum eingebettet sind.
Um Ideen zu verdeutlichen und Beispielanfragen
anzugeben wollen wir ein laufendes Beispiel einführen. Es ist ein
vereinfachter Verbrechenslöser, welcher an ein Beispiel vom
Trio Projekt [
Die Datei der Kriminellen enthalt die Attribute name, status, sex, age und height jeder registrierten Person, wobei die Domänen für die Attribute status und sex {free, jail, parole} und {female, male} sind.
Die Aufzeichnung der Beobachtungen beinhaltet die Zeugenaussagen für ein spezielles Verbrechen, so dass jeder Zeuge nur genau eine Person mit entsprechenden Geschlecht (obs_sex), geschätztem Alter (obs_age) und geschätzter Größe (obs_height) sah. Jedes Aussagentupel in obs ist mit einem Konfidenzwert annotiert, welcher als Eintritts
Criminals (crim) status sex jail female free male free male height 1.63 1.83 1.76
Als ein Beispiel für eine Anfrage aus der Klasse UQonUD wollen wir eine Variante der letzten CQonUD-Anfrage (Listing 3) betrachten: “Bestimme alle Kriminellen, welche möglicherweise beobachtet wurden. Dies bedeutet, dass das Alter ähnlich zum beobachteten Alter ist und dass das beobachtete Geschlecht passend ist” (Listing 4). In dieser Anfrage kommt sowohl ein Ähnlichkeitsprädikat (≈), als auch eine probabilistische Relation (Observation) vor.
SELECT name FROM Criminals C WHERE C.status = ’free’
SELECT name FROM Criminals C WHERE C.status = ’free’ and C.age ≈ 30
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
Logische Anfragen: Ein großer Vorteil von QSQL2 ist, dass das zugrunde liegende theoretische Fundament eine Boolesche Algebra bildet, also viele bekannte mathematische Äquivalenzen wie z. B. Distributivität, Idempotenz und Absorption erfüllt sind. An dieser Stelle sollen einige dieser logischen Eigenschaften exemplarisch von QSQL2 für praxisrelevante Anfragen genutzt werden. Wie wir später noch in Abschnitt 5.4 sehen werden, erfüllen z. B. die FuzzyDatenbanken nicht alle diese logischen Eigenschaften, insofern sind einige der folgenden Anfragen trotz einfacher Syntax nicht selbstverständlich.
Oft macht es Sinn Implikationen der Form A → B auszudrücken, d.h. wenn die erste Aussage wahr ist, muss es die andere auch sein. Durch die bekannte Äquivalenz A → B ≡ ¬A ∨ B kann man diesen Junktor auch auf Anfragen mit Relevanz- und Eintrittswahrscheinlichkeiten anwenden. Analog verhält es sich mit der Äquivalenz A ↔ B. Bei ihr sind im Booleschen Fall entweder beide Variablen wahr oder beide sind falsch. Durch die Umformung A ↔ B ≡ A → B ∧ B → A ≡ (¬A ∨ B) ∧ (¬B ∨ A) ≡ (A ∧ B) ∨ (¬A ∧ ¬B) kann diese Aussage auch äquivalent in QSQL2 ausgedrückt werden.
QSQL2 bietet ebenfalls gewichtete Junktoren. So macht
es manchmal Sinn den Einfluss einer Teilbedingung
heraufoder herabzusetzen. In der Sprache gibt es deshalb jeweils
eine gewichtete Konjunktion, ausgedrückt durch and[θ1, θ2],
und eine gewichtete Disjunktion, ausgedrückt mit or[θ1, θ2].
Die Gewichtsvariablen θi sind reelle Zahlen aus dem
Intervall [
Man könnte sich vorstellen, dass die Identifizierung der Verdächtigen durch die Zeugen nicht eindeutig war, weil das Verbrechen bei Dunkelheit geschehen ist. So kann man folgende Variante der UQonUD-Anfrage in QSQL2 stellen: “Bestimme alle Kriminellen, welche möglicherweise beobachtet wurden. Dies bedeutet, dass das Alter ähnlich zum beobachteten Alter ist und dass die Größe ähnlich zur beobachteten Größe ist. Die Relevanz des beobachteten Größe ist doppelt so hoch wie die des geschätzten Alters.” (Listing 5).
SELECT name FROM Criminals C, Observation O WHERE C.sex = O.sex and C.age ≈ O.obs_age
5.
In den letzten Jahren wurden viele probabilistische
relationale Datenbankansätze vorgeschlagen [
Neben der Berechnungskomplexität ist die Ausdruckskraft ein signifikantes Vergleichsmerkmal. Im Folgenden werden drei unterschiedliche Ansätze beschrieben, wie probabilistische Datenbanken um Ähnlichkeitsprädikate erweitert werden können. 5.1 Ähnlichkeitsprädikate als Built-In-Prädikate
Fuhr und Rölleke schlagen vor die Bewertungsfunktion
eines Ähnlichkeitsprädikates durch eine separate
probabilistische Relation umzusetzen [
Leider gibt es bei diesem Ansatz ein Problem bei der Konstruktion der Ähnlichkeitsfunktion SF. Die Funktion repräsentiert ein Ähnlichkeitsprädikat, aber bzgl. der Auswertung ist es kein unabhängiges Konzept, sondern unterliegt den selben Regeln wie alle probabilistische Relationen. So müssen die Tupel unabhängige Basisereignisse bilden, damit man geeignete Aggregationsfunktionen anwenden kann. Die Unabhängigkeit der Tupel in einer SF-Relation ist aber nicht gegeben. Fuhr und Rölleke schlagen daher vor nur Anfragen zu nutzen, in denen keine Tupel aus der selben SF-Relation kombiniert werden. Deshalb kann keine SF-Relation mehr als einmal in einer Anfrage vorkommen und Projektionen können nicht mehr beliebig genutzt werden. 5.2 Ähnlichkeitsprädikate als Wahrscheinlichkeit von Relationen
Der letzte Ansatz nutzte Ähnlichkeitsprädikate wie
probabilistische Relationen, welche während der
Anfrageauswertung eingebaut werden. Im Gegensatz dazu schlagen Dalvi
und Suciu [
Dieser Ansatz arbeitet nur auf Anfragen mit konjunktivverknüpften Ähnlichkeitsprädiaten. Schon bei einer einfachen Disjunktion von Ähnlichkeitsprädiaten, welche sich auf unterschiedliche Relationen beziehen, ist es nicht mehr möglich, die Auswertung der disjunktiven Ähnlichkeitsbedingung aufzuspalten und hinunter in die entsprechenden Relationen zu schieben. 5.3
Ähnlichkeitsprädikate auf Attributebene
In anderen Modellen wie [
Fuzzy-Datenbanken wie FSQL [
Außerdem bildet die Fuzzylogik [
Wir fassen zusammen, dass im Gegensatz zu QSQL2 die
anderen Ansätze [
In dieser Arbeit wurde die quantenlogik-basierte probabilistische Ähnlichkeitsanfragesprache QSQL2 vorgestellt. Ihre Grundlagen wurden kurz dargelegt, ihre Syntax an Beispielen anschaulich gemacht und ihre Besonderheiten demonstriert.
Im Gegensatz zu probabilistischen Datenbanken ist die Integration und Nutzung von Ähnlichkeitsprädikaten in mehr Fällen möglich. Die zusätzlichen Eigenschaften einer Booleschen Algebra wie Idempotenz oder Distributibität ermöglichen bessere Resultate als z. B. bei Fuzzylogik-basierte Sprachen. Das mathematisch Fundament ermöglicht die Interpretation der Ergebnisse als Wahrscheinlichkeiten, was sie anschaulicher und verständlicher macht.
Danksagung: Diese Arbeit wurde durch die Förderung SCHM 1208/11 – 1 der Deutschen Forschungsgemeinschaft (DFG) unterstützt.