The Complexity of Query Reliability
- Erich Grädel ,
- Yuri Gurevich ,
- Colin Hirsch
1998 ACM Symposium on Principles of Database Systems (PODS'98). |
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 quantifier-free 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 functions like in SQL. Our result that reliability problems of first-order queries have complexity FP#P also holds on this extended model.