Peter Buneman
Atsushi Ohori
Abstract
In order to find a static type system that adequately supports database languages, we need to express the most general type of a program that involves database operations. This can be achieved through an extension to the type system of ML that captures the polymorphic nation of field selection, together with a techniques that generalizes relational operators to arbitrary data structures. The combination provides a statically typed language in which generalized relational databases may be cleanly represented as typed structures. As in ML types are inferred, which relieves the programmer of making the type assertions that may be required in a complex database environment.
These extensions may also be used to provide static polymorphic typechecking in object-oriented languages and databases. A problem that arises with object-oriented databases is the apparent need for dynamic typechecking when dealing queries on heterogeneous collections of objects. An extension of the type system needed for generalized relational operations can also be used for manipulating collections of dynamically typed values in a statically typed language. A prototype language based on these ideas has been implemented. While it lacks a proper treatment of persistent data, it demonstrates that a wide variety of database structures can be cleanly represented in a polymorphic programming language.
- ATKINSON, M. P., AND BUNEMAN, O.P. 1987. Types and persistence in database programming languages. ACM Comput. Surv. 19, 1, 105-190. Google Scholar
Digital Library
- ABITEBOUL, S., AND BONNER, A. 1991. Objects and views. In Proceedings of the 1991 ACM SIGMOD Conference. (Denver, Col., May 29-31). ACM, New York, 238-247. Google ScholarDigital Library
- ATKINSON, M. P., BAILEY, P. J., CHISHOLM, K. J., COCKSHOT'F, W. P., AND MORRISON, R. 1983. An approach to persistent programming. Comput. J. 26, 4 (Nov.), 360-365.Google ScholarCross Ref
- ATrdNSON, M. P., BANClLHON, F., DEWITr, D., DITrRICK, K., MAIER, D., AND ZDONIK, S. 1989. The object-oriented database system manifesto. In Proceedings of the First Deductive and Object-Oriented Database Conference (Kyote, Japan, Dec.).Google Scholar
- ALBANO, A., CARDELLI, r., AND ORSINI, R. 1985. Galileo: A strongly typed, interactive conceptual language. ACM Trans. Database Syst. IO, 2 (June), 230-260. Google ScholarDigital Library
- ABADI, M., CARDELLI, L., PIERCE, B., AND PLOTKIN, C. 1991. Dynamic typing in a statically-typed language. ACM Trans. Program Lang. Syst. 13, 2, 237-268. Google ScholarDigital Library
- APPEL, A. W., AND Ma~CQUEEN, D.B. 1991. Standard ML of New Jersey. In Proceedings of 3rd International Symposium on Programming Languages and Logic Programming. Springer Verlag, New York, 1 13.Google ScholarCross Ref
- AUGUSTSSON, L. 1984. A compiler for lazy ML. In Proceedings of the 1984 ACM Symposium on LISP and Functional Programming (Austin, Tex., Aug. 6-8). ACM, New York, 218-227. Google ScholarDigital Library
- BANCILHON, F., BRIGGS, T., KHOSHAFIAN, S., AND VALDURIEZ, P. 1988. FAD, a powerful and simple database language. In Proceedings of the Conference on Very_ Large Data Bases. 97-105. Google ScholarDigital Library
- BISKUP, J. 1981. A formal approach to null values in database relations. In Advances in Data Base Theory. vol. 1. Plenum Press, New York.Google Scholar
- BUNEMAN, r., JUNG, A., AND OHORI, A. 1991. Using pewerdomains to generalize relational databases. Theor. Comput. Sci. 91, 1, 23-56. Google ScholarDigital Library
- BUNEMAN, P., LIBKIN, L., SUCIU, D., TANNEN, V., AND WONG, L. 1994. Comprehension syntax. SIGMOD Record, 23, I (Mar.), 87-96. Google ScholarDigital Library
- BUNEMAN, P., AND OHORI, A. 1991. A type system that reconciles classes and extents. In Proceedings of the 3rd International Workshop on Database Programming Language (Nafplion, Greece, Aug.). Morgan-Kaufmann, San Marco, Calif., 191-202. Google ScholarDigital Library
- BREAZu-TANNEN, V., BUNEMAN, P., AND NAQVI, S. 1991. Structural recursion as a query language. In Proceedings of the 3rd International Workshop on Database Programming Languages (Nafplion, Greece, Aug.). Morgan-Kaufmann, San Mateo, Calif., 9-19. Google ScholarDigital Library
- BREAZU-TANNEN, V., BUNEMAN, P., AND WONO, L. 1992. Naturally embedded query languages. In Proceedings of the International Conference on Database Theory (Berlin, Oct.). Lecture Notes in Computer Science, Springer-Verlag, New York, 140-154. Google ScholarDigital Library
- BREAzu-TANNEN, V., AND SUB--AM, R. 1991. Logical and computational aspects of programming with sets/bags/lists. In Proceedings of the 18th International Colloquium On Automata, Languages, and Programming (Madrid, Spain, July). lecture Notes in Computer Science, Vol. 510, Springer-Verlag, New York, 60-75. Google ScholarDigital Library
- C~d~OELLI, L. 1986. Amber. In Combinators and Functional Programming, Lecture Notes in Computer Science, Vol. 242. Springer-Verlag, New York, 21-47. Google ScholarDigital Library
- C~ELLI, L. 1988. A semantics of multiple inheritance. Inf. Comput. 76, 138-164. (Special issue devoted to Symposium on Semantics of Data Types, Sophia-Antipolis, France, 1984). Google ScholarDigital Library
- CARDELLI, L., AND MITCHELL, g. 1989. Operations on records. In Proceedings of Mathematical Foundation of Programming Semantics. Lecture Notes in Computer Science, Vol. 442. Springer-Verlag, New York, 22-52. Google ScholarDigital Library
- CAaOZLU, L., AND WEGmSa, P. 1985. On understanding types, data abstraction, and polymorphism. ACM Comput. Surv. 17, 4 (Dec.), 471-522. Google ScholarDigital Library
- COPELAND, G., AND M/flEa, D. 1984. Making Smalltalk a database system. In Proceedings of the ACM SIGMOD Conference (Boston, Mass., June 18-21). ACM, New York, 316-325. Google ScholarDigital Library
- COURCELLE, B. 1983. Fundamental properties of infinite trees. Thcor. Comput. Sci. 25, 95-169.Google ScholarCross Ref
- DAMAS, L., AND MILN~.n, R. 1982. Principal type-schemes for functional programs. In Proceedings of the 9th Annual ACM Symposium on Principles of Programming Languages. (AI- buquerque, N.M., Jan. 25-27). ACM, New York, 207-212. Google ScholarDigital Library
- GALLIER, J., AND SNYDER, W. 1989. Complete sets of transformations for general E-unification. Theor. Comput. Sci. 67, 2, 203-260. Google ScholarDigital Library
- HARPER, R., AND PIEgCE, B. 1991. A record calculus based on symmetric concatenation. In Proceedings of the 18th Annual ACM Symposium on Principles of Programming Languages. (Orlando, Fla., Jan 21-23). ACM, New York, 131-142. Google ScholarDigital Library
- HART, K., AND WONG, L. 1994. Query language for genetic databases. Manuscript available on Vf~f%V via ht tp: / / www. cis. upenn, edu /'wfan / DBHOME. html.Google Scholar
- HINDLEY, R. 1969. The principal type-schema of an object in combinatory logic. Trans. AMS 146 (Dec.), 23-60.Google Scholar
- HOANG, M., MrrCHELL, J., AND VISWANA~, R. 1993. Standard ML weak polymorphism and imperative constructs. In Proceedings of lEEE Symposium on Logic in Computer Science.Google ScholarCross Ref
- HUDAK, P., PEYTON JONES, S., WADLER, P., BOUTEL, B., FAIRBAIRN, J., FASEL, J., GUZMAN, M., HAMMOND, K., HUGHES, J., JOHNSSON, T., KIEBURTZ, D., NIKHIL, R., PARTAIN, W., AND PERTER- SON, J. 1992. Report on programming language Haskell, a non-strict, purely functional language, version 1.2. ACM SIGPLAN Not., Haskell Special Issue 27, 5. Google ScholarDigital Library
- HUET, G. 1976. R~solution d'~quation darts les langages d'ordre 1, 2 .. to. Tech. Pep., Univ. Paris, Paris, France.Google Scholar
- HULL, R., AND KING, R. 1987. Semantic database modeling: Survey, applications and research issues. ACM Comput. Surv. 19, 3, (Sept.). Google ScholarDigital Library
- ICHBIAH, J. H., HELIARD, J. G., ROUBtNE, O., BAP~ES, J. G. P., KRIEG-BRUECKNER, B., AND WICHMANN, B.A. 1979. Rationale of the design of the programming language Ada. ACM SIGPLAN Not. 14, 6. Google ScholarDigital Library
- IMIELmSK% T., AND LIPSI~, JR., W. 1984. Incomplete information in relational databases. J. ACM 31, 4 (Oct.), 761-791. Google ScholarDigital Library
- IMMERMAN, N., PATNAIK, S., AND STEMPLE, D. 1991. The expressiveness of a family of finite set languages. In Proceedings of the lOth ACM Symposium on Principles of Database Systems (Denver, Col., May 29-31). ACM, New York, 37-52. Google ScholarDigital Library
- JATEGAONKAg, L. A., AND MITCHELL, J. C. 1988. ML with extended pattern matching and subtypes. In Proceedings of the ACM Conference on LISP and Functional Programming (Snowbird, Ut., July 25-29). ACM, New York, 198-211. Google ScholarDigital Library
- KIM, W. 1994. Observations on the ODMG-93 proposal. ACM SIGMOD Record 23, 1 (Mar.). Google ScholarDigital Library
- LEROY, X. 1993. Polymorphism by name for references and continuations. In Proceedings of the 20th Annual ACM SIGPLAN-S1GACT Symposium on Principles of Programming Languages (Charleston, S.C., Jan. 10-13). ACM, New York, 220-231. Google ScholarDigital Library
- LEROY, X., AND WIES, P. 1991. Polymorphic type inference and assignment. In Proceedings of the 1$th Annual ACM Symposium on Principles of Programming Languages (Orlando, Fla., Jan. 21-23). ACM, New York, 291-302. Google ScholarDigital Library
- LIPSgl, JR., W. 1979. On semantic issues connected with incomplete information databases. ACM Trans. Database Syst. 4, 3 (Sept.), 262-296. Google ScholarDigital Library
- MACQUEEN, D., PLOTKIN, G, AND SETHI, R. 1986. An ideal model for recursive polymorphic types. Inf. Control 71, 95-130. Google ScholarDigital Library
- MACQUEEN, D. 1988. References and weak polymorphism. Note in Standard ML of New Jersey Distribution Package.Google Scholar
- MORRISON, R., BROWN, A. L., CONNOR, R. C. H., AND DEARLE, A. 1989. Napier88 Reference Manual. Tecb. Rep., Dept. Computer Science, Univ. St Andrews.Google Scholar
- MILNER, R.1978. A theory of type polymorphism in programming. J. Comput. Syst. Sci. 17, 348-375.Google ScholarCross Ref
- MILNER, R., TOFTE, M., AND HARPER, R. 1990. The Definition of Standard ML. The MIT Press, Cambridge, Mass. Google ScholarDigital Library
- MITCHELL, J.C. 1990. Type systems for programming languages. In Handbook of Theoretical Computer Science. J. van Leeuwen, Ed. MIT Press/Elsevier, Cambridge, Mass./Amsterdam, The Netherlands, ch. 8, 365-458. Google ScholarDigital Library
- OBJECT DESIGN, INC. 1991. ObjectStore Reference Manual. Burlington, Mass.Google Scholar
- OHORI, A. 1989a. A simple semantics for ML polymorphism. In Proceedings of the ACM/1FIP Conference on Functional Programming Languages and Computer Architecture (London, England, Sept.). ACM, New York, 281-292. Google ScholarDigital Library
- OHom, A. 1989b. A study of types, semantics and languages for databases and object-oriented programming. Ph.D. dissertation. Univ. of Pennsylvania.Google Scholar
- OHORI, A. 1990. Semantics of types for database objects. Theor. Comput. Sci. 76, 53 91. Google ScholarDigital Library
- OHORI, A. 1992. A compilation method for ML-style polymorphic record calculi. In Proceedings of the 19th Annual ACM/SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Albuquerque, NM., Jan. 19-22). ACM, New York, 154 165. Google ScholarDigital Library
- OHORI, A., ~.Nl) BUNEMAN, P. 1988. Type inference in a database programming language. In Proceedings of the 1988 ACM Conference on LISP and Functional Programming (Snowbird, Ut., July 25-27). ACM, New York, pp. 174-183. Google ScholarDigital Library
- OHOR1, A., AND BUNEM~'~, P. 1994. Static type inference for parametric classes. In Theoretical Aspects of Object-Oriented Programming. J. Mitchell and C. Gunter, Eds. MIT Press, Cambridge, Mass., 121 138. Google ScholarDigital Library
- OHORI, A., BUNEM~'4, P., ^NO BgEAZU-T~Er4, V. 1989. Database programming in Machiavelli: A polymorphic language with static type inference. In Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data (Portland, Ore., May 31-June 2). ACM, New York, 46-57. Google ScholarDigital Library
- OHom, A. 1995. A polymorphic record calculus and its compilation. ACM Trans. Program. Lang. Syst. 17, 6 (Nov.), 844-895. Google ScholarDigital Library
- PLOTKIN, G.1979. Call-by-name, call-by-value, and the A-calculus. Theor. Comput. Sci. I, 125 159.Google Scholar
- REMY, D. 1992. Typing record concatenation for free. In Proceedings of the 19th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Albuquerque, NM., Jan. 19-22). ACM, New York, 166-175. Google ScholarDigital Library
- REMY, D. 1994. Typechecking records and variants in a natural extension of ML. In Theoretical Aspects of Object-Oriented Programming, J. Mitchell and C. Gunter, Eds MIT Press, Cambridge, Mass., 67-96. Google ScholarDigital Library
- ROBINSON, J.A. 1965. A machine-oriented logic based on the resolution principle. J. ACM 12, 1 (Jan.), 23 41. Google ScholarDigital Library
- SCHMH)T, J. W. 1977. Some high level language constructs for data of type relation. ACM Trans. Database Syst. 2, 3 (Sept.), 247-261. Google ScholarDigital Library
- STROUSTRUP, B. The C + + Programming Language. Addison-Wesley, Reading, Mass. Google ScholarDigital Library
- STONEBr~CEa, M., AND ROWE, L. 1986. The Design of POSTGRES. In Proceedings of ACM- SIGMOD International Conference on Management of Data (Washington, D.C., May 28-30). ACM, New York, 340-355. Google ScholarDigital Library
- TORTE, M. 1988. Operational semantics and polymorphic type inference. Ph.D. dissertation, Department of Computer Science, Univ. Edinburgh, Edinburgh, Scotland.Google Scholar
- TURNER, D.A. 1985. Miranda: A non-strict functional language with polymorphic types. In Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science, Vol. 201. Springer-Verlag, New York, 1-16. Google ScholarDigital Library
- WADLER, P. 1991. Comprehending monads. In Proceedings of the ACM Conference on LISP and Functional Programming (Nice, France). Google ScholarDigital Library
- WAND, M. 1987. Complete type inference for simple objects. In Proceedings of the 2nd IEEE Symposium on Logic in Computer Science (Ithaca, NY, June). IEEE, New York, 37-44.Google Scholar
- WAND, M. 1988, Corrigendum: Complete type inference for simple objects. In Proceedings of the 3rd 1EEE Symposium on Logic in Computer Science (Edinburgh, Scotland). IEEE, New York, 132.Google ScholarCross Ref
- WANO, M. 1989. Type inference for record concatenation and simple objects. In Proceedings of 4th IEEE Symposium on Logic in Computer Science. IEEE, New York, 92-97. Google ScholarDigital Library
- WATt, D. A., ANY TR{NOER, P. 1991. Towards a theory of bulk types. Fide Tech. Rep. 91/26, Glasgow Univ., Glasgow, Scotland.Google Scholar
- WroTH, N. 1977. Modula: A language for modular multiprogramming. In Sofiw. Pract. Exper. 7, 1, 3-35.Google Scholar
- WONG, L. 1994. Querying nested collections. Ph.D. dissertation. August 1994. Available as IRCS Rep. 94-09. Dept. of Computer and Information Science, Univ. Pennsylvania, Philadelphia. Google ScholarDigital Library
- ZANIOLO, C. 1984. Database relations with null values. J. Comput. Syst. Sci. 28, 1, 142-166.Google ScholarCross Ref
Index Terms
- Polymorphism and type inference in database programming
Recommendations
Polymorphism, subtyping, and type inference in MLsub
POPL '17: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming LanguagesWe present a type system combining subtyping and ML-style parametric polymorphism. Unlike previous work, our system supports type inference and has compact principal types. We demonstrate this system in the minimal language MLsub, which types a strict ...
Polymorphism, subtyping, and type inference in MLsub
POPL '17We present a type system combining subtyping and ML-style parametric polymorphism. Unlike previous work, our system supports type inference and has compact principal types. We demonstrate this system in the minimal language MLsub, which types a strict ...
Type inference, principal typings, and let-polymorphism for first-class mixin modules
Proceedings of the tenth ACM SIGPLAN international conference on Functional programmingA mixin module is a programming abstraction that simultaneously generalizes λ-abstractions, records, and mutually recursive definitions. Although various mixin module type systems have been developed, no one has investigated principal typings or ...
Reviews
Doris C. Appleby
The authors report on work in progress to implement object-oriented features related to database programming. Defining and manipulating databases usually requires strict adherence to types declared in static schemas. This interferes with polymorphic methods that call for dynamic type checking. The authors show “how to extend the polymorphic type system of ML to database operations, and…that the system [named Machiavelli<__?__Pub Caret>] provides a practical basis for database programming languages where relational and object-oriented databases can be cleanly represented.” The authors have adhered to the ML practice of formally stating and proving semantics along with syntax. The <__?__Pub Fmt nolinebreak>Machiavelli<__?__Pub Fmt /nolinebreak> Core includes several new types: relation, complex object, mutable object, and a set of descriptions. Kinded typing and a <__?__Pub Fmt italic>kind<__?__Pub Fmt /italic> function, K k: type ? k: kind , are necessary for the representation of polymorphic record operations. Also added are four basic operations dealing with sets and partial values, used to define database operations for equality, consistency checking, selection, join, and <__?__Pub Fmt nolinebreak>projection.<__?__Pub Fmt /nolinebreak> Work is planned to provide a proper treatment of persistent data, abstract classes, code sharing, and collection types other than records. This paper is important, summarizing a decade of work. It is well referenced, is clearly organized and written, and deserves a careful reading.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments