Problems related to cardinality constraints

We need only the simple constraints expressing mandatory/optional participation and uniqueness/multivaluedness of components

Opponent: Entity-relationship modeling is used during requirements acquisition phase. At this stage, most constraints are unknown. Thus, we need only very limited expressibility.

Proponent: If the ER model is used only during this phase you do not need so much. However, the ER model is very convenient during conceptual modeling. At this phase all except none constraints should be known. Thus, we need the entire expressibility of the theory of cardinality constraints.

Opponent: Sorry, but people managed in the past very well with the smaller expressibility.

Proponent: And failed in applications which required more.

Opponent: Is there any axiomatization for these cardinality constraints?

Proponent: Yes, you can use the results of Sven Hartmann or those provided by description logics: The only axiom is given by the constraint card(R,X) = (0,.) for any sequence X of components of R. Further, the rules

{card(R,X) = (i,j)} => card(R,X) = (i-i', j+j')

{card(R,X) = (i,j), card(R,X) = (k,l)} => card(R,X) = (max(i,k), min(j,l)

ca be used to deduce the corresponding cardinality constraints if R,X are considered.

But let us now introduce a more complex example which is based on the example used by Casanova, Fagin and Papadimitrou in order to prove non-axiomatizability of sets of functional and inclusion dependencies by Hilbert-type deductive systems:

Given the entity types A, B, C, D.

Further we are given relationship types:

P0 = (B) , i.e. P0 specializes B,

P1 = (P0,A) ,

P = (P1,C),

G0i = (P0), i.e. a specialization of P0 for all i = 1,... n, with card(G0i,P0) = (1,.),

Gi = (G0i, C), for all i = 1,... n, with card(Gi,G0i) = (0,1),

S0i = (P0), i.e. another specialization of P0 for all i = 0,... n-1, with card(S0i,P0) = (1,.) ,

Si = (S0i,C,D) for all i = 0,... n-1,

Sn = (B,C,D) with card(Sn[C,D], C) = (0,1),

PS = (P,Sn),

Q = (P1), i.e. a specialization of P1,

Q0 = (Q,C) with card(Q0[Q[P1[A]],C], Q[P1[A]]) = (0,1),

SG0i = (G(i+1),Si) for i =0,...,n-1 card(SG0i[G(i+1)[B,C],Si[B,C]], Si[B,C]) = (1,.)

SG1i = (Gi, Si) for i=1,...,n-1 with card(SG1i[Gi[B,C],Si[B,C]], Si[B,C]) = (1,.) , and

PS = (P, Sn) with card(PS[Sn[B,D],P[B,C]], P[B,C]) = (1,.) .

Using the proof of Casanova et. al we can now show that no k-ary (not more than k premises in the rules) axiomatization exists for k less or equal n. Any k-ary deductive system has that property that

card(P[A,C], A) = (0,1)

cannot be derived.

This functional dependency however is implied by the given constraints.

Opponent: Sorry, but you have used the higher-order entity-relationship model. Thus, if I would restrict the model to the classical ER model or to the UML-ER model then this would not happen.

Proponent: This is not true again. The counter-example will be more complex. You have to use binary types in order to emulate the HERM schema above.