An introduction to Remy's fast polymorphic record projection

ABSTRACT

Traditionally, a record projection is compiled when all fields of the record are known in advance. The need to know all fields in advance leads to very clumsy programs, especially for querying external data sources. In a paper that had not been widely circulated in the database community, Remy presented in programming language context a constant-time implementation of the record projection operation that does not have such a requirement. This paper introduces his technique and suggests an improvement to his technique in the context of database queries.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Val Tannen , Peter Buneman , Limsoon Wong, Naturally Embedded Query Languages, Proceedings of the 4th International Conference on Database Theory, p.140-154, October 14-16, 1992
• 3: Peter Buneman , Leonid Libkin , Dan Suciu , Val Tannen , Limsoon Wong, Comprehension syntax, ACM SIGMOD Record, v.23 n.1, p.87-96, March 1994 [doi>10.1145/181550.181564]
• 4: L Cardelli, Amber, Proc. of the thirteenth spring school of the LITP on Combinators and functional programming languages, p.21-47, October 1986, Val d'Ajol, France
• 5: Luca Cardelli, A semantics of multiple inheritance, Information and Computation, v.76 n.2-3, p.138-164, February/March 1988 [doi>10.1016/0890-5401(88)90007-7]
• 6: L. Cardelli , J. Donahue , M. Jordan , B. Kalsow , G. Nelson, The Modula–3 type system, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.202-212, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75295]
• 7: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• 8: Carl A. Gunter, Semantics of programming languages: structures and techniques, MIT Press, Cambridge, MA, 1992
• 9: [9] K. Hart, L. Wong, C. Overton, and P. Buneman. Using a query language to integrate biological data, August 1994. Talk given at the Meeting on the Interconnection of Molecular Biology Databases, Stanford.
• 10: Richard Hull , Chee K. Yap, The Format Model: A Theory of database Organization, Journal of the ACM (JACM), v.31 n.3, p.518-544, July 1984 [doi>10.1145/828.832]
• 11: [11] D. Michie. Memo functions and machine learning. Nature, 268:19-22, 1968.
• 12: Robin Milner , Mads Tofte , Robert Harper, The Definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 13: Atsushi Ohori , Peter Buneman , Val Breazu-Tannen, Database programming in Machiavelli—a polymorphic language with static type inference, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.46-57, June 1989, Portland, Oregon, United States
• 14: Atsushi Ohori, A compilation method for ML-style polymorphic record calculi, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.154-165, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143200]
• 15: D. Rémy, Type checking records and variants in a natural extension of ML, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.77-88, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75284]
• 16: [16] D. Remy. Efficient representation of extensible records. In P. Lee, editor, Proceedings of ACM SIGPLAN Workshop on ML and its Applications, pages 12-16, 1992.
• 17: [17] M. Wand. Complete type inference for simple objects. In Proceedings of 2nd IEEE Symposium on Logic in Computer Science, pages 37-44, Ithaca, New York, June 1987.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Design, Management, Measurement, Performance, Theory