The theory of infinite probabilistic databases

Lindner, Peter; Grohe, Martin (Thesis advisor); Kimelfeld, Benny (Thesis advisor)

Aachen : RWTH Aachen University (2021)
Doktorarbeit

Dissertation, RWTH Aachen University, 2021

Kurzfassung

Probabilistische (relationale) Datenbanken erweitern das relationale Datenbankmodell um ein Konzept von Unsicherheit, das in Form von Wahrscheinlichkeitsverteilungen ausgedrückt wird. Solch eine Erweiterung ist in einer Reihe von Anwendungsszenarien sinnvoll und nützlich, in denen inhärent Unsicherheit über das genaue Aussehen der Daten besteht, oder die von der Einführung neuer Unsicherheit profitieren. Das Standard-Modell probabilistischer Datenbanken basiert auf einem "Mögliche Welten"-Ansatz, der alle tatsächlich möglichen Ausprägungen der Datenmenge mit Wahrscheinlichkeiten assoziiert. Obwohl Datenbanken, Logik und stochastische Modelle in der Regel über unendlichen Universen definiert sind, zum Beispiel den reellen Zahlen, betrachtet das herkömmliche Modell nur diskrete Wahrscheinlichkeitsräume über endliche vielen Fakten.In dieser Arbeit erweitern wir den formalen "Mögliche Welten"-Ansatz für probabilistische Datenbanken ins (überabzählbar) Unendliche. Dies erzeugt eine Reihe von neuen, nichttrivialen Problemen und Fragestellungen, die der Klärung bedürfen, allen voran, die Konstruktion geeigneter Wahrscheinlichkeitsräume und die Wohldefiniertheit von Anfragesemantiken. Unser hierzu entwickeltes Modell der Standard-probabilistischen Datenbanken basiert auf dem Begriff der endlichen Punktprozesse aus der Wahrscheinlichkeitstheorie, und wir zeigen, dass dieses Modell tatsächlich die gewünschten Eigenschaften aufweist. Zusätzlich zum "Mögliche Welten"-Ansatz an sich spielen in endlichen probabilistischen Datenbanken gewisse Unabhängigkeitsannahmen eine zentrale Rolle, die wir daher auch für unendliche probabilistische Datenbanken untersuchen. Hierbei charakterisieren wir die Existenz solcher probabilistischen Datenbanken und führen zentrale neue Begrifflichkeiten für Unabhängigkeitsannahmen in verschiedenen neuen Situationen ein. Dies ist erneut auf Konzepte der Punktprozesstheorie zurückzuführen. In diesem Rahmen von Unabhängigkeitsannahmen stellen wir dann erste Studien zu Repräsentationen, Repräsentierbarkeit und Anfragebeantwortung vor. Schließlich befassen wir uns mit einer konkreten probabilistischen Sprache - generativem Datalog, die von Bárány, ten Cate, Kimelfeld, Olteanu und Vagena eingeführt wurde, um probabilistische Programmierung mit der deklarativen Natur von Datenbanksprachen zusammenzuführen. Diese Sprache eignet sich sowohl als Anfragesprache, als auch zur Repräsentation unendlicher probabilistscher Datenbanken. Wir betten generatives Datalog in unser Rahmenwerk der Standard-probabilistischen Datenbanken ein und statten sie mit einer verbesserten Semantik aus, die kontinuierliche Verteilungen und probabilistische Eingaben unterstützt. Mit unseren Ergebnissen und Konzepten begründen wir eine Theorie unendlicher probabilistischer Datenbanken und leisten einen wichtigen Beitrag zum Verständnis des mathematischen Hintergrunds probabilistischer relationaler Datenbanken im Allgemeinen.

Einrichtungen

• Graduiertenkolleg UnRAVeL [080060]
• Fachgruppe Informatik [120000]
• Lehrstuhl für Informatik 7 (Logik und Theorie diskreter Systeme) [122910]