3. DL Semantics

Description Logic Semantics

The following provides the formal set-based semantics of the Description Logic table:

Name	Syntax	Semantics
Top	⊤	𝚫ℐ
Bottom	⊥	∅
Conjunction	C ⊓ D	Cℐ ⋂ Dℐ
Disjunction	C ⊔ D	Cℐ ⋃ Dℐ
Negation	¬C	𝚫ℐ \ Dℐ
Existential restriction	∃r.C	{d ∈ 𝚫ℐ | ∃e ∈ 𝚫ℐ.(d,e) ∈ rℐ ⋀ e ∈ Cℐ}
Value restriction	∀r.C	{d ∈ 𝚫ℐ | ∀e ∈ 𝚫ℐ.(d,e) ∈ rℐ → e ∈ Cℐ}
Self restriction	∃r.Self	{d ∈ 𝚫ℐ | (d,d) ∈ rℐ}
Unqualified number restriction	(≤n r) (≥n r) (=n r)	{d ∈ 𝚫ℐ | #{e | (d,e) ∈ rℐ} ≤ n} {d ∈ 𝚫ℐ | #{e | (d,e) ∈ rℐ} ≥ n} {d ∈ 𝚫ℐ | #{e | (d,e) ∈ rℐ} = n}
Qualified number restriction	(≤n r.C) (≥n r.C) (=n r.C)	{d ∈ 𝚫ℐ | #{e | (d,e) ∈ rℐ ⋀ e ∈ Cℐ} ≤ n} {d ∈ 𝚫ℐ | #{e | (d,e) ∈ rℐ ⋀ e ∈ Cℐ} ≥ n} {d ∈ 𝚫ℐ | #{e | (d,e) ∈ rℐ ⋀ e ∈ Cℐ} = n}
Nominal	{a}	{aℐ}
Role value map	r ⊑ s	{d ∈ 𝚫ℐ | {e | (d,e) ∈ rℐ} = {e | (d,e) ∈ rℐ}}
Predicate restriction	∃c1,…,ck.P	{d ∈ 𝚫ℐ | (c1ℐ(d),…,ckℐ(d)) ∈ P𝔻}
Role composition	r ∘ s	{(d,f) ∈ 𝚫ℐ × 𝚫ℐ | ∃e ∈ 𝚫ℐ.(d,e) ∈ rℐ ⋀ (e,f) ∈ sℐ}
Inverse role	r⁻	{(e,d) ∈ 𝚫ℐ × 𝚫ℐ | (d,e) ∈ rℐ}
Feature chain	g1⋯gnh	(g1⋯gnh)ℐ(d) = hℐ(gnℐ(⋯(giℐ(d))⋯))
General Concept Inclusion	C ⊑ D	Cℐ ⊆ Dℐ
Concept Definition	A ≡ C	Aℐ ≡ Cℐ
Role inclusion	r ⊑ s	rℐ ⊆ sℐ
Role disjointness	Disj(r,s)	rℐ ⋂ sℐ = ∅
Role transitivity	Trans(r)	∀d,e,f ∈ 𝚫ℐ ((d,e) ∈ rℐ ⋀ (e,f) ∈ rℐ → (d,f) ∈ rℐ)
Role functionality	Func(r)	∀d ∈ 𝚫ℐ #{e ∈ 𝚫ℐ
Role reflexivity	Ref(r)	{(d,d)
Role irreflexivity	Irref(r)	rℐ ⊆ {(_d,e) ∈ 𝚫ℐ × 𝚫ℐ
Role symmetry	Sym(r)	{(e,d)
Role antisymmetry	Asym(r)	rℐ ⋂ (rℐ)- ⊆ {(d,d)
Concept assertion	a:C	rℐ ∈ Cℐ
Role assertion	(a,b):r	(aℐ,bℐ) ∈ rℐ

Description Logic and Sets

Description Logic (DL) is used to "describe" concepts and roles (or classes, and relationships/properties). However, these descriptions are an abstract concept over data, rather than specifying particular data.

On the other hand, Sets describe a specific group of instances that are members of the set. This is a concrete representation of the data.

When a Concept (from DL) is applied to a particular context, then a set can be derived. For instance, when the concept "Employee" is considered in the context of a particular company, then the resulting set will contain all of the employees of that company. But when the concept is applied in the context of a different company, then this will result in a completely different set of employees. This is clearer when we combine expressions. For instance, we may want to consider nurses who are employees, and so we create the conjunction of Nurse ⊓ Employee. In the concept of a legal firm, the set of people who are described by this concept is likely to be an empty set, but in a healthcare company the set might be the majority of the workforce. Similarly, when roles are applied in a particular context, this creates a set of specific relationships in that context.

When Concepts and Roles are defined together in relation to one another, they form a Model. When a Model is applied within a context to create sets, this is referred to as Interpreting the model in that context. For our Employees, we may have a role for "reportsTo" which connects most employees to their manager, and when we interpret this in the context of a specific company, we can get a set of everyone who works there, and the reporting structure of that company's Org Chart.

Because the Concepts and Roles in a model can be used to define sets in a particular context, but are not themselves sets, they are not manipulated or combined using the syntax of set operations. Instead, we have similar, related operators, that are specific to Description Logic. This is why DL has ⊓ when set theory uses ⋂, ⊔ when sets use ⋃,and ⊑ when sets use ⊆. These operators are distinct from the set operators, but are visually similar.

Interpretations

An Interpretation ℐ=(𝚫^ℐ,⋅^ℐ) is defined as a set of a instances 𝚫^ℐ, along with an operator ⋅^ℐ that maps concepts to a subset of 𝚫^ℐ, and maps roles to a subset of binary relations defined by 𝚫^ℐ × 𝚫^ℐ. For instance, in the context of a particular company, 𝚫^ℐ could contain all the employees, contractors, business units, assets, and contracts. The ⋅^ℐ mapping then maps this complete set of elements to the appropriate concepts, while also mapping relationships between elements to appropriate roles.

So in a hypothetical company "Peter", "Mary", and "Accounting" may appear within 𝚫^ℐ. This company, that may both be part of the "Employee" class, with ("Mary","Accounting") and ("Peter","Accounting") being part of the "worksIn" role, and ("Peter","Mary") being an element of the "reportsTo" role.

Some roles may also connect entities to elements of a concrete domain 𝔻, where 𝔻 contains values such as strings and numbers. These sorts of roles are often referred to as attributes.

Feature Chains

In the above table we can see "Feature chain" defining a composition of roles to a specific attribute. "Abstract features" describe roles that connect one entity in 𝚫^ℐ to another, such as g^ℐ:𝚫^ℐ→𝚫^ℐ while "concrete features" describe roles that connect entities to concrete values, as in h^ℐ:𝚫^ℐ→𝚫^𝔻.

Predicate Restrictions

In the "Predicate restriction" entry of the table, a set of attributes (which may be abstract roles referencing elements of 𝚫^ℐ, but will typically be values in 𝚫^𝔻) on an entity is referenced, where some predicate P^𝔻 can be applied to these values to determine a true/false value.

For example, consider the attributes startDate and endDate. The predicate greaterThan can be defined as a binary predicate that returns true when the first argument is larger than the second, and false otherwise. Consequently, the expression ∃startDate,endDate.greaterThan references a class of all elements which have startDate and endDate values where the startDate comes after the endDate (we probably want to report all instances of this class as erroneous).

Note that predicates P^𝔻 are not defined by DL, and are expected to be defined elsewhere.