====== Introduction to Description Logics ====== ^ Last verification: | 20180914 | ^ Tools required for this lab: | -- | ===== Introduction ===== * {{http://www.informatik.uni-leipzig.de/~brewka/papers/semweb/DL_vortrag.pdf|Description Logics: an introduction into its basic ideas}} ===== - Description Logics Intro ===== In [[.:lab-ontologies|Introduction to ontologies]] you have learnt basic ideas about ontologies. * Ontologies consist of classes, properties and individuals. * Classes describe sets of objects. * Properties describe relations between classes and attributes of classes. * Individuals are instances of classes linked with other individuals by properties. * Classes may be organized into hierarchies. * Properties may be organized into hierarchies. * There are object properties and data properties. * Properties have domains and ranges. The above information can be expressed in RDF Schema which is a simple ontology language for the Semantic Web. However, more complex ontologies require more expressive language. For example: - How to say that the range of a property ''hasChildren'' is ''Person'' when applied to a person and ''Elephant'' when applied to an elephant? - How to say that all instances of person have a mother that is also a person, or that persons have exactly 2 parents? - How to say that ''isPartOf'' is a transitive property, that ''hasPart'' is the inverse of ''isPartOf'' or that ''touches'' is symmetrical? In this lab, you will get to know more advanced ontologies based on Description Logics (DL). You will learn the __DL languages__ and understand __how OWL corresponds to selected DL__. ==== - Description Logics Basics ==== * 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 [[wp>Semantic networks]] and [[wp>frame language|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 {{.:dl_pp_repr.png?500|semantic network example}}\\ Fig.1. Exemplary graph. * 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) === - Relation to First Order Logic === * 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 ⇔ binary predicates * concepts ⇔ formulas with one free variable ^ 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 | ==== - Description Logic Languages ==== * 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** == - Basic DL language == AL (Attributive Language) - is a minimal language of practical interest ^ 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// (note: without stating it explicitly there is no relation between Person, Female and Elephant, they just denote some sets) * description of a female person: Person \sqcap Female * description of a female elephant: Elephant \sqcap Female * description of a not-female person: Person \sqcap \neg Female * atomic role: //hasChild// * description of a person with children Person \sqcap \exists hasChild. \top * description of a person all of whose children are female Person \sqcap \forall hasChild.Female * description of a person without children Person \sqcap \forall hasChild. \bot Using the above constructors one can define classes e.g.: * Woman \equiv Person \sqcap Female * Man \equiv Person \sqcap \neg Female * Parent \equiv Person \sqcap \exists hasChild. \top * ChildlessPerson \equiv Person \sqcap \forall hasChild. \bot === - More Description Logics === ^ Constructor ^ Syntax ^ Semantics ^ | \mathcal{U} - union | C \sqcup D | (C \sqcup D)^\mathcal{I} = C^\mathcal{I} \cup D^\mathcal{I} | | \mathcal{E} - full existential quantification | \exists R.C | (\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 \\ \leq n R | (\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 | ( \neg C)^\mathcal{I} = \Delta^\mathcal{I} \setminus C^\mathcal{I} | Resulting languages: \mathcal{AL} [ \mathcal{U}][ \mathcal{E} ][\mathcal{N} ][\mathcal{C} ] * e.g. \mathcal{ALU} , \mathcal{ALN} , \mathcal{ALC} === - 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): \lbrace a_{1}, ..., a_{n} \rbrace (semantics: \lbrace a_{1}, ..., a_{n} \rbrace^{\mathcal{I}} = \lbrace a_{1}^{\mathcal{I}}, ..., a_{n}^{\mathcal{I}} \rbrace ) * //fills// constructor for a role: R : a (semantics: (R : a)^{\mathcal{I}} = \lbrace d \in \Delta^{\mathcal{I}} \vert (d,a)^{\mathcal{I}} \in R^{\mathcal{I}}) === - Language extensions === Base DL is ALC (≈ALUE). Additional letters indicate language extensions: - regarding concept constructors * \mathcal{F} for functional number restrictions (e.g., ≤1//hasMother//) * \mathcal{N} for number restrictions (graded modalities, e.g., ≥2//hasChild//, ≤//3hasChild//) * \mathcal{Q} for qualified number restrictions (graded modalities, e.g., ≥2//hasChild//.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 Expressiveness of the language influence its reasoning complexity: [[http://www.cs.man.ac.uk/~ezolin/dl/|DL complexity navigator]] ==== - Knowledge Representation systems 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 {{ .:dl_krs.png?500 |KRS}} === - 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 __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)\\ === - Unique name assumption and Closed-world assumption === There are two features of Description Logic that are not shared by most other data description formalisms: DL does not make the Unique name assumption (UNA) or the Closed-world assumption (CWA): * Not having UNA means that two concepts with different names may be allowed by some inference to be shown to be equivalent. * Not having CWA, or rather having the Open world assumption (OWA) means that lack of knowledge of a fact does not immediately imply knowledge of the negation of a fact. ==== - OWL (Web Ontology Language) and DL ==== * 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 and DL Syntax Compared === {{.:owl-dl-description.gif}}\\ OWL and DL constructs {{.:owl-dl-axioms.gif}}\\ OWL and DL axioms **Example** - Pizza ontology fragment in DL: \\ {{.:owl-pizza.gif}} - The same fragment in OWL Abstract syntax:

Namespace(p = )
      Ontology( 
        Class(p:Pizza partial
          restriction(p:hasBase someValuesFrom(p:PizzaBase)))
        DisjointClasses(p:Pizza p:PizzaBase)
        Class(p:NonVegetarianPizza complete
          intersectionOf(p:Pizza complementOf(p:VegetarianPizza)))
        ObjectProperty(p:isIngredientOf Transitive
          inverseOf(p:hasIngredient))
      )

=== - OWL - Abstract syntax === Using the tables above translate the following class descriptions into DL 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'')

=== - Species of OWL === __OWL 1__: - //OWL Full// is union of OWL syntax and RDF * RDF semantics extended with relevant semantic conditions and axiomatic triples - //OWL DL// is restricted to FOL fragment * 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) - //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) __OWL 2__: * //OPTIONAL//: What DL languages are equivalent to [[http://www.w3.org/TR/owl2-profiles/|OWL 2 profiles]]? * OWL 2 EL * OWL 2 QL * OWL 2 RL * and OWL 2 DL? ===== - Lab instructions ===== ==== - Description Logics - TBox and ABox ==== Here we will do some Description Logics "with pen and paper". * The knowledge base in DL consists of two concepts: * TBox - terminology, intensional representation * ABox - assertions about individuals, extensional representation * 8-) Let's check if you understand this difference properly: Take your ontology from one of the previous labs (WebProtege or Protege). Identify which statements belong to Terminology (TBox) and World Description (ABox). Put them in the report divided into two sections: TBox and ABox. - //NOTE:// You don't have to translate the statements into DL. Just select parts of the existing file. ==== - Description Logics - Reasoning ==== ^ TBox ^ | Directory \sqsubseteq \forall dir\_child.(Directory \sqcup File) \sqcap (\leq 1\ dir\_child^{-}.\top) | | File \sqsubseteq ( \forall dir\_child.\bot)\ \sqcap \neg Directory \sqcap (\leq 1\ dir\_child^{-}.\top) | | | | FileSysRoot \sqsubseteq Directory \sqcap \forall dir\_child^{-}.\bot | | FileSysElement \equiv ( \exists (dir\_child^{-})^{*}.FileSysRoot ) \sqcup ( FileSysRoot ) | ^ ABox ^ | dir\_child(a,b) | | dir\_child(a,c) | | dir\_child(c,a) | | | | dir\_child(MyDir,Research) | | dir\_child(MyDir,Teaching) | | dir\_child(Research,Semweb.tex) | | FileSysElement(Semweb.tex) | | File(Semweb.tex) | * 8-) Let's consider a simple Knowledge Base about directories and files: K=(TBox, ABox). Which of the following statements could be reasoned from K and why? (you can write solutions by hand, take a photo and put it in the report) - FileSysElement \sqsubseteq Directory \sqcup File - FileSysElement \sqsubseteq \forall (dir\_child^{-})^{*}.Directory - FileSysElement(\alpha), where \alpha = a,b,c - FileSysElement(\beta), where \beta = MyDir, Research, Teaching ===== If you want to know more ===== Lecture: * {{.:2014:eis2014semweb-ontology-logic.pdf|Ontology engineering and reasoning in Semantic Web}} (2014) Description Logics: * [[http://www.cambridge.org/pl/academic/subjects/computer-science/programming-languages-and-applied-logic/description-logic-handbook-theory-implementation-and-applications-2nd-edition?format=PB?format=PB|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