Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The concept of a “reasonable” query in a relational data base is investigated. We provide an abstract characterization of the class of queries which are computable, and define the completeness of a query language as the property of being precisely powerful enough to express the queries in this class. Our main result is the completeness of a simple programming language which can be thought of as consisting of the relational algebra augmented with the power of iteration.

REFERENCES

• 1: Aho, A. V., C. Beeri and J. D. Ullman. The Theory of Joins in Relational Data Bases. Proceedings 18th IEEE Symp. on Foundations of Computer Science. Providence, R.I., Oct. 1977.
• 2: Aho, A. V., Y. Sagiv and J. D. Ullman. Equivalences Among Relational Expressions. SIAM J. Computing, 1978.
• 3: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• 4: Bancilhon, F. On the Completeness of Query Languages for Relational Data Bases. Proceedings 7th Symp. on Mathematical Foundations of Computer Science. Zakopane, Poland. (Springer-Verlag Lecture Notes in Computer Science.) Sept. 1978.
• 5: Beeri, C., R. Fagin and J. H. Howard. A Complete Axiomatization for Functional and Multivalued Dependencies. IBM San Jose Research Report RJ 1977.
• 6: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 7: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 8: Codd, E. F. Relational Completeness of Data Base Sublanguages. In Data Base Systems (Rustin, Ed.), Prentice Hall, 1972.
• 9: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 10: Paredaens, J. On the Expressive Power of the Relational Algebra. Information Processing Letters, Vol. 7, No. 2, Feb. 1978.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Languages, Management, Measurement