Ordering and Types in Databases

This paper investigates a method to represent database objects as typed expressions in programming languages. A simple typed language supporting non-flat records, higher-order relations, and natural join expressions is defined. A denotational semantics of this language is then presented. Expressions are interpreted into a domain containing Smyth's powerdomain. In order to give semantics to types, a new model of types, a filter model is proposed. Types are then interpreted as filters in a domain. The type inference system of the language is shown to be sound in this model.