Classification and Compilation of Linear Recursive Queries in Deductive Databases

Cheong Youn, Hyoung Joo Kim, Lawrence Joseph Henschen, Jiawei Han

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

In this paper, we present a graph model which is powerful in classifying and compiling linear recursive formulas in deductive databases. The graph model consists of two kinds of graphs: I-graph and Resolution Graph. We can extract essential properties of a recursive formula from its I-graph and can easily figure out the compiled formula and the query evaluation plan of the recursive formula from its resolution graph. We demonstrate that based on the graph model all the linear recursive formulas can be classified into a taxonomy of classes and each class shares some common characteristics in query compilation and query processing. The compiled formulas and the corresponding query evaluation plans can be derived based on the study of the compilation of each class.

Original languageEnglish (US)
Pages (from-to)52-67
Number of pages16
JournalIEEE Transactions on Knowledge and Data Engineering
Volume4
Issue number1
DOIs
StatePublished - Feb 1992

Keywords

  • Deductive database graph model knowledge base linear recursive query query evaluation plan recursive query compilation

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Classification and Compilation of Linear Recursive Queries in Deductive Databases'. Together they form a unique fingerprint.

Cite this