Computing Full Disjunctions

Summary: Full disjunctions: commutative/associative alternative to outerjoins—all non‑Cartesian subset‑joins minus subsumed tuples; evaluation under or/weak semantics reducible to weak semantics and polynomial in query, database and output sizes. Projection/non‑null selection polytime for γ‑acyclic schemes, NP‑hard in general; weak semantics extends full disjunctions to arbitrary join conditions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hac640e2edab9dd24
Venue: PODS
Year: 2003
Pagerank: 5.1241373e-05
Overall Rank: 9,795 | 34.17%
DOI: 10.1145/773153.773162

Incoming Non-self Citations Over Time

Authors

1. Yaron Kanza (Hebrew University)
2. Yehoshua Sagiv (Hebrew University)

BibTeX Citation

@inproceedings{kanza_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{Computing Full Disjunctions}},
        url = {https://dl.acm.org/doi/10.1145/773153.773162},
        doi = {10.1145/773153.773162},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kanza, Yaron and Sagiv, Yehoshua},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,133	Matching Twigs in Probabilistic XML	2007	VLDB	7.6103114e-05
4,159	Integrating Data Lake Tables	2023	VLDB	6.7687144e-05
4,262	Maximally Joining Probabilistic Data	2007	PODS	6.6954238e-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

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
10	Extending the Data Base Relational Model to Capture More Meaning	1979	SIGMOD	0.00075910134
771	Independent Database Schemas (Extended Abstract)	1982	PODS	0.00014097455
1,199	Outerjoins as Disjunctions	1994	SIGMOD	0.00011559895
1,936	Extending the Algebraic Framework of Query Processing to Handle Outerjoins	1984	VLDB	9.334734e-05
2,655	LORE: A Lightweight Object REpository for Semistructured Data	1996	SIGMOD	8.166934e-05
2,729	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.0855936e-05
2,853	Integrating Information by Outerjoins and Full Disjunctions (Extended Abstract)	1996	PODS	7.9375001e-05
3,268	Hypergraph based reorderings of outer join queries with complex predicates	1995	SIGMOD	7.4730983e-05
4,594	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.5106109e-05
6,630	Representing and Querying XML with Incomplete Information	2001	PODS	5.7264133e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,425	Complexity of Query Processing in Databases with OR-Objects	1989	PODS
2	4,262	Maximally Joining Probabilistic Data	2007	PODS
3	2,853	Integrating Information by Outerjoins and Full Disjunctions (Extended Abstract)	1996	PODS
4	8,241	An Incremental Algorithm for Computing Ranked Full Disjunctions	2005	PODS
5	13,289	Normalizing Incomplete Databases	1995	PODS
6	8,020	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS
7	7,900	On the complexity of division and set joins in the relational algebra	2005	PODS
8	6,198	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD
9	1,503	The Complexity of Evaluating Relational Queries	1983	PODS
10	6,502	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB