A Class Library Implementation of a Principled Open Architecture Knowledge Representation Server with Plug-in Data Types

1 Introduction

One of the basic technologies that may be factored out of virtually all artificial intelligence systems is some form of knowledge representation service.. Theoretical foundations have been developed for such technologies in recent years [Brachman and Levesque, 1984; Ait-Kaci, 1986; Nebel, 1990]. These foundations make it possible to develop general-purpose knowledge representation services that are well-principled, space and time efficient, and embeddable as sub-systems in a wide variety of applications.

Since complexity analyses shows that knowledge representation systems with even minimal features are able to represent intractable problems [Brachman and Levesque, 1984; Nebel, 1988; Schmidt-SchauB, 1989], it has been suggested that the representation and deduction capabilities of knowledge representation services should be limited [Levesque and Brachman, 1987]. The reasons for and against this have been surveyed by Doyle and Patil [1991] who conclude that, while there are sound arguments for such limitations, the capabilities of the resultant systems will often fail to satisfy reasonable application requirements. One impact of this is that system designers may add functionality that provides the missing capabilities in ways that are less principled than those of a general server. A second is that problems may have to be represented in unnatural ways that are conducive to poor performance. A third is that the effect of the limitations on deductive capabilities may not be apparent to users, leading to errors.

The merits of algebraic, type-theoretic semantics for knowledge representation are that they provide formal models and complexity analyses that relate closely to the features and issues of existing knowledge representation systems. For example, they provide simple accounts of common constraints, such as cardinality, extensional inclusion and numeric ranges. Clearly, these are questions of naturality rather than logical power, since accounts of set theory and arithmetic can be developed in first order logic, and algebraic feature constraint logics may be translated into first-order formulae [Smolka, 1992]. However, natural models giving minimal formulations of representational requirements are valuable in both the software engineering of knowledge representation servers, and the effective presentation of the services offered to those using them.

The model for term subsumption knowledge representation used in the development of KRS is that the computational units are: for the TBox, concepts, identified with collections of constraints indexed by roles; and for the ABox, individuals represented as unique identifiers, each of which has associated conceptual variable whose value in any particular state of the knowledge base is a concept. This has the normal semantics for KL-ONE systems that concepts are precisely a composition of constraints­ changing the constraints changes the identity of the concept, whereas individuals are precisely identities of objects­ changing the associated constraints changes the state of the individual, not its identity. In Zalta's [1988] terminology, abstract objects (concepts) encode properties whereas concrete objects (individuals) exemplify them.

Thus, the computational structure of both theory and implementation is modeled as an algebra of constraints, but the nature of the constraints is left undefined. Any data type can be used in representation and deduction provided it can be modeled as a constraint algebra. In KRS the data types and their operations are implemented as separate classes, and 'plugging in' new data types involves adding a new class with four associated operations (composition, subsumption test, input and output). The kernel deduction systems for constraint propagation, for rule, inverse role and co reference application, and for . model checking search, remain unchanged.

3 Constraint Algebras

The semantics of constraints may be developed directly from informal requirements to a formal model. The key notions are that the composition of two constraints should be a well-defined constraint (binary function), that it makes no difference to compose a constraint with itself (idempotency), that grouping of multiple constraints in resolving them to binary compositions makes no difference (associativity), and that the order of application of constraints makes no difference (commutativity). Without these requirements, one would have the semantics of general operators rather than constraints. Together they imply that composition generates a semi-lattice in which it is the join operation. There is a natural order relation of subsumption of constraints, defined as one constraint subsumes another if their composition equals the second constraint. The semilattice can then be extended to be a full lattice by defining a dual, order-inverting meet operation (which, as a side effect, adds the lattice adsorption identities [Gratzer, 1971]). A unique lowest element, or zero, can be defined in the lattice corresponding to the composition of incompatible constraints. A unique greatest element, or unit, can be defined corresponding to a universally applicable constraint.

Thus, the lattice structures common to all knowledge representation systems arise out of the basic primitive of a constraint. Any mathematical or logical formulation is a representation of the properties of this primitive, and any representation schema with reasonably normal semantics will have a constraint algebra interpretation.

Formally, a constraint algebra is defined as a pair of binary operations upon a set, L, n (composition) and U (minimum common generalization), unique greatest and least elements (universal and incoherent constraints), defined ideal sub-lattices (types), defined order and incompatibility relations, ~ (subsumption) and - (disjoint), and defined atomic elements (values), satisfying the following:

