Queries with Difference on Probabilistic Databases
The authors study the feasibility of the exact and approximate computation of the probability of relational queries with difference on tuple-independent databases. They show that even the difference between two "Safe" conjunctive queries without self-joins is "Unsafe" for exact computation. They 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 sub-queries. They give examples of inapproximable queries outside this class.