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: 10360
Venue: VLDB
Year: 2011
Pagerank: 5.8509088e-05
Overall Rank: 6,527 | 55.22%
DOI: 10.14778/3402707.3402741

Incoming Non-self Citations Over Time

Authors

1. Sanjeev Khanna (University of Pennsylvania)
2. Sudeepa Roy (University of Pennsylvania)
3. Val Tannen (University of Pennsylvania)

BibTeX Citation

@article{khanna_vldb11,
        title = {{Queries with Difference on Probabilistic Databases}},
        author = {Khanna, Sanjeev and Roy, Sudeepa and Tannen, Val},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {11},
        pages = {1051--1062},
        doi = {10.14778/3402707.3402741},
        url = {https://doi.org/10.14778/3402707.3402741},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,839	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	5.7576811e-05
7,706	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	5.5638493e-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
17	Provenance Semirings	2007	PODS	0.00059843817
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
574	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00016278855
644	The Complexity of Query Reliability	1998	PODS	0.00015367965
683	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00015005338
1,041	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS	0.00012453494
1,327	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011141552
2,460	Exploiting Shared Correlations in Probabilistic Databases	2008	VLDB	8.5505905e-05
3,229	Computing Query Probability with Incidence Algebras	2010	PODS	7.6209731e-05
4,136	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.8810237e-05
4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	6.7737212e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,476	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD
2	50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
3	7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD
4	8,241	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS
5	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
6	4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
7	644	The Complexity of Query Reliability	1998	PODS
8	4,136	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
9	5,225	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB
10	7,317	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS