Description Logics


Winter 2019
Instructor: Raghava Mutharaju
IIIT-Delhi
IIIT Delhi

Introduction

  • Description Logics are a family of knowledge representation languages
  • They provide the formal underpinnings for OWL (Web Ontology Language)
  • They are decidable fragments of First Order Logic (FOL)
    • Decidability: Decision (yes/no) problem with a method to arrive at the decision (no matter how long it takes)
  • Since DLs are logics, they have formal semantics
    • Precise specification of meaning of the constructs
    • Logical deduction to infer additional facts based on explicitly stated facts
  • The computation of inferences is called reasoning
  • Differences between DLs and other modelling languages (UML, ER)
    • Reasoning
    • Ability to represent complex relationships

Open World Assumption


  • Closed World Assumption (CWA) is the assumption that anything not known to be true is false
  • Open World Assumption (OWA) is the assumption that anything not known to be true is unknown
    • Eg: Italy is part of Europe
    • Eg: Is Spain part of Europe?
    • CWA: No
    • OWA: Unknown

Open World Assumption


  • CWA is used when the system has complete information or if a definitive answer is required from the available information
    • Eg: Relational tables with information on only Italy
    • Eg: Flight booking information
  • OWA is useful when the system has incomplete information.
    • Eg: Knowledge in an ontology is incomplete
    • Eg: Open nature of WWW where data is constantly changing

No Unique Name Assumption


  • In Unique Name Assumption (UNA), the assumption is that entities with different names (which act as IDs) represent different entities
    • Italy is a country
    • Spain is a country
    • Under CWA, UNA is followed: Italy and Spain are different
  • Description Logics and OWL make the assumption that different names do not necessarily represent different individuals (no UNA)

No Unique Name Assumption


  • Under OWA, UNA is not followed: unless explicitly stated, we do not know yet whether two individuals are the same or different
  • Different organizations can build ontologies on the same theme and could have individuals with the same name
    • Eg: http://www.example1.org/institute/IIIT-D
    • Eg: http://www.example2.org/institute/IIIT-D

Basic Building Blocks

  • DLs are used to model entities and the relationships between them in a domain of interest
    • RDF is also used for the same purpose except that DLs are more expressive
  • There are three types of entities
    1. Individuals: same as constants (FOL), resources (RDF), instances
    2. Concepts: sets of individuals or unary predicates (FOL)
    3. Roles: binary relation between the individuals or binary predicates (FOL)

Naming Conventions


  • Individuals: lower camelcase is used
    • Eg: sebastianRudolph
  • Concepts: camelcase is used
    • Eg: Parent, ChildlessPerson
  • Roles: lower camelcase is used
    • Eg: hasDaughter

DL Syntax

  • Person(mary)
    • (RDF) :mary rdf:type :Person .
    • This is called concept assertion
  • hasWife(john,mary)
    • (RDF) :john :hasWife :mary .
    • This is called role assertion
  • Concept assertions and role assertions together are called ABox axioms (Assertional Knowledge)
  • Woman $\sqsubseteq$ Person
    • (RDF) :Woman rdfs:subClassOf :Person .
    • This is called concept inclusion
    • Woman is subsumed by Person
  • Person $\equiv$ Human
    • This is called concept equivalence
  • Such type of concept level axioms are called TBox axioms (Terminological Knowledge)
  • hasWife $\sqsubseteq$ hasSpouse
    • :hasWife rdfs:subPropertyOf :hasSpouse .
    • This is called role inclusion
  • Role equivalence is also supported
  • hasFather $\circ$ hasBrother $\sqsubseteq$ hasUncle
    • This is role composition
  • Axioms that talk about relationship between roles are called RBox axioms
  • Woman $\sqsubseteq$ Person
    • (FOL) $\forall$x (Woman(x) $\rightarrow$ Person(x))
  • hasWife $\sqsubseteq$ hasSpouse
    • (FOL) $\forall$x $\forall$y (hasWife(x,y) $\rightarrow$ hasSpouse(x,y))
  • Exam $\sqsubseteq$ $\forall$hasExaminer.Professor
    • All examiners of an exam must be professors
    • This also includes those exams that have noexaminer
  • HappyPerson $\equiv$ $\forall$hasChild.HappyPerson
    • The above quantification includes the case of a childless person being happy
  • Exam $\sqsubseteq$ $\exists$hasExaminer.Professor
    • Every exam must have at least one examiner who is a professor

Special Classes and Properties


  • $\top$ (Top)
    • Super concept for all the concepts in the domain
    • Contains everything
  • $\bot$
    • Sub concept for all the concepts in the domain
    • Contains nothing; empty concept
  • U
    • Top property
    • Every pair of concepts are in U
  • Empty property
    • Empty property; contains nothing

Bolean Concept Constructors


  • $\sqcap$ (Intersection or Conjunction)
    • Mother $\equiv$ Female $\sqcap$ Parents
    • Mothers are exactly female parents
  • $\sqcup$ (Union or Disjunction)
    • Parent $\equiv$ Mother $\sqcup$ Father
    • Parent is either a mother or a father
  • $\neg$ (Complement or Negation)
    • UnmarriedWoman $\equiv$ Woman $\sqcap$ $\neg$Married

