Object-oriented data models represent a current endpoint in the evolution of data models 23]. Their formalization has been attempted in a variety of papers, including 5; 6; 19]. This short paper indicates what we consider the common intersection of these (and other) approaches; we list the relevant features and components, and give an idea of how to formalize the notion of an object-oriented database schema.
An object-oriented data model has to capture a variety of requirements 8; 27], which di er considerably from those that traditional data models have to meet. However, many system developers seem not to care about formal models as a solid foundation of their system, but simply design a \data de nition language" in which the relevant features can be coded. In our opinion, a formal model for object-oriented databases basically has to capture the same intuitions as models for other types of databases, which are the following:
1. It has to provide an adequate linguistic abstraction for certain database applications. 2. It should provide a precise semantics for a data de nition language. 3. It has to be composed of both a speci cation and an operational part. 4. It represents a computational paradigm as a basis for formal investigations. In this short note, we do not present a comprehensive survey of formal models for object-oriented databases which have been proposed in the literature, but instead try to point out the fundamentals of how such models are obtained. The result can be considered as a framework in which the essentials of the object-oriented paradigm can be expressed concisely and further studied. Indeed, we give hints to various such investigations that have recently been undertaken.
In this section, we describe what we perceive as the core aspects of various proposals for object models, and we do so by distinguishing structural from behavioral aspects. Thus, we generally consider schemas, the central notion of any conceptual database description, to be pairs of the form S = (S struc ,
; in what follows, we rst consider each component in isolation and then indicate how the two interact. We mention, however, that while it is generally agreed that an object-oriented data model has to capture both structure and behavior, the former can be obtained by using the experience from the relational, nested relational and complex-object models, but the latter represents a completely new challenge to database researchers. Consequently, a consensus seems achieved for structure, but not for behavior. The core aspects of formal models for objectoriented databases are summarized in Figure 1, in which labels of arrows represent function names. In brief, the only structuring mechanism is the class which describes both structure and behavior for its instances, the objects. Structure is captured as a type for a class (in our notation, a function \type" associates a type with each class; the other function names shown above are to be interpreted similarly, see below). A type is nothing but a description of a domain, i.e., a set of values, and may or may not be named (in the former case, type names distinct from class names and attribute names must be provided). Values comprise the state of an object and can be as complex as the type system allows (i.e., depending on the availability of base types and constructors like tuple, set, bag, list, etc.). Behavior is manifested in a set of messages associated with each class (its external interface), which are internally implemented using methods that are executable on objects. Hence, objects have a state and a behavior; in addition, they are uniquely identi ed. Messages are speci ed by providing a signature, and by associating several signatures with the same message name, the latter gets overloaded. Not shown in Figure 1 is the possibility to organize classes in an inheritance hierarchy; also not shown is the fact that class attributes are allowed to reference other classes, thereby forming an aggregation lattice.
We next look at structural as well as behavioral aspects in more detail. Regarding the modeling of structure, more precisely highly-structured information, complex data types are all that is basically needed, since they serve as descriptions for domains of complex values. One way to introduce such types, i.e., to de ne a type system T, is the following:
(i) integer, string, float, boolean T;
(ii) if A i are distinct attributes and t i 2 T, 1 i n; then A 1 : t 1 ; : : :; A n : t n ] 2 T (\tuple type"); (iii) if t 2 T; then ftg 2 T (\set type"); (iv) if t 2 T; then < t >2 T (\list type").
In other words, a type system is made up of base types, from which complex types may be derived using (eventually attributes and) constructors. Note that this requires nothing additional but the availability of attribute names. Clearly, other base types as well as additional or alternative constructors could straightforwardly be included. Notice also that here types are not named; for practical reasons, the use of type names may be desirable (e.g., in order to be able to reuse type de nitions in various places throughout a schema), and if it is, it can easily be added to the above in the way indicated earlier.
The notion of a domain as a \reservoir" of possible values can be de ned as follows; it just has to obey constructor applications: (a) dom(integer) is the set of all integers; dom is analogously de ned for string, float, boolean;
(b) dom( A 1 : t 1 ; : :
In a structurally object-oriented context, the rst thing that needs to be introduced beyond complex types and domains as de ned above is the possibility to share pieces of information between distinct types, or to aggregate objects from simpler ones. At the level of type declarations, an easy way to model this is the introduction of another reservoir of names, this time called class names, which are additionally allowed as types. In other words, object types are complex types as above with the following new condition:
(v) C T, where C is a nite set of class names. This states nothing but the fact that class names are allowed as types (below we will complement this with the requirement that classes themselves have types).
The intuition behind this new condition is that objects from the underlying application all are distinguished by their identity, get collected into classes, and can reference other objects (share subobjects). To provide for this at the level of domains, let us rst assume the availability of a nite set OID of object identi ers which includes the special identier nil (to capture \empty" references); next, object domains, i.e., sets of possible values for objects are complex values as above with the following additional condition:
(e) dom(c) = OID for each c 2 C. Thus, classes are assumed to be instantiated by objects (class-name types take object identi ers as values, in the same way as, say, the integer type takes integer numbers as values). Clearly, this alone is not enough, since class instances commonlyhave distinct sets of object identi ers associated with them. We will show below how that (and, for example, the fact that sometimes inclusion dependencies need to hold between sets of class instances) is captured at the instance level.
The object-oriented paradigm has another dimension for organizing information besides aggregation, which is inheritance, or the possibility to de ne a class as a specialization of one or more other classes. To this end, a subtyping relation is needed through which it can be expressed that a subclass inherits the structure of a superclass. Such a relation can be de ned in various ways; for example, it can be dened semantically by requiring that the sets of values or instances of types, where one is a subtype of the other, are in a subset relationship. We prefer a simpler, syntactical approach, which has, for example, the advantage that checking subtype relationships can be automated:
Let T be a set of object types. A subtyping relation T T is de ned as follows:
(i) t t for each t 2 T, (ii) A 1 : t 1 ; : : :; A n : t n ] A 0 1 : t 0 1 ; : : :
With these preparations, we arrive at the following de nition for objectbase schemas that can describe structure of arbitrary complexity: A structural schema is a named quadruple of the form S struc = (C; T; type; isa) where (i) C is a ( nite) set of class names, (ii) T is a ( nite) set of types which uses as class names only elements from C, (iii) type : C ! T is a total function associating a type with each class name, (iv) isa C C is a partial order on C which is consistent w.r.t. subtyping, i.e., c isa c 0 ) type(c) type(c 0 ) for all c; c 0 2 C. This de nition resembles what can be found in a variety of models proposed in the literature, including 17; 19; 20; 25] and others. Notice that it still leaves several aspects open, like single vs. multiple inheritance; if the latter is desired, a condition needs to be added stating how to con icts should be resolved. Also, implementations typically add a number of additional features, like attributes as functions 22; 29], a distinction of class attributes from instance attributes (the latter are shared by all objects associated with a class, while the former represent, for example, aggregate information like an average salary only relevant to the class as a whole) 7], a unique root of the class hierarchy from which every class inherits 20], a distinction between private and public attributes 12], a di erent set of constructors (like one with an additional array constructor to describe matrices), an explicit inclusion of distinct types of relationships between classes and their objects (in particular various forms of composition, see 18]), integrity constraints which represent semantic information on the set of valid databases instances (a proposal in that direction appears in 3; 4], where object constraints, class constraints, and database constraints are distinguished). For another example, the ODMG-93 proposal for a standardized model 10] contains explicit keys, (binary) relationships, and inverse attributes. None of these features appear in our model, the reason being that these are not speci c to object-orientation.
The second important aspect of an object-oriented database is that it is intended to capture behavior, besides structure. To this end, the relevant intuition is that classes have attached to them a set of messages, which are speci ed in the schema via signatures, and which are implemented as methods. In addition, behavior can be inherited by subclasses, and message names can be overloaded, i.e., re-used in various contexts.
So a behavioral schema is a named ve-tuple of the form S behav = (C; M; P; messg; impl) where (i) C is a ( nite) set of class names as above (again needed here since references to it have to be made), (ii) M is a ( nite) set of message names, where each m 2 M has associated with it a nonempty set sign(m) = fs 1 ; : : :s l g, l 1, of signatures; each s h , 1 h l, has the form s h : c t 1 : : : t p ! t for c 2 C, t 1 ; : : :; t p ; t 2 T (each signature has the receiver of the message as its rst component), (iii) P is a ( nite) set of methods or programs, (iv) messg : C ! 2 M is a mapping s.t. for each c 2 C and for each m 2 messg(c) there exists a signature s 2 sign(m) satisfying s 1] = c, (v) impl: f(m; c) j m 2 messg (c)g ! P is a partial function.
In combining structural and behavioral schemas, we nally obtain an objectbase schema of the form S = (C; (T; type; isa;); (M; P; isa; messg; impl)). S is called consistent if the following conditions are satis ed:
(i) c isa c 0 implies messg(c 0 ) messg(c) for all c; c 0 2 C, (ii) if c isa c 0 and s; s 0 2 sign(m) for m 2 M such that s : c t 1 : : : t n ! t, s 0 : c 0 t 0 1 : : : t 0 n ! t 0 , then t i t 0 i for each i, 1 i n, and t t 0 , (iii) for each m 2 messg(c) there exists a c 0 2 C) s.t. c isa c 0 and impl(m; c 0 ) is de ned. Condition (i) just says that subclasses inherit the behavior of their superclasses. Condition (ii) says that message-name overloading is done with compatible signatures, and is called the covariance condition in 20 ; 9]. The covariance condition is a signi cant difference from what is used at a corresponding point in programming languages, and which is known as the contravariance condition; for a detailed explanation, see 9]. Finally, Condition (iii) states that for each message associated with a class, its implementation must at least be available in some superclass.
It is interesting to note that various natural conditions can be imposed on the programs that are used as implementations of messages. We now sketch one of them, which is based on the view that programs are functions on domains 20]. More formally, if m 2 M and s : c t 1 : : : t n ! t 2 sign(m), then impl(m; c), if de ned, is a program p 2 P of the form p : dom(c) dom(t 1 ) : : : dom(t n ) ! dom(t)
The condition in question informally states that if message overloading appears in isa-related classes (so that the corresponding signatures satisfy the covariance condition), then the associated programs coincide (as functions) on the subclass. More formally, we have: If jsign(m)j > 1 for some m 2 M, then the following holds: If s; s 0 2 sign(m) such that s : c t 1 : : : t n ! t, s 0 : c 0 t 0 1 : : : t 0 n ! t 0 , c isa c 0 , t i t 0 i for each i, 1 i n, t t 0 , and impl(m; c) = p, impl(m; c 0 ) = p 0 , then p and p 0 agree on dom(c) dom(t 1 ) : : : dom(t n ).
A variety of formal investigations for behavioral schemata in the sense de ned above can already be found in the literature, which investigate questions including termination of method executions, limited depth of method-call nestings (an issue related to precompilation of method executions), wellde nedness of method calls, i.e., consistency as well as reachability considerations (issues related to type inference and schema evolution), expressiveness of method implementation languages (relative to some notion of completeness), complexity of method executions, or potential parallelism of method evaluations. To investigate such issues, our general notion of schema is made precise in various ways. For example, 15] xes a simple imperative language for implementing methods as retrieval programs, contrasts them with update programs and shows undecidability results for the latter. 1; 2] as well as 11] introduce distinct notions of a method schema to study behavioral issues of OODBS; for example, 2] investigates implications of the covariance condition using the formalism of program schemas, while 11] looks at tractability guarantees corresponding to those known for relational query languages. Also, it is pretty straightforward to de ne an object algebra for a model like the one sketched in the previous section; see, for example, the papers in 13]. That carries over to issues like query optimization, implementation of operations, and query processing. A survey of other recent investigations that have similar bases or origins can be found in 28].
We emphasize again that the model just sketched can be seen as description of the core of vastly any object-oriented model; however, this is valid only relative to the fact that many specialities, which have been proposed in the literature, or which are being built into commercial systems, are neglected here.
We conclude this section with a brief indication of how object databases, i.e., sets of class instances or extensions, can be de ned over a given schema: For a given objectbase schema S, an objectbase over S is a triple d(S) = (O, inst, val) s.
We next survey several modeling issues in objectoriented databases which have not yet received enough research attention:
1. Entities can have roles that vary over time. For example, some person object may at one point be a student, at another an employee, and at a third a club member; while the person's identity never changes, its type changes several times. For example, in a design environment it is usually necessary to maintain incomplete designs, i.e., objects whose types get completed in the course of time. 4. Classes may contain \too few" instances. For example, consider a database in which all persons living in a large country are represented. In this context, so many combinations of meaningful properties have to be distinguished that it might become necessary to introduce arti cial name constructions for classes, like unmarried-nonstudent-autoOwnerrenter-taxpayer 26], and each such class has only very few instances. More generally, the name space available for classes might not be su cient. 5. Objects and their classes might come into existence in reverse order. A database user in a design environment like CAD creates objects in the rst place, not type de nitions or even classes. The usage of databases thus di ers considerably from traditional applications where schema design has to be completed prior to instance creation. We mention that one issue or the other from this list is sometimes re ected already in existing models, but never as a basic design target. Alternative approaches, which takes these issues into consideration right from the start, appear, for example, in 21; 24; 16]. A possible general concept for the solution of these problems seems the exploitation of prototype languages, which suggest to model applications without a classi cation that partitions the world into entity sets. A prototype represents default behavior for some concept, and new objects can re-use part of the knowledge stored in a prototype by saying how they di er from it. Upon receiving a message an object does not understand, it can forward (delegate) it to its prototype to invoke more general behavior. In the area of object-oriented programming languages, many people believe that this approach has advantages over the class-based one with inheritance, with respect to the representation of default knowledge and incrementally and dynamically modifying concepts. The investigation of classless models in the context of object-oriented databases has only recently been proposed in 26], and a concrete model is reported in 14]. 4
In this short paper we have tried to give a rough personal account of recent work on formal models for object-oriented databases. Although there is not a single uniform such model, the foundations on which such models have to be built seem understood, and even standardization e orts have recently been launched 10]. On the other hand, a number of interesting research issues still deserve further investigation. In particular, formal models as they are currently available seem hardly suited for the nonstandard applications which initiated the consideration of object-orientation in the context of databases. A reason seems to be that many researchers have too much of a relational background, and try to exploit that as long as possible; this is more than con rmed by the ODMG-93 proposal. As was done a number of years ago, when database people discovered what programming-language or knowledge-representation people had been studying for years already, it seems again necessary to take recent developments in these areas into account, and to adopt them for solving the problems database applications have.