LEAST FIXED POINT COMPUTING IN RELATIONAL DATABASE

Abstract

This thesis explores approaches and implementation of least fixed point(LFP) operator in relational database context. The special case of transitive closure(TC) computing is studied intensively. TC algorithms can be classified into two types: set-oriented and tuple-oriented algorithms. Performance of TC computing were studied extensively in the literature. The effect of data characteristics on the performance of algorithms were also identified but most result were given under certain assumptions. These issues are further investigated in this thesis. Three representative algorithms are chosen to be simulated. A set of data characteristics affecting algorithm performance are identified. The cost metrics used are I/O cost in number of tuples and that in number of pages. Sample relations with certain characteristics are generated the transitive closures of which are evaluated using the three sample algorithms. Experiment data is collected to show interesting aspects of computing. For a deeper insight, a formal analysis is done for TC algorithms. This analysis takes into account the effect of limited amount of memory and is a closer representation of the computing process. In contrast to the popular belief in database community that set-oriented approach is better than tuple-oriented ones, both experiment result and analysis result given in this thesis show that tuple-oriented algorithm performs better in most cases. Possible ways of extending relational database with an LFP operator are explored. A prototype system, which employs a differential approach to compute LFP using relational algebra operators as primitives, is implemented. Two access methods, B++-tree, which was proposed previously to support differential evaluation of LFP and the established B+-tree, are supported. The total cost is broken into three parts: cost of file manipulation, cost of inference, and cost of duplicate elimination. Four sample logic programs are chosen to be evaluated using B+-tree and B++-tree, respectively. Experiment data is collected. Based on the cost model, it is revealed that inference(join) cost is the dominating contributor to the total cost. Use of B++-tree reduces the cost to some extent but the improvement is not very significant. This suggests that new index structures may be proposed to further reduce inference cost so that the performance can be improved significantly. This thesis is the first step to study the efficient implementation of TC/LFP operator in relational database and the related issues. Major future research issues identified are: 1. Various aspects of TC computing. Interesting issues include: comparison between tuple-oriented computing and set-oriented ones, study of data characteristics and their effect on the algorithm performance. 2. The optimization of iterative LFP computing. Interesting issues include: design of access method, choice of indexing scheme, selection of join method and computing sequence. 3. A formal analysis of the cost structure of general LFP computing based on the cost model proposed in this thesis. This analysis should include data characteristics as well as memory factors as parameters.