Database Paper Browser

Back to papers

Distributed Transitive Closure Computations: The Disconnection Set Approach

Summary: Disconnection set approach enables distributed transitive closure via domain-fragmented subqueries for connectivity, shortest path, and BOM. Algebraic, update-friendly computation yields near-linear speedups on multi-processor deployments and generalizes to other domains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
7956
Venue
VLDB
Year
1990
Pagerank
5.8698466e-05
Overall Rank
4,855 | 66.26%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank Citing Paper Year Venue Pagerank
1,872 Diagnosis of Asynchronous Discrete Event Systems: Datalog to the Rescue! 2005 PODS 0.00010255586
2,134 Incremental Evaluation of Rules and its Relationship to Parallelism 1991 SIGMOD 9.4690121e-05
3,113 Parallelism in a Main-Memory DBMS: The performance of PRISMA/DB 1992 VLDB 7.5433318e-05
12,487 Randomized Algorithms for Data Reconciliation in Wide Area Aggregate Query Processing 2007 VLDB 4.1905499e-05
12,881 Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB 1993 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank Cited Paper Year Venue Pagerank
9 Implementation Techniques For Main Memory Database Systems 1984 SIGMOD 0.001426258
157 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.0004048407
255 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00030342925
792 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016580866
885 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015565543
1,078 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014223265
1,905 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 0.00010142772
4,320 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.2822407e-05
5,754 A Parallel Processing Strategy for Evaluating Recursive Queries 1986 VLDB 5.3391931e-05
6,664 A File Structure Supporting Traversal Recursion 1989 SIGMOD 4.965987e-05
7,225 Efficient Search in Very Large Databases 1988 VLDB 4.7910249e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,411 Communication Steps for Parallel Query Processing 2013 PODS 0.00012118832
7,182 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.802834e-05
792 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016580866
4,320 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.2822407e-05
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.0001629507
3,860 On Distributed Processibility of Datalog Queries by Decomposing Databases 1989 SIGMOD 6.6864693e-05
885 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015565543
1,078 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014223265
8,569 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB 4.4893996e-05
12,881 Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB 1993 VLDB 4.1905499e-05