A polymorphic relational algebra and its optimization

The notion of a polymorphic database and the optimization of polymorphic queries-specifically, optimization of queries under the Morpheus data model-is addressed. The notion of query optimization through type inference, applicable both to polymorphic databases and traditional monomorphic databases, is introduced. The Morpheus data model and its type inference rules are reviewed and a polymorphic relational algebra is characterized. It is shown how the inference rules can be used for static optimization of a few sample queries. It is concluded that type inference provides a formal mechanism for optimizing a very rich extension to the relational algebra. The approach retains the basic framework that lead to the wide acceptance of the relational model, while enriching it with the structural expressiveness of the object-oriented approaches of recent years