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.6954238e-05
Overall Rank: 4,262 | 71.36%
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.00023251151
3,133	Matching Twigs in Probabilistic XML	2007	VLDB	7.6103114e-05
6,743	Efficiently Answering Durability Prediction Queries	2021	SIGMOD	5.6892637e-05
7,060	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.6086666e-05
7,621	Processing Top-k Join Queries	2010	VLDB	5.4808989e-05
7,674	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS	5.4746904e-05
8,931	Incorporating Constraints in Probabilistic XML	2008	PODS	5.2534908e-05
12,705	Transducing Markov Sequences	2010	PODS	4.9769913e-05
12,867	Query Answering Techniques on Uncertain and Probabilistic Data	2008	SIGMOD	4.9769913e-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.00042926566
571	The Theory of Probabilistic Databases	1987	VLDB	0.00016204158
1,199	Outerjoins as Disjunctions	1994	SIGMOD	0.00011559895
2,619	ProTDB: Probabilistic Data in XML	2002	VLDB	8.2180287e-05
2,853	Integrating Information by Outerjoins and Full Disjunctions (Extended Abstract)	1996	PODS	7.9375001e-05
6,502	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.7622992e-05
8,241	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS	5.3686457e-05
9,795	Computing Full Disjunctions	2003	PODS	5.1241373e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,615	On the Complexity of Join Predicates	2001	PODS
2	4,390	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
3	8,014	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,737	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
7	5,342	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB
8	7,470	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS
9	7,862	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS
10	1,503	The Complexity of Evaluating Relational Queries	1983	PODS