DBScholar

Back to papers

A Study of Transitive Closure As a Recursion Mechanism

Summary: Linearly recursive queries collapse to transitive closure, possibly wrapped by relational-algebra operations. Even with repeated variables and constants, the equivalence holds, guiding TC-centric language design and enabling efficient deductive-database implementations. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h9dde759cb8f634b6
Venue
SIGMOD
Year
1987
Pagerank
8.9903441e-05
Overall Rank
2,126 | 85.76%
DOI
10.1145/38713.38750

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{jagadish_sigmod87,
        title = {{A Study of Transitive Closure As a Recursion Mechanism}},
        author = {Jagadish, H V and Agrawal, Rakesh and Ness, Linda},
        series = {{SIGMOD} '87},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/38713.38750},
        url = {https://dl.acm.org/doi/10.1145/38713.38750},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank Citing Paper Year Venue Pagerank
299 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00021766741
1,142 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00011812263
2,078 One-Sided Recursions 1987 PODS 9.0607099e-05
3,030 Graph-Theoretic Methods In Database Theory 1990 PODS 7.7156987e-05
5,472 Distributed Transitive Closure Computations: The Disconnection Set Approach 1990 VLDB 6.10153e-05
7,002 Hybrid Transitive Closure Algorithms 1990 VLDB 5.6075959e-05
7,293 Efficient Identification of Implicit Facts in Incomplete OWL2-EL Knowledge Bases 2014 VLDB 5.5484494e-05
7,599 A Generalized Transitive Closure for Relational Queries 1988 PODS 5.4717527e-05
8,218 On Tree-Based Techniques for Query Evaluation 1992 PODS 5.3595692e-05
12,452 Slider: an Efficient Incremental Reasoner 2015 SIGMOD 4.9605343e-05
13,453 Semigroup techniques in recursive query optimization 1990 PODS 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank Cited Paper Year Venue Pagerank
18 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00058816744
67 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.0003786983
950 A Time Bound on the Materialization of Some Recursively Defined Views 1985 VLDB 0.00012888761
1,142 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00011812263
1,204 Data Independent Recursion in Deductive Databases 1986 PODS 0.00011517335
1,292 On the Computation of the Transitive Closure of Relational Operators 1986 VLDB 0.00011145435
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 306 A Graphical Query Language Supporting Recursion 1987 SIGMOD
2 2,112 Evaluation Of Database Recursive Logic Programs As Recurrent Function Series 1986 SIGMOD
3 9,382 Optimizing Recursive Queries in SQL 2005 SIGMOD
4 1,292 On the Computation of the Transitive Closure of Relational Operators 1986 VLDB
5 1,142 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB
6 9,647 A Theory of Regular Queries 2016 PODS
7 1,368 Efficient Transitive Closure Algorithms 1988 VLDB
8 13,495 Classification Of Recursive Formulas In Deductive Databases 1988 SIGMOD
9 1,423 Estimating the Size of Generalized Transitive Closures 1989 VLDB
10 7,599 A Generalized Transitive Closure for Relational Queries 1988 PODS