Top and Bottom Concepts


  • $\top$ (Top)
    • $\top$ $\equiv$ Male $\sqcup$ Female
    • Everybody is either male or female
    • C $\sqcup$ $\neg$C $\equiv$ $\top$, for any arbitrary concept C
  • $\bot$ (Bottom)
    • Male $\sqcap$ Female $\equiv$ $\bot$
    • Nobody can be both a male and a female at the same time
    • Male and Female are disjoint with each other
    • C $\sqcap$ $\neg$C $\equiv$ $\bot$, for any arbitrary concept C

Nominals


  • Nominal is a concept that has exactly one instance (singleton)
  • They are closed concepts where we can enumerate the list of its instances
  • Enumeration can be achieved by using the union ($\sqcup$) operator
    • MyBirthdayGuests $\equiv$ {bill} $\sqcup$ {john} $\sqcup$ {mary}
    • MyBirthdayGuests $\equiv$ {bill,john,mary}
  • No UNA, so we have to explicitly state that they are different
    • {bill} $\sqcap$ {john} $\sqcap$ {mary} $\equiv$ $\bot$

Cardinality Restrictions


  • Allows us to restrict the number of individuals that can be reached via a role
  • at-least restriction
    • Exam $\sqsubseteq$ $\geq$2 hasExaminer
  • at-most restriction
    • Exam $\sqsubseteq$ $\leq$2 hasExaminer
  • exact restriction
    • Exam $\sqsubseteq$ $=$2 hasExaminer
    • Exam $\sqsubseteq$ $\geq$2 hasExaminer $\sqcap$ $\leq$2 hasExaminer
  • General form: $\geq$nR, $\leq$nR, $=$nR, where n is a non-negative integer

Qualified Cardinality Restrictions


  • Qualified cardinality restrictions are a generalization of (unqualified) cardinality restrictions
  • They allow us to specify to which concept the second argument of role R is connected to
    • $\geq$nR.C, $\leq$nR.C, $=$nR.C
    • Exam $\sqsubseteq$ $\geq$2 hasExaminer.Professor
  • Unqualified cardinality restrictions can be expressed as follows
    • $\geq$nR.$\top$, $\leq$nR.$\top$, $=$nR.$\top$

Inverse Roles


  • Direction of the relation is reversed
  • Eg: hasSon(a,b) and sonOf(b,a)
    • hasSon $\equiv$ sonOf$^{-}$
  • Eg: hasParent(a,b) and hasChild(b,a)
    • hasParent $\equiv$ hasChild$^{-}$

Role Characteristics

  • Transitive
    • R(a,b) and R(b,c) $\rightarrow$ R(a,c)
    • Eg: hasAncestor
  • Symmetric
    • R(a,b) $\rightarrow$ R(b,a)
    • Eg: hasSpouse
    • R $\equiv$ R$^{-}$
  • Asymmetric
    • R(a,b) $\rightarrow$ not R(b,a)
    • Eg: hasChild
  • Reflexive
    • R(a,a) for all a
    • Eg: hasRelative
  • Irreflexive
    • not R(a,a) for any a
    • Eg: parentOf
  • Functional
    • R(a,b) and R(a,c) $\rightarrow$ b=c
    • Eg: hasHusband
    • $\top$ $\sqsubseteq$ $\leq$1R
  • InverseFunctional
    • R(a,b) and R(c,b) $\rightarrow$ a=c
    • Eg: hasHusband
    • $\top$ $\sqsubseteq$ $\leq$1R$^{-}$

Description Logics

ALC


  • Attributive Logic with Complement (ALC)
  • Considered to be the most fundamental description logics
  • Notations
    • Set of individuals represented by a,b,c,...
    • Set of atomic classes represented by A,B,...
    • Set of role names represented by R,S,...
  • TBox statements
    • C $\equiv$ D or C $\sqsubseteq$ D
  • ABox statements
    • C(a) or R(a,b)

ALC


  • (Complex) class expressions are constructed as

    • $C,D ::= A|\top|\bot|$$\neg$$C|C$$\sqcap$$D|C\sqcup$$D|\forall$$R.C|\exists$$R.C$

  • Eg: $A$ $\sqcap$ $B$ $\sqsubseteq$ $C$ $\sqcup$ $(D$ $\sqcap$ $\exists$$R.K)$

Naming Description Logics


  • Letters describe the language constructs that are allowed in that particular Description Logic
    • $S$ is for ALC + role transitivity
    • $H$ is for role hierarchies (simple role inclusion axioms)
    • $O$ is for nominals
    • $I$ is for inverse roles
    • $N$ is for cardinality restrictions
    • $Q$ is for qualified cardinality restrictions

Naming Description Logics


  • Letters describe the language constructs that are allowed in that particular Description Logic
    • $D$ is for datatypes
    • $F$ is for role functionality
    • $R$ is for generalized role inclusion axioms (property chains)
    • $E$ is for existential role restrictions
  • $SHOIN(D)$
  • $SROIQ(D)$

Expressivity and Complexity trade-off

  • As the expressivity increases, the reasoning (and querying) complexity also increases
Description Logic Reasoning Complexity
$ALC$ ExpTime
$SHIQ$ ExpTime
$SHOQ$ ExpTime
$SHIO$ ExpTime
$SHOIN$ NExpTime
$SHOIQ$ NExpTime
$SROIQ$ N2ExpTime

References


  1. Foundations of Semantic Web Technologies. Pascal Hitzler et. al. CRC Press.
  2. A Description Logic Primer. Markus Krötzsch, František Simančík, Ian Horrocks. In CoRR abs/1201.4089. arxiv.org 2012.