Introduction to Description Logics

Last verification:	20180914
Tools required for this lab:	–

Introduction

Description Logics: an introduction into its basic ideas

1 Description Logics Intro

In Introduction to ontologies you have learnt basic ideas about ontologies.

Ontologies consist of classes, properties and individuals.
- Classes describe sets of objects.
- Properties describe relations between classes and attributes of classes.
- Individuals are instances of classes linked with other individuals by properties.
Classes may be organized into hierarchies.
Properties may be organized into hierarchies.
There are object properties and data properties.
Properties have domains and ranges.

The above information can be expressed in RDF Schema which is a simple ontology language for the Semantic Web.

However, more complex ontologies require more expressive language. For example:

How to say that the range of a property hasChildren is Person when applied to a person and Elephant when applied to an elephant?
How to say that all instances of person have a mother that is also a person, or that persons have exactly 2 parents?
How to say that isPartOf is a transitive property, that hasPart is the inverse of isPartOf or that touches is symmetrical?

In this lab, you will get to know more advanced ontologies based on Description Logics (DL). You will learn the DL languages and understand how OWL corresponds to selected DL.

1.1 Description Logics Basics

DL are a family of Knowledge Representation formalisms
they describe world of interest by means of concepts and relations between them
they provide formal semantics and inference services

DLs are related to Semantic networks and frame languages
basic idea is to represent knowledge in a network form where
- nodes → characterize concepts (or more complex relationships)
- links → describe relationships among concepts

Fig.1. Exemplary graph.

Semantic networks were not equipped with formal logic-based semantics.

1.1.1 Examples of DL expressions

Assertions about individuals

concept assertions e.g.
- $person(Fred)$ - Fred is a person
- $cat(Tibbs)$ Tibbs is a cat
role assertions e.g.
- $has\_pet(Fred, Tibbs)$ - Fred has a pet which is Tibbs

Statements about concepts

