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

Programming Primitives for Database Languages.

Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62
@inproceedings{DBLP:conf/popl/Chandra81,
  author    = {Ashok K. Chandra},
  title     = {Programming Primitives for Database Languages},
  booktitle = {POPL},
  year      = {1981},
  pages     = {50-62},
  ee        = {db/conf/popl/Chandra81.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper examines a number of programming primitives in query languages for relational databases. The basic framework is a language based on relational algebra, whose variables take relations as values. The primitives considered are (i) looping, (ii) counters, (iii) generic (or unranked) variables, (iv) equality, (v) bounded looping (which corresponds to counting the number of tuples in a relation), and (vi) isomorphism class (which corresponds to knowing the isomorphism class of the data base). A comparison diagram is given relating all combinations of these six primitives, and several of the resulting classes of queries are characterized by their complexity or algebraic properties. It is shown, for example, that equality cannot be simulated using all the other primitives, that generic variables (with loops) cannot be simulated with only ranked variables and all the other primitives, and that with bounded loops one can determine the isomorphism class of the database when generic variables are allowed, but not otherwise.

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

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 Eighth Annual ACM Symposium on Principles of Programming Languages, Williamsburg, Virginia, January 1981. ACM 1981 BibTeX
Contents

References

[ASU]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
[AU]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[B]
François Bancilhon: On the Completeness of Query Languages for Relational Data Bases. MFCS 1978: 112-123 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: A Database Sublanguage Founded on the Relational Calculus. SIGFIDET Workshop 1971: 35-68 BibTeX
[C3]
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
[Ch]
Donald D. Chamberlin, Morton M. Astrahan, Kapali P. Eswaran, Patricia P. Griffiths, Raymond A. Lorie, James W. Mehl, Phyllis Reisner, Bradford W. Wade: SEQUEL 2: A Unified Approach to Data Definition, Manipulation, and Control. IBM Journal of Research and Development 20(6): 560-575(1976) BibTeX
[Cha]
Chin-Liang Chang: DEDUCE 2: Further Investigations of Deduction in Relational Data Bases. Logic and Data Bases 1977: 201-236 BibTeX
[CH1]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases (Preliminary Report). STOC 1979: 309-318 BibTeX
[CH2]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. FOCS 1980: 333-347 BibTeX
[CH]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
[F]
...
[GM]
Hervé Gallaire, Jack Minker (Eds.): Logic and Data Bases, Symposium on Logic and Data Bases, Centre d'études et de recherches de Toulouse, 1977. Advances in Data Base Theory Plemum Press 1978, ISBN 0-306-40060-X
Contents BibTeX
[HSW]
Gerald Held, Michael Stonebraker, Eugene Wong: INGRES: A Relational Data Base System. AFIPS National Computer Conference 1975: 409-416 BibTeX
[IBM]
...
[K]
Robert A. Kowalski: Predicate Logic as Programming Language. IFIP Congress 1974: 569-574 BibTeX
[LP]
...
[P]
Jan Paredaens: On the Expressive Power of the Relational Algebra. Inf. Process. Lett. 7(2): 107-111(1978) BibTeX
[Pi]
Alain Pirotte: High Level Data Base Query Languages. Logic and Data Bases 1977: 409-436 BibTeX
[S]
Larry J. Stockmeyer: The Polynomial-Time Hierarchy. Theor. Comput. Sci. 3(1): 1-22(1976) BibTeX
[U]
Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
BibTeX
[V]
...
[Va]
E. Vandijck: Towards a more familiar relational retrieval language. Inf. Syst. 2(4): 159-169(1977) BibTeX
[Z1]
...
[Z2]
...
[Z3]
Moshé M. Zloof: Query-by-Example: A Data Base Language. IBM Systems Journal 16(4): 324-343(1977) BibTeX

Referenced by

  1. Frank Neven, Martin Otto, Jerzy Tyszkiewicz, Jan Van den Bussche: Adding For-Loops to First-Order Logic. ICDT 1999: 58-69
  2. Philippe Picouet, Victor Vianu: Expressiveness and Complexity of Active Databases. ICDT 1997: 155-172
  3. Catriel Beeri, Tova Milo, Paula Ta-Shma: On Genericity and Parametricity. PODS 1996: 104-116
  4. Philippe Picouet, Victor Vianu: Semantics and Expressiveness Issues in Active Databases. PODS 1995: 126-138
  5. Marc Andries, Luca Cabibbo, Jan Paredaens, Jan Van den Bussche: Applying an Update Method to a Set of Receivers. PODS 1995: 208-218
  6. Jerzy Tyszkiewicz: On the Kolmogorov Expressive Power of Boolean Query Languages. ICDT 1995: 97-110
  7. Sérgio Lifschitz, Victor Vianu: A Probabilistic View of Datalog Parallelization. ICDT 1995: 294-307
  8. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  9. Latha S. Colby, Edward L. Robertson, Lawrence V. Saxton, Dirk Van Gucht: A Query Language for List-Based Complex Objects. PODS 1994: 179-189
  10. Surajit Chaudhuri, Moshe Y. Vardi: On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs. PODS 1994: 107-116
  11. Karl Denninghoff, Victor Vianu: Database Method Schemas and Object Creation. PODS 1993: 265-275
  12. Jan Van den Bussche, Dirk Van Gucht, Gottfried Vossen: Reflective Programming in the Relational Algebra. PODS 1993: 17-25
  13. Cheong Youn, Hyoung-Joo Kim, Lawrence J. Henschen, Jiawei Han: Classification and Compilation of Linear Recursive Queries in Deductive Databases. IEEE Trans. Knowl. Data Eng. 4(1): 52-67(1992)
  14. Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66
  15. Serge Abiteboul, Kevin J. Compton, Victor Vianu: Queries Are Easier Than You Thought (Probably). PODS 1992: 23-32
  16. Karl Denninghoff, Victor Vianu: The Power of Methods With Parallel Semantics. VLDB 1991: 221-232
  17. Yeh-Heng Sheng: A Non-deterministic Deductive Database Language. SIGMOD Conference 1991: 188-197
  18. Neil Immerman, Sushant Patnaik, David W. Stemple: The Expressiveness of a Family of Finite Set Languages. PODS 1991: 37-52
  19. Yeh-Heng Sheng: IDLOG: Extending the Expressive Power of Deductive Database Languages. SIGMOD Conference 1990: 54-63
  20. Serge Abiteboul, Eric Simon, Victor Vianu: Non-Deterministic Languages to Express Deterministic Transformations. PODS 1990: 218-229
  21. Richard Hull, Jianwen Su: On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions (Extended Abstract). SIGMOD Conference 1989: 147-158
  22. Stavros S. Cosmadakis: On the First-Order Expressibility of Recursive Queries. PODS 1989: 311-323
  23. Xiaolei Qian: On the Expressive Power of the Bounded Iteration Construct. DBPL 1989: 411-421
  24. Richard Hull, Jianwen Su: On Bulk Data type Constructors and Manipulation Primitives: A Framework for Analyzing Power and Complexity. DBPL 1989: 396-410
  25. Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351
  26. Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9
  27. Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250
  28. Kazimierz Subieta, Marek Missala: Data Manipulation in NETUL. ER 1987: 391-407
  29. Moshe Y. Vardi: On the Integrity of Databases with Incomplete Information. PODS 1986: 252-266
  30. Marc H. Graham, Moshe Y. Vardi: On the Complexity and Axiomatizability of Consistent Database States. PODS 1984: 281-289
  31. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
BibTeX

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Complete | Author
Copyright © Sat May 16 23:34:34 2009 by Michael Ley (ley@uni-trier.de)