Queries with Difference on Probabilistic Databases

Summary: Probability of queries with difference on tuple-independent databases; even safe differences may be unsafe for exact computation. An FPRAS for a broad class, limited by nesting of difference; outside this class some queries are inapproximable. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10169
Venue: VLDB
Year: 2011
Pagerank: 5.0731258e-05
Overall Rank: 6,415 | 55.38%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,804	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	4.9224361e-05
7,601	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	4.698961e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
31	Provenance Semirings	2007	PODS	0.0007857786
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292
101	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.0004955674
571	The Complexity of Query Reliability	1998	PODS	0.00019910719
627	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00018959005
706	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00017845469
1,268	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012931993
1,609	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011150935
2,656	Exploiting Shared Correlations in Probabilistic Databases	2008	VLDB	8.3620622e-05
3,314	Computing Query Probability with Incidence Algebras	2010	PODS	7.2318581e-05
4,442	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.186154e-05
4,720	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.973811e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,581	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	4.492241e-05
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292
8,132	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS	4.5784634e-05
7,162	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	4.8132423e-05
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
4,720	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.973811e-05
571	The Complexity of Query Reliability	1998	PODS	0.00019910719
6,169	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB	5.1716068e-05
4,442	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.186154e-05
7,163	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	4.8132033e-05