Classification of Recursive Formulas in Deductive Databases.

@inproceedings{DBLP:conf/sigmod/YounHH88,
  author    = {Cheong Youn and
               Lawrence J. Henschen and
               Jiawei Han},
  editor    = {Haran Boral and
               Per-{\AA}ke Larson},
  title     = {Classification of Recursive Formulas in Deductive Databases},
  booktitle = {Proceedings of the 1988 ACM SIGMOD International Conference on
               Management of Data, Chicago, Illinois, June 1-3, 1988},
  publisher = {ACM Press},
  year      = {1988},
  pages     = {320-328},
  ee        = {http://doi.acm.org/10.1145/50202.50241, db/conf/sigmod/YounHH88.html},
  crossref  = {DBLP:conf/sigmod/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper, we present results on the classification of linear recursive formulas in deductive databases and apply those results to the compilation and optimization of recursive queries. We also introduce compiled formulas and query evaluation plans for a representative query for each of these classes.

To explain general recursive formulas, we use a graph model that shows the connectivity between variables. The connectivity between variables is the most critical part in processing recursive formulas. We demonstrate that based on such a graph model all the linear recursive formulas can be classified into several classes and each class shares some common characteristics in 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.

Copyright © 1988 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod7592 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[Banc 86]

François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52

[Banc 86]

François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15

[Gall 84]

Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984)

[Han 85a]

Jiawei Han, Hongjun Lu: Some Performance Results on Recursive Query Processing in Relational Database Systems. ICDE 1986: 533-541

[Han 85b]

...

[Han 87]

Jiawei Han, Lawrence J. Henschen: Handling Redundancy in the Processing of Recursive Database Queries. SIGMOD Conference 1987: 73-81

[Hens 84]

Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984)

[Ioan 85]

Yannis E. Ioannidis: A Time Bound on the Materialization of some Recursively Defined Views. VLDB 1985: 219-226

[Naug 86]

Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. PODS 1986: 267-279

[Reit 78]

Raymond Reiter: Deductive Question-Answering on Relational Data Bases. Logic and Data Bases 1977: 149-177

[Reit 84 ]

...

[Shap 80]

Stuart C. Shapiro, Donald P. McKay: Inference with Recursive Rules. AAAI 1980: 151-153

[Ullm 85]

Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985)

[Youn 87]

...

[Youn 88]

...