In this paper, we present a type model for object-oriented databases. Most object-oriented databases only provide users with flat objects whose structure is a record of other objects. In order to have a powerful expression power, an object-oriented database should not only provide objects but also complex values recursively built using the set, tuple and disjunctive constructors. Our type model presents two notions: that of classes whose instances are objects with identity and that of types whose instances are complex values. The two notions are mixed in that an object is modeled as a pair containing an identifier and a value, and a value is a complex structure which contains objects and values. We define in this context the notions of subtyping and provide a set inclusion semantics for subtyping.

The Altair group is currently designing an object-oriented data base system called O 2 . This paper presents a formal description of the object-oriented data model of this system. It proposes a type system defined in the framework of a set-and-tuple data model. It models the well known inheritance mechanism and enforces strong typing.

We present a probabilistic model for evaluating the size of relations derived from given relations through relational algebra operators. We define tools to estimate the derived relations size and we state the assumptions underwhich we perform such an evaluation.The particular class of data base schemata in which we evaluate the derived relation size is characterized by properties such as independence between two relations having union-compatible domains or independence between distinct tuples in a relation. We show that, knowing the expected size of all projections of each relation in the database, we can compute the size of each query expressed in relational algebra and we give the results for each operator of this language (selection, projection, union, intersection, e-join).