Real time retrieval and update of materialized transitive closure
K.-C. Guh, C. Sun, C. Yu · 1991
A data structure is used to store materialized transitive closure such that the evaluation of transitive closure, deletions and insertions of tuples can be performed efficiently. Experiments have been carried out on a Sun/3/180 system. It is verified experimentally and theoretically that it takes on the average O(m") to retrieve the ancestors/descendants of the given node, where m" is the number of ancestors/descendants of the given node, and it takes on the average O(m*m') to perform an insertion or a deletion of a tuple (a,b), where m is the number of ancestors of a+1 and m' is the number of descendants of b+1. It is shown that, when the data types is integer, retrieval of the ancestors/descendants of a given node takes no more than 0.0001 s; insertion/deletion of a tuple and the corresponding update involving m*m"=elements in the data structure takes approximately 0.07 s. When data type is a string of length 20, the corresponding retrieval time and insertion/deletion times are 0.0008 s and 1.5 s respectively.>