concept definitions (necessary and sufficient conditions) e.g.
- $man \equiv person \sqcap adult \sqcap male$ - A man is an adult male person
- $cat\_liker \equiv person \sqcap \exists likes.cat$ - A cat liker is a person and there exists a cat that he/she likes
relations between concepts e.g.
- $likes(cat\_liker, cat)$ - (every) cat liker likes a cat
- $eats\_only(sheep, grass)$ - (every) sheep eats only grass
axioms e.g.
- $cat \sqsubseteq animal$ a cat is an animal (hierarchy of concepts)
- $sheep \sqsubseteq animal \sqcap \forall eats.grass$ a sheep is an animal which eats only grass (it's a necessary but not sufficient condition)

1.1.2 Relation to First Order Logic

mostly DL are subsets of first-order logic | but not all of DL (e.g. those with transitive closure of rules are not)
- concept names ⇔ unary predicates
- atomic roles ⇔ binary predicates
- concepts ⇔ formulas with one free variable

Description	DL syntax	FOL syntax	Set algebra
A man is a male and an adult and a person	$C_{1} \sqcap ... \sqcap C_{n}$	$C_{1}(x) \land ... \land C_{n}(x)$	$C_{1} \cap ... \cap C_{n}$
A newspaper is a broadsheet or a tabloid	$C_{1} \sqcup ... \sqcup C_{n}$	$C_{1}(x) \lor ... \lor C_{n}(x)$	$C_{1} \cup ... \cup C_{n}$
Everything a vegetarian eats is not an animal	$\neg C$	$\neg C(x)$	$C^c$ (complement of set)
EU countries are: Germany, France, …, Poland	$\lbrace x_{1} \rbrace \sqcup ... \sqcup \lbrace x_{n} \rbrace$	$x=x_{1} \lor ... \lor x=x_{n}$	$\lbrace x_{1} \rbrace \cup ... \cup \lbrace x_{n} \rbrace$
An old lady has only cats	$\forall P.C$	$\forall y.P(x,y) \rightarrow C(y)$	$\pi_Y(P) \subseteq C$
A dog owner has some dog(s)	$\exists P.C$	$\exists y.P(x,y) \land C(y)$	$\pi_Y(P) \cap C \neq \emptyset$ (Π - projection)
A reasonable man has maximum 1 woman	$\leq nP$	$\exists^{\leq n}y.P(x,y)$	$card(P)\leq n$ (card - cardinality)
An animal lover has minimun 3 pets	$\geq nP$	$\exists^{\geq n}y.P(x,y)$	$card(P) \geq n$
A kid is the same as a young person	$C \equiv D$	$\forall x.C(x) \leftrightarrow D(x)$	$C \equiv D$
Every cat is an animal	$C \sqsubseteq D$	$\forall x.C(x) \rightarrow D(x)$	$C \subseteq D$

1.2 Description Logic Languages

elementary descriptions are atomic concepts and atomic roles
complex descriptions built from them inductively with concept constructors
Description Languages are distinguished by the constructors they provide

1.2.1 Basic DL language

AL (Attributive Language) - is a minimal language of practical interest

Constructor	Syntax	Semantics
(atomic concept)	$A$	$A^{\mathcal{I}} = A^{\mathcal{I}} \subseteq \Delta^{\mathcal{I}}$
(atomic role)	$R$	$R^{\mathcal{I}} = R^{\mathcal{I}} \subseteq \Delta^{\mathcal{I}} \times \Delta^{\mathcal{I}}$
(universal concept)	$\top$	$\top^{\mathcal{I}} = \Delta^{\mathcal{I}}$
(bottom concept)	$\bot$	$\bot^{\mathcal{I}} = \emptyset$
(atomic negation)	$\neg A$	$(\neg A)^{\mathcal{I}} = \Delta^{\mathcal{I}} \setminus A^{\mathcal{I}}$
(intersection)	$C \sqcap D$	$(C \sqcap D)^{\mathcal{I}} = C^{\mathcal{I}} \cap D^{\mathcal{I}}$
(value restriction)	$\forall R.C$	$(\forall R.C)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \vert \forall b, (a,b) \in R^\mathcal{I} \rightarrow b \in C^{\mathcal{I}} \rbrace$
(limited existential quantification)	$\exists R.\top$	$(\exists R.\top)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \vert \exists b, (a,b) \in R^\mathcal{I} } \rbrace$

Examples

atomic concepts: Person, Female, Elephant (note: without stating it explicitly there is no relation between Person, Female and Elephant, they just denote some sets)
- description of a female person: $Person \sqcap Female$
- description of a female elephant: $Elephant \sqcap Female$
- description of a not-female person: $Person \sqcap \neg Female$
atomic role: hasChild
- description of a person with children $Person \sqcap \exists hasChild. \top$
- description of a person all of whose children are female $Person \sqcap \forall hasChild.Female$
- description of a person without children $Person \sqcap \forall hasChild. \bot$

Using the above constructors one can define classes e.g.:

$Woman \equiv Person \sqcap Female$
$Man \equiv Person \sqcap \neg Female$
$Parent \equiv Person \sqcap \exists hasChild. \top$
$ChildlessPerson \equiv Person \sqcap \forall hasChild. \bot$

1.2.1 More Description Logics

Constructor	Syntax	Semantics
$\mathcal{U}$ - union	$C \sqcup D$	$(C \sqcup D)^\mathcal{I} = C^\mathcal{I} \cup D^\mathcal{I}$
$\mathcal{E}$ - full existential quantification	$\exists R.C$	$(\exists R.C)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \vert \exists b, (a,b) \in R^\mathcal{I} \land b \in C^{\mathcal{I}} \rbrace$
$\mathcal{N}$ - number restrictions:	$\geq n R$ $\leq n R$	$(\geq n R)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \arrowvert { \mid\lbrace b \mid (a,b) \in R^\mathcal{I} \rbrace \mid \geq n } \rbrace$ $(\leq n R)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \arrowvert { \mid\lbrace b \mid (a,b) \in R^\mathcal{I} \rbrace \mid \leq n } \rbrace$
$\mathcal{C}$ - negation	$\neg C$	$( \neg C)^\mathcal{I} = \Delta^\mathcal{I} \setminus C^\mathcal{I}$

