The processing of recursive queries is likely to be one of the features of the next generation of database systems, and it is a property that is also required in expert databases. The problem with recursive queries is that they are computationally expensive to execute. Linear recursive queries can be expressed as transitive closures, and using these closures is a useful approach to precessing recursive queries. Computing the transitive closure itself is also computationally expensive, however, and many attempts have been made to do this efficiently. One of these attempts involves materializing or explicitly precomputing “appropriate” transitive closures that are required frequently and storing them; but the disadvantage of this technique has been that these closures can consist of huge numbers of tuples, and their storage management becomes a problem.

This paper proposes a compression technique to reduce the storage requirement of appropriate transitive closures while still permitting queries related to the closure, which allow recursive query processing to be answered efficiently. Updates to the underlying database involve adding nodes and arcs to the compressed closure, which can also be done efficiently. The authors present details of simulation results to verify that their compression strategy is of benefit.

This detailed report covers a specific piece of research work in a narrow area of future generation database query processing and is not for the general reader, but papers in ACM Transactions on Database Systems are not meant to be. The paper is long and difficult to read, but I am a general reader in this area of database processing and not one of the specialists for whom the paper is presumably intended. The bibliography is good.