ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Factoring Augmented Regular Chain Programs.

Peter T. Wood: Factoring Augmented Regular Chain Programs. VLDB 1990: 255-263
@inproceedings{DBLP:conf/vldb/Wood90,
  author    = {Peter T. Wood},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {Factoring Augmented Regular Chain Programs},
  booktitle = {16th International Conference on Very Large Data Bases, August
               13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1990},
  isbn      = {1-55860-149-X},
  pages     = {255-263},
  ee        = {db/conf/vldb/Wood90.html},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In previous papers we have proposed a graphical query language for expressing traversal recursions in labelled, directed graphs. A fundamental feature of the language is the use of regular expressions to specify constraints on paths in these graphs. When only constants are allowed in regular expressions, it has been shown thatthese queries can be evaluated efficiently. In this paper, we study the inclusion of variables in regular expressions. We show that efficient evaluation algorithms still exist, and in so doing provide a translation to a class of Datalog programs, the augmented regular chain programs, which can always be factored. This class of programs is incomparable to previously identified classes of factorable programs.

Copyright © 1990 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Dennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek (Eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings. Morgan Kaufmann 1990, ISBN 1-55860-149-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[BMSU86]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BKBR87]
Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BR87]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CM90]
Mariano P. Consens, Alberto O. Mendelzon: GraphLog: a Visual Formalism for Real Life Recursion. PODS 1990: 404-416 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CMW87]
Isabel F. Cruz, Alberto O. Mendelzon, Peter T. Wood: A Graphical Query Language Supporting Recursion. SIGMOD Conference 1987: 323-330 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CMW88]
Isabel F. Cruz, Alberto O. Mendelzon, Peter T. Wood: G+: Recursive Queries Without Recursion. Expert Database Conf. 1988: 645-666 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HU79]
John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ioan89]
Yannis E. Ioannidis: Commutativity and its Role in the Processing of Linear Recursion. VLDB 1989: 155-163 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MW89]
Alberto O. Mendelzon, Peter T. Wood: Finding Regular Simple Paths in Graph Databases. VLDB 1989: 185-193 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Naug88]
Jeffrey F. Naughton: Compiling Separable Recursions. SIGMOD Conference 1988: 312-319 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NRSU89a]
Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NRSU89b]
Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ullm85]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Wood88]
...

Copyright © Tue Mar 16 02:22:00 2010 by Michael Ley (ley@uni-trier.de)