10m ago

11 Views

0 Downloads

895.14 KB

61 Pages

Transcription

Foundations of Description LogicsSebastian RudolphInstitute AIFB, Karlsruhe Institute of Technology, [email protected] This chapter accompanies the foundational lecture on Description Logics (DLs) at the 7th Reasoning Web Summer School in Galway,Ireland, 2011. It introduces basic notions and facts about this family oflogics which has signiﬁcantly gained in importance over the recent yearsas these logics constitute the formal basis for today’s most expressive ontology languages, the OWL (Web Ontology Language) family.We start out from some general remarks and examples demonstratingthe modeling capabilities of description logics as well as their relationto ﬁrst-order predicate logic. Then we begin our formal treatment byintroducing the syntax of DL knowledge bases which comes in threeparts: RBox, TBox and ABox. Thereafter, we provide the correspondingstandard model-theoretic semantics and give a glimpse of the alternativeway of deﬁning the semantics via an embedding into ﬁrst-order logic withequality.We continue with an overview of the naming conventions for DLsbefore we delve into considerations about diﬀerent notions of semanticalikeness (concept and knowledge base equivalence as well as emulation).These are crucial for investigating the expressivity of DLs and performingnormalization. We move on by reviewing knowledge representation capabilities brought about by diﬀerent DL features and their combinationsas well as some model-theoretic properties associated thereto.Subsequently, we consider typical reasoning tasks occurring in thecontext of DL knowledge bases. We show how some of these tasks canbe reduced to each other, and have a look at diﬀerent algorithmic approaches to realize automated reasoning in DLs.Finally, we establish connections between DLs and OWL. We showhow DL knowledge bases can be expressed in OWL and, conversely, howOWL modeling features can be translated into DLs.In our considerations, we focus on the description logic SROIQ whichunderlies the most recent and most expressive yet decidable version ofOWL called OWL 2 DL. We concentrate on the logical aspects and omitdata types as well as extralogical features from our treatise. Examplesand exercises are provided throughout the chapter.A. Polleres et al. (Eds.): Reasoning Web 2011, LNCS 6848, pp. 76–136, 2011.c Springer-Verlag Berlin Heidelberg 2011

Foundations of Description Logics1Introduction77Come join the DL vaudeville show!It’s variable-free, althoughWith quantiﬁers, not, and, orQuite deeply rooted in FOLklore.Still, curing the ﬁrst-order ailmentWe sport decidable entailment!While formal, logic-based approaches to representing and working with knowledge occurthroughout human history, the advent and widespread adoption of programmable computing devices in the 20th century has led to intensiﬁedstudies of both theoretical and practical aspects ofknowledge representation and automated reasoning. Rooted in early AI approaches, DescriptionLogics (DLs) have developed into one of the mainknowledge representation formalisms. The maturity of the ﬁeld is also reﬂected by the adoption ofFig. 1. The DL logodescription logics as prior speciﬁcation paradigmfor ontological descriptions – culminating in the standardization of the OWLweb ontology language by the World Wide Web Consortium (W3C) – as wellas the availability of highly optimized and readily deployable (yet open source)tools for automated inferencing. Thanks to this “dissemination path,” DLs constitute the theoretical backbone for information systems in many disciplines,among which life sciences can be seen as the “early adopters” [Sidhu et al., 2005;Wolstencroft et al., 2005; Golbreich et al., 2006].1.1OutlookWhat is in this Lecture. This document is supposed to give a gentle introduction into state-of-the-art description logics. Before going into technicalitiesthe remainder of this section will brieﬂy discuss how DLs are positioned in thelandscape of knowledge representation formalisms, provide some examples formodeling features of DLs, and sketch the most prominent application context:the Semantic Web.Section 2 starts the formal treatment by introducing the syntax of knowledgebases of the description logic SROIQ. Section 3 provides the correspondingmodel-theoretic semantics and substantiates the claimed connection betweenDLs and ﬁrst-order predicate logic (FOL) by giving a translation from SROIQinto FOL with equality.Section 4 reviews the naming scheme for DLs between the basic DL ALCand the high-end DL SROIQ. Section 5 provides several notions that capturethat diﬀerent syntactic speciﬁcations may have the same (or “alike”) semanticalimpact. The motivation of Section 6 is to give a feeling for the modeling powerprovided by diﬀerent constructs and the according model-theoretic consequences.Subsequently, Section 7 considers typical reasoning tasks normally occurringin the context of DL-based knowledge representation and discusses the mutual

