Queries with difference on probabilistic databases
Sanjeev Khanna, Sudeepa Roy, Val Tannen · Proceedings of the VLDB Endowment · 2011
We study the feasibility of the exact and approximate computation of the probability of relational queries with difference on tuple-independent databases. We show that even the difference between two "safe" conjunctive queries without self-joins is "unsafe" for exact computation. We turn to approximation and design an FPRAS for a large class of relational queries with difference, limited by how difference is nested and by the nature of the subtracted subqueries. We give examples of inapproximable queries outside this class.