SciDok

Eingang zum Volltext in SciDok

Lizenz

Dissertation zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-58146
URL: http://scidok.sulb.uni-saarland.de/volltexte/2014/5814/


Efficient querying and learning in probabilistic and temporal databases

Effizientes Anfragen und Lernen in probabilistischen und temporalen Datenbanken

Dylla, Maximilian

pdf-Format:
Dokument 1.pdf (3.110 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Datenbank , Zeitliches Datenbanksystem , Datalog , Konsistenz <Informatik> , Wahrscheinlichkeit , Überwachtes Lernen
Freie Schlagwörter (Deutsch): Probabilistische Datenbank
Freie Schlagwörter (Englisch): temporal database , probabilistic database , consistency constraints , learning , querying
Institut: Fachrichtung 6.2 - Informatik
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Hauptberichter: Weikum, Gerhard (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 09.05.2014
Erstellungsjahr: 2014
Publikationsdatum: 20.06.2014
Kurzfassung auf Englisch: Probabilistic databases store, query, and manage large amounts of uncertain information. This thesis advances the state-of-the-art in probabilistic databases in three different ways:
1. We present a closed and complete data model for temporal probabilistic databases and analyze its complexity. Queries are posed via temporal deduction rules which induce lineage formulas capturing both time and uncertainty.
2. We devise a methodology for computing the top-k most probable query answers. It is based on first-order lineage formulas representing sets of answer candidates. Theoretically derived probability bounds on these formulas enable pruning low-probability answers.
3. We introduce the problem of learning tuple probabilities which allows updating and cleaning of probabilistic databases. We study its complexity, characterize its solutions, cast it into an optimization problem, and devise an approximation algorithm based on stochastic gradient descent.
All of the above contributions support consistency constraints and are evaluated experimentally.
Kurzfassung auf Deutsch: Probabilistische Datenbanken können große Mengen an ungewissen Informationen speichern, anfragen und verwalten. Diese Doktorarbeit treibt den Stand der Technik in diesem Gebiet auf drei Arten vorran:
1. Ein abgeschlossenes und vollständiges Datenmodell für temporale, probabilistische Datenbanken wird präsentiert. Anfragen werden mittels Deduktionsregeln gestellt, welche logische Formeln induzieren, die sowohl Zeit als auch Ungewissheit erfassen.
2. Ein Methode zur Berechnung der k Anworten höchster Wahrscheinlichkeit wird entwickelt. Sie basiert auf logischen Formeln erster Stufe, die Mengen an Antwortkandidaten repräsentieren. Beschränkungen der Wahrscheinlichkeit dieser Formeln ermöglichen das Kürzen von Antworten mit niedriger Wahrscheinlichkeit.
3. Das Problem des Lernens von Tupelwahrscheinlichkeiten für das Aktualisieren und Bereiningen von probabilistischen Datenbanken wird eingeführt, auf Komplexität und Lösungen untersucht, als Optimierungsproblem dargestellt und von einem stochastischem Gradientenverfahren approximiert. All diese Beiträge unterstützen Konsistenzbedingungen und wurden experimentell analysiert.
Lizenz: Veröffentlichungsvertrag für Dissertationen und Habilitationen

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English