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

On the Expressive Power of Query Languages for Relational Databases.

Eric C. Cooper: On the Expressive Power of Query Languages for Relational Databases. POPL 1982: 361-365
@inproceedings{DBLP:conf/popl/Cooper82,
  author    = {Eric C. Cooper},
  title     = {On the Expressive Power of Query Languages for Relational Databases},
  booktitle = {POPL},
  year      = {1982},
  pages     = {361-365},
  ee        = {db/conf/popl/Cooper82.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The query languages used in relational database systems are a special class of programming languages. The majority, based on first- order logic, lend themselves to analysis using formal methods. First, we provide a definition of relational query languages and their expressive power. We prove some general results and show that only a proper subset of first- order logic formulas may be used as a practical query language. We characterize this subset in both semantic and syntactic terms. We then analyze the expressive power of several real query languages, including languages based on the relational calculus, languages with set operators and aggregate functions, and procedural query languages.

Since the partial ordering "is more expressive than" determines a lattice among relational query languages, the results of the paper may be viewed as determining some of the structure of this lattice. We conclude with some applications of the results to the optimization problem for query processing.

Copyright © 1982 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.


POPL Proceedings Compendium

CDROM Version: Load the CDROM "POPL, The First Ten Years" and ...

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Printed Edition

Conference Record of the Ninth Annual ACM Symposium on Principles of Programming Languages,Albequerque, New Mexico, January 1982. ACM 1982 BibTeX
Contents

References

[AU]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[CB]
Marco A. Casanova, Philip A. Bernstein: A Formal System for Reasoning about Programs Accessing a Relational Database. ACM Trans. Program. Lang. Syst. 2(3): 386-414(1980) BibTeX
[CH]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases (Preliminary Report). STOC 1979: 309-318 BibTeX
[C1]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[C2]
E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX
[HSW]
Gerald Held, Michael Stonebraker, Eugene Wong: INGRES: A Relational Data Base System. AFIPS National Computer Conference 1975: 409-416 BibTeX
[U]
Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
BibTeX

Referenced by

  1. Mariano P. Consens, Alberto O. Mendelzon: Low Complexity Aggregation in GraphLog and Datalog. ICDT 1990: 379-394
  2. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  3. Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984)
  4. Umeshwar Dayal: Processing Queries with Quantifiers: A Horticultural Approach. PODS 1983: 125-136
  5. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
  6. Hervé Gallaire: Impacts of Logic and Databases (Invited Paper). VLDB 1981: 248-259
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:34:34 2009