78S. Rudolphreducibility of these tasks. In Section 8, we give a shallow overview over diﬀerentalgorithmic paradigms for automated inferencing with DLs. Finally, in Section 9,we provide a way to translate SROIQ knowledge bases into OWL ontologiesand, conversely, show how OWL axioms can be translated into DLs.What is not in this Lecture. Due to space limitations, we have to restrictthis lecture in many respects. We will focus on the core logical aspects of description logics and hence omit datatypes, keys, etc. despite their obvious practicalimportance for knowledge representation. Likewise, this is not supposed to bean introduction into OWL nor any other Semantic Web speciﬁcation language.Thus, we will only brieﬂy state how DL knowledge bases can be translated intoOWL such that OWL reasoning tools can be harnessed to perform DL reasoningtasks. Moreover, we will refrain from looking into sub-Boolean fragments of DLs,even though they are practically important for serving as theoretical basis forthe tractable proﬁles of the latest version of OWL. On the theoretical side, wewill omit considerations about computational complexity of reasoning tasks.Required Previous Knowledge. This lecture is meant to be introductory andfoundational. Consequently, we tried to make it as self-contained as feasibly possible and hope that it is comprehensible even without any background in formallogics, although it can do no harm either. We presume, however, a certain familiarity with basic concepts and notations of naı̈ve set theory. We do not expectprior knowledge about Semantic Web formalisms like the Resource DescriptionFramework (RDF) or OWL, still it would come handy to fully comprehend thecomments about the connections between DLs and OWL.1.2DLs in the Context of Other FormalismsHistorically, DLs have emerged from semantic networks [Quillian, 1968] andframe-based systems [Minsky, 1974]. These early knowledge representation approaches had the advantage of being rather intuitively readable and comprehensible. On the downside, it turned out that the understanding of the precisemeaning of these diagrammatic representations diﬀered widely amongst humans.This also became apparent by the heterogeneous behavior of tools implementedto reason with these structures. Under a plethora of names (among them terminological systems and concept languages), description logics developed out ofthe attempt to endow these intuitive representations with a formal semantics toestablish a common ground for human and tool interoperability.With the formal semantics introduced it was rather immediately clear that –abstracting from the syntax used – DLs can be seen as a fragment of ﬁrst-orderpredicate logic (short: FOL), many of them even as a fragment of FOL’s twovariable fragment [Borgida, 1996] in cases extended with counting quantiﬁers[Pratt-Hartmann, 2005]. As opposed to general FOL where logical inferencing isundecidable, DL research has been focusing on decidable fragments to such anextent that today, decidability is almost conceived as a necessary condition tocall a formalism a DL.

