The relational model for databases proposed by Codd [5,6,7] owed its resounding success to using a simple, yet powerful, mathematical formalism to capture the representation and manipulation of data. It made a clear distinction between the formal semantics of its constructs and operations (the Relational Algebra) and the effective computation of query expressions taking their meaning in the Relational Algebra (the Relational Calculus). In its essence, the only mathematical formalism used by Relational Algebra is elementary Set Theory. This enabled expressing simply and elegantly database queries whose semantic correctness is straightforward to establish due to the pure declarativity of the Relational Algebra. It also enabled using the formal algebraic properties of its operations (such as commutativity, associativity, etc.) to optimize implementation of the Relation Calculus while provably preserving a query's formal meaning. Thus, the Relational Calculus provides the kernel language in which to express the various constructs of a practical query language based on relations, which are ascribed a precise formal semantics in the Relational Algebra. Such a practical query language has been proposed, and well accepted, as a standard known as the Structured Query Language (SQL).2
Object-oriented databases have evolved out of the relational model by allowing more flexibility in the form taken by the data and incorporating the object-oriented notions of type encapsulation and inheritance. The added flexibility consists essentially in allowing arbitrary nesting of record object structures (i.e., tuples) and collections (i.e., sets, bags, lists, etc.). In other words, whereas the relational model deals exclusively with relations over tuples of primitive types (i.e., sets of flat tuples--so-called ``relational normal forms''), the object model imposes no such restriction. The other added conveniences--(polymorphic) typing, inheritance, and class/method encapsulation--have been introduced for the same obvious reasons as for general-purpose programming languages (i.e., data abstraction, reusability, modularity, etc.). As it turns out, the mere task of dealing with non-normal form objects alone in the same simple formal fashion as was done in the relational model (i.e., providing an algebra and a calculus that can be optimized thanks to the algebra's equational theory) has been a hard task to tackle. Only recently have some elegant, yet powerful, formalisms emerged that begin to meet the challenge [1,16,17]. In other words, these formalisms are good candidates to stand with respect to OQL, the ODMG Object Query Language standard [2], as the relational algebra and calculus stand with respect to SQL.
While the work done in the past twenty or so years in programming language design theory has made object-orientation and typing an orthogonal issue to the underlying computational model, one does need an underlying calculus to start with (e.g., in order to have C++, one needs to have C first). In other words, given a calculus, be it functional, logical, or imperative, it is not a major task to recast it as an object-oriented calculus by adapting its syntax and typing rules to deal with encapsulation and inheritance, while keeping its underlying computational model. My intention, thus, is to start with a ``flat'' typed object algebra and calculus rich enough to express and optimize the construction of a constraint model from a high-level definition of the kind supported by OPL, and delay incorporating true object-orientation until such a basic formalism is at hand. Indeed, providing full object-orientation for MATISSE is only a second phase which should unfold relatively straightforwardly once its basic formalism has been designed.