Description Logics Basics, Applications, And More Ian .

2y ago
93.10 KB
16 Pages
Last View : 1m ago
Last Download : 1y ago
Upload by : Harley Spears

Description Logics—Basics, Applications, and MoreIan HorrocksInformation Management GroupUniversity of Manchester, UKUlrike SattlerTeaching and Research Area for Theoretical Computer ScienceRWTH Aachen, GermanyRWTH AachenGermany1

Overview of the Tutorial History and Basics: Syntax, Semantics, ABoxes, Tboxes, Inference Problemsand their interrelationship, and Relationship with other (logical) formalisms Applications of DLs: ER-diagrams with demo, ontologies, etc. includingsystem demonstration Reasoning Procedures: simple tableaux and why they work Reasoning Procedures II: more complex tableaux, non-standard inference problems Complexity issues Implementing/Optimising DL systemsRWTH AachenGermany2

Description Logics family of logic-based knowledge representation formalisms well-suited for therepresentation of and reasoning about terminological knowledge configurations ontologies database schemata– schema design, evolution, and query optimisation– source integration in heterogeneous databases/data warehouses– conceptual modelling of multidimensional aggregation . descendents of semantics networks, frame-based systems, and KL-ONE aka terminological KR systems, concept languages, etc.RWTH AachenGermany3

Architecture of a Standard DL SystemKnowledge BaseTerminologyFather Man u has child. .Human Mammal u Biped.DescriptionLogicConcrete SituationJohn:Human u FatherJohn has child Bill.RWTH AachenGermanyINFERENCESYSTEMINTERFACE4

Introduction to DL IA Description Logic - mainly characterised by a set of constructors that allowto build complex concepts and roles from atomic ones,concepts correspond to classes / are interpreted as sets of objects,roles correspond to relations / are interpreted as binary relations on objects,Example: Happy Father in the DL ALC RWTH AachenGermanyMan u ( has-child.Blue) u( has-child.Green) u( has-child.Happy t Rich)5

Introduction to DL: Syntax and Semantics of ALCSemantics given by means of an interpretation I ( I , ·I ):SyntaxExampleSemanticsatomic conceptAHumanA I Iatomic roleRlikesR I I IConstructorFor C, D concepts and R a role nameconjunctionC u D Human u MaleC I DIdisjunctionCtDNice t RichC I DI C Meat I \ C InegationRWTH AachenGermanyexists restrict. R.C has-child.Human {x y.hx, yi RI y C I }value restrict. R.C has-child.Blond {x y.hx, yi RI y C I }6

Introduction to DL: Other DL r restriction( n R)( 7 has-child){x {y.hx, yi RI } n}(; ALCN )( n R)( 1 has-mother){x {y.hx, yi RI } n}inverse roleR has-child {hx, yi hy, xi RI }trans. roleR has-child (RI ) concrete domainu1, . . . , un.P h-father·age, age. {x huI1 (x), . . . , uIn (x)i P }etc.Many other different DLs/DL constructors have been investigatedRWTH AachenGermany7

Introduction to DL: Knowledge Bases: TBoxesFor terminological knowledge: TBox containsConcept definitionsAxiomsA C (A a concept name, C a complex concept) Man u has-child.HumanFather Human Mammal u has-child .Human; introduce macros/names for concepts, can be (a)cyclicC1 v C2 (Ci complex concepts) favourite.Brewery v drinks.Beer; restrict your modelsAn interpretation I satisfiesa concept definitionan axioma TBoxRWTH AachenGermany.A C iff AI C IC1 v C2 iff C1I C2ITiff I satisfies all definitions and axioms in T; I is a model of T8

Introduction to DL: Knowledge Bases: ABoxesFor assertional knowledge: ABox containsConcept assertionsRole assertionsa : C (a an individual name, C a complex concept)John : Man u has-child.(Male u Happy)ha1, a2i : R (ai individual names, R a role)hJohn, Billi : has-childAn interpretation I satisfiesa concept assertiona role assertionan ABoxRWTH AachenGermanya : C iff aI C Iha1, a2i : R iff haI1 , aI2 i RIA iff I satisfies all assertions in A; I is a model of A9

Introduction to DL: Basic Inference ProblemsSubsumption: C v DIs C I D I in all interpretations I ?w.r.t. TBox T : C vT DIs C I D I in all models I of T ?; structure your knowledge, compute taxonomyConsistency: Is C consistent w.r.t. T ? Is there a model I of T with C I 6 ?of ABox A: Is A consistent?of KB (T ,A): Is (T ,A) consistent?Is there a model of A?Is there a model of both T and A?Inference Problems are closely related:C vT D iff C u D is inconsistent w.r.t. T ,(no model of I has an instance of C u D )C is consistent w.r.t. T iff not C vT A u A; Decision Procdures for consistency (w.r.t. TBoxes) sufficeRWTH AachenGermany10

