Algorithm 1 (Subsumption Algorithm) Given a concept description D and description graph G = ( N , E , n 0 , l ), subsumes?( D , G ) is defined to be true if and only if one of the following conditions hold:
1. The description graph G is marked incoherent.

2. D is a concept name or T, and D is an element of the atoms of no.

3. D is (≥ n r) and i) some r-edge of no has r as its role, and min greater than or equal to n; or ii) n = 0.

4. D is (< n r ) and some r-edge of no has r as its role, and max less than or equal to n.

5. D is a 1 · · a n ↓ b 1 · · b m , and there are rooted paths with label a 1 · · a n and b 1 · · b m in G ending at the same node.

6. D is Vr.C, for a role r, and either (i) some r-edge of no has r as its role and C'
as its restriction graph with subsumes?( C, G t ); or (ii) subsumes?( C, G ( T )). (Reason: Vr T = T )
7. D is Va.C, for an attribute a, and (i) some a-edge of G is of the form (no,a,n'), and subsumes?( C, ( N, E, n', l )); or  (ii) some r-edge of no has a as its attribute, and C' as its restriction graph with subsumes?( C, G ′ ); or (iii) subsumes?( C, G ( T )).

8. D is E N F and both subsumes?(E, G) and subsumes?(F, G) are true.
There are only two differences between this algorithm and the one for total attributes presented by Borgida and Patel-Schneider (see also Algorithm 2). First, in the partial attribute case, given D = Va.C, one needs to look up the value restriction either in some a-edge or some r-edge of G , since attributes can label both a-edges and r-edges. (In the total attribute case, attributes can only label a-edges so that examining r-edges was not necessary.) The second and most important distinction is the treatment of same-as equalities. As shown in the above algorithm, with D = a 1 ···a n ↓ b 1 ···b m one only needs to check whether there exist two paths labeled v := a1 ···an and w := b1 ···bm leading the same node in G. In the total attribute case, however, it suffices if there exist prefixes v' and w' of v and w with this property, as long as the remaining suffixes are identical.

Soundness and completeness of this algorithm is stated in the following theorem.

Theorem 3 Let C , D be CLASSIC- descriptions. Then, C E D iff subsumes?(D,GC),
where Gc is the canonical form of G(C). The soundness of the subsumption algorithm, i.e., the if direction in the theorem stated above, is pretty obvious. As in (Borgida & Patel-Schneider, 1994), the main point of the only-if direction (proof of completeness) is that the canonical graph Gc is deterministic, i.e., from any node, given a role or attribute name r, there is at most one outgoing r-edge or a-edge with r as label. We point the reader to (Borgida & Patel-Schneider, 1994) for the proof, since it is almost identical to the one for total attributes already published there. These proofs reveal that, for the if direction of Theorem 3, description graphs need not be normalized. Thus, one can also show: