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: 10170
Venue: VLDB
Year: 2011
Pagerank: 5.0682868e-05
Overall Rank: 6,410 | 55.46%
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,800	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	4.918071e-05
7,604	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	4.6944524e-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.00078516827
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415
103	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00049520051
572	The Complexity of Query Reliability	1998	PODS	0.00019888988
630	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00018942778
702	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00017848789
1,269	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012911894
1,612	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011142757
2,649	Exploiting Shared Correlations in Probabilistic Databases	2008	VLDB	8.3728762e-05
3,315	Computing Query Probability with Incidence Algebras	2010	PODS	7.2247513e-05
4,439	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.1806955e-05
4,722	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.9646931e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,578	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	4.4879347e-05
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415
8,134	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS	4.5740737e-05
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	4.8086254e-05
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05
4,722	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.9646931e-05
572	The Complexity of Query Reliability	1998	PODS	0.00019888988
6,167	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB	5.1725053e-05
4,439	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.1806955e-05
7,162	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	4.8085863e-05