Resulting languages: $\mathcal{AL} [ \mathcal{U}][ \mathcal{E} ][\mathcal{N} ][\mathcal{C} ]$

e.g. $\mathcal{ALU}$ , $\mathcal{ALN}$ , $\mathcal{ALC}$

1.2.2 Nominals in TBox

in some DL individual names (nominals) can be used also in TBox
there exists concept constructors using nominals e.g.
- Set (one-of constructor): $\lbrace a_{1}, ..., a_{n} \rbrace$ (semantics: $\lbrace a_{1}, ..., a_{n} \rbrace^{\mathcal{I}} = \lbrace a_{1}^{\mathcal{I}}, ..., a_{n}^{\mathcal{I}} \rbrace$ )
- fills constructor for a role: $R : a$ (semantics: $(R : a)^{\mathcal{I}} = \lbrace d \in \Delta^{\mathcal{I}} \vert (d,a)^{\mathcal{I}} \in R^{\mathcal{I}}$ )

1.2.3 Language extensions

Base DL is ALC (≈ALUE). Additional letters indicate language extensions:

regarding concept constructors
- $\mathcal{F}$ for functional number restrictions (e.g., ≤1hasMother)
- $\mathcal{N}$ for number restrictions (graded modalities, e.g., ≥2hasChild, ≤3hasChild)
- $\mathcal{Q}$ for qualified number restrictions (graded modalities, e.g., ≥2hasChild.Doctor))
- $\mathcal{O}$ for nominals/singleton classes (e.g., {Italy})
regarding role constructors
- role intersection: R∩S, role union: R∪S, complement roles: ¬R, chain (composition) of roles: RoS
- $\mathcal{I}$ for inverse roles (e.g., $isChildOf \equiv hasChild^{–}$ )
additional role axioms
- $\mathcal{S}$ Role transitivity - often used for $\mathcal{ALC}$ extended with transitive roles
- $\mathcal{H}$ Role hierarchy (e.g., $hasDaughter \sqsubseteq hasChild$ )
- $\mathcal{R}$ Complex role inclusions: RoS ⊆ R, RoS ⊆ S
other
- $^{(\mathcal{D})}$ Use of datatype properties, data values or data types

Expressiveness of the language influence its reasoning complexity: DL complexity navigator

1.3 Knowledge Representation systems based on DL

A Knowledge Representation System based on DL provides means to set up a knowledge base, to manipulate it and reason about it
The knowledge base consists of
- TBox - terminology, intensional representation
- ABox - assertions about individuals, extensional representation

1.3.1 Terminologies (TBox)

a TBox is a finite set of terminological axioms about concepts
terminological axioms: $C \sqsubseteq D (R \sqsubseteq S)$ or $C \equiv D (R \equiv S)$
definitions - an equality that has an atomic concept on the left-hand side

terminologies may be cyclic or acyclic
terminologies may include specialization statements - axioms of the form $C \sqsubseteq D$

TBox semantics:

an interpretation (function) $\mathcal{I}$ maps each concept name to a subset of the domain
an interpretation satisfies an axiom $C \sqsubseteq D (R \sqsubseteq S)$ if: $C^{\mathcal{I}} \subseteq D^{\mathcal{I}}$ or $R^{\mathcal{I}} \subseteq S^{\mathcal{I}}$
an interpretation I satisfies a concept definition $C \equiv D (R \equiv S)$ if: $C^{\mathcal{I}} = D^{\mathcal{I}}$ or $R^{\mathcal{I}} = S^{\mathcal{I}}$
an interpretation satisfies a TBox (Terminology) if it satisfies all definitions and all axioms → I is a model of T

TBox Example

$\\ Animal \sqsubseteq \exists eats. \top \\ \mathit{Giraffe} \sqsubseteq Animal\\ Giraffe \sqsubseteq \forall eats.Leaf\\$

$\\ Vegetarian \equiv (\forall eats.(\neg (\exists partOf.Animal))) \sqcap (\forall eats.(\neg Animal)) \sqcap Animal\\ Cow \sqsubseteq Vegetarian\\ MadCow \equiv \exists eats.(\exists partOf.Sheep \sqcap Brain) \sqcap Cow \\$

