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

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

• 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... e.g., just to start with: W3C Semantic Web Activity Website

• web content encoded in Unicode, resources identified by URI
• the structure provided by → XML tags
  • the grammar by → XML Schema
• 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
  • they should be compatible with Rule Interchange Format

• 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

• 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 too weak to describe resources in sufficient detail
  • No localised range and domain constraints Can’t say that the range of hasChild is person when applied to persons and elephant when applied to elephants
  • existence/cardinality constraints Can’t say that all instances of person have a mother that is also a person, or that persons have exactly 2 parents
  • No transitive, inverse or symmetrical properties Can’t say that isPartOf is a transitive property, that hasPart is the inverse of isPartOf or that touches is symmetrical
• Difficult to provide reasoning support
  • non-standard semantics
• learn more...

• 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

• 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

• 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

• 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 networks were not equipped with formal logic-based semantics.

• assertions about individuals
  • concept assertions e.g.
    • - Fred is a person
    • Tibbs is a cat
  • role assertions e.g.
    • - Fred has a pet which is Tibbs
• statements about concepts
  • concept definitions (necessary and sufficient conditions) e.g.
    • - A man is an adult male person
    • - A cat liker is a person and there exists a cat that he/she likes
  • relations between concepts e.g.
    • - (every) cat liker likes a cat
    • - (every) sheep eats only grass
  • axioms e.g.
    • a cat is an animal (hierarchy of concepts)
    • a sheep is an animal which eats only grass (it's a necessary but not sufficient condition)

• 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

• 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 ⇔ binarty predicates
  • concepts ⇔ formulae with one free variable

• Software Engineering 1 of the first: CLASSIC - Software Information System
• Configuration
  • design of complex systems created by multiple components
• Medicine (decision support, ontologies)
• Natural Language processing
• Database management
  • reasoning about ERD Entity Relationship Diagrams
  • query processing and optimization
• Creating ontologies for Semantic Web

• 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

• Symbols
  • A, B - atomic concepts
  • R - atomic role
  • C, D - concept descriptions
• construction syntax rule:
• atomic negation and limited existential quantification negation can only be applied to atomic concepts, and only the top concept is allowed in the scope of an existential quantification

• given by means of interpretation which consists of two parts:
• domain of interpretation: - a non-empty set to which all the symbols and relations are mapped
• an interpretation function which assigns
  • to every atomic concept a set:
  • to every atomic role a binary relation:

• atomic concepts: Person, Female, Elephant note: without stating it explicitly there is no relation between Person, Female and Elephant, they just denote some sets
  • a female person:
  • a female elephant:
  • a not-female person:
• atomic role: hasChild
  • a person with children
  • a person all of whose children are female
  • a person without children

• distinguished by the constructors they provide
• - union :
• - full existential quantification :
• - number restrictions:
  • 
  • 
• - negation :

• resulting languages:

• Smallest propositionally closed (propositionally closed languages provide, either implicitly or explicitly, conjunction, union and negation of class descriptions DL is
• equivalence with :
  • 
  • 
• Concepts constructed using booleans:
• restricted quantifiers:
• Only atomic roles
• corresponds to a fragment of FOL obtained by restricting the syntax to formulas containing only 2 variables

• a TBox is a finite set of terminological axioms about concepts
• terminological axioms: or
• definitions - an equality that has an atomic concept on the left-hand side

• terminologies may be cyclic or acyclic acyclic terminologies have definitiorial impact. Their semantics is called descriptive semantics. Cyclic terminologies (used e.g. to model recursive structures ) needs fixed point semantics… (see F.Baader,W.Nutt - Basic Description Logics in DL Handbook.)
• terminologies may include specialization statements - axioms of the form

Selected definitions...

• an interpretation (function) maps each concept name to a subset of the domain

• an interpretation satisfies an axiom if: or

• an interpretation I satisfies a concept definition if: or

• an interpretation satisfies a TBox (Terminology) if it satisfies all definitions and all axioms → I is a model of T

• an ABox contains extensional knowledge about the domain of interest (individuals)
• concept assertions, e.g. C(a)
• role assertions, R(b,c)

• 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 role assertion R(b,c) iff
  • an ABox iff it satisfies all assertions in ABox A → I is a model of A

• 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

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

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

• consistency checking
  • an ABox is consistent w.r.t. a TBox T, if there is an interpretation that is a model of both A and T.
  • an ABox is consistent, if it is consistent w.r.t. the empty TBox. one can get rid of acyclic TBox by expanding concepts in TBox (replacing concepts with the right-hand side of their definitions)
• instance checking
  • 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

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

• 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

• 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

• 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

1. use of the fact that: C is subsumed by D ⇔ is unsatisfiable
2. start from ground facts (ABox axioms)
3. syntactic decomposition using tableaux expansion rules
   • Tableau rules correspond to constructors in logic ()
   • Some rules are nondeterministic (e.g., ) (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

• We know that:
  • 
  • 
  • ,,
• We can infer that:
  • Every old lady must have a pet cat.(Because she must have some pet and all her pets must be cats.)
  • Minnie is an old lady
  • Tom is a cat
• We know that:
  • 
  • 
  • 
• We can infer that:
  • there are no mad cows!
• More examples with this ontology here...
• see OwlSight Ontology Browser for explanation…

• base DL is ALC (≈ALUE)
• Additional letters indicate language extensions:
  • regarding concept constructors
    • for functional number restrictions (e.g., ≤1hasMother)
    • for number restrictions (graded modalities, e.g., ≥2hasChild, ≤3hasChild)
    • for qualified number restrictions (graded modalities, e.g., ≥2hasChild.Doctor))
    • 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
    • for inverse roles (e.g., )
  • additional role axioms
    • Role transitivity - often used for extended with transitive roles
    • Role hierarchy (e.g., )
    • Complex role inclusions: RoS ⊆ R, RoS ⊆ S
  • other
    • Use of datatype properties, data values or data types

• DL complexity navigator

• Web Ontology Language,
• DAML+OIL
• 3 species: OWL Lite, OWL DL and OWL Full
• OWL Working Group works on OWL 2

• 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

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

• learn more about OWL species...

• OWL Working Group is working on a new version of OWL based on the propositions of OWL 1.1. Submission Request: OWL 2 which (according to Wikipedia) corresponds to SROIQ(D)
  • R - complex roles inclusion (RoS ⊆ R, RoS ⊆ S)

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

• 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

• 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

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

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

• W3C Semantic Web Activity Website
• Description Logics Website
• Ian Horrocks's presentations
• Protege - a tool for creating/editing ontologies
• Pellet - a DL reasoner
• OwlSight - an ontology browser

• The Description Logic Handbook: Theory, Implementation and Applications
  • D. Nardi and R. J. Brachman - An introduction to description logics
  • F. Baader and W. Nutt - Basic description logics
• http://dl.kr.org/
• http://www.cs.man.ac.uk/~horrocks/Slides/index.html
• www.informatik.uni-leipzig.de/~brewka/papers/semweb/DL_vortrag.pdf
• http://www.cs.man.ac.uk/~horrocks/ISWC2003/Tutorial/

• Any questions?