Lehrgebiet Informationssysteme

FB Informatik

LG IS

AG DBIS

(C) AG DBIS

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

Full paper (postscript version, compressed by gzip or PDF version )

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 criteria 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.

in: Proc. 2nd Symposium on Mathematical Fundamentals of Database Theory, Visegrad, Hungary, June 1989, pp. 415-428