Polymorphic type inference for the relational algebra in the functional database programming language neon. 44th annual Southeast regional conference

A database programming language is a programming language ex-tended with database operations. In this paper we extend a core functional language with explicitly labeled tuples and the opera-tions of the relational algebra. We present the functional database programming language Neon along with a polymorphic type infer-ence algorithm that can infer a ‘type formula’, that is, a type to-gether with type constraints, for any valid Neon program. Neon has the following salient features: (1) let-bound polymorphism, (2) explicitly labeled tuples, (3) polymorphic tuple operations, no-tably extension, (4) sets and set operations, and (5) polymorphic relational algebra operations, notably natural join. To type-check a Neon program the standard Damas-Milner type inference algo-rithm needs to be extended so that it collects constraints on type variables imposed by tuple and relational operations. The type in-ference algorithm has been successfully implemented in Haskell. 1