Introduction to DL: Basic Inference Problems IIFor most DLs, the basic inference problems are decidable,with complexities between P and ExpTime.Why is decidability important? Why does semi-decidability not suffice?If subsumption (and hence consistency) is undecidable, and subsumption is semi-decidable, then consistency is not semi-decidable consistency is semi-decidable, then subsumption is not semi-decidable Quest for a “highly expressive” DL with decidable/“practicable” inference problemswhere expressiveness depends on the applicationpracticability changed over the timeRWTH AachenGermany11

Introduction to DL: HistoryComplexity of Inferences provided by DL systems over the timeInvestigation of Complexity of Inference Problems/Algorithms startsUndecidableKL-ONENIKLLoomFact,ExpTimeDLP, RaceCrack, KrisPSpaceNPPTimeClassic (AT&T)late’80sRWTH AachenGermanyearly’90smid’90slate’90s12

Introduction to DL: State-of-the-implementation-artIn the last 5 years, DL-based systems were built that can handle DLs far more expressive than ALC (close relatives of converse-DPDL) Number restrictions: “people having at most 2 children” Complex roles: inverse (“has-child” — “child-of”),transitive closure (“offspring” — “has-child”),role inclusion (“has-daughter” — “has-child”), etc. implement provably sound and complete inference algorithms(for ExpTime-complete problems) can handle large knowledge bases(e.g., Galen medical terminology ontology: 2,740 concepts, 413 roles, 1,214 axioms) are highly optimised versions of tableau-based algorithms perform (surprisingly well) on benchmarks for modal logic reasoners(Tableaux’98, Tableaux’99)RWTH AachenGermany13

Relationship with Other Logical Formalisms: First Order Predicate LogicMost DLs are decidable fragments of FOL: Introducea unary predicate φA for a concept name Aa binary relation ρR for a role name RTranslate complex concepts C, D as follows:tx(A) φA(x),ty (A) φA(y),tx(C u D) tx(C) tx(D),ty (C u D) ty (C) ty (D),tx(C t D) tx(C) tx(D),ty (C t D) ty (C) ty (D),tx( R.C) y.ρR(x, y) ty (C),ty ( R.C) x.ρR(y, x) tx(C),tx( R.C) y.ρR(x, y) ty (C), ty ( R.C) x.ρR(y, x) tx(C).A TBox T {Ci v Di} is translated as ΦT x.tx(Ci) tx(Di)1 i nRWTH AachenGermany14

Relationship with Other Logical Formalisms: First Order Predicate Logic IIC is consistent iff its translation tx(C) is satisfiable,C is consistent w.r.t. T iff its translation tx(C) ΦT is satisfiable,C v D iff tx(C) tx(D) is validC vT D iff Φt x.(tx(C) tx(D)) is valid.; ALC is a fragment of FOL with 2 variables (L2), known to be decidable; ALC with inverse roles and Boolean operators on roles is a fragment of L2; further adding number restrictions yields a fragment of C2(L2 with “counting quantifiers”), known to be decidable in contrast to most DLs, adding transitive roles/transitive closure operatorto L2 leads to undecidability many DLs (like many modal logics) are fragments of the Guarded Fragment most DLs are less complex than L2:L2 is NExpTime-complete, most DLs are in ExpTimeRWTH AachenGermany15

Relationship with Other Logical Formalisms: Modal LogicsDLs and Modal Logics are closely related:ALC multi-modal K:C u D C D, C C, R.C hRiC ,CtD C D R.C [R]C transitive frames (e.g., in K4)transitive roles regular expressions on programs (e.g., in PDL)regular expressions on roles converse programs (e.g., in C-PDL)inverse roles deterministic programs (e.g., in D-PDL)number restrictions no TBoxes available in modal logics.; “internalise” axioms using a universal role u: C D [u](C D) no ABox available in modal logics ; use nominalsRWTH AachenGermany16

Description Logic RWTH Aachen Germany 4. Introduction to DL I A Description Logic - mainly characterised by a set of constructors that allow to build complex concepts and roles from atomic ones, concepts correspond to classes / are interpreted as sets of objects, roles correspond to relations / are interpreted as binary relations on objects, Example: Happy Father in the DL ALC Manu (9has-child .

Related Documents:

Introduction, Description Logics Petr K remen October 5, 2015 Petr K remen 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 Introduction, Description Logics .

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 .

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 .

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 .

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

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