Description Logics and OWL in the Semantic Web

Weronika T. Furmańska wtf@agh.edu.pl, Grzegorz J. Nalepa gjn@agh.edu.pl


SW logo DL logo

Outline

  • SemanticWeb
    • Vision, goals and methods. Layer cake architecture. URI, XML, RDF, Ontologies, Rules…
  • Description Logics
    • Introduction
      • History and background. A DL system. Basic notation and features. Applications of DL and DL-based systems. Relations to other formalisms
    • Basic DL
      • AL Syntax. AL Semantics. DL families. ALC. TBox - Terminologies. ABox - World Description. Language extensions
    • Reasoning in DL
      • Inference tasks. Reasoning algorithms.
  • OWL - Web Ontology Languages
    • OWL and DL. Reasoning on the Web. Current state and remaining challenges.

Semantic Web

  • a vision of the Semantic Web first proposed in May 2001 in an article by Tim Berners-Lee, James Hendler and Ora Lassila published by Scientific American as “an extension of the current one, in which information is given well-defined meaning, better enabling computers and people to work in cooperation.”

  • the idea was to make the Web content “understandable” for machines and enable automated reasoning over it
  • the goal was to create an environment where software agents could solve complex searching and reasoning tasks
  • the way to do it is to present information in some standarized formats (markup languages) and give the means to reason about it
  • the world wide research began...

Semantic Web Layer Cake(s)

sw layer cakes

  • web content encoded in Unicode, resources identified by URI
  • the structure provided by → XML tags
  • metadata (basic/primitive semantics) encoded in → RDF
  • semantics (meaning and relations between concepts) given by means of → Ontologies: OWL, (somehow also RDFS)
  • rule languages are being developed → e.g. RuleML, R2ML, SWRL

Resource Description Framework

  • RDF is a framework for describing resources on the web
  • written in XML and designed to be read by computers
  • uses Web identifiers (URIs) to identify resources (documents, pictures, paragraphs, books, …)
  • describes resources with properties and property values
    • Properties themselves are also resources (URIs) - they point to a particular definition on the Web
  • RDF Statements are <subject, predicate, object> triples
  • a graphical formalism for representing metadata
    • triple statements can be represented as a graph
  • for an example let's go to W3Schools

RDF Schema

  • RDFS extends RDF with “schema vocabulary” such as:
    • Class, Property
    • type, subClassOf, subPropertyOf
    • range, domain
  • allows to define vocabulary terms and the relations between those terms - therefore is recognized as an ontology language
    • it gives “extra meaning”(semantics) to particular RDF predicates and resources and thus specifies how a term should be interpreted
    • RDFS constructors:
      • <Person,type,Class>, <hasColleague,type,Property>, <Professor,subClassOf,Person>, <Carole,type,Professor>, , <hasColleague,range,Person>, <hasColleague,domain,Person>

RDFS - difficulties

Desirable features identified for Web Ontology Language

  • Extends existing Web standards such as XML, RDF, RDFS
  • Easy to understand and use
  • Should be based on familiar KR idioms
  • Formally specified
  • Of “adequate” expressive power
  • Possible to provide automated reasoning support

Towards Web Ontology Language...

  • Two languages were developed to satisfy above requirements
    • OIL: developed by group of (largely) European researchers (several from EU OntoKnowledge project)
    • DAML: developed by group of (largely) US researchers (in DARPA DAML programme)
  • Efforts were merged to produce DAML+OIL
  • Development was carried out by “Joint EU/US Committee on Agent Markup Languages”
  • DAML+OIL submitted to W3C as basis for standardisation
    • Web-Ontology (WebOnt) Working Group formed
    • WebOnt group developed OWL language based on DAML+OIL
  • OWL language now a W3C Recommendation
  • OWL is based on Description Logics

Ontology in Computer Science

  • An ontology is an engineering artefact consisting of:
    • A vocabulary used to describe (a particular view of) some domain
    • An explicit specification of the intended meaning of the vocabulary.
      • Often includes classification based information
    • Constraints capturing additional knowledge about the domain
  • Ideally, an ontology should:
    • Capture a shared understanding of a domain of interest
    • Provide a formal and machine manipulable model of the domain
  • OWL Ontology Browser: OWLSight

Description Logics

  • 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

History and Background

  • 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

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

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)

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

Relation to First Order Logic

  • mostly DL are subsets of first-order logic
    • concept names ⇔ unary predicates
    • atomic roles ⇔ binarty predicates
    • concepts ⇔ formulae with one free variable

