Number Restrictions on Complex Roles in Description Logics: A Preliminary Report.
Franz Baader, Ulrike Sattler · Description Logics · 1996
Number restrictions are concept constructors that are available in almost all implemented description logic systems. However, even though there has lately been considerable effort on integrating expressive role constructors into description logics, the roles that may occur in number restrictions are usually of a very restricted type. Until now, only languages with number restrictions on atomic roles and inversion of atomic roles, or with number restrictions on intersection of atomic roles have been investigated in detail. In the present paper, we increase the expressive power of description languages by allowing for more complex roles in number restrictions. As role constructors, we consider composition of roles (which will be present in all our languages), and intersection, union and inversion of roles in different combinations. We will present two decidability results (for the basic language that extends A~U by number restrictions on roles with composition, and for one extension of this language), and three undecidability results for three other extensions of the basic language. 1 Motivation and introduction Description logics is a field of knowledge representation in which there is a rather close interaction between theory and practice. On the one hand, there are various implemented systems based on description logics, which offer a palette of description formalisms with differing expressive power [Peltason,1991; Brachman et a/.,1991; MacGregor,1991; Mays et al.,1991; Baader et al.,1994; Bresciani et al.,1995]. On the other hand, the computational properties (like de*This author is supported by the Deutsche Forschungsgemeinschaft under Grant No. Sp 230 6-6. cidability, complexity) of various description formalisms have thoroughly been investigated [Nebel,1988; Schmidt-Schauss,1989; Patel-Schneider,1989; Donini et a/.,1991a; 1991b]. These investigation were often motivated by the use of certain constructors in systems or the need for these constructors in specific applications [Baader & Hanschke,1993; Franconi,1994], and the results have influenced the design of new systems. The terminological formalisms of knowledge representation systems based on description logics provide constructors that can be used to build complex concepts and roles out of atomic concepts (unary predicates) and roles (binary predicates). Until recently, the main emphasis, both in implemented systems and in theoretical research, was on constructors for building complex concepts. The need for rich role constructors in certain application domains (such as representing rich schema languages for databases [Calvanese et a/.,1994; 1995], or domains that require the appropriate modeling of part-whole relations [Padgham & Lambrix,1994; Artale et a/.,1994; Sattler,1995]) has triggered research on description languages that also provide for expressive role constructors [Baader,1990; De Giacomo & Lenzerini,1995]. These investigations were facilitated by the observation that the formalisms considered in description logics are very similar to certain modal logics [Schild,1991; De Giacomo & Lenzerini,1994]. In particular, well-known modal logics, such as propositional dynamic logics (PDL) and its extensions [Fischer & Ladner,1979; BenAri et a/.,1982; Harel,1984], provide for role constructors like composition, union, transitive closure, and inversion. Number restrictions are concept constructors that are available in almost all implemented description logic systems. They allow to restrict the number of role successors of an individual w.r.t, a given role. For example, if has-child is an atomic role and person is an atomic concept, then we can describe all persons having at most 2 children by the concept person ~ (_< 2 has-child). In contrast to the rather prominent rSle that number restrictions play in deFrom: AAAI Technical Report WS-96-05. Compilation copyright © 1996, AAAI (www.aaai.org). All rights reserved. scription logics, the corresponding constructors in modal logic--so-called graded modalities [Fine,1972; van der HoekD intersection of roles can prohibit that a parent marries his/her own child: (_< 0 has-childYlis-married-to); union and composition can be used to describe that all children have the same name as their parent: (= 1 has-name [_] (has-childohas-name)). Number restrictions on complex roles are not only of interest in toy examples like the family domain used above. Our original motivation for considering these constructs comes from a process engineering application, where planning and optimization of large chemical plants is supported by building process models. The engineering knowledge concerning standard building blocks of these models is to be represented in a description logic system. For example, the concept (device V1 (= 1 controlled-by))describes devices that are controlled by a single control unit. If we want to describe a device such that all devices connected to it are controlled by the same control unit, we need composition in the number restriction: (device [-1 (= 1 connected-to o controlled-by)). To assure that the device itself is also controlled by the same unit controlling the devices connected to it, we additionally need union in the number restriction: (device [-1 (---1 controlled-by U connected-toocontrolled-by)). Inversion of roles comes in if we need the role controls as well. There are also more complex properties of devices and other parts of process models that could be expressed with number restrictions on complex roles. However, to be useful in practice, it is not sufficient to have a description language that can just be used to represent the relevant properties of objects. The description logic system must also be able to reason about the descriptions. As a positive result in this direction, we show that the subsumption and the satisfiability problem for the language AggAf(o), which extends AlL with number restrictions on roles built with composition, are decidable. On the other hand, three extensions of this language turn out to be undecidable: Af-E+with number restrictions on roles built with composition and union; MEg with number restrictions on roles built with composition and intersection; and MEg with number restrictions on roles built with composition, union, and inversion. However, if union and intersection are restricted to role chains of the same length, then we obtain a decidable extension of Af_~. In the next section, we introduce syntax and semantics of the concept and role constructors that will be considered. Section 3.1 describes the algorithm that decides satisfiability of AE_gAf(o)-concepts, and Section 3.2 extends this decidability result to number restrictions on union and intersection of role chains of the same length. The subsequent section sketches the undecidability proofs, which all use a reduction of the domino problem. In Section 5, we mention related decidability and undecidability results from modal and description logics. 2 Concept and role constructors We define syntax and semantics of all the constructors considered in the present paper, and introduce the description languages that will be investigated in more detail. Definition 1 Starting with atomic roles from a set NR of role names, complex roles are built using the role constructors composition (RoS), union (R 0 intersection (R ~ S), inversion (R-I), and transitive closure ( R+ ). The set of Mr_E-concepts is built from a set Nc of concept names using the concept constructors disjunction (C U D), conjunction (C N D), negation (-~C),