

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

An a-edge is a tuple of the form (n1, a, n2) where n1, n2 are nodes and a is an attribute name.

A label of a node is defined to be ⊥ or a tuple of the form ( C, H ), consisting of a finite set C of concept names (the atoms of the node) and a finite set H of tuples (the r-edges of the node). Concept names in a description graph stand for atomic concept names and T.

We will occasionally use the notation n.Atoms and n.REdges to access the components C
and H of the node n.

An r-edge is a tuple, (r,m, M, G'), consisting of a role or attribute name, r; a min, m, which is a non-negative integer; a max, M, which is a non-negative integer or ∞; and a
(recursively nested) description graph G ′ . The graph G ′ will often be called the restriction graph of the node for the role r .  We require the nodes of G to be distinct from all the nodes of G and other nested description graphs of G. If r is an attribute, then we require: m = 0 and M E {0, 1}.

Given a description graph G and a node n E G.Nodes, we define G In to be the graph
(N, E, n, l); Gm is said to be rooted at n. A sequence p = noald2 ···aknk with k ≥ 0 and (ni-1, aj,ni) E G.Edges, i = 1, . . ,k, is called path in G from the node no to nk (p E G
for short); for k = 0 the path p is called empty; w = a 1 ···ak is called the label of p (the empty path has label ε ); p is called rooted if n 0 is the root of G. Occasionally, we write noal … aknk E G omitting the intermediate nodes.

Throughout this work we make the assumption that description graphs are connected.

A description graph is said to be connected if all nodes of the graph can be reached by a rooted path and all nested graphs are connected. The semantics of description graphs (see Definition 6) is not altered if nodes that cannot be reached from the root are deleted.

In order to merge description graphs we need the notion of "recursive set of nodes" of a description graph G : The recursive set of nodes of G is the union of the nodes of G and the recursive set of nodes of all nested description graphs of G.

Just as for concept descriptions, the semantics of description graphs is defined by means of an interpretation I . We introduce a function Y which assigns an individual of the domain of I to every node of the graph. This ensures that all same-as equalities are satisfied.