The complexity of query reliability
Erich Grädel, Yuri G. Gurevich, Colin Hirsch · 1998
The reliability of database queries on databases with uncertain information is studied, on the basis of a probabilistic model for unreliable databases. While it was already known that the reliability of quantifierfree queries is computable in polynomial time, we show here that already for conjunctive queries, the reliability may become highly intractable. We exhibit a conjunctive query whose reliability problem is complete for FP #P . We further show, that FP #P is the typical complexity level for the reliability problems of a very large class of queries, including all second-order queries. We study approximation algorithms and prove that the reliabilities of all polynomial-time evaluable queries can be efficiently approximated by randomized algorithms. Finally we discuss the extension of our approach to the more general metafinite database model where finite relational structures are endowed with functions into an infinite interpreted domain; in addition queries may use aggregate ...