Reasoning With Expressive Description Logics
Reasoning with Expressive Description LogicsLogical Foundations for the Semantic WebIan Horrockshorrocks@cs.man.ac.ukUniversity of ManchesterManchester, UKReasoning with Expressive Description Logics – p. 1/40
Talk OutlineReasoning with Expressive Description Logics – p. 2/40
Talk OutlineIntroduction to Description LogicsReasoning with Expressive Description Logics – p. 2/40
Talk OutlineIntroduction to Description LogicsThe Semantic Web: Killer App for (DL) Reasoning?Web Ontology LanguagesDAML OIL LanguageReasoning with Expressive Description Logics – p. 2/40
Talk OutlineIntroduction to Description LogicsThe Semantic Web: Killer App for (DL) Reasoning?Web Ontology LanguagesDAML OIL LanguageReasoning with DAML OILOilEd DemoReasoning with Expressive Description Logics – p. 2/40
Talk OutlineIntroduction to Description LogicsThe Semantic Web: Killer App for (DL) Reasoning?Web Ontology LanguagesDAML OIL LanguageReasoning with DAML OILOilEd DemoDescription Logic ReasoningReasoning with Expressive Description Logics – p. 2/40
Talk OutlineIntroduction to Description LogicsThe Semantic Web: Killer App for (DL) Reasoning?Web Ontology LanguagesDAML OIL LanguageReasoning with DAML OILOilEd DemoDescription Logic ReasoningResearch ChallengesReasoning with Expressive Description Logics – p. 2/40
Introduction to Description LogicsReasoning with Expressive Description Logics – p. 3/40
What are Description Logics?Reasoning with Expressive Description Logics – p. 4/40
What are Description Logics? A family of logic based Knowledge Representation formalisms Descendants of semantic networks and KL-ONE Describe domain in terms of concepts (classes), roles(relationships) and individualsReasoning with Expressive Description Logics – p. 4/40
What are Description Logics? A family of logic based Knowledge Representation formalisms Descendants of semantic networks and KL-ONE Describe domain in terms of concepts (classes), roles(relationships) and individuals Distinguished by: Formal semantics (model theoretic)– Decidable fragments of FOL– Closely related to Propositional Modal & Dynamic Logics Provision of inference services– Sound and complete decision procedures for key problems– Implemented systems (highly optimised)Reasoning with Expressive Description Logics – p. 4/40
DL ArchitectureKnowledge BaseAbox (data)John : Happy-FatherInterface.Man Human u Male.Happy-Father Man u has-child.Female u . . .Inference SystemTbox (schema)hJohn, Maryi : has-child.Reasoning with Expressive Description Logics – p. 5/40
Short History of Description LogicsReasoning with Expressive Description Logics – p. 6/40
Short History of Description LogicsPhase 1: Incomplete systems (Back, Classic, Loom, . . . ) Based on structural algorithmsReasoning with Expressive Description Logics – p. 6/40
Short History of Description LogicsPhase 1: Incomplete systems (Back, Classic, Loom, . . . ) Based on structural algorithmsPhase 2: Development of tableau algorithms and complexity results Tableau-based systems for Pspace logics (e.g., Kris, Crack) Investigation of optimisation techniquesReasoning with Expressive Description Logics – p. 6/40
Short History of Description LogicsPhase 1: Incomplete systems (Back, Classic, Loom, . . . ) Based on structural algorithmsPhase 2: Development of tableau algorithms and complexity results Tableau-based systems for Pspace logics (e.g., Kris, Crack) Investigation of optimisation techniquesPhase 3: Tableau algorithms for very expressive DLs Highly optimised tableau systems for ExpTime logics (e.g.,FaCT, DLP, Racer) Relationship to modal logic and decidable fragments of FOLReasoning with Expressive Description Logics – p. 6/40
Latest DevelopmentsPhase 4:Reasoning with Expressive Description Logics – p. 7/40
Latest DevelopmentsPhase 4: Mature implementationsReasoning with Expressive Description Logics – p. 7/40
Latest DevelopmentsPhase 4: Mature implementations Mainstream applications and Tools Databases– Consistency of conceptual schemata (EER, UML etc.)– Schema integration– Query subsumption (w.r.t. a conceptual schema) Ontologies and Semantic Web (and Grid)– Ontology engineering (design, maintenance, integration)– Reasoning with ontology-based markup (meta-data)– Service description and discoveryReasoning with Expressive Description Logics – p. 7/40
Latest DevelopmentsPhase 4: Mature implementations Mainstream applications and Tools Databases– Consistency of conceptual schemata (EER, UML etc.)– Schema integration– Query subsumption (w.r.t. a conceptual schema) Ontologies and Semantic Web (and Grid)– Ontology engineering (design, maintenance, integration)– Reasoning with ontology-based markup (meta-data)– Service description and discovery Commercial implementations Cerebra system from Network Inference LtdReasoning with Expressive Description Logics – p. 7/40
The Semantic WebReasoning with Expressive Description Logics – p. 8/40
The Semantic Web VisionReasoning with Expressive Description Logics – p. 9/40
The Semantic Web Vision Web made possible through established standards TCP/IP for transporting bits down a wire HTTP & HTML for transporting and rendering hyperlinked textReasoning with Expressive Description Logics – p. 9/40
The Semantic Web Vision Web made possible through established standards TCP/IP for transporting bits down a wire HTTP & HTML for transporting and rendering hyperlinked text Applications able to exploit this common infrastructure Result is the WWW as we know itReasoning with Expressive Description Logics – p. 9/40
The Semantic Web Vision Web made possible through established standards TCP/IP for transporting bits down a wire HTTP & HTML for transporting and rendering hyperlinked text Applications able to exploit this common infrastructure Result is the WWW as we know it 1st generation web mostly handwritten HTML pagesReasoning with Expressive Description Logics – p. 9/40
The Semantic Web Vision Web made possible through established standards TCP/IP for transporting bits down a wire HTTP & HTML for transporting and rendering hyperlinked text Applications able to exploit this common infrastructure Result is the WWW as we know it 1st generation web mostly handwritten HTML pages 2nd generation (current) web often machine generated/activeReasoning with Expressive Description Logics – p. 9/40
The Semantic Web Vision Web made possible through established standards TCP/IP for transporting bits down a wire HTTP & HTML for transporting and rendering hyperlinked text Applications able to exploit this common infrastructure Result is the WWW as we know it 1st generation web mostly handwritten HTML pages 2nd generation (current) web often machine generated/active Both intended for direct human processing/interactionReasoning with Expressive Description Logics – p. 9/40
The Semantic Web Vision Web made possible through established standards TCP/IP for transporting bits down a wire HTTP & HTML for transporting and rendering hyperlinked text Applications able to exploit this common infrastructure Result is the WWW as we know it 1st generation web mostly handwritten HTML pages 2nd generation (current) web often machine generated/active Both intended for direct human processing/interaction In next generation web, resources should be more accessible toautomated processesReasoning with Expressive Description Logics – p. 9/40
The Semantic Web Vision Web made possible through established standards TCP/IP for transporting bits down a wire HTTP & HTML for transporting and rendering hyperlinked text Applications able to exploit this common infrastructure Result is the WWW as we know it 1st generation web mostly handwritten HTML pages 2nd generation (current) web often machine generated/active Both intended for direct human processing/interaction In next generation web, resources should be more accessible toautomated processes To be achieved via semantic markup Metadata annotations that describe content/functionReasoning with Expressive Description Logics – p. 9/40
The Semantic Web Vision Web made possible through established standards TCP/IP for transporting bits down a wire HTTP & HTML for transporting and rendering hyperlinked text Applications able to exploit this common infrastructure Result is the WWW as we know it 1st generation web mostly handwritten HTML pages 2nd generation (current) web often machine generated/active Both intended for direct human processing/interaction In next generation web, resources should be more accessible toautomated processes To be achieved via semantic markup Metadata annotations that describe content/function Coincides with Tim Berners-Lee’s vision of a Semantic WebReasoning with Expressive Description Logics – p. 9/40
The Semantic Web Vision Web made possible through established standards TCP/IP for transporting bits down a wire HTTP & HTML for transporting and rendering hyperlinked text Applications able to exploit this common infrastructure Result is the WWW as we know it 1st generation web mostly handwritten HTML pages 2nd generation (current) web often machine generated/active Both intended for direct human processing/interaction In next generation web, resources should be more accessible toautomated processes To be achieved via semantic markup Metadata annotations that describe content/function Coincides with Tim Berners-Lee’s vision of a Semantic WebReasoning with Expressive Description Logics – p. 9/40
OntologiesReasoning with Expressive Description Logics – p. 10/40
Ontologies Semantic markup must be meaningful to automated processesReasoning with Expressive Description Logics – p. 10/40
Ontologies Semantic markup must be meaningful to automated processes Ontologies will play a key role Source of precisely defined terms (vocabulary) Can be shared across applications (and humans)Reasoning with Expressive Description Logics – p. 10/40
Ontologies Semantic markup must be meaningful to automated processes Ontologies will play a key role Source of precisely defined terms (vocabulary) Can be shared across applications (and humans) Ontology typically consists of: Hierarchical description of important concepts in domain Descriptions of properties of instances of each conceptReasoning with Expressive Description Logics – p. 10/40
Ontologies Semantic markup must be meaningful to automated processes Ontologies will play a key role Source of precisely defined terms (vocabulary) Can be shared across applications (and humans) Ontology typically consists of: Hierarchical description of important concepts in domain Descriptions of properties of instances of each concept Degree of formality can be quite variable (NL–logic)Reasoning with Expressive Description Logics – p. 10/40
Ontologies Semantic markup must be meaningful to automated processes Ontologies will play a key role Source of precisely defined terms (vocabulary) Can be shared across applications (and humans) Ontology typically consists of: Hierarchical description of important concepts in domain Descriptions of properties of instances of each concept Degree of formality can be quite variable (NL–logic) Increased formality and regularity facilitates machine understandingReasoning with Expressive Description Logics – p. 10/40
Ontologies Semantic markup must be meaningful to automated processes Ontologies will play a key role Source of precisely defined terms (vocabulary) Can be shared across applications (and humans) Ontology typically consists of: Hierarchical description of important concepts in domain Descriptions of properties of instances of each concept Degree of formality can be quite variable (NL–logic) Increased formality and regularity facilitates machine understanding Ontologies can be used, e.g.: To facilitate buyer–seller communication in e-commerce In semantic based search To provide richer service descriptions that can be more flexiblyinterpreted by intelligent agentsReasoning with Expressive Description Logics – p. 10/40
Ontologies Semantic markup must be meaningful to automated processes Ontologies will play a key role Source of precisely defined terms (vocabulary) Can be shared across applications (and humans) Ontology typically consists of: Hierarchical description of important concepts in domain Descriptions of properties of instances of each concept Degree of formality can be quite variable (NL–logic) Increased formality and regularity facilitates machine understanding Ontologies can be used, e.g.: To facilitate buyer–seller communication in e-commerce In semantic based search To provide richer service descriptions that can be more flexiblyinterpreted by intelligent agentsReasoning with Expressive Description Logics – p. 10/40
Ontologies Semantic markup must be meaningful to automated processes Ontologies will play a key role Source of precisely defined terms (vocabulary) Can be shared across applications (and humans) Ontology typically consists of: Hierarchical description of important concepts in domain Descriptions of properties of instances of each concept Degree of formality can be quite variable (NL–logic) Increased formality and regularity facilitates machine understanding Ontologies can be used, e.g.: To facilitate buyer–seller communication in e-commerce In semantic based search To provide richer service descriptions that can be more flexiblyinterpreted by intelligent agentsReasoning with Expressive Description Logics – p. 10/40
Ontologies Semantic markup must be meaningful to automated processes Ontologies will play a key role Source of precisely defined terms (vocabulary) Can be shared across applications (and humans) Ontology typically consists of: Hierarchical description of important concepts in domain Descriptions of properties of instances of each concept Degree of formality can be quite variable (NL–logic) Increased formality and regularity facilitates machine understanding Ontologies can be used, e.g.: To facilitate buyer–seller communication in e-commerce In semantic based search To provide richer service descriptions that can be more flexiblyinterpreted by intelligent agentsReasoning with Expressive Description Logics – p. 10/40
Web Ontology LanguagesReasoning with Expressive Description Logics – p. 11/40
Web Ontology Languages OIL and DAML-ONT web ontology languages developed inEuropean and DARPA projectsReasoning with Expressive Description Logics – p. 11/40
Web Ontology Languages OIL and DAML-ONT web ontology languages developed inEuropean and DARPA projects Efforts merged to produce DAML OILReasoning with Expressive Description Logics – p. 11/40
Web Ontology Languages OIL and DAML-ONT web ontology languages developed inEuropean and DARPA projects Efforts merged to produce DAML OIL Submitted to W3C as basis for standardisation WebOnt working group developing OWL language standardReasoning with Expressive Description Logics – p. 11/40
Web Ontology Languages OIL and DAML-ONT web ontology languages developed inEuropean and DARPA projects Efforts merged to produce DAML OIL Submitted to W3C as basis for standardisation WebOnt working group developing OWL language standard DAML OIL/OWL “layered” on top of RDFS RDFS based syntax and ontological primitives (subclass etc.) Adds much richer set of primitives (transitivity, cardinality, . . . )Reasoning with Expressive Description Logics – p. 11/40
Web Ontology Languages OIL and DAML-ONT web ontology languages developed inEuropean and DARPA projects Efforts merged to produce DAML OIL Submitted to W3C as basis for standardisation WebOnt working group developing OWL language standard DAML OIL/OWL “layered” on top of RDFS RDFS based syntax and ontological primitives (subclass etc.) Adds much richer set of primitives (transitivity, cardinality, . . . )Reasoning with Expressive Description Logics – p. 11/40
Web Ontology Languages OIL and DAML-ONT web ontology languages developed inEuropean and DARPA projects Efforts merged to produce DAML OIL Submitted to W3C as basis for standardisation WebOnt working group developing OWL language standard DAML OIL/OWL “layered” on top of RDFS RDFS based syntax and ontological primitives (subclass etc.) Adds much richer set of primitives (transitivity, cardinality, . . . ) Describes class/property structure of domain (Tbox) E.g., Person subclass of Animal whose parents are all PersonsReasoning with Expressive Description Logics – p. 11/40
Web Ontology Languages OIL and DAML-ONT web ontology languages developed inEuropean and DARPA projects Efforts merged to produce DAML OIL Submitted to W3C as basis for standardisation WebOnt working group developing OWL language standard DAML OIL/OWL “layered” on top of RDFS RDFS based syntax and ontological primitives (subclass etc.) Adds much richer set of primitives (transitivity, cardinality, . . . ) Describes class/property structure of domain (Tbox) E.g., Person subclass of Animal whose parents are all Persons Uses RDF for class/property membership assertions (Abox) E.g., john instance of Person; hjohn, maryi instance of parentReasoning with Expressive Description Logics – p. 11/40
Logical Foundations of DAML OILReasoning with Expressive Description Logics – p. 12/40
Logical Foundations of DAML OIL DAML OIL equivalent to very expressive Description LogicReasoning with Expressive Description Logics – p. 12/40
Logical Foundations of DAML OIL DAML OIL equivalent to very expressive Description Logic More precisely, DAML OIL is (extension of) SHIQ DLReasoning with Expressive Description Logics – p. 12/40
Logical Foundations of DAML OIL DAML OIL equivalent to very expressive Description Logic More precisely, DAML OIL is (extension of) SHIQ DL DAML OIL benefits from many years of DL research Well defined semantics Formal properties well understood (complexity, decidability) Known reasoning algorithms Implemented systems (highly optimised)Reasoning with Expressive Description Logics – p. 12/40
Logical Foundations of DAML OIL DAML OIL equivalent to very expressive Description Logic More precisely, DAML OIL is (extension of) SHIQ DL DAML OIL benefits from many years of DL research Well defined semantics Formal properties well understood (complexity, decidability) Known reasoning algorithms Implemented systems (highly optimised) DAML OIL classes can be names (URI’s) or expressions Various constructors provided for building class expressionsReasoning with Expressive Description Logics – p. 12/40
Logical Foundations of DAML OIL DAML OIL equivalent to very expressive Description Logic More precisely, DAML OIL is (extension of) SHIQ DL DAML OIL benefits from many years of DL research Well defined semantics Formal properties well understood (complexity, decidability) Known reasoning algorithms Implemented systems (highly optimised) DAML OIL classes can be names (URI’s) or expressions Various constructors provided for building class expressions Expressive power determined by Kinds of constructor provided Kinds of axiom allowedReasoning with Expressive Description Logics – p. 12/40
DAML OIL Class ConstructorsReasoning with Expressive Description Logics – p. 13/40
DAML OIL Class alityQDL SyntaxC 1 u . . . u CnC1 t . . . t Cn C{x1 . . . xn } P.C P.C6nP.C nP.CExampleHuman u MaleDoctor t Lawyer Male{john, mary} hasChild.Doctor hasChild.Lawyer61hasChild.Male 2hasChild.Lawyer(Modal Syntax)C 1 . . . CnC 1 . . . Cn Cx1 . . . xn[P ]ChP iC[P ]n 1 ChP in CReasoning with Expressive Desc
Description Logic Reasoning Research Challenges Reasoning with Expressive Description Logics – p. 2/40. Talk Outline Introduction to Description Logics The Semantic Web: Killer App for (DL) Reasoning? Web Ontology Languages DAML OIL Language Reasoning with DAML OIL OilEd Demo Description Logic Reasoning Research Challenges Reasoning with Expressive Description Logics – p. 2/40. Talk .
Introduction, Description Logics Petr K remen petr.kremen@fel.cvut.cz October 5, 2015 Petr K remen petr.kremen@fel.cvut.cz Introduction, Description Logics October 5, 2015 1 / 118. Our plan 1 Course Information 2 Towards Description Logics 3 Logics 4 Semantic Networks and Frames 5 Towards Description Logics 6 ALCLanguage Petr K remen petr.kremen@fel.cvut.cz Introduction, Description Logics .
Basic Description Logics Franz Baader Werner Nutt Abstract This chapter provides an introduction to Description Logics as a formal language for representing knowledge and reasoning about it. It first gives a short overview of the ideas underlying Description Logics. Then it introduces syntax and semantics, covering the basic constructors that are used in systems or have been introduced in the .
For many applications natural choices would be various more expressive logics, including the predicate logic or various modal logics. These logics, however, lack the kind of efficient and scalable algorithms that are available for the classical propositional logic. The existence of high performance algorithms for reasoning with propositional
An Introduction to Description Logics Daniele Nardi Ronald J. Brachman Abstract This introduction presents the main motivations for the development of Description Logics (DL) as a formalism for representing knowledge, as well as some important basic notions underlying all systems that have been created in the DL tradition. In addition, we provide the reader with an overview of the entire book .
Fedrico Chesani Introduction to Description Logic(s) Some considerations A Description Language DL Extending DL Description Logics Description Logics and SW A simple logic: DL Concept-forming operators Sentences Semantics Entailment Sentences d 1: d 2 Concept d 1 is equivalent to concept d 2, i.e. the individuals that satisfy d 1 are precisely those that satisfy d 2 Example: PhDStudent .
system. HSR-OD-1-LD: Intelligent one-button table adjustment. HSU-OD-F2-LD: Simple Flex Memory handset, without display. HSU-MDF-4F2-LD: Flex Memory handset with 4 memory keys and display. IRR-DSK-SET: Infrared remote control with 2 sets of up and down keys and memory keys. ACS-ADAP-MOUSE: Computer mouse control adapter.
Department of Computer Science, University of Link oping, Sweden . 9.3 How to Develop a Modal Logic for an Application . . . . . . . . 70 . the classical propositional and predicate calculus modal logics, including logics of programs and temporal logics
Le fabricant et l’utilisateur d’un additif alimentaire sont tenus: a. de transmettre à l’OSAV toute nouvelle information scientifique ou techni-que susceptible d’influer sur l’évaluation de la sécurité de cet additif; et b. d’informer l’OSAV, sur demande, des usages de l’additif concerné. Art. 11 Modification des annexes L’OSAV adapte régulièrement les annexes de la .
