|
|
|
@inproceedings{DBLP:conf/pods/GradelGH98,
author = {Erich Gr{\"a}del and
Yuri Gurevich and
Colin Hirsch},
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-996-3},
pages = {227-234},
ee = {http://doi.acm.org/10.1145/275487.295124, db/conf/pods/GradelGH98.html},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
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.
Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.