Winter 2019

Instructor: Raghava Mutharaju

IIIT-Delhi

- 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

- 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

- 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

- 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)

- 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

- 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
- Individuals: same as constants (FOL), resources (RDF), instances
- Concepts: sets of individuals or unary predicates (FOL)
- Roles: binary relation between the individuals or binary predicates (FOL)

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

- 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
*no*examiner - 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

- $\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

- $\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$ (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

- 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$

- 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 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$

- 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$^{-}$

- 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$^{-}$

- 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)

- (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)$

- 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

- 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)$

- 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 |

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