The Complexity of Query Reliability
Erich Gradel, Yuri Gurevich, Colin Hirch
Full Paper (PDF)

Abstract
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 reliabilitymay 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 forthe 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.

References

References, where available, link to the DBLP on the World Wide Web.

[1]
...
[2]
...
[3]
...
[4]
Richard M. Karp, Michael Luby: Monte-Carlo Algorithms for Enumeration and Reliability Problems. FOCS 1983: 56-64
[5]
...
[6]
Laks V. S. Lakshmanan, Nicola Leone, Robert Ross, V. S. Subrahmanian: ProbView: A Flexible Probabilistic Database System. TODS 22(3): 419-469(1997)
[7]
...
[8]
...
[9]
Michel de Rougemont: The Reliability of Queries. PODS 1995: 286-291
[10]
Raymond T. Ng, V. S. Subrahmanian: Stable Semantics for Probabilistic Deductive Databases. Information and Computation 110(1): 42-83(1994)
[11]
Leslie G. Valiant: The Complexity of Enumeration and Reliability Problems. SIAM J. Comput. 8(3): 410-421(1979)
[12]
Klaus W. Wagner: Some Observations on the Connection Between Counting an Recursion. TCS 47(3): 131-147(1986)
[13]
Esteban Zimányi: Query Evaluation in Probabilistic Relational Databases. TCS 171(1-2): 179-219(1997)
BIBTEX

@inproceedings{DBLP:conf/pods/GradelGH98,
author = {Erich Gr{\"a}del and
Yuri Gurevich and
Colin Hirch},
title = {The Complexity of Query Reliability},
booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-966-3},
pages = {227-234},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}


DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).