Open Access

Sebastian Lehrack

• In contrast to traditional data applications, many real-world scenarios nowadays depend on managing and querying huge volumes of uncertain and incomplete data. This new type of applications emerge, for example, when we integrate data from various sources, analyse social/biological/chemical networks or conduct privacy-preserving data mining. A very promising concept addressing this new kind of probabilistic data applications has been proposed in the form of probabilistic databases. Here, a tuple only belongs to its table or query answer with a specific likelihood. That probability expresses the uncertainty about the given data or the confidence in the answer. The most challenging task for probabilistic databases is query evaluation. In fact, there are even simple relational queries for which determining the occurrence probability of a single answer tuple is hard for #P. Lineage formulas constitute the central concept under investigation in this work. In short, the mechanism behind lineage formulas facilitates the representation andIn contrast to traditional data applications, many real-world scenarios nowadays depend on managing and querying huge volumes of uncertain and incomplete data. This new type of applications emerge, for example, when we integrate data from various sources, analyse social/biological/chemical networks or conduct privacy-preserving data mining. A very promising concept addressing this new kind of probabilistic data applications has been proposed in the form of probabilistic databases. Here, a tuple only belongs to its table or query answer with a specific likelihood. That probability expresses the uncertainty about the given data or the confidence in the answer. The most challenging task for probabilistic databases is query evaluation. In fact, there are even simple relational queries for which determining the occurrence probability of a single answer tuple is hard for #P. Lineage formulas constitute the central concept under investigation in this work. In short, the mechanism behind lineage formulas facilitates the representation and evaluation of events of the probability space, which is defined by a probabilistic database. On the basis of lineage formulas, we devise a framework that is designed as a combination of a relational database layer and an additional probabilistic query engine. In particular, the following three aspects are studied: (i) an efficient construction of lineage formulas, (ii) an orthogonal combination of lineage optimization techniques, which are performed within the relational database layer and the probabilistic query engine, and (iii) effective and compact data structures to represent lineage formulas within a probabilistic query engine. The developed framework provides a novel lineage construction method that is able to construct nested lineage formulas, to avoid large tuple sets within the relational database layer tuples, and to provide full relational algebra support. In addition, the proposed system completely resolves the conflict between the contradicting query plans optimized for the relational database layer and the probabilistic query engine.…
• Probabilistische Datenbanken standen in den letzten Jahren im Fokus intensiver Forschungsaktivitäten. Dies wurde durch eine Vielzahl von Anwendungsszenarien motiviert, in denen eine effiziente Verwaltung von großen, unsicheren Datenbeständen unabdingbar ist. Typische Anwendungsgebiete lassen sich leicht in den Bereichen der Datenextraktion und -integration, der wissenschaftlichen Datenauswertung und der Analyse von sensorischen und sozialen Netzwerken finden. In einer probabilistischen Datenbank wird jedes Datentupel mit einer Eintrittswahrscheinlichkeit annotiert. Diese verdeutlicht, mit welcher Wahrscheinlichkeit das jeweilige Tupel zu einer bestimmten Datentabelle bzw. zu einem berechneten Anfrageergebnis gehört. Für probabilistische Datenbanken ist die Berechnung der Eintrittswahrscheinlichkeit für ein Ergebnistupel die größte Herausforderung, da dieses Problem in der Komplexitätsklasse #P liegt. Diese Klasse beinhaltet alle Probleme, die mindestens so schwer sind wie das Zählen aller erfüllenden Modelle einerProbabilistische Datenbanken standen in den letzten Jahren im Fokus intensiver Forschungsaktivitäten. Dies wurde durch eine Vielzahl von Anwendungsszenarien motiviert, in denen eine effiziente Verwaltung von großen, unsicheren Datenbeständen unabdingbar ist. Typische Anwendungsgebiete lassen sich leicht in den Bereichen der Datenextraktion und -integration, der wissenschaftlichen Datenauswertung und der Analyse von sensorischen und sozialen Netzwerken finden. In einer probabilistischen Datenbank wird jedes Datentupel mit einer Eintrittswahrscheinlichkeit annotiert. Diese verdeutlicht, mit welcher Wahrscheinlichkeit das jeweilige Tupel zu einer bestimmten Datentabelle bzw. zu einem berechneten Anfrageergebnis gehört. Für probabilistische Datenbanken ist die Berechnung der Eintrittswahrscheinlichkeit für ein Ergebnistupel die größte Herausforderung, da dieses Problem in der Komplexitätsklasse #P liegt. Diese Klasse beinhaltet alle Probleme, die mindestens so schwer sind wie das Zählen aller erfüllenden Modelle einer aussagenlogischen Formel. Es gilt NP ⊆ #P. Traditionell werden Auswertungsverfahren für probabilistische Datenbanken in intensionale und extensionale Ansätze unterteilt. Intensionale Ansätze greifen auf die Konstruktion und Auswertung von Abstammungsformeln zurück. Auf der Basis von Abstammungsformeln, die das zentrale Untersuchungsobjekt dieser Arbeit darstellen, können Ereignisse des Wahrscheinlichkeitsraumes einer probabilistischen Datenbank repräsentiert werden. In der vorliegenden Dissertation wird ein System entworfen, welches als Kombination einer relationalen Datenbank-Schicht und einer zusätzlichen probabilistischen Auswertungskomponente konzipiert ist. Hierbei werden folgende drei Hauptaspekte untersucht: (i) die effiziente Konstruktion von Abstammungsformeln, (ii) die orthogonale Kombination von Optimierungstechniken und (iii) die Entwicklung von effektiven und kompakten Datenstrukturen für die Kodierung von Abstammungsformeln für die probabilistische Auswertungskomponente. Die entwickelten Techniken ermöglichen die schnelle Generierung von geschachtelten Abstammungsformeln, die Vermeidung von großen Tupel-Mengen innerhalb der relationen Datenbank-Schicht und die Unterstützung aller relationalen Anfrage-Operatoren.…