Introduction to Description Logics

Last verification: 20180914
Tools required for this lab:

Introduction

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:

  1. How to say that the range of a property hasChildren is Person when applied to a person and Elephant when applied to an elephant?
  2. How to say that all instances of person have a mother that is also a person, or that persons have exactly 2 parents?
  3. 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

semantic network example
Fig.1. Exemplary graph.

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

1.1.1 Examples of DL expressions

Assertions about individuals

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

Statements about concepts

  1. 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
  2. relations between concepts e.g.
    •  likes(cat\_liker, cat) - (every) cat liker likes a cat
    •  eats\_only(sheep, grass) - (every) sheep eats only grass
  3. 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:

  1. 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})
  2. 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^{–})
  3. 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
  4. 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

KRS

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

  1. Pizza ontology fragment in DL:
  2. 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:

  1. OWL Full is union of OWL syntax and RDF
    • RDF semantics extended with relevant semantic conditions and axiomatic triples
  2. 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)
  3. 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
  • 8-) 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)
  • 8-) 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

If you want to know more

Lecture:

Description Logics:

pl/dydaktyka/semweb/lab-desc-logic.txt · ostatnio zmienione: 2018/09/14 14:00 przez kkutt
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0