Evaluation of relational algebra queries on probabilistic databases: tractability and approximation

Thesis

Query processing is a core task in probabilistic databases: Given a query and a database that encodes uncertainty in data by means of probability distributions, the problem is to compute possible query answers together with their respective probabilities of being correct. This thesis advances the state of the art in two aspects of query processing in probabilistic databases: complexity analysis and query evaluation techniques. A dichotomy is established for non-repeating, con- junctive relational algebra queries with negation that separates #P-hard queries from those with PTIME data complexity. A framework for computing proba- bilities of relational algebra queries is presented; the probability computation algorithm is based on decomposition methods and provides exact answers in the case of exhaustive decompositions, or anytime approximate answers with absolute or relative error guarantees in the case of partial decompositions. The framework is extended to queries with aggregation operators. An experimental evaluation of the proposed algorithms’ implementations within the SPROUT query engine complements the theoretical results. The SPROUT² system uses this query engine to compute answers to queries on uncertain, tabular Web data.

Authors: Fink, RD

• Publication date: 2014
• DOI: 10.5287/ora-dx1vv7kvd
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: database system; uncertain database; database; computational complexity; Probabilistic database
• Subjects: Probability; Applications and algorithms; Discrete mathematics (statistics); Computer science (mathematics); Scalable systems