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: 7962
Venue: VLDB
Year: 1986
Pagerank: 0.00011437537
Overall Rank: 1,259 | 91.37%
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
282	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.0002242162
839	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00013692785
1,086	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB	0.00012252192
1,114	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00012118382
1,330	Efficient Transitive Closure Algorithms	1988	VLDB	0.00011140171
1,382	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010965236
2,076	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD	9.212586e-05
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
4,146	Efficiently Supporting Procedures In Relational Database Systems	1987	SIGMOD	6.8732593e-05
4,150	Commutativity and Its Role in the Processing of Linear Recursion	1989	VLDB	6.8705682e-05
5,341	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB	6.2602701e-05
6,840	Hybrid Transitive Closure Algorithms	1990	VLDB	5.7575344e-05
7,438	A Generalized Transitive Closure for Relational Queries	1988	PODS	5.6184826e-05
13,065	Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB	1993	VLDB	5.093636e-05
13,182	Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy	1987	VLDB	5.093636e-05
13,186	An Extended Disjunctive Normal Form Approach for Optimizing Recursive Logic Queries in Loosely Coupled Environments	1987	VLDB	5.093636e-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.00083340894
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00060089598
217	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00024458594

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,775	A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering	1990	VLDB
2	282	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD
3	1,382	Estimating the Size of Generalized Transitive Closures	1989	VLDB
4	2,076	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD
5	5,341	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB
6	1,086	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB
7	8,035	On Tree-Based Techniques for Query Evaluation	1992	PODS
8	1,330	Efficient Transitive Closure Algorithms	1988	VLDB
9	1,114	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB
10	7,438	A Generalized Transitive Closure for Relational Queries	1988	PODS