ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Commutativity and its Role in the Processing of Linear Recursion.

Yannis E. Ioannidis: Commutativity and its Role in the Processing of Linear Recursion. VLDB 1989: 155-163
@inproceedings{DBLP:conf/vldb/Ioannidis89,
  author    = {Yannis E. Ioannidis},
  editor    = {Peter M. G. Apers and
               Gio Wiederhold},
  title     = {Commutativity and its Role in the Processing of Linear Recursion},
  booktitle = {Proceedings of the Fifteenth International Conference on Very
               Large Data Bases, August 22-25, 1989, Amsterdam, The Netherlands},
  publisher = {Morgan Kaufmann},
  year      = {1989},
  isbn      = {1-55860-101-5},
  pages     = {155-163},
  ee        = {db/conf/vldb/Ioannidis89.html},
  crossref  = {DBLP:conf/vldb/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We investigate the role of commutativity in query processing of linear recursion. We give a sufficient condition for two linear, function-free, constant-free, and range-restricted rules to commute. The condition depends on the form of the rules themselves. For a restricted class of rules, we show that the condition is necessary and sufficient and can be tested in polynomial time in the size of the rules. Using the algebraic structure of such rules, we study the relationship of commutativity with several other properties of linear recursive rules. We show that commutativity is in the center of several important special classes of linear recursion, i.e., separable recursion and recursion with recursivelyredundant predicates.

Copyright © 1989 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

Peter M. G. Apers, Gio Wiederhold (Eds.): Proceedings of the Fifteenth International Conference on Very Large Data Bases, August 22-25, 1989, Amsterdam, The Netherlands. Morgan Kaufmann 1989, ISBN 1-55860-101-5
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Journal Version

Yannis E. Ioannidis: Commutativity and its Role in the Processing of Linear Recursion. J. Log. Program. 14(3&4): 223-252(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Aho74]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Aho79a]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Aho79b]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Banc85]
...
[Beer87]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Chan77]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ioan85]
Yannis E. Ioannidis: A Time Bound on the Materialization of some Recursively Defined Views. VLDB 1985: 219-226 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ioan86a]
Yannis E. Ioannidis, Eugene Wong: An Algebraic Approach to Recursive Inference. Expert Database Conf. 1986: 295-309 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ioan86b]
Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ioan87]
Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ioan88a]
...
[Ioan88b]
...
[Naug86]
Jeffrey F. Naughton: Redundancy in Function-Free Recursive Rules. SLP 1986: 236-245 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
[Rama89]
Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman, Moshe Y. Vardi: Proof-Tree Transformation Theorems and Their Applications. PODS 1989: 172-181 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tars55]
...

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