Type inference in a database programming language

ABSTRACT

We extend an ML-like implicit type system to include a number of structures and operations that are common in database programming including sets, labeled records, joins and projections. We then show that the type inference problem of the system is decidable by extending the notion of principal type schemes to include conditions on substitutions. Combined with Milner's polymorphic let constructor, our language also supports type inheritance.

REFERENCES

• BO88: Peter Buneman , Achim Jung , Atsushi Ohori, Using powerdomains to generalize relational databases, Theoretical Computer Science, v.91 n.1, p.23-55, Dec. 9, 1991 [doi>10.1016/0304-3975(91)90266-5]
• Car84: Luca Cardelli, A semantics of multiple inheritance., Proc. of the international symposium on Semantics of data types, p.51-67, July 1984, Sophia-Antipolis, France
• CW86: Luca Cardelli , Peter Wegner, On understanding types, data abstraction, and polymorphism, ACM Computing Surveys (CSUR), v.17 n.4, p.471-523, Dec. 1985 [doi>10.1145/6041.6042]
• DKM84: Cynthia Dwork , Paris C. Kanellakis , John C. Mitchell, On the sequential nature of unification, Journal of Logic Programming, v.1 n.1, p.35-50, June 1984 [doi>10.1016/0743-1066(84)90022-0]
• DM82: Luis Damas , Robin Milner, Principal type-schemes for functional programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-212, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582176]
• GJ79: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• Gol74: E.M. Gold. Complexity of automaton identification from given data. 1974. Unpublished manuscript, Reference found in {GJ79}.
• HMM86: R. Harper, D. B. MacQueen, and R. Milner. Standard ML. LFCS Report Series ECS-LFCS-86-2, Department of Computer Science, University of Edinburgh, March 1986.
• Mil78: R. Milner. A Theory of Type Polymorphism in Programming. Journal of Uompater and System Sciences, 17:348-375, 1978.
• Mit84: John C. Mitchell, Coercion and type inference, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.175-185, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800529]
• Rob65: J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
• Sta88: R. Stansifer, Type inference with subtypes, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.88-97, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73568]
• Wan87: M. Wand. Complete Type Inference for Simple Objects. In Proceedings of the Second Anual Symposium on Logic in Uompater Science, pages 37-44, Ithaca, New York, June 1987.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

General Terms:
Algorithms, Design, Languages