Intuitively, the extension of a relationship in a database state is a set of labeled tuples, and su h a set does not ontain the same element twi e. Therefore it is impli it in the semanti s of the ER model that there annot be two labeled tuples onne ted through all roles of the relationship to exa tly the same elements of the domain. In a model of the aluni knowledge base orresponding to the ER s hema, on the other hand, ea h tuple is represented by a new individual, and the above ondition is not impli it anymore. It also annot be imposed in aluni by suitable assertions. The following lemma, however, shows that we do not need su h an expli it ondition, when we are interested in reasoning on an aluni knowledge base orresponding to an ER s hema. This is due to the fa t that we an always restri t ourselves to onsidering only relation-des riptive models.

Lemma 4.7 Let S be an ER s hema, (S) be the aluni know ledge base obtained from S
a ording to Denition 4.5, and C be a on ept expression of (S). If C is nitely 
onsistent in (S), then there is a nite relation-des
riptive model I of (S) su
h that CI6= ;. Proof. Let I0 be a nite model of (S) su
h that CI6= ;. We 
an build a nite relationdes riptive model I0 by starting from I0 and applying the following 
onstru
tion on
e for ea h relationship in RS .

Let I be the model obtained in the previous step and let R 2 RS with rel S (R) =
[U1: E1; : : : ; Uk: Ek ℄ be the next relationship to whi
h we apply the 
onstru
tion. We 
onstru t from I a model IR su
h that 
ondition 8 is satised for relationship R.

Given an individual r 2 ((R))I, we denote by Ui(d), i 2 f1; : : : ; kg the (unique)
individual e su h that (r; e) 2 ((Ui ))I. For ei 2 ((Ei))I, i 2 f1; : : : ; kg we dene X(U1:e1;:::;Uk:ek) = fr 2 ((R))Ij Ui(d) = ei ; for i 2 f1; : : : ; kgg. We 
all 
on
i
t-set a set X(U1:e1;:::;Uk:ek) with more than one element. From ea
h 
on
i
t-set X(U1 :e1;:::;Uk:ek)
we randomly hoose one individual r, and we say that the others indu e a on i t on

(U1: e1; : : : ; Uk: ek). We 
all Conf the (nite) set of all ob je
ts indu
ing a 
on
i
t on some
(U1: e1; : : : ; Uk: ek).

We dene an interpretation I2Conf as the disjoint union of 2℄Conf 
opies of I, one 
opy, denoted by IZ , for every set Z 2 2Conf. We denote by dZ the 
opy in IZ of the individual d in I. Sin e the disjoint union of two models of an aluni knowledge base is again a model, I2Conf is a model of (S). Let IZ and IZ0 be two 
opies of I in I2Conf . We 
all ex hanging Uk(rZ ) with Uk(rZ0 ) the operation on I2Conf 
onsisting of repla
ing in ((Uk ))IZ
the pair (rZ ; Uk (rZ )) with (rZ ; Uk(rZ0 )) and, at the same time, repla
ing in ((Uk ))IZ0the pair (rZ0 ; Uk(rZ0 )) with (rZ0 ; Uk(rZ )). Intuitively, by ex
hanging Uk(rZ ) with Uk(rZ0 ), the individuals rZ and rZ0 do not indu
e 
on
i
ts anymore.

We onstru t now from I2Conf an interpretation IR as follows: For ea
h r 2 Conf and for ea h Z 2 2Conf su h that r 2 Z, we ex hange Uk(rZ ) with Uk(rZnfrg). It is possible to show that all on i ts are thus eliminated while no new on i t is reated. Hen e, in IR, 
ondition 8 for R is satised. We still have to show that IR is a model of (S) in whi h CIR 6= ;. Indeed, it is straightforward to he k by indu tion that for every on ept expression C0 appearing in (S), for all Z 2 2Conf, d 2 C0I if and only if dZ 2 C0IR . Thus all assertions of (S) are still satised in IR and CIR 6= ;.