An incremental, strongly typed, database query language (functional, combinators)
Rishiyur S. Nikhil · 1984
We present an experimental programming system for databases that permits an interactive and applicative style of programming. The system is based on the applicative language FQL, for which we show two versions; a basic version resembling Backus' FP that is compact and easy to implement, and an extended version that resembles ML, and is easier to use. The language is portable in that it can be interfaced easily to existing database systems. We show a novel implementation technique for FQL that eliminates the need for environments, permits the construction of infinite (or very large) structures, and provides several self-optimizing features. The technique uses new machine-based combinators which offer improvements in performance over the standard S and K combinators. The language is strongly-typed, supporting polymorphic and higher-order functions, and abstract data types. A type-inferencing algorithm allows us to type-check an expression even in the absence of type declarations. This type-inference algorithm is also used to resolve the overloading of identifiers. The Functional Data Model through which databases are viewed meshes cleanly into the type system and the implementation of the language, allowing us to deal with databases without the introduction of any new concepts. The type system also provides a rich schema-browsing facility, again within the same framework. The use of a polymorphic type system in the context of incremental program development is explored. Here a function may be tested (executed) before other functions that it depends on are defined, or modified after other functions depend on it. The type system provides detailed information about dependencies between functions, and about the nature and location of type-errors, allowing the minimization of type-checking that must be performed incrementally.