Paper Info
Title
Processing the transitive-closure logic rules on shared-nothing multiprocessor systems
Abstract
The author presents and evaluates, using rigorous analytical models, a number of parallel algorithms suitable for processing an important class of recursive queries, the instantiated transitive closure (TC) queries. These algorithms are variants of the sequential δ-wavefront algorithm, designed to run on a shared-nothing (message-passing) type of multiprocessor system. The results obtained indicate that the relative performance of these algorithms is a strong function of not only the parameters which characterize the database and the processed query. Two parallel algorithms have been identified to be the best performing ones, one for systems with slow interconnection networks and the other for systems with fast networks. It is also found that allocating too many nodes to a query which does not need them results in a substantial loss of potential speedup in the processing of the query
Year
DOI
Venue
1990
10.1109/CMPSAC.1990.139354
COMPSAC
Keywords
Field
DocType
database theory,distributed databases,parallel algorithms,query languages,fast networks,instantiated transitive closure,query processing,recursive queries,shared-nothing multiprocessor systems,slow interconnection networks,transitive-closure logic rules,algorithm design,parallel algorithm,message passing,transitive closure
Query optimization,Query language,Computer science,Parallel algorithm,Shared nothing architecture,Theoretical computer science,Multiprocessing,Database theory,Transitive closure,Speedup
Conference
Citations 
PageRank 
References 
0
0.34
2
Authors
1
Name
Order
Citations
PageRank
Qadah, G.Z.15477.84