The reliability of queries (extended abstract)
Michel de Rougemont · 1995
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 D15, pQ (lIll), 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 PQ (.DB), when Q is defined in various logic-based languages.We show that pQ (DB) is computable in polynomial time when Q is defined in first-order logic and that PQ (Ill?) is P#p computable when Q is defined in Datalog.We then discuss possible ways of estimating the reliability y for natural distributions.