Foundations of Description Logics79Remark 1. Recap that in theoretical computer science, a class of problems iscalled decidable, if there is a generic algorithm that can take any problem instancefrom this class as an input and provide a yes-or-no answer to it after ﬁnite time. Inthe context of logics, the generic problem normally investigated is whether a givenset of statements logically entails another statement. In case there is no danger ofconfusion about the type of problem considered, sometimes the logic itself is calleddecidable or undecidable.In contrast to the well-known correspondence to FOL, it took some time todiscover the close relation of DLs to modal logics [Schild, 1991]; in fact, the basicdescription logic ALC is just a syntactic variant of the multi-modal logic Km .As a consequence of this, there is also a close relationship of DLs to the GuardedFragment [Andréka et al., 1998], a very expressive fragment of FOL which is stilldecidable.For application purposes, DLs can be tailored to the speciﬁc requirementsof a concrete usage scenario. To this end, a set of modeling features is selectedsuch that the resulting logic has suﬃcient expressivity for the intended purposewhile still being manageable in terms of the inferencing needed. This strategyhas led to thorough investigations and ﬁnally a deeper understanding of theimpact of the diverse standard modeling features on decidability and complexityof reasoning.Remark 2. Thereby, the boundaries of the above mentioned fragments are sometimes crossed. For instance, functionality statements and cardinality constraints ingeneral are not supported by the Guarded Fragment, the same holds for transitivitystatements, which also lie outside the two-variable fragment. DLs featuring regular expressions on roles [Calvanese et al., 2009] even go beyond FOL with equality,but we will not discuss them here.Beyond decidability, a crucial design principle in DLs is to establish favorable trade-oﬀs between expressivity and scalability. On the theoretical side, establishing complexity results for inferencing problems (a tradition started byBrachman and Levesque [1984] and meanwhile widely accepted as central partof the DL research methodology) helps to roughly estimate how scalable andhow “implementable” reasoning methods are likely to be. Of course, for thedeployment in practice, many engineering and optimization considerations arenecessary even if they do not inﬂuence the worst-case complexities. Today, thereexist several highly optimized and eﬃcient systems for reasoning in DL-basedformalisms [Motik et al., 2009c; Sirin et al., 2007; Tsarkov and Horrocks, 2006].1.3DL Modeling in a NutshellThis section provides an informal introduction of the most common modelingfeatures in DLs. For the interested reader with some background in logics, wewill relate them to FOL with equality by giving the corresponding terms andlogical translations in square brackets.All DLs are based on a vocabulary [signature] containing individual names[constants], concept names [unary predicates] and role names [binary predicates].

80S. RudolphTwo speciﬁc class names, and , denote the concept containing all individualsand the empty concept, respectively. Usually, a DL knowledge base [theory]is partitioned into an assertional part, called ABox and a terminological part,which is further subdivided into TBox and RBox. The ABox contains assertionalknowledge [ground facts], the notation of which coincides with FOL: there areconcept assertions such asActor(angelina)(indicating that the individual named angelina belongs to the set of all actors)and role assertions likemarried(angelina,brad)(stating that the individuals named angelina and brad are in the relation ofbeing married). The TBox contains universal statements. The notation usedin DLs does not need variables and is inspired by set theory. We can specifysubsumptions, e.g. by expressing that every actor is an artist viaActor Artist [ x Actor(x) Artist(x) ]. A speciﬁc feature of DLs is that concept namescan be combined into complex concepts by Boolean operators, as inActor USGovernor Bodybuilder Austrian [ x Actor(x) USGovernor(x) Bodybuilder(x) Austrian(x) ], expressingthat every actor who is a US governor is also a bodybuilder or not Austrian.Another way to deﬁne complex concepts is by quantifying over roles, as forinstance in knows.Actor hasfriend.Envious [ x y(knows(x, y) Actor(y)) z(hasfriend(x, z) Envious(z)) ], whichstates that everybody knowing some actor has only envious friends.The modeling features introduced above constitute ALC (attributive languagewith complements, [Schmidt-Schauß and Smolka, 1991]), the smallest DL that isBoolean-closed (i.e. it allows Boolean operators to be applied to concepts withoutrestriction).As stated before, in order to satisfy requirements emerging from practicalmodeling scenarios, these basic modeling features have been enriched by moreand more expressive features for specifying and querying knowledge. In DLs, thisdevelopment has led from the basic ALC to more expressive formalisms. Roleinverses can be used to “traverse” roles backward e.g. in HasChild. hasChild .Grandparent[ x( y(hasChild(x, y)) z(hasChild(z, x) Grandparent(x)))], expressingthat everybody having a child is the child of only grandparents. Cardinalityconstraints allow for specifying the number of related instances:Polygamist 2.Married.

Foundations of Description Logics81[ x(Polygamist(x) y z(Married(x, y) Married(x, z) y z))] states thata polygamist is married to at least two distinct individuals. By means of nominals, classes can be deﬁned by enumerating their instances: the axiom Married.{brad} {angelina}[ x(Married(x, brad) x angelina)] claims that being married to Brad is aproperty only applying to Angelina.The RBox of a DL knowledge base allows for further, role-centric mo