Asynchronous Chain Recursions.

Jiawei Han, Wenyu Lu: Asynchronous Chain Recursions. DASFAA 1989: 285-292
  author    = {Jiawei Han and
               Wenyu Lu},
  editor    = {Sukho Lee and
               Hideko S. Kunii and
               Won Kim and
               In Sup Paik and
               Yahiko Kambayashi},
  title     = {Asynchronous Chain Recursions},
  booktitle = {International Symposium on Database Systems for Advanced Applications,
               Seoul, Korea, April 10-12, 1989},
  publisher = {Dept. of Computer Science, KAIST, P.O. Box 150, ChongRyang, Seoul,
               131-650, Korea},
  year      = {1989},
  pages     = {285-292},
  ee        = {db/conf/dasfaa/HanL89.html},
  crossref  = {DBLP:conf/dasfaa/89},
  bibsource = {DBLP,}


An asynchronous chain recursion (AC) is a recursion whose compiled formula consists of singfe chain or asynchronous chains. It is a generalization of transitive closure recursion and single-chain recursion (SC). This paper shows that many complex function-free recursions, which may contain multiple linear recursive rules, nonlinear recursive rules, mutually recursive rules and multiple-level recursions, can be compiled to ACs. Our study on the compilation methods, the simplification of compiled formulas and the query processing of ACs shows that ACs are frequently encountered, and they can be compiled to relatively simple compiled formulas and processed efficiently using transitive closure processing methods.

Copyright © 1989 by The Organizing Commitee of the International Symposium on Database Systems for Advanced Applications. Permission to copy without all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the DASFAA copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Organizing Commitee of the International Symposium on Database Systems for Advanced Applications. To copy otherwise, or to republish, requires a fee and/or special permission from the Organizing Commitee.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 2, EDBT, ICDT, MFDBS, DASFAA" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX


Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226 BibTeX
Jiawei Han, Lawrence J. Henschen: Handling Redundancy in the Processing of Recursive Database Queries. SIGMOD Conference 1987: 73-81 BibTeX
Jiawei Han, Wo-Shun Luk: What Kinds of Recursion Can Be Processed by Transitive Closure Strategies? ISMIS 1988: 170-179 BibTeX
Jiawei Han: Selection of Processing Strategies for Different Recursive Queries. JCDKB 1988: 59-68 BibTeX
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
Yannis E. Ioannidis: A Time Bound on the Materialization of Some Recursively Defined Views. Algorithmica 1(3): 361-385(1986) BibTeX
Yannis E. Ioannidis, Eugene Wong: Transforming Nonlinear Recursion into Linear Recursion. Expert Database Conf. 1988: 401-421 BibTeX
Jack Minker, Jean-Marie Nicolas: On recursive axioms in deductive databases. Inf. Syst. 8(1): 1-13(1983) BibTeX
Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348 BibTeX
Jeffrey F. Naughton: Compiling Separable Recursions. SIGMOD Conference 1988: 312-319 BibTeX
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
Weining Zhang, Clement T. Yu: A Necessary Condition for a Doubly Recursive Rule to be Equivalent to a Linear Recursive Rule. SIGMOD Conference 1987: 345-356 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:05:14 2009