On the Computation of the Transitive Closure of Relational Operators

Summary: Introduces divide-and-conquer algorithms for transitive closure and recursively defined views, reducing iteration depth from N to logarithmic. Analytical and experimental results show substantial performance gains for complete materialization over conventional fixed-point iteration. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h10426fd511552b87
Venue: VLDB
Year: 1986
Pagerank: 0.00011184757
Overall Rank: 1,287 | 91.35%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Yannis E. Ioannidis (University of California Berkeley)

BibTeX Citation

@article{ioannidis_vldb86,
        title = {{On the Computation of the Transitive Closure of Relational Operators}},
        author = {Ioannidis, Yannis E.},
        journal = {PVLDB},
        series = {{VLDB} '86},
        pages = {403--410},
        year = {1986}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
294	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00021927874
859	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00013418999
1,110	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB	0.00011984945
1,140	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00011853213
1,363	Efficient Transitive Closure Algorithms	1988	VLDB	0.00010914322
1,416	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010734049
2,109	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD	9.0238479e-05
3,020	Graph-Theoretic Methods In Database Theory	1990	PODS	7.7448163e-05
4,221	Efficiently Supporting Procedures In Relational Database Systems	1987	SIGMOD	6.7238906e-05
4,228	Commutativity and Its Role in the Processing of Linear Recursion	1989	VLDB	6.7165815e-05
5,451	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB	6.1243992e-05
6,981	Hybrid Transitive Closure Algorithms	1990	VLDB	5.6287975e-05
7,576	A Generalized Transitive Closure for Relational Queries	1988	PODS	5.4924986e-05
13,355	Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB	1993	VLDB	4.9793485e-05
13,472	Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy	1987	VLDB	4.9793485e-05
13,476	An Extended Disjunctive Normal Form Approach for Optimizing Recursive Logic Queries in Loosely Coupled Environments	1987	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081992507
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
225	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00023995155

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,937	A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering	1990	VLDB
2	294	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD
3	1,416	Estimating the Size of Generalized Transitive Closures	1989	VLDB
4	2,109	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD
5	1,110	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB
6	5,451	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB
7	8,195	On Tree-Based Techniques for Query Evaluation	1992	PODS
8	1,363	Efficient Transitive Closure Algorithms	1988	VLDB
9	1,140	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB
10	7,576	A Generalized Transitive Closure for Relational Queries	1988	PODS