Approximate Lifted Inference with Probabilistic Databases

Summary: Approximate evaluation of #P-hard queries in probabilistic DBs via upper-bound plans; take the minimum. Schema-aware pruning keeps essential plans; safety iff a single plan, generalizing PTIME CQ results; 3 optimization techniques speed min-safe-plan evaluation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11175
Venue: VLDB
Year: 2015
Pagerank: 5.1725053e-05
Overall Rank: 6,167 | 57.14%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Wolfgang Gatterbauer
2. Dan Suciu

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,161	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00013579831
2,494	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	8.6457436e-05
2,589	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	8.4868591e-05
4,162	SlimShot: In-Database Probabilistic Inference for Knowledge Bases	2016	VLDB	6.386842e-05
5,859	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	5.2963939e-05
6,685	Probabilistic Databases for All	2020	PODS	4.9591332e-05
6,996	Tractable Lineages on Treelike Instances: Limits and Extensions	2016	PODS	4.8629707e-05
8,334	Beta Probabilistic Databases: A Scalable Approach to Belief Updating and Parameter Learning	2017	SIGMOD	4.5390028e-05
8,578	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	4.4879347e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040465394
322	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00027523667
1,015	Tuffy: Scaling up Statistical Inference in Markov Logic Networks using an RDBMS	2011	VLDB	0.00014630577
1,972	Approximate Lineage for Probabilistic Databases	2008	VLDB	9.8937766e-05
2,424	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	8.8415494e-05
3,084	Knowledge Expansion over Probabilistic Knowledge Bases	2014	SIGMOD	7.5967738e-05
4,079	Towards High-Throughput Gibbs Sampling at Scale: A Study across Storage Managers	2013	SIGMOD	6.4621024e-05
4,722	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.9646931e-05
5,270	Probabilistic Databases with MarkoViews	2012	VLDB	5.5925747e-05
6,019	Linearized and Single-Pass Belief Propagation	2015	VLDB	5.2365238e-05
6,800	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	4.918071e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
572	The Complexity of Query Reliability	1998	PODS	0.00019888988
4,708	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	5.9763416e-05
8,578	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	4.4879347e-05
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05
6,410	Queries with Difference on Probabilistic Databases	2011	VLDB	5.0682868e-05
12,364	Query Evaluation with Soft-Key Constraints	2008	PODS	4.1905499e-05
4,722	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.9646931e-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
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415