Definition 2 An interpretation I consists of a nonempty domain Δ I and an interpretation function I. The interpretation function assigns extensions to atomic identifiers as follows:
- The extension of a concept name E is some subset E T of the domain.

- The extension of a role name r is some subset r x of Δ x × Δ x .

- The extension of an attribute name a is some partial function a x from ∆ x to ∆ x , i.e.,
if (x, y1) E a T and (x, y2) E a T then y1 = y2
Given roles or attributes r i , we use (r 1 ···rn) I to denote the composition of the binary relations r T . If n = 0 then the result is ε T , which denotes the identity relation, i.e., ε T :=
{d,d) | d ∈ Δ T } . For an individual d ∈ Δ T , we define r T (d) := {e | (d, e) ∈ r T } . If the r i 's are attributes, we say that (r 1 ··rn) ¯ is defined for d iff (r 1 ···rn) ¯ (d) ̸= 0; occasionally, we will refer to (r1 . . rn)(d) I as the image of d under (r1 . . . rn)I(d).

The extension C I of a concept description C is inductively defined as follows:

$$\bullet\;\;\top\,^{\cal T}:=\,\Delta^{\cal T};$$
* $(\geq n\,r\,)^{\mathcal{I}}:=\{d\in\Delta^{\mathcal{I}}\mid cardinality\big{(}\,\{e\in\Delta^{\mathcal{I}}\mid(d,e)\in r^{\mathcal{I}}\}\big{)}\geq n\,\}$;
- (≤ n r ) I := {d ∈ Δ I | cardinality({e ∈ Δ I | (d, e) ∈ r I }) ≤ n };
- ( C Π D ) T := C T ∩ D T ;
- (Vr.C) X := {d E A X | r X (d) C C X } where r  is a role or an attribute;

$$\mathbf{\partial}\cdot\mathbf{\partial}b_{h}\,)^{\mathcal{I}}:=\{d\in\Delta^{\mathcal{I}}\mid$$

- ( a 1 · · a k ↓ b 1 · · b h ) × := { d ∈ ∆ × | ( a 1 · · a k ) ×  and ( b 1 · · b h ) ×  are  defined  for  d

$$\left(\,\{e\in\Delta^{\mathcal{I}}\,|\,\left(d,e\right)\in r^{\mathcal{I}}\}\right)\leq n\,\},$$

and (a 1 ···ak) Z (d) = (b 1 ···bh) Z (d)}.
Note that in the above definition attributes are interpreted as partial functions. Since the main point of this paper is to demonstrate the impact of different semantics for attributes, we occasionally restrict the set of interpretations to those that map attributes to total functions. Such interpretations are called t-interpretations and the attributes interpreted in this way are called total attributes in order to distinguish them from partial ones.

We stress, as remarked in the introduction, that in the definition of ( a 1 · · · a k ↓ b 1 · · · b h ) · ,
a 1 · · a k and b 1 · · b h must be defined on d in order for d to satisfy the same-as restriction.

Although this is the standard semantics for same-as equalities, one could also think of relaxing this restriction. For example, the same-as condition might be specified to hold if either both paths are undefined or both images are defined and have identical values. A
third definition might be satisfied if even just one of the paths is undefined. Each of these definitions of the semantics of same-as might lead to different results. However, in this paper we only pursue the standard semantics.

The subsumption relationship between concept descriptions is defined as follows.

Definition 3 A concept description C is subsumed by the concept description D (C E D
for short) if and only if for all interpretations I, CI C DI.  If we consider only total interpretations, we get t-subsumption: C Et D iff C T C D T for all t-interpretations I.