

![0_image_0.png](0_image_0.png)

$${\textsf{e}}\sqcap\exists{=}1_{a_{1}}\sqcap\forall a$$

whi h is translated to

## C _ Abstra Tclass U

8value.(Re Type u 9=1a1 u 8a1.(Re
Type u 9=1a2 u 8a2.(Re
Type u 9=1a3 u 8a3.C))):
Figure 9 shows a model of (S) represented as a graph. For 
larity, we have named the instan es of C, and hen e of Abstra tClass, with o and the instan es of Re Type with v. Observe the two dierent types of y les in the graph. The y le involving individuals o2; v3; v4, and v5 does not 
ause any problems sin
e it 
ontains an ar labeled with value, whi h is not part of the stru ture onstituting a omplex value. In fa t, v3 represents the re ord value [[a1: [[a2: [[a3: o2℄℄℄℄℄℄. On the other hand, due to the bad 
y
le involving v1 and v2, individual v1 represents (together with o2 
onne
ted via a3 to v1) a re
ord of innite depth.

We an nevertheless establish a orresponden e from nite models of (S) possibly ontaining bad y les to legal instan es of the ob je t-oriented s hema S. This an be a hieved by unfolding the bad y les in a model of (S) to innite trees. Obviously, the unfolding of a y le into an innite tree, generates an innite number of nodes, whi h would orrespond to an innite database state. However, we an restri t the dupli ation of individuals to those that represent set and re ord values, and thus are instan es of SetType and Re Type. The instan es of Abstra tClass, instead, are not dupli ated in the pro ess of unfolding, and therefore their number remains nite. Moreover, sin e the set of possible a tive values asso iated with ea h ob je t identier is bound by the depth of the s hema, we an in fa t blo k the unfolding of bad y les to the nite tree of depth equal to the depth of the s hema.

Let us rst formally dene the depth of an ob je t-oriented s hema S.

Denition 5.7 For a type expression T we dene depth (T ) indu tively as follows:

$$d\,eph(T)=\left\{\begin{array}{ll}0,&\mbox{if$T=C$.}\\ \max_{1\leq i\leq k}\left(d\,eph(T_{i})\right),&\mbox{if$T=\mbox{Union$T_{1}$,$\ldots$,$T_{k}$End.}}\\ 1+d\,eph(T^{\prime}),&\mbox{if$T=\mbox{Set-of$T^{\prime}$.}$}\\ 1+\max_{1\leq i\leq k}\left(d\,eph(T_{i})\right),&\mbox{if$T=\mbox{Record$A_{1}$:$T_{1}$,$\ldots$,$A_{k}$:$T_{k}$End.}}\end{array}\right.$$

The depth of an ob je t-oriented s hema S is dened as the maximum of depth (T ) for a type expression T in S.

