1Description LogicsWhat Are Description Logics?z 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 individualsz Distinguished by:– Formal semantics (typically model theoretic)z Decidable fragments of FOLz Closely related to Propositional Modal & Dynamic Logics– Provision of inference servicesz Sound and complete decision procedures for key problemsz Implemented systems (highly optimized)Description Logicsz Major focus of KR research in the 80’s– Led by Ron Brachman – (AT&T Labs)– Grew out of early network-based KR systems like semantic networks and frames.z Major systems and languages –– 80s: KL-ONE, NIKL, KANDOR, BACK, CLASSIC, LOOM– 90s: FACT, RACER, – 00s: DAML+OIL, OWLz Used as the basis for the Semantic web languages DAML+OIL and OWLz Some (one) commercial systemsDescription Logicsz Thought to be well-suited for the representation of and reasoning about– ontologies– terminological knowledge– Configurations and configuration problems– database schemataz schema design, evolution, and query optimizationz source integration in heterogeneous databases/data warehousesz conceptual modeling of multidimensional aggregation2Example of Network KRz Person, Female, etc are conceptsz hasChild is a property of Person – hasChild relates Parent to Person– Nil means infinity. A Parent is a Person with between 1 and infinity childrenz Large arrows are “IS-A” links– A Mother is a (specialization of a) Parentz Concepts are either primitive or definitions.– Primitive concepts have only necessary properties– Defined concepts have necessary and sufficient conditions.**Graphical notation introduced by KL-ONEDL Paradigmz A Description Logic is mainly characterized by a set of constructors that allow one to build complex descriptions or terms out of conceptsand roles from atomic ones– Concepts correspond to classes z and are interpreted as sets of objects,– Roles correspond to relations z and are interpreted as binary relations on objectsz Set of axioms for asserting facts about concepts, roles and individualsBasic Concepts of a DLz Individuals are treated exactly the same as constants in FOL. z Concepts are exactly the same as Unary Predicates in FOL.z Roles are exactly the same as Binary Predicates in FOL.Descriptionsz Just Like in FOL, what we are dealing with (ultimately) are sets of individuals and relations between individuals. z The basic unit of semantic significance is the Description.z “We are describing sets of individuals”z Description logics differ in the operators they allowz If a “happy father” is a man with both a son and a daughter and all of whose children are either rich or happy, then we can describe the concept in a typical DL asHappyFather = Man ∩∃hasChild.Female ∩∃hasChild.Male ∩∀hasChild.(Rich ∪Happy)3Typical Architecture Knowledge BaseTBoxABoxInferenceSystemInterfaceDefinitions ofTerminologyAssertionsaboutindividualsfather= man ∏ E has.child Xhuman=mammal ∏ biped…john = human ∏ fatherjohn has.child maryThe division into TBox and ABox doesn’t have a logical significance, butis made for conceptual and implementation convenience.A family of languagesz The expressiveness of a description logic is determined by the operators that it uses. z Add or eliminate certain operators (e.g., ¬, ∪), and the statements that can be expressed are increased/reduced in number. z Higher expressiveness implies higher complexityz AL or Attributive Language is the base and includes just a few operators z Other DLs are described by the additional operators they includeAL: Attributive Language Constructor Syntax Example atomic concept C Human atomic negation ~ C ~ Human atomic role R hasChildconjunction C ^ D Human ^ Male value restrict. ∀R.C Human ∀ hasChild.Blond Existential rest. (lim) ∃R Human ∃ hasChildTop (univ. conc.) T Tbottom (null conc) ⊥⊥for concepts C and D and role R ALCConstructor Syntax Example atomic concept C Human negation ~ C ~ (Human V Ape)atomic role R hasChildconjunction C ^ D Human ^ Male disjunction C V D Nice V Rich value restrict. ∀R.C Human ∀ hasChild.Blond Existential rest. ∃R.C Human ∃ hasChild.MaleTop (univ. conc.) T Tbottom (null conc) ⊥⊥ALC is the smallest DL that is propositionally closed (i.e., includes full negation and disjunction) and include booleans (and, or, not) and restrictions on role values4Other ConstructorsConstructor Syntax Examplenumber restriction >= n R >= 7 hasChild <= n R <= 1 hasmotherinverse role R- haschild-Transitive role R* hasChild*Role composition R ◦ R hasParent ◦ hasBrotherQualified # restric. >= n R.C >= 2 hasChild.Female Singleton concepts {<name>} {Italy}∀ and ∃ deserve special attention.z Note that they only can come before a Role: ∀HasChild.Girl ∃isEmployedBy.Farmerz Remember, they describe sets of individuals.z ∀HasChild.Girl would be interpreted as: The set { x | ∀(y)( HasChild(x,y) Æ Girl(y) ) }Note the conditional: Are you in that set?.z ∃isEmployedBy.Farmer would be: The set { x | ∃(y)( isEmployedBy(x,y) & Farmer(y) ) }Special names and combinationsSee http://en.wikipedia.org/wiki/Description_logicz S = ALC + transitive propertiesz H = role hierarchy, e.g., rdfs:subPropertyOfz O = nominals, e.g., values constrained by enumerated classes, as in owl:oneOf and owl:hasValuez I = inverse propertiesz N = cardinality restrictions (owl:cardinality, owl:maxCardonality)z(D)= use of datatypes propertiesz etc.z OWL-DL is SHOIN(D)OWL as a DL z OWL-DL is SHOIN(D)z We can think of OWL as having three kinds of statementsz Ways to specify classes – the intersection of humans and malesz Ways to state axioms about those classes– Humans are a subclass of apesz Ways to talk about individuals– John is a human, john is a male, john has a child mary5Subsumption: D ⊆C ?z Concept C subsumes D iff on every interpretation I– I(D) ⊆I(C)z This means the same as (for complex statements D and C) the assertion:– ∀(x)(D(x) Æ C(x)) z Determining whether one concept logically contains another is called the subsumption problem.z Subsumption is undecidable for reasonably expressive languages, z and non-polynomial for fairly restricted ones.• These problems can be reduced to subsumption (for languages with negation).• Can be reduced to the satisfiability
View Full Document
Unlocking...