[Back]

R. Ostrcil:
"Data representation, queries and updates in probabilistic and uncertain databases";
Supervisor: R. Pichler; Institut für Informationssysteme, Arbeitsbereich Datenbanken & Artificial Intelligence, 2008; final examination: 10-2008.

Probabilistic and uncertain databases have been a subject of research for more than a decade. This research is gaining more importance by current applications like mapping of large schemas and evaluation of erroneous data. Uncertain databases contain records with more than one alternative that cannot become true at the same time. Each possible combination of possibilities is addressed as a so called "possible world". Probabilistic databases additionally contain probability information for each occurrence of a possible world. For an end-user of an uncertain database there shall be no difference in the user.
The challenge is the representation of the data in an uncertain database. Because of the required storage capacity it is impossible to store all alternatives in a classical way. A method has to be developed to store the data of such databases in a succinct way. Also for the operations query, update, insert and delete an equivalent transformed operation is needed that works directly on the compact representation, because applying the original operation on all possible worlds would mean too much effort on storage and runtime.
The goal of this thesis was an in-depth comparison of three commonly used methods that were proposed in the literature for the representation of such databases. We provide a synopsis of the most important features of these methods in terms of their data representation mechanisms and their realization of query and update operations. The conclusion suggests one of the representations and it proposes areas that should be the subject of future research.

Das Gebiet der probabilistischen und ungewissen Datenbanken ist seit über einem Jahrzehnt Gegenstand der Forschung und gewinnt durch aktuelle Anwendungen zunehmend an Bedeutung. Beispiele dieser Anwendungen sind die Zusammenführung unterschiedlicher Datenbestände mit umfangreichen und komplexen Strukturen und die Auswertung fehlerbehafteter Daten. Ungewisse Datenbanken enthalten für zumindest einen Datensatz mehrere Möglichkeiten, die aber nicht gleichzeitig zutreffen können. Man spricht in diesem Zusammenhang von mehreren "möglichen Welten", die auf diese Weise dargestellt werden.
Probabilistische Datenbanken enthalten zusätzlich zu den alternativen Möglichkeiten auch eine Information darüber, mit welcher Wahrscheinlichkeit eine Alternative eintritt. Für den Benutzer einer probabilistischen Datenbank soll es keinen Unterschied in der Schnittstelle im Vergleich zu klassischen Datenbanksystemen geben.
Die Herausforderung besteht in der Repräsentation der Daten in ungewissen Datenbanken. Es ist aus Speicherplatzgründen unmöglich, alle möglichen Welten für sich zu speichern. Es muss daher nach Verfahren gesucht werden, wie derartige Datenbanken in kompakter Form repräsentiert werden können. Auch für die Operationen Abfrage und Änderung gilt es, transformierte und äquivalente Operationen zu finden, die direkt auf die kompakte Repräsentation angewandt werden, da eine Anwendung dieser Operationen auf alle möglichen Welten aus Zeit- und Aufwandsgründen ausscheidet.
Diese Diplomarbeit bietet einen eingehenden Vergleich von drei verbreiteten Verfahren, die in der Literatur für die Repräsentation von derartigen Datenbanken vorgeschlagen wurden. Es wird eine Zusammenschau der wichtigsten Eigenschaften dieser Verfahren in Bezug auf ihre Mechanismen der Datenrepräsentation und der Realisierung der Operationen Abfrage und Änderung geboten. Das Resümee gibt eine Empfehlung für eine der Darstellungen und für zukünftige Forschung.

databases, probabilistic, incertain, query, update