The processing and evaluation of transitive closure queries

Jiawei Han, Ghassen Qadah, Chinying Chaou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationAdvances in Database Technology—EDBT 1988 - International Conference on Extending Database Technology, Proceedings
EditorsStefano Ceri, Joachim W. Schmidt, Michele Missikoff
PublisherSpringer-Verlag
Pages49-75
Number of pages27
ISBN (Print)9783540190745
DOIs
StatePublished - Jan 1 1988
Externally publishedYes
Event1st International Conference on Extending Database Technology, EDBT 1988 - Venice, Italy
Duration: Mar 14 1988Mar 18 1988

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume303 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other1st International Conference on Extending Database Technology, EDBT 1988
CountryItaly
CityVenice
Period3/14/883/18/88

Fingerprint

Transitive Closure
Wavefronts
Wave Front
Query
Evaluation
Processing
Deductive Databases
Deductive System
Closure Operator
Database Systems
Compilation
Heuristics
Path
Costs
Operator

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Han, J., Qadah, G., & Chaou, C. (1988). The processing and evaluation of transitive closure queries. In S. Ceri, J. W. Schmidt, & M. Missikoff (Eds.), Advances in Database Technology—EDBT 1988 - International Conference on Extending Database Technology, Proceedings (pp. 49-75). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 303 LNCS). Springer-Verlag. https://doi.org/10.1007/3-540-19074-0_47

The processing and evaluation of transitive closure queries. / Han, Jiawei; Qadah, Ghassen; Chaou, Chinying.

Advances in Database Technology—EDBT 1988 - International Conference on Extending Database Technology, Proceedings. ed. / Stefano Ceri; Joachim W. Schmidt; Michele Missikoff. Springer-Verlag, 1988. p. 49-75 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 303 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Han, J, Qadah, G & Chaou, C 1988, The processing and evaluation of transitive closure queries. in S Ceri, JW Schmidt & M Missikoff (eds), Advances in Database Technology—EDBT 1988 - International Conference on Extending Database Technology, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 303 LNCS, Springer-Verlag, pp. 49-75, 1st International Conference on Extending Database Technology, EDBT 1988, Venice, Italy, 3/14/88. https://doi.org/10.1007/3-540-19074-0_47
Han J, Qadah G, Chaou C. The processing and evaluation of transitive closure queries. In Ceri S, Schmidt JW, Missikoff M, editors, Advances in Database Technology—EDBT 1988 - International Conference on Extending Database Technology, Proceedings. Springer-Verlag. 1988. p. 49-75. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-19074-0_47
Han, Jiawei ; Qadah, Ghassen ; Chaou, Chinying. / The processing and evaluation of transitive closure queries. Advances in Database Technology—EDBT 1988 - International Conference on Extending Database Technology, Proceedings. editor / Stefano Ceri ; Joachim W. Schmidt ; Michele Missikoff. Springer-Verlag, 1988. pp. 49-75 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{07115a74eb184c9e8cba89d9ee95c651,
title = "The processing and evaluation of transitive closure queries",
abstract = "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.",
author = "Jiawei Han and Ghassen Qadah and Chinying Chaou",
year = "1988",
month = "1",
day = "1",
doi = "10.1007/3-540-19074-0_47",
language = "English (US)",
isbn = "9783540190745",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "49--75",
editor = "Stefano Ceri and Schmidt, {Joachim W.} and Michele Missikoff",
booktitle = "Advances in Database Technology—EDBT 1988 - International Conference on Extending Database Technology, Proceedings",

}

TY - GEN

T1 - The processing and evaluation of transitive closure queries

AU - Han, Jiawei

AU - Qadah, Ghassen

AU - Chaou, Chinying

PY - 1988/1/1

Y1 - 1988/1/1

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-Verlag

ER -