Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A correction of the termination conditions of the Henschen-Naqvi technique
Briggs D. Journal of the ACM31 (4):711-719,1984.Type:Article
Date Reviewed: Sep 1 1992

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.

Reviewer:  M. T. özsu Review #: CR115026
1) Henschen, L. J. and Naqvi, S. A. On compiling queries in recursive first-order databases. J. ACM 31, 1 (Jan. 1984), 47–85.
Bookmark and Share
 
Query Processing (H.2.4 ... )
 
 
Logic Programming (I.2.3 ... )
 
 
Query Languages (H.2.3 ... )
 
 
Mathematical Logic (F.4.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Query Processing": Date
A compression technique to materialize transitive closure
Jagadish H. (ed) ACM Transactions on Database Systems 15(3): 558-598, 1990. Type: Article
Oct 1 1992
Efficient and optimal query answering on independent schemes
Atzeni P. (ed), Chan E. Theoretical Computer Science 77(3): 291-308, 1990. Type: Article
Nov 1 1991
The complexity of evaluating relational queries
Cosmadakis S. Information and Control 58(1-3): 101-112, 1984. Type: Article
Feb 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy