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: 8146
Venue: VLDB
Year: 1990
Pagerank: 6.2602701e-05
Overall Rank: 5,341 | 63.36%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Maurice A.W. Houtsma (University of Twente)
2. Peter M.G. Apers (University of Twente)
3. Stefano Ceri (University of Modena)

BibTeX Citation

@article{houtsma_vldb90,
        title = {{Distributed Transitive Closure Computations: The Disconnection Set Approach}},
        author = {Houtsma, Maurice A.W. and Apers, Peter M.G. and Ceri, Stefano},
        journal = {PVLDB},
        series = {{VLDB} '90},
        pages = {335},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,425	Diagnosis of Asynchronous Discrete Event Systems: Datalog to the Rescue!	2005	PODS	8.6005163e-05
2,530	Incremental Evaluation of Rules and its Relationship to Parallelism	1991	SIGMOD	8.458663e-05
3,090	Parallelism in a Main-Memory DBMS: The performance of PRISMA/DB	1992	VLDB	7.7686303e-05
12,671	Randomized Algorithms for Data Reconciliation in Wide Area Aggregate Query Processing	2007	VLDB	5.093636e-05
13,065	Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB	1993	VLDB	5.093636e-05

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
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00083340894
217	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00024458594
282	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.0002242162
1,086	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB	0.00012252192
1,259	On the Computation of the Transitive Closure of Relational Operators	1986	VLDB	0.00011437537
1,330	Efficient Transitive Closure Algorithms	1988	VLDB	0.00011140171
2,076	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD	9.212586e-05
4,773	Parallel Processing of Recursive Queries in Distributed Architectures	1989	VLDB	6.5149869e-05
5,563	A Parallel Processing Strategy for Evaluating Recursive Queries	1986	VLDB	6.1716947e-05
6,594	A File Structure Supporting Traversal Recursion	1989	SIGMOD	5.8296302e-05
7,342	Efficient Search in Very Large Databases	1988	VLDB	5.6386997e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,207	Communication Steps for Parallel Query Processing	2013	PODS
2	7,438	A Generalized Transitive Closure for Relational Queries	1988	PODS
3	1,086	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB
4	4,773	Parallel Processing of Recursive Queries in Distributed Architectures	1989	VLDB
5	1,114	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB
6	4,343	On Distributed Processibility of Datalog Queries by Decomposing Databases	1989	SIGMOD
7	1,330	Efficient Transitive Closure Algorithms	1988	VLDB
8	1,259	On the Computation of the Transitive Closure of Relational Operators	1986	VLDB
9	8,775	A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering	1990	VLDB
10	13,065	Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB	1993	VLDB