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: 11174
Venue: VLDB
Year: 2015
Pagerank: 5.1716068e-05
Overall Rank: 6,169 | 57.09%
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,204	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00013319541
2,501	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	8.6453446e-05
2,588	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	8.4909562e-05
4,164	SlimShot: In-Database Probabilistic Inference for Knowledge Bases	2016	VLDB	6.3923099e-05
5,858	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	5.2997454e-05
6,683	Probabilistic Databases for All	2020	PODS	4.9638979e-05
6,997	Tractable Lineages on Treelike Instances: Limits and Extensions	2016	PODS	4.8676446e-05
8,340	Beta Probabilistic Databases: A Scalable Approach to Belief Updating and Parameter Learning	2017	SIGMOD	4.5433598e-05
8,581	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	4.492241e-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.0040449103
321	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00027527389
1,014	Tuffy: Scaling up Statistical Inference in Markov Logic Networks using an RDBMS	2011	VLDB	0.00014640258
1,970	Approximate Lineage for Probabilistic Databases	2008	VLDB	9.896375e-05
2,365	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	8.9551432e-05
3,081	Knowledge Expansion over Probabilistic Knowledge Bases	2014	SIGMOD	7.6031501e-05
4,077	Towards High-Throughput Gibbs Sampling at Scale: A Study across Storage Managers	2013	SIGMOD	6.4678697e-05
4,720	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.973811e-05
5,266	Probabilistic Databases with MarkoViews	2012	VLDB	5.5972559e-05
6,015	Linearized and Single-Pass Belief Propagation	2015	VLDB	5.2415551e-05
6,804	A Dichotomy for Non-repeating Queries with Negation in Probabilistic Databases	2014	PODS	4.9224361e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
571	The Complexity of Query Reliability	1998	PODS	0.00019910719
4,706	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	5.9820914e-05
8,581	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	4.492241e-05
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
6,415	Queries with Difference on Probabilistic Databases	2011	VLDB	5.0731258e-05
12,356	Query Evaluation with Soft-Key Constraints	2008	PODS	4.1945683e-05
4,720	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.973811e-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
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292