have a value (since they participate in same-as equalities), and this value cannot belong to the empty set.)

2. If some r-edge in a node has its min greater than its max, mark the node incoherent.

( Reason:  ≥ 2 r Π ≤ 1 r ≡ ↓)
3. Add T to the atoms of every node, if absent.

4. If some r-edge in a node has its restriction graph marked incoherent, change its max to 0. (Reason: (≤ 0 r) ≡ ∀r. T. )
5. If some r-edge in a node has a max of 0, mark its restriction graph as incoherent.

( Reason:  See 4.)
6. If some r-edge is of the form ( r, 0, 00, G ′ ) where G ′ only contains one node with empty set of atoms or with the atoms set to {T} and no r-edges, then remove this r-edge.

( Reason:  Vr T ≡ T .)
7. If some node has two r-edges labeled with the same role, merge the two edges, as described above. ( Reason: Vr.C N Ar.D = Ar.( C N D ).)
8. If some description graph has two a-edges from the same node labeled with the same attribute, merge the two edges, as described above. ( Reason: Va.C NVa.D E
∀ a ( C Π D ) )
9. If some node in a graph has both an a-edge and an r-edge for the same attribute, then
"lift up the r-edge" if the precondition is satisfied (see above). ( Reason: The value restrictions imposed on attributes that participate in same-as equalities must be made explicit and gathered at one place similar to the previous to cases.)
We need to show that the transformations to canonical form do not change the semantics of the graph. The main difficulty is in showing that the merging processes and the lifting preserve the semantics. The only difference from (Borgida & Patel-Schneider, 1994) is that in addition to merging r-edges and a-edges we also need to lift up r-edges.  Therefore, we omit the proofs showing that merging edges preserves extensions. The proofs of the following two lemmas are routine and quite similar to the one of Lemma 5. Lemma 3  Let G = ( N, E, no,l ) be a description graph with two mergeable a-edges and let G ' = ( N ', E ', n ', l ') be the result of merging these two a-edges. Then, G ≡ G '.

Lemma 4 Let n be a node with two mergeable r-edges and let n' be the node with these edges merged. Then, n x = n 1 for every interpretation I.

Lemma 5 Let G = (N, E, no, l) be a description graph with node n and a-edge (n, a, n"). Suppose n has an associated r-edge (a, m, M, Ga). Provided that the precondition for lifting r-edges is satisfied and that G' = (N',E',n',l') is the result of this transformation, then G = G .

Proof. It is sufficient to show that Gj n = Gj n , since only the label of n is changed in Cj and only n obtains an additional a-edge, which points to the graph G a not connected to