Parallel Computation of Transitive Closure Queries on Fragmented Databases

摘要

The paper focuses on recursive query processing. The authors consider solution methods for three types of classic queries: connection, bill of material, and shortest path. They consider these classic graph problems from a database viewpoint, assuming that the graph be represented by a large, updatable data collection. They describe how to take advantage of parallel computation. Therefore, they introduce a clever partitioning of the original graph into subgraphs having minimal node intersection. This node intersection is called 'disconnection set,' and some minimal information about it is precomputed and stored. Algebraic programs to compute connection and shortest path queries in a relational database are presented. They show how a fragmentation can be derived, and how updates influence the stored information about 'disconnection sets.'