• 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

• 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

• 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

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

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