Probabilistic Databases Under Open World Assumptions

Kontakt

Peter Lindner

Telefon

work
+49 241 80 21716

E-Mail

E-Mail
 

Probabilistische Datenbanken (PDBs) [1] werden verwendet, um große Mengen ungewisser (wahrscheinlichkeitsbehafteter) Daten abzuspeichern, zu verarbeiten und abzufragen. Solche Daten können etwa durch automatische Informationsextraktion, ungenaue Sensordaten oder durch Machine-Learning-Modelle zustande kommen. PDBs werden über die sogenannte “possible worlds”-Semantik (”mögliche-Welten”-Semantik) modelliert. Statt einer einzelnen relationalen Datenbank beschreibt eine PDB eine Wahrscheinlichkeitsverteilung über eine Sammlung traditioneller Datenbankinstanzen. Diese einzelnen Instanzen nennt man die “möglichen Welten” der PDB. Formal ausgedrückt ist eine PDB also ein Wahrscheinlichkeitsraum über Mengen relationaler Strukturen.

Erste Arbeiten zu probabilistischen Datenbanken reichen in die 80er und 90er Jahre zurück mit (unter anderem) den richtungsweisenden Arbeiten von Cavallo und Pittarelli [2], von Barbará et al. [3] und von Fuhr und Röllecke [4]. Das Theme gewann Mitte der 2000er Jahre neue Aufmerksamtkeit mit den Arbeiten von Dalvi und Suciu (siehe [5]), die für die Komplexität der Anfragebeantwortung einer natürlichen Klasse von Anfragen eine Dichotomie aufstellen konnten, die einfache und schwierige Anfragen klar voneinander trennt. Bis zu dieser Zeit, hatten die konkreten Begrifflichkeiten und Definitionen, die für probabilistische Datenbanken verwendet wurden zumeist zwei Eigenschaften gemein:

  • das zugrundeliegende Universum der Elemente (bzw. die Vereinigung aller zu den Attributen gehörenden “Universen”) haben eine feste, endliche Größe; und
  • das stochastische Modell ist durch Verwendung verschiedener Unabhängigkeitsannahmen sehr einfach gestrickt.

Parallel dazu und später wurden jedoch auch Systeme vorgeschlagen, die sogar kontinuierliche Wahrscheinlichkeitsverteilungen in den Daten modellieren können (zum Beispiel [6] und [7]). Auch wurde eine kontinuierliche, formale Semantik für Baumdatenbanken aufgestellt [8]. Dennoch unterliegen die probabilistischen Daten in diesen Modellen der sogenannten Closed-World-Assumption (etwa “Annahme einer abgeschlossenen Welt”) - diese besagt, dass jeder Fakt, der in der Datenbank nicht explizit mit einer positiven Wahrscheinlichkeit gelistet ist, fast sicher (d. h. mit Wahrscheinlichkeit 1) falsch ist. Ceylan et al. [9] weisen darauf hin, dass die Verwendung einer Open-World-Assumption für viele Anwendungsszenarien die bessere Wahl wäre und schlagen for, für bisher “unspezifizierte” Fakten ein Wahrscheinlichkeitsintervall anzunehmen. Trotzdem ist dieser Ansatz zunächst auch auf ein endliches Universum fixer Größe beschränkt und verwendet eine starke Unabhängigkeitsannahme. Obwohl die angenommene Unabhängigkeit im endlichen Rahmen keine echte Einschränkung ist, ist unklar, ob und wie diese Methodik so erweitert werden kann, dass sie auch ein unendliches Universum unterstützt.

Ziel dieses Forschungsprojektes ist es, das theoretische Fundament für probabilistische Datenbanken mit unendlichem Universum und komplexen Korrelationen zu legen bzw. zu schärfen und die Möglichkeiten zu untersuchen, in einem solchen Modell (approximativ) Anfragen unter Beachtung der Open-World-Assumption zu beantworten.

Gegenwärtig gibt es keine direkten Verbindungen zu den anderen Themen des Graduiertenkollegs.