Query models that involve computing the transitive closure of relations and the optimization of these queries have been an active research area in the last decade. One problem that complicates the issue is that some of the relations may be recursively defined. The Henschen-Naqvi technique [1] handles these queries on recursively defined relations by translating them into iterative relational algebra programs, which can then be evaluated by a conventional relational query processor. The Henschen-Naqvi technique is considered to be one of the most efficient recursive query evaluation strategies, but it fails to produce all the answers under certain conditions. This deficiency is due to its premature termination condition.
Briggs points out this flaw in the Henschen-Naqvi technique and describes a correction to the problem. The paper starts with a review of the Henshen-Naqvi technique and demonstrates the problem by means of an example. It then analyzes the cause of the failure, and finally proposes a new termination condition to remedy the flaw in the original technique. The analysis of the problem is based on a graph model of computation based on rule expansions, which is interesting in itself and has helped solve problems in query processing.
The paper is important from two perspectives. First, it improves an already well-regarded recursive query processing technique. Second, the identification of the premature condition has already inspired additional work of searching for correct and effective termination conditions. Many of these results have since been reported. This well-written paper is essential reading for researchers working in this area.