Some performance results on recursive query processing in relational database systems

The processing of recursive queries in relational database systems poses a great challenge in research on expert database systems. This paper uses both analytical and experimental methods to investigate the performance of several different algorithms in processing a recursive query in first-order recursive databases. The analytical method estimated the I/O and CPU cost and the storage needed in processing recursive queries. The experimental tests were performed on a synthetic relational database built on top of WISS (Wisconsin Storage System) on VAX 11/750. Both analytical and experimental results indicate that for efficient recursive database processing it is important to apply the following heuristics: performing selection first, making use of wavefront relations, and grouping those joins which reduce the size of intermediate results. The termination conditions for recursive queries are also discussed in the paper.