so in detail, because the tools used for deciding subsumption are intimately related to the computation of lcs.

T-subsumption in CLASSIC is decided by a multi-part process. First, descriptions are turned into description graphs. Next, description graphs are put into canonical form, where certain inferences are explicated and other redundancies are reduced by combining nodes and edges in the graph. Finally, t-subsumption is determined between a description and a canonical description graph.

In order to "inherit" the proofs, we have tried to minimize the necessary adjustments to the specification in (Borgida & Patel-Schneider, 1994). For this reason, roughly speaking, attributes are treated as roles unless they form part of a same-as equality. (Note that attributes participating in a same-as construct must have values!) To some extent, this will allow us to adopt the semantics of the original description graphs, which is crucial for proofs. However, the two different occurrences of attributes, namely, in a same-as equality vs. a role in a value-restriction, require us to modify and extend the definition of description graphs, the normalization rules, and the subsumption algorithm itself.

In the following, we present the steps of the subsumption algorithm in detail. We start with the definition of description graphs.

## 3.1 Description Graphs

Intuitively, description graphs reflect the syntactic structure of concept descriptions. A description graph is a labeled, directed multigraph, with a distinguished node.  Roughly speaking, the edges ( a-edges ) of the graph capture the constraints expressed by same-as equalities. The labels of nodes contain, among others, a set of so-called r-edges, which correspond to value restrictions. Unlike the description graphs defined by Borgida and Patel-Schneider, here the r-edges are not only labeled with role names but also with attribute nmes. (We shall comment later on the advantage of this modification in order to deal with partial attributes.) The r-edges lead to nested description graphs, representing the concepts of the corresponding value restrictions.

Before defining description graphs formally, in Figure 1 we present a graph corresponding to the concept description Lemon defined in the introduction.  We use G(Manufacturer),
G (Model), as well as G (RepairReport) to denote description graphs for the concept names M anufacturer, Model, and RepairReport. These graphs are very simple; they merely consist of one node, labeled with the corresponding concept name. In general, such graphs can be more complex since a value restriction like Vr.C leads to a (possibly complex) nested concept description C .

Although number restrictions on attributes are not allowed, r-edges labeled with attributes, like model and madeBy, always have the restriction [0, 1] in order to capture the semantics of attributes. Formally, description graphs, nodes, and edges are defined mutually recursively as follows: Definition 5 A description graph G is a tuple ( N, E, no,l), consisting of a finite set N of nodes; a finite set E of edges (a-edges); a distinguished node no E N (root of the graph); and a functionl from N into the set of labels of nodes.  We will occasionally use the notation G.Nodes, G.Edges, and G.root to access the components N, E and no of the graph G.