Treffer: A Correction of the Termination Conditions of the Henschen-Naqvi Technique

Henschen and Naqvi described a technique for translating queries on recursively defined relations of a Datalog database into iterative programs that invoke a query processor for conventional select-project-join queries of the relational algebra. Although the technique has been cited as one of the most efficient available, it will in some cases fail to produce all answers defined by the usual semantics for such databases. The technique is reviewed, a recursive query is exhibited where it fails, the cause of failure is noted, and a correction is described. A graphical representation of the computation based on a formal representation of rule expansions is employed.