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
7955
Venue
VLDB
Year
1990
Pagerank
5.8764777e-05
Overall Rank
4,852 | 66.25%
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,865 Diagnosis of Asynchronous Discrete Event Systems: Datalog to the Rescue! 2005 PODS 0.00010275334
2,131 Incremental Evaluation of Rules and its Relationship to Parallelism 1991 SIGMOD 9.4776341e-05
3,108 Parallelism in a Main-Memory DBMS: The performance of PRISMA/DB 1992 VLDB 7.5501593e-05
12,478 Randomized Algorithms for Data Reconciliation in Wide Area Aggregate Query Processing 2007 VLDB 4.1945683e-05
12,871 Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB 1993 VLDB 4.1945683e-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.0014279444
175 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.00038338694
246 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00030949575
786 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016660109
880 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015667998
1,055 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014422575
1,648 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 0.00011028408
4,288 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.2891396e-05
5,743 A Parallel Processing Strategy for Evaluating Recursive Queries 1986 VLDB 5.3442345e-05
6,661 A File Structure Supporting Traversal Recursion 1989 SIGMOD 4.9707787e-05
7,226 Efficient Search in Very Large Databases 1988 VLDB 4.7953551e-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.0001212565
7,181 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.8074621e-05
786 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016660109
4,288 Parallel Processing of Recursive Queries in Distributed Architectures 1989 VLDB 6.2891396e-05
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00016369666
3,855 On Distributed Processibility of Datalog Queries by Decomposing Databases 1989 SIGMOD 6.6953401e-05
880 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015667998
1,055 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014422575
8,572 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB 4.4937074e-05
12,871 Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB 1993 VLDB 4.1945683e-05