ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

On the Power of Algebras with Recursion.

Catriel Beeri, Tova Milo: On the Power of Algebras with Recursion. SIGMOD Conference 1993: 377-386
@inproceedings{DBLP:conf/sigmod/BeeriM93,
  author    = {Catriel Beeri and
               Tova Milo},
  editor    = {Peter Buneman and
               Sushil Jajodia},
  title     = {On the Power of Algebras with Recursion},
  booktitle = {Proceedings of the 1993 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 26-28, 1993},
  publisher = {ACM Press},
  year      = {1993},
  pages     = {377-386},
  ee        = {http://doi.acm.org/10.1145/170035.170090, db/conf/sigmod/BeeriM93.html},
  crossref  = {DBLP:conf/sigmod/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We consider the relationship between the deductive and the functional/algebraic query language paradigms. Previous works considered this subject for a non-recursive algebra, or an algebra with a fixed point operation, and the corresponding class of deductive queries is that defined by stratified programs. We consider here algebraic languages extended by general recursive definitions. We also consider languages that allow non-restricted use of negation. It turns out that recursion and negation in the algebraic paradigm need to be studied together. The semantics used for the comparison is the valid semantics, although other well-known declarative semantics can also be used to derive similar results. We show that the class of queries expressed by general deduction with negation can be captured using algebra with recursive definitions.

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

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Peter Buneman, Sushil Jajodia (Eds.): Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. ACM Press 1993 BibTeX , SIGMOD Record 22(2), June 1993
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1250 KB]

References

[1]
Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX
[2]
...
[3]
Catriel Beeri: New Data Models and Languages - the Challenge. PODS 1992: 1-15 BibTeX
[4]
Catriel Beeri, Tova Milo: Subtyping in OODB's. PODS 1991: 300-314 BibTeX
[5]
Catriel Beeri, Tova Milo: Functional and Predicative Programming in OODB's. PODS 1992: 176-190 BibTeX
[6]
Catriel Beeri, Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: The Valid Model Semantics for Logic Programs. PODS 1992: 91-104 BibTeX
[7]
Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 BibTeX
[8]
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
[9]
...
[10]
...
[11]
Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[12]
...
[13]
Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. PODS 1993: 49-58 BibTeX
[14]
Stéphane Grumbach, Victor Vianu: Tractable Query Languages for Complex Object Databases. PODS 1991: 315-327 BibTeX
[15]
Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. J. Comput. Syst. Sci. 43(1): 219-267(1991) BibTeX
[16]
Neil Immerman, Sushant Patnaik, David W. Stemple: The Expressiveness of a Family of Finite Set Languages. PODS 1991: 37-52 BibTeX
[17]
...
[18]
Michael Kifer: On Safety, Domain Independence, and Capturability of Database Queries (Preliminary Report). JCDKB 1988: 405-415 BibTeX
[19]
...
[20]
...
[21]
James W. Thatcher, Eric G. Wagner, Jesse B. Wright: Data Type Specification: Parameterization and the Power of Specification Techniques. ACM Trans. Program. Lang. Syst. 4(4): 711-732(1982) BibTeX
[22]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[23]
Allen Van Gelder: Negation as Failure Using Tight Derivations for General Logic Programs. SLP 1986: 127-138 BibTeX
[24]
Allen Van Gelder, Kenneth A. Ross, John S. Schlipf: Unfounded Sets and Well-Founded Semantics for General Logic Programs. PODS 1988: 221-230 BibTeX
[25]
...

Referenced by

  1. Frank Neven, Jan Van den Bussche, Dirk Van Gucht, Gottfried Vossen: Typed Query Languages for Databases Containing Queries. PODS 1998: 189-196
  2. Carlos A. Tau, Clara Smith, Claudia Pons, Ana María Monteiro: Formally Speaking About Schemata, Bases, Classes and Objects. DASFAA 1995: 308-317
  3. Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. PODS 1993: 49-58
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:16 2009