In case the set of atoms and r-edges of n is empty, define C n := T.

Referring to the graph G in Figure 1, C G contains the same-as equalities model o madeBy ↓ model o madeBy and madeBy ↓ model o madeBy. Furthermore, if no denotes the root of G, C has the value restrictions VE.C nn , Vmodel.T, and VmodelmadeBy.T, where C nn corresponds to Lemon as defined in the introduction, but without the same-as equality. Note that, although in this case the same-as equality model o madeBy ↓ model o madeBy is not needed, one cannot dispense with 1.(i) in the construction above, as illustrated by the following example: Without 1.(i), the description graph G ( a ↓ a ) would be turned into the description T, which is not equivalent to a ↓ a since the same-as equality requires that the path a has a value, which may not be the case.

It is easy to prove that the translation thus defined is correct in the following sense
(Küsters & Borgida, 1999).

Lemma 2  Every connected description graph G is equivalent to its translation CG, i.e., for all interpretations I: GI = CI.

## 3.4 Canonical Description Graphs

In the following we occasionally refer to "marking a node incoherent"; this means that the label of this node is changed to ⊥ . " Marking a description graph as incoherent " means that the description graph is replaced by the graph G ( ⊥ ) corresponding to ⊥ , i.e., the graph consisting only of one node with label ⊥ .

One important property of canonical description graphs is that they are deterministic, i.e., every node has at most one outgoing edge (a-edge or r-edge) labeled with the same attribute or role name. Following Borgida and Patel-Schneider (1994), in order to turn a description graph into a canonical graph we need to merge a-edges and r-edges. In addition, different from their work, it might be necessary to "lift" r-edges to a-edges.

To merge two a-edges (n,a,n,) and (n,a,n2) in a description graph G, replace them with a single new edge (n, a, n') where n' is the result of merging n 1 and n 2 .  In addition, replace n 1 and n 2 by n 1 in all other a-edges of G.

In order to merge two r-edges (r, s, k, G, ), (r, s2, k, G2) replace them by the new r-edge
(r, max(s1, s2), min(k1, k2), G1 ⊕ G2).

To lift up an r-edge ( a, m, M, G a ) of a node n in a concept graph G with an a-edge
(n, a, n 1 ), remove it from n.REdges, and augment G by adding G g .Nodes to G.Nodes, G . Edges to G.Edges, as well as adding (n, a, G a .Root) to G.Edges. A precondition for applying this transformation is that M = 1, or M = 0 and G a corresponds to the graph G( L ). The reason for this precondition is that if an r-edge of the form ( a, 0, 0, G g ) is lifted without G a being inconsistent, the fact that no a -successors are allowed is lost. Normalization rule 5 (see below) will guarantee that this precondition can always be satisfied.

A description graph G is transformed into canonical form by exhaustively applying the following normalization rules. A graph is called canonical if none of these rules can be applied.

1. If some node in G is marked incoherent, mark the description graph as incoherent.

( Reason: Even if the node is not a root, attributes corresponding to a-edges must always