The semantic notions of knowledge representation can now be modeled formally by taking any bounded lattice as a constraint algebra in which the atoms are values, other elements are constraints upon those values, ideals are types of values, the order relation is one of constraint subsumption, the incompatibility relation as one of disjoint constraints, the unit element as a universal constraint and the zero element as an incoherent constraint. The next section defines types for record structures as constraint algebras giving a complete account of the semantics of term subsumption knowledge representation schema.

4 Constraint Algebras for the T-box and A-box

To develop the semantics for concepts in the T-box and worlds of individuals in the A-box, take any constraint algebra, L, and consider an indefinite product of such algebras, X= L x L x L ... , indexed by a set of projections, n, such that 1t E n, X E X ::::) 1tX E L. The arity of an element of X is defined to be the number of non-1 projections. There is a natural constraint lattice formed by X under the definitions:

That is, the lattice operations operate on a component by component basis, and any projection becoming zero implies that the product is itself zero. The order relation of (LS) may also be computed on a component by component basis:

The base algebra L may be treated as a sublattice of X by defining a specific x E nand the mapping, Jl: A~X:

(XI) through (X6) construct one constraint lattice as the indefinite product of another such that the original lattice may be mapped to a sublattice of the product. This construction may be iterated indefmitely to construct a well­ founded sequence of constraint lattices of increasing order corresponding to the well-founded construction of sets in classical set theory. The order of an element of one of the lattices is defined to be the position in this sequence of its initial definition. The complexity of an element is defined recursively as its arity plus the arities of each of its non-unit projections-this corresponds to the number of non-unit modes in its expansion or graph.

4.1 T -box Representation

If the projections are defined to be roles and the lattice elements concepts, this construction is adequate to account for representation and deduction in the T -box of term subsumption systems. Concept subsumption is the order relation of (XS) and individual classification is the same relation if the A-Box is taken simply to associate an individual with a concept asserted of it.

Some issues relating to the complexity of subsumption and classification are now apparent. The subsumption of (XS) for elements of a given order in a system that stores only non-unit projections and caches precomputed lower order subsumptions involves only n cache accesses where n is the minimum of the arities of the elements being compared. This model of subsumption computation gives an upper bound that makes it appear highly tractable. However, there are a number of reasons why this result is misleading.

First, the subsumption relation in the base lattice will generally not be cached because the space complexity will be high even if the time complexity is not, and the time complexity could also be high in an open architecture system in which arbitrary lattices can be plugged in (including the product lattices just defined). In practice, the base lattices currently used in systems such as CLASSIC are such that subsumption computation is tractable as will be shown in the next section.

Second, the composition of concepts may generate large numbers of additional (anonymous) concepts such that the caching assumed may itself become intractable in space and time. Nebel [1990] has given a simple construction of a series of related concepts where the number of anonymous concepts grows exponentially with the number of originally defined concepts. In KRS the number of anonymous concepts generated by a given concept definition is reported as an auxiliary complexity measure.

Third, it is unrealistic to implement assertions about individuals in a caching scheme. Individual classification may involve a complete expansion of the concepts testing each node at the base lattice level. The number of tests is then the complexity defined above which can also grow exponentially with the number of concepts defined.

Fourth, the subsumption relation defined in (XS) is intensional. It does not take into account the constraints that may be propagated in the A-box to ensure that the concepts associated with individuals cannot become incoherent. Extensional subsumption taking into account such constraint propagation is consistent with, but a stronger partial order, than intensional subsumption. This is how intractability may be shown in CLASSIC by representing satisfiability of a restricted CNF formula [Lenzerini and Schaerf, 1991].

4.2 A-box Representation

If the projections are defined to be individuals and the lattice elements worlds, the construction, (XI) through (XS), is adequate to account for representation and some aspects of deduction in the A-box of term subsumption systems. World subsumption through the order relation of (XS) corresponds to monotonic reasoning, that the subsumed world can be reached from the other by a series of assertions about individuals. However, there are additional modes of reasoning in the A-box that make its analysis more complex.

First, CLASSIC-like systems implement rules as pairs of concepts such that if an individual is classified as falling under the first then the second is asserted of it.

Second, individuals may participate in base lattice constructions, for example through extension and cardinality constraints on sets of individuals, and hence assertions of a concept as applying to one individual may imply that other concepts apply to other individuals. In particular, cardinality constraints may imply the existence of (Skolem) individuals not previously created.

Third, there may be assertions about individuals that, while they do not lead to incoherence directly, do so indirectly through the previous two mechanisms. Taking into account these implicit constraints may involve a search over possible worlds that may grow exponentially with the number of individuals involved.

