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.

Provided by: Association for Computing Machinery Topic: Data Management Date Added: Mar 2011 Format: PDF

Find By Topic