@phdthesis{Lehrack2016, author = {Lehrack, Sebastian}, title = {Efficient and flexible lineage construction for probabilistic databases}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-40460}, school = {BTU Cottbus - Senftenberg}, year = {2016}, abstract = {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 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.}, subject = {Probabilistic database; Lineage formula; Query evaluation; Uncertainty; Query optimization; Probabilistische Datenbank; Abstammungsformel; Anfrageauswertung; Unsicherheit; Anfrageoptimierung; Probabilistisches Datenbanksystem; Unsicherheit}, language = {en} }