$\\ Elderly \sqsubseteq Adult\\ OldLady \equiv Elderly \sqcap Female \sqcap Person \\$

$\\ OldLady \sqsubseteq \exists hasPet.Animal \sqcap \forall hasPet.Cat \\ DogOwner \equiv Person \sqcap \exists hasPet.Dog \\ AnimalLover \equiv Person \sqcap \geq 3 hasPet \\$

1.3.2 World Description (ABox)

an ABox contains extensional knowledge about the domain of interest (individuals)
concept assertions, e.g. C(a)
role assertions, R(b,c)

ABox semantics

an interpretation I maps each individual name to an element in the domain

an interpretation satisfies (with regards to terminology T):
- a concept assertion C(a) iff $a^{\mathcal{I}} \in C^{\mathcal{I}}$
- a role assertion R(b,c) iff $< b^{\mathcal{I}}, c^{\mathcal{I}} > \in R^{\mathcal{I}}$
- an ABox iff it satisfies all assertions in ABox A → I is a model of A

ABox Example

$\\Cat(Tibbs)\\ Dog(Fido)\\ Cow(Flossie)\\ \\ Person(Fred)\\ Person(Joe)\\ \leq 1 hasPet(Joe)\\ Female(Minnie)\\ Male(Mick)\\ \\ hasPet(Joe, Fido)\\ hasPet(Fred,Tibbs)\\ isPetOf(Rex,Mick)\\ \\ reads(Mick, DailyMirror)\\ drives(Mick, Q123ABC)\\ \\ Van(Q123ABC)\\ WhiteThing(Q123ABC)\\$

1.3.3 Unique name assumption and Closed-world assumption

There are two features of Description Logic that are not shared by most other data description formalisms: DL does not make the Unique name assumption (UNA) or the Closed-world assumption (CWA):

Not having UNA means that two concepts with different names may be allowed by some inference to be shown to be equivalent.
Not having CWA, or rather having the Open world assumption (OWA) means that lack of knowledge of a fact does not immediately imply knowledge of the negation of a fact.

1.4 OWL (Web Ontology Language) and DL

OWL exploits results of 15+ years of DL research
- Well defined (model theoretic) semantics
- Formal properties well understood (complexity, decidability)
- Known reasoning algorithms
- Implemented systems (highly optimised)
OWL ontology equivalent to DL KB (TBox + ABox)

1.4.1 OWL and DL Syntax Compared

OWL and DL constructs

OWL and DL axioms

Example

Pizza ontology fragment in DL:

The same fragment in OWL Abstract syntax:

