dcs-tr-295.ps.Z Description Logics are not just for the FLIGHTLESS-BIRDS: A New Look at the Utility and Foundations of Description Logics Alex Borgida ABSTRACT: This paper presents some of the underlying principles of description logics (also known as terminological logics or KLONE-style languages), grounding them in the lattice of terms organized by the so-called ``subsumption'' relationship. A survey of the increasingly varied uses of description logics, including industrial applications, is presented by considering their role in a number of different operations that one can apply to a knowledge base, including languages for queries, answers, updates, rules, and constraints. Finally, we discuss some of the complexity results related to the logics of descriptions, and survey a spectrum of responses to the many intractability proofs. dcs-tr-295a.ps.Z TITLE: On the Relationship between Description Logic and Predicate Logic Queries. AUTHOR: Alex Borgida, Dept. of Computer Science, Rutgers University. ABSTRACT: Description Languages (DLs) are descendants of the KL-ONE knowledge representation system, and form the basis of several object-centered knowledge base management systems developed in recent years, including ones in industrial use. Originally used for conceptual modeling (to define views), DLs are seeing increased use as query languages for retrieving information. This paper, aimed at a general audience that includes database researchers, considers the relationship between the expressive power of DLs and that of query languages based on Predicate Calculus. We show that all descriptions built using constructors currently considered in the literature can be expressed as formulae of the First Order Predicate Calculus with at most three variable symbols, though we have to allow numeric quantifiers and infinitary disjunction in order to handle a couple of special constructors. Conversely, we show that all first-order queries (formulae with one free variable) built up from unary and binary predicates using at most three variables can be expressed as descriptions. We establish similar results for the subset of FOPC involving two variable symbols. We also show that certain subsets of constructors can be used to express only formulae in such well-studied subsets of FOPC as conjunctive queries and existential queries. For these languages, we gain ideas for subsumption algorithms from the work in the database literature on the containment problem of existential queries. The paper also suggests how one can transfer to DLs results from the theoretical database literature about languages based on predicate calculus with recursion. This includes a new decidability result for DLs with recursive concept definitions. lcsr-tr-209.ps.Z TITLE: The frame problem in object-oriented specifications: an exhibition of problems and approaches AUTHOR: Alex Borgida, Dept. of Computer Science, Rutgers University ABSTRACT: We present first a series of examples involving the development of information systems, which suggest a number of desirable features for object-oriented specification techniques, especialy those supporting inheritance. Most of these features have difficulties with the so-called *frame axioms* --- assertions which state what values have been left unchanged by some procedure. We then examine the benefits and disadvantages of a variety of proposals for dealing with the frame problem, some of which are based on ideas presented earlier in the literature, while others are novel. The approaches are grouped into two families: one which introduces notational conventions/abbreviation for stating frame axioms, and one which embeds them into the language semantics. Of particular interest may be the introduction of a model-theoretic version of the assumption that things don't change unless they have to, and the possibility of relating this to syntactic techniques for stating such frame axioms in standard logic. lcsr-tr-228.ps.Z Explaining Subsumption in Description Logics Deborah L. McGuinness and Alex Borgida Dept. of Computer Science Rutgers University Abstract Description Logic-based systems include extensive, complex reasoning components that may produce results that surprise users, yet these systems typically provide little or no explanation support. In this paper, we explore the explanation of subsumption reasoning in Description Logics from one perspective---explanation for knowledge engineers. We adopt a deductive framework for presenting the variety of inferences supported in these systems, and thereby achieve a simple, uniform specification of the notion of explanation. We then address the problem of overly-long and overly-detailed explanations by introducing the notions of atomic descriptions and atomic explanations. We also provide an implementation perspective by discussing the design space and presenting some desiderata for explanation modules. We have implemented our approach in the CLASSIC knowledge representation system. lcsr-tr-238.ps.Z TITLE: Modular Implementation of Individual Reasoning in PROTODL --- the Extensible Description Logic Management System. AUTHORS: Alex Borgida, Daniel Kudenko DATE: December 1994 ABSTRACT: This is the second report in a series on the PROTODL system, which is an *extensible* knowledge representation and reasoning system based on Description Logics (DLs). We have motivated elsewhere [Borgida&Brachman92, Borgida92] the utility of being able to add new concept constructors to a DL, and, while in previous papers we have concentrated on subsumption reasoning, in this paper we consider reasoning about individuals. We present the modular implementation of a Description Logic-based KBMS which performs inferences about individuals in such a way that the addition of each new concept constructors is achieved by introducing a series of functions (and possibly modifying some old ones). Considerable emphasis has been placed on the efficient handling of *incremental* updates. This is accomplished by combining the primitive procedures in different ways in order to obtain variants of the standard procedures for inferring concept (non)membership -- variants that take into account the fact that the previous state of the KB was consistent, and that we know what specific kind of update has been performed, and when dependency links have been set.