Name
Abstract | ||
|---|---|---|
We describe an algorithm that evaluates queries over probabilistic databases using Mobius' inversion formula in incidence algebras. The queries we consider are unions of conjunctive queries (equivalently: existential, positive First Order sentences), and the probabilistic databases are tuple-independent structures. Our algorithm runs in PTIME on a subset of queries called "safe" queries, and is complete, in the sense that every unsafe query is hard for the class FP#P. The algorithm is very simple and easy to implement in practice, yet it is non-obvious. Mobius' inversion formula, which is in essence inclusion-exclusion, plays a key role for completeness, by allowing the algorithm to compute the probability of some safe queries even when they have some subqueries that are unsafe. We also apply the same lattice-theoretic techniques to analyze an algorithm based on lifted conditioning, and prove that it is incomplete. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1807085.1807113 | PODS |
Keywords | Field | DocType |
conjunctive queries,incidence algebra,probabilistic database,first order | Discrete mathematics,Conjunctive query,Computer science,First order,Inversion (meteorology),Incidence algebra,P,Theoretical computer science,Probabilistic logic,Completeness (statistics),Probabilistic database | Conference |
Citations | PageRank | References |
30 | 1.09 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nilesh Dalvi | 1 | 1767 | 67.10 |
| Karl Schnaitter | 2 | 209 | 9.61 |
| Dan Suciu | 3 | 9625 | 1349.54 |