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: 1280
Venue: PODS
Year: 2003
Pagerank: 5.243371e-05
Overall Rank: 9,646 | 33.83%
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,075	Matching Twigs in Probabilistic XML	2007	VLDB	7.7839831e-05
4,123	Integrating Data Lake Tables	2023	VLDB	6.8878137e-05
4,187	Maximally Joining Probabilistic Data	2007	PODS	6.8456588e-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

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.0007727299
742	Independent Database Schemas (Extended Abstract)	1982	PODS	0.00014426824
1,176	Outerjoins as Disjunctions	1994	SIGMOD	0.00011809075
1,887	Extending the Algebraic Framework of Query Processing to Handle Outerjoins	1984	VLDB	9.5347906e-05
2,603	LORE: A Lightweight Object REpository for Semistructured Data	1996	SIGMOD	8.3535371e-05
2,671	On The Integrity Of Databases With Incomplete Information	1986	PODS	8.2736086e-05
2,791	Integrating Information by Outerjoins and Full Disjunctions (Extended Abstract)	1996	PODS	8.119781e-05
3,263	Hypergraph based reorderings of outer join queries with complex predicates	1995	SIGMOD	7.584572e-05
4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.6623097e-05
6,501	Representing and Querying XML with Incomplete Information	2001	PODS	5.8604724e-05

Semantically Similar Papers

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