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.6248763e-05
Overall Rank: 3,929 | 72.67%
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
321	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00027527389
2,978	Matching Twigs in Probabilistic XML	2007	VLDB	7.7845728e-05
5,043	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS	5.7411631e-05
6,681	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	4.9643102e-05
6,960	Efficiently Answering Durability Prediction Queries	2021	SIGMOD	4.8849367e-05
7,692	Processing Top-k Join Queries	2010	VLDB	4.6761366e-05
8,558	Incorporating Constraints in Probabilistic XML	2008	PODS	4.4937074e-05
12,213	Transducing Markov Sequences	2010	PODS	4.1945683e-05
12,378	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	4.1945683e-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.00057857292
450	The Theory Of Probabilistic Databases	1987	VLDB	0.00022822073
1,032	Outerjoins as Disjunctions	1994	SIGMOD	0.00014544529
2,774	ProTDB: Probabilistic Data in XML	2002	VLDB	8.134432e-05
2,966	Integrating Information by Outerjoins and Full Disjunctions (Extended Abstract)	1996	PODS	7.8002072e-05
5,141	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.6673499e-05
8,072	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	4.5922874e-05
9,511	Computing Full Disjunctions	2003	PODS	4.3340927e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,553	On the Complexity of Join Predicates	2001	PODS	5.439162e-05
4,720	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.973811e-05
7,539	A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries	2021	PODS	4.7166538e-05
4,953	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8085795e-05
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-05
6,169	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB	5.1716068e-05
7,163	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	4.8132033e-05
7,601	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS	4.698961e-05
915	The Complexity of Evaluating Relational Queries	1983	PODS	0.0001538509