An implementation technique for database query languages

ABSTRACT

Structured query languages, such as those available for relational databases, are becoming increasingly desirable for all database management systems. Such languages are applicative: there is no need for an assignment or update statement. A new technique is described that allows for the implementation of applicative query languages against most commonly used database systems. The technique involves “lazy” evaluation and has a number of advantages over existing methods: it allows queries and functions of arbitrary complexity to be constructed; it reduces the use of secondary storage; it provides a simple control structure through which interfaces to other programs may be constructed; and the implementation, including the database interface, is quite compact. Although the technique is presented for a specific functional programming system and for a CODASYL DBMS, it is general and may be used for other query languages and database systems.

REFERENCES

• 1: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 2: Peter Buneman , Robert E. Frankel, FQL: a functional query language, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582104]
• 3: BURGE, W.H. Recursive Programming Techniques. Addison-Wesley, Reading, Mass., 1975.
• 4: BURSTALL, I:{.M., COLLINS, J.S., AND POPPLESTONE, R.J. Programming in POP-2, Edinburgh University Press, Edinburgh, Scotland, 1971.
• 5: Donald D. Chamberlin , Raymond F. Boyce, SEQUEL: A structured English query language, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.249-264, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811515]
• 6: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 7: DATA BASE TASK GROUP. April 1971 Report, ACM, New York, 1971.
• 8: FRANKEL, R.E. FQL--The design and implementation of a functional query language. M.S. thesis. Moore School, University of Pennsylvania, May 1979.
• 9: FRIEDMAN, D.P., AND WISE, D.S. CONS should not evaluate its arguments. In Automata, Languages, and Programming. Edinburgh University Press, Edinburgh, Scotland, 1976.
• 10: GERRITSEN, R. Seed Reference Manual. International Database Systems, Philadelphia, Pa., 1978.
• 11: Michael Hammer , Dennis McLeod, The semantic data model: a modelling mechanism for data base applications, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509264]
• 12: Harvest User Manual. International Database Systems, Philadelphia, Pa., 1979.
• 13: HELD, G., STONEBRAKER, M., AND WONG, E. INGRES: A relational database system. In Proc. AFIPS 1975 Nat. Computer Conf., Vol. 44. AFIPS Press, Arlington, Va., 1975.
• 14: Peter Henderson , James H. Morris, Jr., A lazy evaluator, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.95-103, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811543]
• 15: Kenneth E. Iverson, Operators, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.161-176, Oct. 1979 [doi>10.1145/357073.357074]
• 16: P. J. Landin, Correspondence between ALGOL 60 and Church's Lambda-notation: part I, Communications of the ACM, v.8 n.2, p.89-101, Feb. 1965 [doi>10.1145/363744.363749]
• 17: P. J. Landin, A correspondence between ALGOL 60 and Church's Lambda-notations: Part II, Communications of the ACM, v.8 n.3, p.158-167, March 1965 [doi>10.1145/363791.363804]
• 18: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 19: MXLNER, R. A theory of type polymorphism in programming. J. Comput. Syst. Sci., 17 (1978), 348-375.
• 20: David W. Shipman, The functional data model and the data languages DAPLEX, ACM Transactions on Database Systems (TODS), v.6 n.1, p.140-173, March 1981 [doi>10.1145/319540.319561]
• 21: 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]
• 22: John Miles Smith , Diane C. P. Smith, Database abstractions: aggregation and generalization, ACM Transactions on Database Systems (TODS), v.2 n.2, p.105-133, June 1977 [doi>10.1145/320544.320546]
• 23: TURNER, D.A. A new implementation technique for applicative languages. Softw. Pract. Exper. 9 (1979), 31-49.
• 24: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 25: WIRTH, N. The programming language Pascal. Acta inf 1, 1(1971), 35-63.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

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

General Terms:
Human Factors, Languages

Keywords:
applicative programing, coroutines, database interfaces, lazy evaluation