We study the feasibility of the exact and approximate com-putation of the probability of relational queries with differ-ence on tuple-independent databases. We show that even the difference between two"safe" conjunctive queries with-out self-joins is"unsafe" for exact computation. We turn to approximation and design an FPRAS for a large class of re-lational 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. © 2011 VLDB Endowment.