Types With Extents: On Transforming and Querying Self-Referential Data-Structures (Dissertation Proposal)

The central theme of this paper is to study the properties and expressive power of data-models which use type systems with extents in order to represent recursive or self-referential data-structures. A standard type system is extended with classes which represent the finite extents of values stored in a database. Such an extended type system expresses constraints about a database instance which go beyond those normally associated with the typing of data-values, and takes on an important part of the functionality of a database schema. Recursion in data-structures is then constrained to be defined via these finite extents, so that all values in a database have a finite representation. The idea of extending a type system with such classes is not new. In particular [2] introduced a type system and data models equivalent to those used here. However such existing work focuses on the expressive power of systems which allow the dynamic creation of recursive values, while we are concerned more with the properties of querying and manipulating databases containing known static extensions of data-values.