SUBTYPING IN OODBS

One of the central concepts supported by object-oriented databases is isa relationship. Its intuitive simplicity is deceptive. In reality, t his term denotes several concepts, such as subtyping, subset relations hips, and inheritance of structure and/or behavior. Each of these is n on-trivial, and their interaction may be quite subtle. This paper deal s with subtyping and its properties, in the context of a model that al lows arbitrary data types and type constructors (but no function const ructor). For simplicity a model based on the algebraic specification a pproach is used, which partially explains the inability to deal with t he function constructor. Two intuitive ideas about subtyping are gener alized and investigated: first, that the set of elements associated wi th a subtype is a subset of the set associated with supertype, and sec ond, that each element of the subtype may be used in any place where a n element of the supertype is expected. A generalized subtyping relati on among abstract data types is defined, and its properties are invest igated. In particular, it is shown that often there exist many possibl e subtyping relations among two types and that testing for some desira ble properties, such as correctness, is in general undecidable. The no tion of natural subtyping relation (that is related to parametric abst ract data types) is introduced and shown to have a simple correctness proof. The paper concludes with a generalized type checking algorithm. (C) 1995 Academic Press, Inc.