Universality of data retrieval languages

ABSTRACT

We consider the question of how powerful a relational query language should be and state two principles that we feel any query language should satisfy. We show that although relational algebra and relational calculus satisfy these principles, there are certain queries involving least fixed points that cannot be expressed by these languages, yet that also satisfy the principles. We then consider various extensions of relational algebra to enable it to answer such queries. Finally, we discuss our extensions to relational algebra in terms of a new programming language oriented model for queries.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: {ASU} A. V. Aho, Y. Sagiv, and J. D. Ullman, "Equivalences Among Relational Expressions," SIAM J. Computing, 1978.
• 3: {B} F. Bancilhon, "On the completeness of query languages for relational expressions," Rapport de Recherche No. 297, IRIA, Rocquencourt, France, May, 1978.
• 4: 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]
• 5: {C2} E. F. Codd, "Relational Completeness of Data Base Sublanguages," in Data Base Systems (R. Rustin, ed.), Prentice-Hall, Englewood Cliffs, N. J., 1972, pp. 65-98.
• 6: {Ch} A. Church, Introduction to Mathematical Logic, Vol. 1, Princeton University Press, 1956.
• 7: 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]
• 8: C.J. J. Date, An Introduction to Database Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1981
• 9: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 10: {P} J. Paredaena, Information Processing Letters 7:2, 1978.
• 11: {S} C. P. Schnorr, "An Algorithm for Transitive Closure with Linear Expected Time," SIAM J. Computing7:2 (May, 1978), 127-133.
• 12: John Miles Smith , Philip Yen-Tang Chang, Optimizing the performance of a relational algebra database interface, Communications of the ACM, v.18 n.10, p.568-579, Oct. 1975 [doi>10.1145/361020.361025]
• 13: {SY} Y. Sagiv and M. Yannikakis, "Equivalence Among Relational Expressions with the Union and Difference Operations," Proc. ACM International Conference on Very Large Data Bases, Sept., 1978.
• 14: {T} A. Tarski, "A Lattice-Theoretical Fixpoint Theorem and its Applications," Pacific J. Mathematics5:2 (June, 1955), 285-309.
• 15: {Z} M. M. Zloof, "Query-by-Example: a Database Language," IBM Syst. J.,16:4 (1977), pp. 324-343.