TY - GEN
T1 - The processing and evaluation of transitive closure queries
AU - Han, Jiawei
AU - Qadah, Ghassen
AU - Chaou, Chinying
N1 - Funding Information:
The work was supported by the U.S. National Science Foundation under Grant DCR-860-8311 and by the Simon Fraser University under the President's Research Grant and the Research Grant of Centre for System Science. The authors would like to express our thanks to Larry Henschen for his helpful discussions and to the anonymous reviewers for their helpful comments on the paper.
Publisher Copyright:
© 1988, Springer-Verlag.
PY - 1988
Y1 - 1988
N2 - A transitive closure operator will be an important new operator in future deductive database systems. We discuss the compilation of recursive rule clusters into formulas containing transitive closure operations and study three promising algorithms for the processing of transitive closure queries: the wavefront algorithm, the δ-wavefront algorithm and the level-relaxed δ-wavefront algorithm. The relative processing efficiency of these algorithms are analyzed and compared based on different database structures and accessing methods. Our study shows that the δ-wavefront algorithm performs consistently better than the wavefront algorithm, and the level-relaxed δ-wavefront algorithm has high potential of further reducing I/O accessing cost on the databases with clustered derivation paths. The study also provides some interesting heuristics on the database structures and implementation techniques in the processing of recursive database queries.
AB - A transitive closure operator will be an important new operator in future deductive database systems. We discuss the compilation of recursive rule clusters into formulas containing transitive closure operations and study three promising algorithms for the processing of transitive closure queries: the wavefront algorithm, the δ-wavefront algorithm and the level-relaxed δ-wavefront algorithm. The relative processing efficiency of these algorithms are analyzed and compared based on different database structures and accessing methods. Our study shows that the δ-wavefront algorithm performs consistently better than the wavefront algorithm, and the level-relaxed δ-wavefront algorithm has high potential of further reducing I/O accessing cost on the databases with clustered derivation paths. The study also provides some interesting heuristics on the database structures and implementation techniques in the processing of recursive database queries.
UR - http://www.scopus.com/inward/record.url?scp=84909751089&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84909751089&partnerID=8YFLogxK
U2 - 10.1007/3-540-19074-0_47
DO - 10.1007/3-540-19074-0_47
M3 - Conference contribution
AN - SCOPUS:84909751089
SN - 9783540190745
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 49
EP - 75
BT - Advances in Database Technology—EDBT 1988 - International Conference on Extending Database Technology, Proceedings
A2 - Ceri, Stefano
A2 - Schmidt, Joachim W.
A2 - Missikoff, Michele
PB - Springer
T2 - 1st International Conference on Extending Database Technology, EDBT 1988
Y2 - 14 March 1988 through 18 March 1988
ER -