Maximally Joining Probabilistic Data

Summary: Defines "maximal answers" for probabilistic DBs: output minimally incomplete join results above a probability threshold to expose useful high-probability partial answers. Characterizes two enumeration tasks; data-tractable, but combined complexity: first NP-hard, second #P-hard, with efficient algorithms for several key cases. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1440
Venue: PODS
Year: 2007
Pagerank: 6.620459e-05
Overall Rank: 3,929 | 72.70%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Benny Kimelfeld
2. Yehoshua Sagiv

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
322	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00027523667
2,981	Matching Twigs in Probabilistic XML	2007	VLDB	7.7783189e-05
5,041	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS	5.7356447e-05
6,682	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	4.9596732e-05
6,959	Efficiently Answering Durability Prediction Queries	2021	SIGMOD	4.8805791e-05
7,660	Processing Top-k Join Queries	2010	VLDB	4.6814547e-05
8,555	Incorporating Constraints in Probabilistic XML	2008	PODS	4.4893996e-05
12,221	Transducing Markov Sequences	2010	PODS	4.1905499e-05
12,386	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415
453	The Theory Of Probabilistic Databases	1987	VLDB	0.00022801484
1,034	Outerjoins as Disjunctions	1994	SIGMOD	0.00014532543
2,783	ProTDB: Probabilistic Data in XML	2002	VLDB	8.1268718e-05
2,972	Integrating Information by Outerjoins and Full Disjunctions (Extended Abstract)	1996	PODS	7.7933514e-05
5,137	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.6653126e-05
8,076	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	4.587923e-05
9,512	Computing Full Disjunctions	2003	PODS	4.3299485e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,561	On the Complexity of Join Predicates	2001	PODS	5.4346872e-05
4,722	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.9646931e-05
7,538	A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries	2021	PODS	4.7121279e-05
4,926	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8184457e-05
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415
2,246	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2039096e-05
6,167	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB	5.1725053e-05
7,162	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	4.8085863e-05
7,604	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	4.6944524e-05
912	The Complexity of Evaluating Relational Queries	1983	PODS	0.00015374685