Efficient maintenance of explicit transitive closures with set-oriented update propagation and parallel processing

摘要

Explicitly storing the transitive closure of a relation appears to be a solution providing fast access to recursivelu defined data. However, two problems are to be solved: (i) update propagations have to be efficiently processed and (ii) efficient access and limited storage space have to be reconciled. This paper focuses on the minimization of the cost of the propagation of the updates from the base relation to the deduced one. Only a part of the transitive closure relation is influenced by the base modification and has to be recomputed. Algorithms for instance-oriented propagations of insertion and deletion are proposed. Then, we take into account a set of deleted and/or inserted tuples in a single manipulation. The proposed method maintains an arbitrary set-oriented update in no more than 2 passes over the transitive closure. The execution times are decreased by the intensive use of parallelism; the explicit transitive closure is divided horizontally into several fragments, clustered on a set of disks, and then, processed by several processors. A shared-nothing implementation is investigated.