Namespace(p = <http://example.com/pizzas.owl#>)
      Ontology( <http://example.com/pizzas.owl#>
        Class(p:Pizza partial
          restriction(p:hasBase someValuesFrom(p:PizzaBase)))
        DisjointClasses(p:Pizza p:PizzaBase)
        Class(p:NonVegetarianPizza complete
          intersectionOf(p:Pizza complementOf(p:VegetarianPizza)))
        ObjectProperty(p:isIngredientOf Transitive
          inverseOf(p:hasIngredient))
      )

1.4.2 OWL - Abstract syntax

Using the tables above translate the following class descriptions into DL syntax:

Ontology(
 Class(pp:male partial)
 Class(pp:adult partial)
 Class(pp:elderly partial pp:adult)

 Class(pp:pet complete restriction(pp:is_pet_of someValuesFrom(owl:Thing)))

 Class(pp:animal partial restriction(pp:eats someValuesFrom(owl:Thing)))

 /* Vegetarians do not eat animals or parts of animals */

 Class(pp:vegetarian complete 
    intersectionOf(pp:animal
      restriction(pp:eats allValuesFrom(complementOf(pp:animal)))
      restriction(pp:eats 
	 allValuesFrom(complementOf(restriction(pp:part_of 
					        someValuesFrom(pp:animal)))))))

 DisjointClasses(pp:dog pp:cat)

 ObjectProperty(pp:eaten_by)
 ObjectProperty(pp:eats inverseOf(pp:eaten_by) domain(pp:animal)) 

 SubPropertyOf(pp:has_pet pp:likes)

 Individual(pp:Tom type(owl:Thing))
 Individual(pp:Tibbs type(pp:cat))

1.4.3 OWL - XML syntax

OWL is layered over RDFS and uses some RDF(S) syntax (e.g. rdfs:subClassOf)

<owl:Class>
  <owl:intersectionOf rdf:parseType="collection">
    <owl:Class rdf:about="#Person"/>
    <owl:Restriction>
      <owl:onProperty rdf:resource="#hasChild"/>
      <owl:toClass>
        <owl:unionOf rdf:parseType="collection">
          <owl:Class rdf:about="#Doctor"/>
          <owl:Restriction>
            <owl:onProperty rdf:resource="#hasChild"/>
            <owl:hasClass rdf:resource="#Doctor"/>
          </owl:Restriction>
        </owl:unionOf>
      </owl:toClass>
    </owl:Restriction>
  </owl:intersectionOf>
</owl:Class>

1.4.4 Species of OWL

OWL 1:

OWL Full is union of OWL syntax and RDF
- RDF semantics extended with relevant semantic conditions and axiomatic triples
OWL DL is restricted to FOL fragment
- Has standard (First Order) model theoretic semantics
- Equivalent to SHOIN(D): role transitivity(S) + role hierarchy (H) + nominals (O) + inverse (I) + number restrictions (N) + datatype properties, data values or data types (D) = SHOIN(D)
OWL Lite is „simpler” subset of OWL DL
- Equivalent to SHIF(D): role transitivity(S) + role hierarchy (H) + inverse (I) + functionality (F) + datatype properties, data values or data types (D)= SHIF(D)

OWL 2:

OPTIONAL: What DL languages are equivalent to OWL 2 profiles?
- OWL 2 EL
- OWL 2 QL
- OWL 2 RL
and OWL 2 DL?

2 Lab instructions

2.1 Description Logics - TBox and ABox

Here we will do some Description Logics „with pen and paper”.

The knowledge base in DL consists of two concepts:
- TBox - terminology, intensional representation
- ABox - assertions about individuals, extensional representation

Let's check if you understand this difference properly: Take your ontology from one of the previous labs (WebProtege or Protege). Identify which statements belong to Terminology (TBox) and World Description (ABox). Put them in the report divided into two sections: TBox and ABox.
1. NOTE: You don't have to translate the statements into DL. Just select parts of the existing file.

2.2 Description Logics - Reasoning

TBox
$Directory \sqsubseteq \forall dir\_child.(Directory \sqcup File) \sqcap (\leq 1\ dir\_child^{-}.\top)$
$File \sqsubseteq ( \forall dir\_child.\bot)\ \sqcap \neg Directory \sqcap (\leq 1\ dir\_child^{-}.\top)$

$FileSysRoot \sqsubseteq Directory \sqcap \forall dir\_child^{-}.\bot$
$FileSysElement \equiv ( \exists (dir\_child^{-})^{*}.FileSysRoot ) \sqcup ( FileSysRoot )$

ABox
$dir\_child(a,b)$
$dir\_child(a,c)$
$dir\_child(c,a)$

$dir\_child(MyDir,Research)$
$dir\_child(MyDir,Teaching)$
$dir\_child(Research,Semweb.tex)$
$FileSysElement(Semweb.tex)$
$File(Semweb.tex)$

Let's consider a simple Knowledge Base about directories and files: $K=(TBox, ABox)$ . Which of the following statements could be reasoned from $K$ and why? (you can write solutions by hand, take a photo and put it in the report)
1. $FileSysElement \sqsubseteq Directory \sqcup File$
2. $FileSysElement \sqsubseteq \forall (dir\_child^{-})^{*}.Directory$
3. $FileSysElement(\alpha)$ , where $\alpha = a,b,c$
4. $FileSysElement(\beta)$ , where $\beta = MyDir, Research, Teaching$