Thumbnail
Access Restriction
Subscribed

Author Lu, Hongjun ♦ Mikkilineni, Krishna ♦ Richardson, James P.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©1987
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Remuneration ♦ Radio frequency ♦ Ice ♦ Writing
Abstract Recursive query evaluation is a capability of deductively-augmented database systems that conventional database systems do not support well, if at all. Many recursive queries involve computation of the transitive closure of a relation. Previously published algorithms for transitive closure are iterative in nature, performing repeated joins, unions, and differences until convergence is obtained. In this paper, we present an adaptation of Warren's algorithm for computing the transitive closure of a relation. Warren's algorithm was originally designed for a bit matrix representation of a binary relation; we have adapted it for use with a binary relation represented as a set of tuples, as in a relational database management system. This adapted algorithm computes the transitive closure in two passes over the relation. We analyze the performance of this algorithm, and compare it to the performance of two algorithms based on relational algebra: an iterative algorithm, and an improved version of the iterative algorithm that eliminates unnecessary I/O at the expense of more computation. We evaluate the performance of the algorithms for different source relation sizes, available memory sizes, join selectivities, and maximum path length. Our results show that no algorithm has uniformly superior performance; the adaptation of Warren's algorithm is superior when the source and result relations are not too much larger than main memory. We conclude that in future systems with large main memory, Warren's algorithm generally performs best, and thus should be implemented with the option of switching to an iterative algorithm when the source or result sizes are very large.
Description Author affiliation: Honeywell Computer Sciences Center, Golden Valley, Minnesota, USA (Lu, Hongjun; Mikkilineni, Krishna; Richardson, James P.)
ISBN 9780818607622
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1987-02-03
Publisher Place USA
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 1.90 MB
Page Count 8
Starting Page 112
Ending Page 119


Source: IEEE Xplore Digital Library