Transitive Closure and the LOGA Strategy for its Efficient Evaluation.pdf

in: Proc. 2nd Symposium on Mathematical Fundamentals of Database Theory, Visegrad, Hungary, June 1989, pp. 415-428 + Transitive Closure and the LOGA -Strategy for its Efficient Evaluation W. Yan Central South University of Technology, Changsha, China current address: Department of Computer Science, University of Kaiserslautern P.O. Box 3049, 6750 Kaiserslautern, West Germany N. Mattos Department of Computer Science, University of Kaiserslautern Abstract One of the key problems when extending relational database query languages to include deductive capabilities, is to provide them with efficient methods for answering recursive queries. During the last few years many algorithms have been proposed to deal with transitive closure computation of a relation. In this paper, we discuss some important cri- teria for developing transitive closure algorithms. After presenting these issues, we describe an algorithm for transitive closure computation and show some results of performance measurements comparing several algorithms. 1. Introduction In the last few years the support of deductive capability in database systems (DBS) has been extensively required by the increasing number of so-called non-standard applications. One of the most promising approaches to support this requirement is to extend DBS to include the whole functionality underlying the theoretical foundation of first order logic. In so doing, a user of such a Deductive DBS (DDBS) [GMN84] can descriptively express his queries as well as his integrity constraints in first order logic. A