
## 2. Description Logics: An Introduction

DLs are used to describe situations using various kinds of individuals**, related by** roles**, and**
grouped into concepts**. Roles that are restricted to be (partial) functions are distinguished,**
and are called attributes.

In this section we present the syntax and semantics of DLs, as **well as outlining the**
interaction with a typical DL-based KBMS, and some implementation strategies.

## 2.1 Syntax And Semantics

As illustrated in Figure 1, DLs provide a compositional and structured language for talking about these kinds of things. Composite concepts are **obtained according to the**
syntax presented in Table 1, which includes the concept constructors mentioned in this paper. The meta-symbols have the following referents: CN is a concept name, p **is an**
atomic role (including an attribute), f is an attribute, C and D **are general concepts,** b is an individual, while n **is an integer; subscripts may occasionally be added to the above.**
RoleChain ::= [p1**, . . . , p**n] AttributeChain ::= [f1**, . . . , f**n]
C ::= thing | **nothing** | CN
| and( C1, . . ., Cn ) | at-least(n,p) | **at-most**(n,p)
| all(p,C) | some(p,C) | fills(p,b) | one-of(b1**, . . . b**n)
| same-as(AttributeChain1, **AttributeChain**2) | subset-of(RoleChain1, **RoleChain**2)

## Table 1: Syntax Of Concept Constructors Used.

To give meaning to the above syntactic terms, one can give descriptions a denotational semantics using an interpretation I=(∆I,·
I). I **starts by assigning to each concept name**
a subset of the domain ∆I, to each role a subset of ∆I× ∆I**, to each attribute an element**
of ∆I × ∆Irestricted to be functional, and to each individual some element of ∆I**. The**
interpretation is then extended to composite terms as follows. First, role chains (resp.

attribute chains) are interpreted as mappings resulting from relation composition:

$[p_{1},\cdots,p_{n}]^{T}=\{x\mapsto S_{x}\ \mid\ S_{x}=\{y\mid\exists z_{1},...,z_{n+1}.\ z_{1}=x\wedge z_{n+1}=y\wedge\bigwedge_{i=1}^{n}(z_{i},z_{i+1})\in p_{i}^{T}\}\}$

Table 2 then presents the interpretation of complex terms using the interpretation of their components.

Alternatively, by noting that concepts are like unary predicates, and roles are like binary predicates, we can offer translation schemes from descriptions to Predicate Calculus. For example, and(AMERICAN,OLD) corresponds to the formula AMERICAN(γ)∧OLD(γ**), where** γ is a free variable, while all(authoredBy,VENUSIAN) corresponds to ∀y.authoredBy(**γ, y**) ⇒
VENUSIAN(y).

The connection between these two kinds of specifications is that interpretations can be applied to both predicate calculus formulas as well as concepts (Baader, 1996; Borgida,