DBScholar

Back to papers

An Incremental Algorithm for Computing Ranked Full Disjunctions

Summary: Introduces IncrementalFD, an incremental algorithm for computing full disjunctions that reduces total runtime and offers lower cost for retrieving only k tuples (for any constant k). For a natural class of ranking functions it emits tuples in ranking order and supports block-based execution. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h3d2c0e180503a9cd
Venue
PODS
Year
2005
Pagerank
5.351182e-05
Overall Rank
8,259 | 44.64%
DOI
10.1145/1065167.1065180

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{cohen_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{An Incremental Algorithm for Computing Ranked Full Disjunctions}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065180},
        doi = {10.1145/1065167.1065180},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cohen, Sara and Sagiv, Yehoshua},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank Citing Paper Year Venue Pagerank
3,143 Matching Twigs in Probabilistic XML 2007 VLDB 7.5857903e-05
4,158 Integrating Data Lake Tables 2023 VLDB 6.7595989e-05
4,277 Maximally Joining Probabilistic Data 2007 PODS 6.67394e-05
6,514 Full Disjunctions: Polynomial-Delay Iterators in Action 2006 VLDB 5.7438288e-05
8,207 On the Complexity of Package Recommendation Problems 2012 PODS 5.3613986e-05
Previous Page 1 / 1 Next

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
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010688884
505 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00017162373
511 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017061618
796 On the Complexity of Bounded-Variable Queries 1995 PODS 0.00013890233
1,201 Outerjoins as Disjunctions 1994 SIGMOD 0.00011523243
1,712 Rank-aware Query Optimization 2004 SIGMOD 9.7961248e-05
2,861 Integrating Information by Outerjoins and Full Disjunctions (Extended Abstract) 1996 PODS 7.9122274e-05
9,828 Computing Full Disjunctions 2003 PODS 5.1074821e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 6,482 Output-sensitive Conjunctive Query Evaluation 2024 PODS
2 6,557 Ranked Enumeration of Join Queries with Projections 2022 VLDB
3 2,625 Evaluating Rank Joins with Optimal Cost 2008 PODS
4 12,726 Efficient Rank Join with Aggregation Constraints 2011 VLDB
5 8,036 Optimization of Multiple-Relation Multiple-Disjunct Queries 1988 PODS
6 9,828 Computing Full Disjunctions 2003 PODS
7 2,602 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB
8 5,506 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB
9 511 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB
10 6,514 Full Disjunctions: Polynomial-Delay Iterators in Action 2006 VLDB