On the Optimal Approximation of Queries Using Tractable Propositional Languages
This paper investigates the problem of approximating conjunctive queries without self-joins on probabilistic databases by lower and upper bounds that can be computed more efficiently. The authors study bounds in the languages of read-once formulas, where every variable occurs at most once, and of read-once formulas in disjunctive normal form. They show equivalences of syntactic and model-theoretic characterisations of optimal bounds for unate formulas, and present algorithms that can enumerate them with polynomial delay. Such bounds can be computed by queries expressed using first-order queries extended with transitive closure and a special choice construct.