The first two modes of reasoning do not in themselves lead to intractability but, taken together with the third, they allow intractable problems to be represented in the A-box that go beyond those already discussed for the T -box.

5 Base Algebras for CLASSIC-Like Systems

Specific base lattices for CLASSIC-like systems may be constructed from a four element constraint algebra as shown on the left of Figure 1 in which @ is the zero element, (!) the unit element, and @ and @ are complementary elements distinct from them. The semantics of this lattice is that of role constraints:

• Indeterminate Q)

a role possibly existing.

Overdeterminate @ a role existing but unfillable.

• Applicable @ a role definitely existing.
• Nonapplicable @ a role definitely not existing.

This lattice supports no data types in itself but it can be extended to support any arbitrary combination of data types by inserting their constraint lattices between @ and @ such that their unit elements represents the relevant types and their zero elements are mapped to @. Figure 1 center shows two mutually incompatible constraint lattices inserted in this way. Figure 1 right shows two compatible lattices inserted such that one is a sublattice of the other, corresponding to type coercion.

In CLASSIC-like systems there is a distinguished data type based on sets of individuals. The algebra of subsets of a set with set union as meet and set intersection as join is a constraint lattice. However, its semantics do not support the distinction between FILLS and ONE-OF constraints, the CLOSE constraint, or cardinality constraints. The following constructions do so by combining the constraints of the algebra of subsets with those of the dual lattice.

Consider an arbitrary set, S, its powerset, Ps, and the Cartesian product on its powerset, P = Ps x Ps. There is a natural constraint lattice formed by P under the definitions:

The semantics of this lattice are those of constraints upon the subsets of S with the ftrst projection of the product being a lower bound corresponding to FILL, the second projection being an upper bound corresponding to ONE­ OF, unsatisftable constraints in which the lower bound is not contained in the upper bound mapping to zero, and the lattice operations corresponding to complementary pairs of intersections and unions of lower bounds and upper bounds. The atoms of this lattice are elements in which the lower and upper bounds coincide. They provide the semantics for CLOSE in corresponding to a set constrained to consist precisely of its specified members.

The SAME-AS constraint corresponds to an equality assertion between nodes of a concept structure. It is simply implemented in the A-box by indirect addressing. The semantics of NOT in KRS are represented by having a complement as the second projection, that is S-u rather than u. Complements behave well under intersection and union with sets and other complements, generating either sets or complements, and causing no problems in implementation. In particular, this allows a very simple implementation of disjoint primitives as shown later.

Cardinality constraints may be added to this structure to give an extended constraint lattice based on the product C = Ps x Ps x I x I, where I is the set of non-negative integers. There is a natural constraint lattice formed by C under the definitions:

The semantics of this lattice are those of constraints upon the subsets of S as before with the additional constraints on cardinality corresponding to AT -LEAST and AT -MOST. Figure 2 shows an example of this lattice for two elements.

PRIMITIVE and DISJOINT -PRIMITIVE constraints are implemented through a hidden role filled by elements of a P lattice based on the set of concepts rather than that of individuals. A concept defined to be primitive stores its own name as FILLS in this role. A concept defined to be disjoint to another stores the other's name as NOT in this role. This results in the proper semantics for primitive concepts.

Thus, the capabilities of CLASSIC are implemented in KRS through a single data type which is a set with upper and lower bounds and cardinality constraints. It is a an unusual data type compared with those of conventional programming languages, but it is readily implemented and optimized for fast and memory-efficient operation.

A principled implementation of some applications of the TEST constraint used to extend CLASSIC is made available in KRS by direct support of data types such as integers, time intervals, strings, and so on, through the lattice constructions of Figure 1. This allows general abstract data types to be integrated in CLASSIC-like systems. What it does not support is operations upon them that do not correspond to the lattice joins and meets, and the use of side-effects to communicate with other subsystems.

6 Architecture of KRS

The KRS architecture is shown in Figure 3. It supports the normal features of KL-ONE-like systems in allowing concepts to be defined, and assertions to be made about individuals in terms of these concepts. What is essentially type propagation inference can then be used to deduce the consequences of the assertions through reference to the definitions. KRS also supports the rule schema of CLASSIC, extended to handle rules with exceptions, such that an individual recognized as satisfying one concept has another automatically asserted of it. This integrates production rule and frame-based reasoning. It also supports model checking [Halpern and Vardi, 1991] or "puzzle mode" reasoning in which, if necessary, after propagation of type and rule constraints a search of possible worlds is carried out to determine whether additional conclusions can be drawn because not to do so would lead to absurdity.

