A Study of Semantics, Types and Languages for Databases and Object-Oriented Programming

The purpose of this thesis is to investigate a type system for databases and object-oriented programming and to design a statically typed programming language for these applications. Such a language should ideally have a static type system that supports: polymorphism and static type inference, rich data structures and operations to represent various data models for databases including the relational model and more recent complex object models, central features of object-oriented programming including user definable class hierarchies, multiple inheritance, and data abstraction, the notion of extents and object-identities for object-oriented databases. Without a proper formalism, it is not obvious that the construction of such a type system is possible. This thesis attempts to construct one such formalism and proposes a programming language that uniformly integrate all of the above features. The specific contributions of this thesis include: A simple semantics for ML polymorphism and axiomatization of the equational theory of ML. A uniform generalization of the relational model to arbitrary complex database objects that are constructed by labeled records, labeled variants, finite sets and recursive definition. A framework for semantics of types for complex database objects. The notion of conditional typing schemes that extends Milner\u27s typing scheme for ML to a wide range of complex structures and operations. A formulation of the notion of classes and inheritance in an ML style static type system. The notion of views that enable us to represent object-oriented databases in an ML style static type system. A proposal of a polymorphic programming language, Machiavelli, for databases and object-oriented programming with static type inference. In addition to the above technical contributions, a prototype implementation of Machiavelli that embodies most of the features presented in this thesis has been done in Standard ML of New Jersey