|
|
|
@inproceedings{DBLP:conf/pods/Rougemont95,
author = {Michel de Rougemont},
title = {The Reliability of Queries},
booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, May 22-25, 1995, San Jose,
California},
publisher = {ACM Press},
year = {1995},
isbn = {0-89791-730-8},
pages = {286-291},
ee = {http://doi.acm.org/10.1145/212433.212479, db/conf/pods/Rougemont95.html},
crossref = {DBLP:conf/pods/95},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
We consider an unreliabable database as a random variable defined from a relational database with various probabilistic models. For a given query Q, we define its reliability on a database DB, rhoQ(DB), as the probability that the answer to Q on an unreliable random instance coincides with the answer to Q on DB.
We investigate the computational complexity of computing rhoQ(DB), when Q is defined in various logic-base d languages. We show that rhoQ(DB) is computable in polynomial time when Q is defined in first-order logic and that rhoQ(DB) is P#P computable when Q is defined in Datalog. We then discuss possible ways of est imating the reliability for natural distributions.
Copyright © 1995 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.