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: h461094835d1538bf
Venue: PODS
Year: 2007
Pagerank: 6.6984258e-05
Overall Rank: 4,262 | 71.35%
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
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023258672
3,132	Matching Twigs in Probabilistic XML	2007	VLDB	7.6137556e-05
6,738	Efficiently Answering Durability Prediction Queries	2021	SIGMOD	5.6918011e-05
7,057	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.6113229e-05
7,615	Processing Top-k Join Queries	2010	VLDB	5.4834169e-05
7,668	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS	5.4772833e-05
8,923	Incorporating Constraints in Probabilistic XML	2008	PODS	5.2559789e-05
12,699	Transducing Markov Sequences	2010	PODS	4.9793485e-05
12,861	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	4.9793485e-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
51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00042936299
571	The Theory of Probabilistic Databases	1987	VLDB	0.00016210743
1,198	Outerjoins as Disjunctions	1994	SIGMOD	0.00011565328
2,617	ProTDB: Probabilistic Data in XML	2002	VLDB	8.2219007e-05
2,853	Integrating Information by Outerjoins and Full Disjunctions (Extended Abstract)	1996	PODS	7.9412355e-05
6,499	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.7650247e-05
8,234	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	5.3711847e-05
9,789	Computing Full Disjunctions	2003	PODS	5.1265605e-05

Semantically Similar Papers

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