Probabilities and Provenance via Tree Decompositions
Cnrs Lifl, Cnrs Ltci, Cnrs Ipal · 2014
Query evaluation is hard on probabilistic databases, even on very simple probabilistic data frameworks and fairly simple queries, except for limited classes of safe queries. We study the problem from a different angle: rather than restricting the queries, at which conditions on the data can we tractably evaluate expressive queries on probabilistic instances? More specifically, we restrict the data treewidth, which we define on a circuit-based generalization of c-tables, in a natural way that restricts both the underlying instance and the annotations. We then leverage known tree-automata constructions to evaluate queries on bounded-treewidth instances, for such logical fragments as monadic second-order logic or frontier-guarded Datalog. We prove that we can compute in linear time a boundedtreewidth lineage circuit for automaton runs on tree decompositions of bounded-treewidth instances, so that the probability of the query can then be evaluated in linear-time data complexity (assuming unitcost arithmetic). We also show that a similar construction can yield a circuit representation of the semiring provenance for absorptive semirings in the case of monotone queries. For known probabilistic data frameworks, this results implies bounded-treewidth tractability of query evaluation on BID relational models, and sufficient tractability conditions for probabilistic XML models.