Polymorphism and Type Inference in Database Programming

The polymorphic type system of ML can be extended in two ways that make it appropriate as the basis of a database programming language. The first is an extension to the language of types that captures the polymorphic nature of field selection; the second is a technique that generalizes relational operators to arbitrary data structures. The combination provides a statically typed language in which relational databases may be cleanly represented as typed structures. As in ML types are inferred, which relieves the programmer of making the rather complicated type assertions that may be required to express the most general type of a program that involves field selection and generalized relational operators. It is also possible to use these ideas to implement various aspects of object-oriented databases. By implementing database objects as reference types and generating the appropriate views - sets of structures with identity - we can achieve a degree of static type checking for object-oriented databases. Moreover it is possible to exploit the type system to check the consistency of object-oriented classes (abstract data types with inheritance). A prototype language based on these ideas has been implemented. While it lacks some important practical features, it demonstrates that a wide variety of database structures can be cleanly represented in a polymorphic programming language