DL and FOPL Compared


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

Applications of DL and DL-based systems

  • Software Engineering
  • Configuration
    • design of complex systems created by multiple components
  • Medicine (decision support, ontologies)
  • Natural Language processing
  • Database management
    • reasoning about ERD
    • query processing and optimization
  • Creating ontologies for Semantic Web

Basic DL

  • 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
  • AL (Attributive Language) - is a minimal language of practical interest

AL syntax

  • Symbols
    • A, B - atomic concepts
    • R - atomic role
    • C, D - concept descriptions
  • construction syntax rule: C, D \rightarrow A \vert \top \vert \bot \vert \neg A \vert C \sqcap D \vert \forall R.C \vert \exists R.\top
  • atomic negation and limited existential quantification

AL semantics

  • given by means of interpretation which consists of two parts:
  • domain of interpretation: \Delta^{\mathcal{I}} - a non-empty set to which all the symbols and relations are mapped
  • an interpretation function which assigns
    • to every atomic concept a set: A \rightarrow A^{\mathcal{I}} \subseteq \Delta^{\mathcal{I}}
    • to every atomic role a binary relation: R^{\mathcal{I}} \rightarrow \Delta^{\mathcal{I}} \times \Delta^{\mathcal{I}}

AL syntax and semantics table


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
    • a female person: Person \sqcap Female
    • a female elephant: Elephant \sqcap Female
    • a not-female person: Person \sqcap \neg Female
  • atomic role: hasChild
    • a person with children Person \sqcap \exists hasChild. \top
    • a person all of whose children are female Person \sqcap \forall hasChild.Female
    • a person without children Person \sqcap \forall hasChild. \bot

DL "families"

  • distinguished by the constructors they provide
  • \mathcal{U} - union : (C \sqcup D)^\mathcal{I} = C^\mathcal{I} \cup D^\mathcal{I}
  • \mathcal{E} - full existential quantification : (\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)^\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)^\mathcal{I} = \Delta^\mathcal{I} \setminus C^\mathcal{I}
  • resulting languages: \mathcal{AL} [ \mathcal{U}][ \mathcal{E} ][\mathcal{N} ][\mathcal{C} ]

ALC

  • Smallest propositionally closed DL is \mathcal{ALC}
  • equivalence with \mathcal{ALUE}:
    • C \sqcup D \equiv \neg(\neg C \sqcap \neg D)
    • \exists R.C \equiv \neg \forall R.\neg C
  • Concepts constructed using booleans: \sqcup, \sqcap, \neg
  • restricted quantifiers: \exists, \forall
  • Only atomic roles
  • \mathcal{ALC} corresponds to a fragment of FOL obtained by restricting the syntax to formulas containing only 2 variables

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

Selected definitions...

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

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

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)
    • fills constructor for a role


Constructor Semantics
\lbrace a_{1}, ..., a_{n} \rbrace \lbrace a_{1}, ..., a_{n} \rbrace^{\mathcal{I}} = \lbrace a_{1}^{\mathcal{I}}, ..., a_{n}^{\mathcal{I}} \rbrace
R : a (R : a)^{\mathcal{I}} = \lbrace d \in \Delta^{\mathcal{I}} \vert (d,a)^{\mathcal{I}} \in R^{\mathcal{I}}

DL Inference

  • Reasoning tasks
  • Open World Assuption
  • Rules
  • Reasoning algorithms
    • Structural subsumption algorithms
    • Tableau algorithms

Reasoning tasks for TBox

  • satisfiability
    • a concept C is satisfiable with respect to T if there exists a model (an interpretation) I of T such that C^{\mathcal{I}} is not empty
  • subsumption
    • a concept C is subsumed by a concept D w.r.t. T if C^{\mathcal{I}} \subseteq D^{\mathcal{I}} for every model I of T
  • equivalence
    • two concepts C and D are equivalent w.r.t. T if C^{\mathcal{I}} = D^{\mathcal{I}} for every model I of T
  • disjointness
    • two concepts C and D are disjoint w.r.t. T if C^{\mathcal{I}} \cap D^{\mathcal{I}} = \emptyset for every model I of T

Reasoning tasks for ABox

  • consistency checking
  • instance checking
    • A \models \alpha iff every interpretation I which satisfies A also satisfies α
  • realization - the most specific concept for a given individual
  • retrieval - individuals which are instances of a given concept

