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: 1439
Venue: PODS
Year: 2007
Pagerank: 6.8456588e-05
Overall Rank: 4,187 | 71.28%
DOI: 10.1145/1265530.1265572

Incoming Non-self Citations Over Time

Authors

1. Benny Kimelfeld (Hebrew University)
2. Yehoshua Sagiv (Hebrew University)

BibTeX Citation

@inproceedings{kimelfeld_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{Maximally Joining Probabilistic Data}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265572},
        doi = {10.1145/1265530.1265572},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kimelfeld, Benny and Sagiv, Yehoshua},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
238	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.0002369322
3,075	Matching Twigs in Probabilistic XML	2007	VLDB	7.7839831e-05
6,761	Efficiently Answering Durability Prediction Queries	2021	SIGMOD	5.7822533e-05
6,917	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.7400564e-05
7,522	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS	5.6029996e-05
7,550	Processing Top-k Join Queries	2010	VLDB	5.6011318e-05
8,761	Incorporating Constraints in Probabilistic XML	2008	PODS	5.3766157e-05
12,408	Transducing Markov Sequences	2010	PODS	5.093636e-05
12,571	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	5.093636e-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
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
557	The Theory of Probabilistic Databases	1987	VLDB	0.00016541752
1,176	Outerjoins as Disjunctions	1994	SIGMOD	0.00011809075
2,569	ProTDB: Probabilistic Data in XML	2002	VLDB	8.4090027e-05
2,791	Integrating Information by Outerjoins and Full Disjunctions (Extended Abstract)	1996	PODS	8.119781e-05
6,373	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.8946564e-05
8,071	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	5.4935818e-05
9,646	Computing Full Disjunctions	2003	PODS	5.243371e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,467	On the Complexity of Join Predicates	2001	PODS
2	4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
3	7,851	A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries	2021	PODS
4	3,453	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS
5	50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
6	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
7	5,225	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB
8	7,317	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS
9	7,706	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS
10	1,467	The Complexity of Evaluating Relational Queries	1983	PODS