Programming primitives for database languages

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.

REFERENCES

• 1: {ASU} Aho, A. V., Y. Sagiv and J. D. Ullman, Equivalences among relational expressions. SIAM J. Computing (1978).
• 2: 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]
• 3: {B} 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).
• 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} Codd, E. F., A data base sublanguage founded on the relational calculus, Proc. ACM SIGFIDET Workshop on Data Description, Access and Control (Codd and Dean, Eds.), ACM, San Diego (Nov. 1971) pp. 35-68.
• 6: {C3} Codd, E. F., Relational completeness of data base sublanguages. In Data Base Systems (Rustin, Ed.), Prentice Hall (1972).
• 7: {Ch} Chamberlin, D. D., et. al. SEQUEL 2: a unified approach to data definition, manipulation, and control. IBM J. Res. Dev., 20,6 (1976) pp. 560-575.
• 8: {Cha} Chang, C. L., DEDUCE 2: Further investigations of deduction in relational data bases, in {GM}, pp. 201-236. See also. Chang, C. L., DEDUCE: A deductive query language for relational data bases, in Pattern Recognition and Artificial Intelligence, (C. H. Chan, Ed.), Academic Press (1976) pp. 108-134.
• 9: Ashok K. Chandra , David Harel, Computable queries for relational data bases (Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.309-318, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804423]
• 10: {CH2} Chandra, A. K. and D. Harel, Structure and complexity of relational queries, Proc. 21st Symp. on Foundations of Comp. Sci., Syracuse, N.Y. (Oct. 1980), pp. 333-347.
• 11: 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]
• 12: {F} Fagin, R., Monadic generalized spectra, Zeitschr. f. Math. Logik und Grundlagen d. Math. 21 (1975) pp.89-96.
• 13: Herve Gallaire , Jack Minker, Logic and Data Bases, Perseus Publishing, 1978
• 14: {HSW} Held, G. D., M. R. Stonebraker, and E. Wong, INGRES: A relational data base system, AFIPS Conf. Proc., 44 (1975) pp. 409-416.
• 15: {IBM} Query-by-Example, Terminal User's Guide, IBM manual SH20-2078-0 (Sep. 1978); see also Query-by-Example, Program Description/Operations Manual, IBM manual SH20-2077-0 (Sep. 1977).
• 16: {K} Kowalski, R. A., Predicate logic as a programming language, Proc. IFIP 74, North-Holland (1974) pp. 556-574.
• 17: {LP} Lacroix, M., A. Pirotte, ILL: An English structured query language for relational data bases, Proc. IFIP TC-2 Working Conf. on Modelling in Data Base Management Syst. (G. M. Nijssen, Ed.), Nice, North-Holland (1977) pp.
• 18: {P} Paredaens, J., On the Expressive Power of the Relational Algebra, Information Processing Letters,7,2 (Feb. 1978).
• 19: {Pi} Pirotte, A., High level data base query languages, in Logic and Data Bases, H. Gallaire and J. Minker (eds.), Plenum Press, NY (1978), 409-436.
• 20: {S} Stockmeyer, L. J., The polynomial-time hierarchy. TCS, 3 (1977) pp. 1-22.
• 21: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 22: {V} van Emden, M. H., Computation and deductive information retrieval. In Formal Description of Programming Concepts, E. Neuhold, ed., North-Holland (1978) pp. 421-439.
• 23: {Va} Vandijck, E., Towards a more familiar relational retrieval language, Inf. Syst., 2, 4 (1977). pp. 159-169.
• 24: {Z1} Zloof, M. Query by Example, RC4917, IBM Research, Yorktown Heights (July 1974).
• 25: {Z2} Zloof, M, Query-by-Example: Operations on the Transitive Closure. RC5526, IBM Research, Yorktown Heights (Oct. 1976).
• 26: {Z3} Zloof, M., Query-by-Example: a data base language, IBM Syst. J., 4 (1977) 324-343.