Reduction of reasoning tasks

  • all TBox tasks can be reduced to subsumption or satisfiability
    • C and D are disjoint ⇔ C \sqcap D is subsumed by ⊥
    • e.g. C is subsumed by D ⇔ C \sqcap \neg D is unsatisfiable (this is used in tableau-based algorithms)
  • all inferences can be reduced to consistency checking of an ABox

Open World semantics

  • DL Knowledge Base vs. Relational Database
    • database schema ↔ TBox
    • instance with data ↔ ABox
    • contrary to relational databases, absence of information in ABox means lack of knowledge, not a negative information
  • ABox represents possibly infinitely many interpretations
  • open-world semantics requires nontrivial reasoning, answering queries is more complex

Rules

  • in some DL systems in addition to TBox and ABox one can use trigger rules to express knowledge
  • C ⇒ D
  • if an individual is proved to be an instance of C, then derive that it is also an instance of D
  • C ⇒ D is not a logical implication, it does not mean that ¬D → ¬C :!:

Structural subsumption algorithms

  • these algorithms compare the syntactic structure of concept descriptions
  • they are very efficient

but

  • only complete for simple languages
    • e.g. cannot handle full negation and disjuntion

Tableau algorithms

  1. use of the fact that: C is subsumed by D ⇔ C \sqcap \neg D is unsatisfiable
  2. start from ground facts (ABox axioms)
  3. syntactic decomposition using tableaux expansion rules
    • Tableau rules correspond to constructors in logic ( \sqcap, \sqcup, ...)
    • Some rules are nondeterministic (e.g., \sqcup, \leq ) (In practice, this means search)
  4. Inferring constraints on (elements of) model
  5. Stop when no more rules applicable or clash occurs
    • Cycle check (blocking) often needed to ensure termination

Inference Example

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

DL family vs. reasoning complexity

OWL

DL and OWL

  • 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)
  • OWL DL based equivalent to SHOIN(D) DL

3 species of OWL

  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 (≈ DAML+OIL)
    • Has standard (First Order) model theoretic semantics
    • Equivalent to SHOIN(D)
  3. OWL Lite is “simpler” subset of OWL DL
    • Equivalent to SHIF(D)

OWL and DL Syntax Compared


OWL Constructor DL syntax OWL Axiom DL syntax
Thing \top equivalentClass C \equiv D
Nothing \bot suClassOf C \sqsubseteq D
complementOf (\neg) equivalentProperty S \equiv R
intersectionOf (C \sqcap D) subPropertyOf S \sqsubseteq R
unionOf (C \sqcup D) inverseOf S \equiv R^-
allValuesFrom (\forall R.C) transitiveProperty R^+ \sqsubseteq R
someValuesFrom (\exists R.C) functionalProperty \top \sqsubseteq \leq 1 R
minCardinality (\geq n R) sameIndividualAs a = b
maxCardinality (\leq n R) differentFrom a \neq b
oneOf \lbrace a_1, ..., a_n \rbrace

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

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>

Increased Expressive Power - Datatypes and Nominals

  • OWL supports XML Schema primitive datatypes
  • there is a clean separation between “object” classes and datatypes (the domains are disjoint)
  • Nominals are used in extensionally defined classes
    • Written in OWL as oneOf(Austria, …, UnitedKingdom)
    • Equivalent to a disjunction of nominals: {Austria ∪ … ∪ UnitedKingdom}
  • Used in extended OWL Abox axioms
  • using Datatypes and Nominals in Ontologies increase the complexity of reasoning and remains a challenge

Reasoning in OWL DL

  • why?
    • Semantic Web's aim is to enable automated reasoning using knowledge specified in Ontologies
  • what can we do?
    • Design and maintenance of ontologies
    • Integration of ontologies
    • Querying class and instance data w.r.t. ontologies
  • reasoning with lots of nominals
    • the presence of individuals in KB makes reasoning more complex computationally, may require extensions of some TBox reasoning techniques

Future challenges

  • OWL not expressive enough for some applications
  • Role box (SROIQ)
  • Concrete domains/datatypes
    • role box + concrete domains is basis for OWL 2
  • Database style keys
  • learn more...

Rule languages over OWL

  • SWRL
    • union of OWL DL and Horn logic (Horn clauses)
    • looses decidability
  • RuleML, R2ML

If you want to know more

References

Thank you

  • Any questions?



SW logo DL logo