Classification and Compilation of Linear Recursive Queries in Deductive Databases

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

doi:10.1109/69.124897

Classification and Compilation of Linear Recursive Queries in Deductive Databases

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

Computer Science

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	52-67
Number of pages	16
Journal	IEEE Transactions on Knowledge and Data Engineering
Volume	4
Issue number	1
DOIs	https://doi.org/10.1109/69.124897
State	Published - 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

Access to Document

10.1109/69.124897

Cite this

@article{a4adb3f4eb0942c8aa71702e1b3a48da,

title = "Classification and Compilation of Linear Recursive Queries in Deductive Databases",

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.",

keywords = "Deductive database graph model knowledge base linear recursive query query evaluation plan recursive query compilation",

author = "Cheong Youn and Kim, {Hyoung Joo} and Henschen, {Lawrence Joseph} and Jiawei Han",

year = "1992",

month = feb,

doi = "10.1109/69.124897",

language = "English (US)",

volume = "4",

pages = "52--67",

journal = "IEEE Transactions on Knowledge and Data Engineering",

issn = "1041-4347",

publisher = "IEEE Computer Society",

number = "1",

}

TY - JOUR

T1 - Classification and Compilation of Linear Recursive Queries in Deductive Databases

AU - Youn, Cheong

AU - Kim, Hyoung Joo

AU - Henschen, Lawrence Joseph

AU - Han, Jiawei

PY - 1992/2

Y1 - 1992/2

N2 - 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.

AB - 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.

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

UR - http://www.scopus.com/inward/record.url?scp=0026821035&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026821035&partnerID=8YFLogxK

U2 - 10.1109/69.124897

DO - 10.1109/69.124897

M3 - Article

AN - SCOPUS:0026821035

SN - 1041-4347

VL - 4

SP - 52

EP - 67

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

IS - 1

ER -

Classification and Compilation of Linear Recursive Queries in Deductive Databases

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this