

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

the rest of G ′ . W.l.o.g. we therefore may assume that n is the root of G, i.e., n = n 0 . Let d E G™. Thus, there is a function Y from N into ∆ ™ as specified in Definition 6 and an individual e such that d = Y(n), e = Y(n"), and (d,e) E aT. This implies e E GT. Hence, there exists a function Y ′ from G α . N odes into ∆ × for G α and e satisfying the conditions in Definition 6. Since the sets of nodes of G and G a are disjoint, we can define Y to be the union of Y and Y', i.e., Y''(m) := Y(m) for all nodes m in G and Y''(m) := Y'(m) for all nodes m in G α . Since, by construction, for the additional a-edge ( n, α, G α, Root ) ∈ E ′ we have (Y"(n),Y"(G",Root)) E aT, it follows that all conditions in Definition 6 are satisfied for d and G ′ , and thus, d ∈ G ′ I ′
Now let d ∈ G f T . Thus, there is a function Y from N ′ into ∆ T according to Definition 6.

Let e := Y"( G a .Root ) = Y"( n''). Let G" be the description graph we obtain from G a by deleting the nodes corresponding to G a , which is the same graph as G without the r-edge
( a, m, M, G a ). If we restrict Y" to the nodes of G ff, then it follows d ∈ G ff x . Furthermore, restricting Y" to the nodes of G a yields e E G a . In particular, G a can not be marked incoherent. Then, our precondition ensures M = 1. Thus, since e is the only a -successor of d, we can conclude d ∈ G I .

→
Having dealt with the issue of merging and lifting, it is now easy to verify that "normalization" does not affect the meaning of description graphs.

Theorem 2  If G is a description graph and G 1 is the corresponding canonical description graph, then G ≡ G'.

As an example, the canonical description graph of the graph given in Figure 1 is depicted in Figure 2.

## 3.5 Subsumption Algorithm

The final part of the subsumption process is checking to see if a canonical description graph is subsumed by a concept description. As in Borgida and Patel-Schneider (1994), where attributes are total, it turns out that it is not necessary to turn the potential subsumer into a canonical description graph. The subsumption algorithm presented next can also be considered as a characterization of subsumption.