borgida-kr92.dvi.Z  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 A. Borgida, ``Towards the Systematic Development of Terminological
Reasoners: CLASP Reconstructed'', in B.Nebel, C.Rich, and W.Swartout,
editors, {\em Principles of Knowledge Representation and Reasoning:
Proceedings of the Third International Conference} (KR'92$^{\bf *}$),
Boston, MA, October 1992, pp.259--269
 \begin{abstract}
  It is argued that considerable benefits can be obtained by making
 KR\&R systems easily extendable, so that new language constructs can
 be added on a per-application basis. In order to achieve this
 extensibility we need techniques for formally specifying the
 extensions, and for modularly and locally modifying the
 implementations. We present two such techniques applicable to the
 family of reasoners based on Description/Terminological Logics, namely
 natural semantics rules of inference, and the \protodl\ customizable
 KBMS architecture. The bulk of the paper aims to demonstrate the
 efficacy of these techniques, together with some heuristics for their
 use, by showing how we could reconstruct a previously proposed
 description logic: Devanbu and Litman's extension to \classic, called
 \clasp, designed to reason about actions and plans. In the process, we
 uncover a few deficiencies in the original proposal, and provide for
 the first time a formal semantics for \clasp.
 \end{abstract}

icse93.hqx.Z ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  A. Borgida, J. Mylopoulos, R. Reiter, `` {\tt And nothing else
changes ...} -- The frame problem in procedure specifications'', {\em
15th Int. Conf. on Software Engineering}, May 1993, Baltimore, MD.

oo-frame-problem.dvi.Z~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 A. Borgida, {\em The frame problem in object-oriented specifications: an
exhibition of problems and approaches}, Technical Report 209, DCS, Rutgers.

  \begin{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 {\em 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.  \end{abstract}

lcs-aaai.ps.Z~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  W. Cohen, A. Borgida, H. Hirsh, ``Computing Least Common Subsumers
in Description Logics'', {\em Proceeding of AAAI'92 Conference},
pp.754--760, San Jose, CA, July 1992.  

 \begin{abstract} Description logics are a popular formalism for
  knowledge representation and reasoning.  This paper introduces a new
  operation for description logics: computing the ``least common
  subsumer'' of a pair of descriptions. This operation computes the
  largest set of commonalities between two descriptions.  After arguing
  for the usefulness of this operation, we analyze it by relating
  computation of the least common subsumer to the well-understood
  problem of testing subsumption; a close connection is shown in the
  restricted case of ``structural subsumption''.  We also present a
  method for computing the least common subsumer of ``attribute chain
  equalities'', and analyze the tractability of computing the least
  common subsumer of a set of descriptions---an important operation in
  inductive learning.  \end{abstract}


cikm.dvi.Z ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 A. Borgida, R. Brachman, ``Customizable Classification Inference in
the ProtoDL Description Management System'', {\em Proc. International
Conference on Information and Knowledge Management}, Baltimore, MD,
November 1992, pp.482--490.

   \abstract Description Languages (DLs) form the basis of several
  knowledge base management systems developed in recent years. DLs have
  logics that support reasoning with intensional descriptions and the
  subsumption relationship between them, and provide services not
  available in other KBMS.  After a brief review of DL-based KBMS, we
  motivate the need for being able to {\em extend} the expressive power
  of the associated languages and {\em customize} the inferences drawn
  by them.  We present the architecture of \protodl, which facilitates
  the addition of new description constructors to a DL, and the addition
  to the implementation of all the necessary inferences to support them.
  This extensibility provides a number of advantages, including the
  ability to introduce domain-specific language features (e.g., for
  time, planning, etc.), and a new alternative to the unpleasant
  traditional choice between building systems that are fully expressive
  (at the cost of incomplete or unpredictably slow implementation) and
  systems of restricted expressive power (at the cost of being unusable
  in many practical applications).

concept-langs-as-type.dvi.Z ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  A.Borgida, ``From Type Systems to Knowledge Representation: Natural
Semantics Specifications for Description Logics'', {\it International
Journal of Intelligent and Cooperative Information Systems}, March
1992, pp.93--126.

  \abstract{ We explore the similarities and differences between concept
  definitions in {\em description logics (DLs)} such as KL-ONE, Classic,
  Back, Loom, etc.  and the types normally encountered in programming
  languages.  The similarities include (i) grouping elements of a value
  space, (ii) having a term-like compositional nature, (iii) being
  related by subtype/subsumption relationship, and (iv) parallels
  between the notions of type checking, type coercion and type inference
  on the one hand, and corresponding notions of integrity checking,
  concept instantiation and individual recognition.  The major
  differences include dynamic rather than static type-checking for
  individuals, and records with set-valued attributes (and hence types
  involving cardinality constraints, attribute hierarchies, etc.).  We
  also speculate on the possible applications of the parallel between
  DLs and programming language type systems.

sigmod93.dvi.Z ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 A. Borgida, R. Brachman, ``Loading data into description reasoners'',
{\em ACM SIGMOD Conf. on Data Management}, May 1993, Washington, DC,
pp. 217 -- 226.

  \begin{abstract} Knowledge-base management systems (KBMS) based on
  description logics are being used in a variety of situations where
  access is needed to large amounts of data stored in existing
  relational databases.  We present the architecture and algorithms of a
  system that converts most of the inferences made by the KBMS into a
  collection of SQL queries, thereby relying on the optimization
  facilities of existing DBMS to gain efficiency, while maintaining an
  object-centered view of the world with a substantive semantics and
  significantly different reasoning facilities than those provided by
  Relational DBMS and their deductive extensions.  We address a number
  of optimization issues that arise in the translation process due to
  the fact that SQL queries with different syntax (but identical
  semantics) are not treated uniformly by current database management
  systems.  \end{abstract}

types-w-exceptions.tex.Z ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 A. Borgida, ``Type systems for querying class hierarchies with
non-strict inheritance'', {\it Proc. ACM PODS Conference$^{\bf *}$},
Philadelphia, PA, March 1989, pp.394--400.

  Type checking at query compilation time is important for both
  detecting programmer errors and reducing the running time of queries.
  We have argued elsewhere @cite[sigmod88] that entity-based data
  management systems which support class hierarchies, such as semantic
  data models and object-oriented dbms, should not be confined to have
  STRICT INHERITANCE -- i.e., they should permit contradictions between
  class specifications, albeit in an explicit and controlled way.  In
  this paper we present a type system for queries manipulating objects
  in such classes. We provide sound and complete axiomatizations of the
  predications "S is a subtype of T" and "expression e has type T".  The
  absence of strict inheritance has normally been felt to preclude
  effective type checking. We show that the problem is co-NP-hard when
  disjoint types are admitted in the schema, but present a low-order
  polynomial-time algorithm that determines the absence of type errors
  in a query when the database has only entities.