KRS supports a wide variety of data types through a data type manager accessing separate modules through a uniform interface such that constraints supported, such as interval bounds on numbers, enter fully into concept definitions, individual assertions and deductive inference. Complexity measures are derived from the concept definitions that estimate the probable costs of problem solving in a particular domain.

The algebraic model of knowledge representation leads directly to an open architecture implementation as a class library as illustrated in Figure 4. The knowledge base class has two main instance variables, one holding individual records and the other holding concept records. The base knowledge base class implements the type lattice on the left of Figure 1, having codes for indeterminate, applicable, non­ applicable and overdeterminate values and constraints. It also supports other constraints by reference codes containing a type code and pointer. The type code is used to access a list of data type support objects which is initially empty. For each data type implemented an object is added to the list that supports it by providing storage for values and constraints of that subtype, and methods to compute and support input/output with such values and constraints.

Figure 4 at the bottom left also illustrates another important feature of the class library construction. Type subsumption computation for record structures is simply expressed recursively. However, to attain the known complexity lower bound requires that already computed subsumption relations be cached to avoid duplicate computation. This caching is implemented in a sub-class in KRS, allowing the simple recursive computation to be called as an inherited method during debugging as a check on the correctness of the caching algorithm.

The utility of the class library construction are also apparent in the implementation of model checking reasoning in KRS. This is the mode that exhibits intractability so that it is appropriate to implement it as a separate service. It involves a search of possible worlds once other forms of inference have reached a fixed point. The form of reasoning is that certain further constraints upon existing individuals that appear possible may not be so because their consequences are inconsistent. If one searches all possible worlds resulting from the assertion of combinations of such constraints then constraints which apply in all consistent worlds are necessary and can be deduced. Puzzles are usually designed so that there is only one world that is consistent, but real problems usually involve multiple possible worlds as consistent extensions. In KRS this mode of reasoning is implemented by making the individual records instance variable shown at the top of Figure 4 a pointer to a tree structure of possible worlds. The rest of the reasoning and type system remains unchanged.

6 Conclusions

Now that the theoretical foundations of knowledge representation servers have been developed in terms of abstract data types, and the demand for embeddable implementations is growing, it is attractive to investigate the possibility of class libraries supporting efficient, extensible implementations. This paper has specified the requirements, detailed the relevant theory, and shown how this has led to a class library implementation of a fast, principled, open architecture knowledge representation server.

Acknowledgements

This work was funded in part by the Natural Sciences and Engineering Research Council of Canada.

representation server and visual language. C 0 C S' 91 : Proceedings of Conference on Organizational Computing Systems. pp.80-94. ACM Press. 1991.

[Gratzer, 1971] G. Grlitzer. Lattice Theory. Freeman, 1971.

[Halpern and Vardi, 1991] J.Y. Halpern and M.Y. Vardi. Model checking vs. theorem proving: a manifesto. Artificial Intelligence and the mathematical Theory of Computation. pp.151-176. Academic Press. 1991.

[Lenzerini and Schaerf, 1991] M. Lenzerini and A. Schaerf. Concept languages as query languages. AAAI' 91 : Proceedings of the Ninth National Conference on Artificial Intelligence. pp.471-476. AAAI Press, 1991.

[Levesque and Brachman, 1987] H.J. Levesque and R.J. Brachman. Expressiveness and tractability in knowledge representation and reasoning. Computational Intelligence 3 78-93, 1987.

[Nebel, 1988] B. Nebel. Computational complexity of terminological reasoning in BACK. Artificial Intelligence 34 371-383, 1988.

[Nebel, 1990] B. Nebel. Reasoning and Revision in Hybrid Representation Systems. Berlin: Springer, 1990.

[Schmidt-SchauB, 1989] M. Schmidt-SchauB. Subsumption in KL-ONE is undecidable. KR' 89: First International Conference on Principles of Knowledge Representation and Reasoning. pp.421-431. Morgan Kauffman. 1989.

[Smolka, 1992] G. Smolka. Feature-constraint logics for unification grammars. Journal Logic Programming 12(12) 51-87, 1992.

[Vilain, 1991] M. Vilain. Deduction as parsing: tractable classification in the KL-ONE framework. AAA/' 91 : Proceedings of the Ninth National Conference on Artificial Intelligence. pp.464-470. AAAI Press, 1991.

[Zalta, 1988] E.N. Zalta. Intensional Logic and the Metaphysics of Intentionality. MIT Press, 1988.