Introduction

For knowledge base systems to be e ective for largescale applications, it is essential that they support e cient retrieval and update operations on large, shared knowledge bases. Database system research has focussed on issues of performance and concurrent access to large data sets and we wish to exploit the resulting technologies for the storage and management of knowledge bases.

Past research in this area has tended to use relational systems for the persistent storage of knowledge bases. While this strategy does meet the requirements of controlled data sharing, the large semantic gap between the knowledge representation structures and the relational structures makes it more di cult to utilise data semantics in query optimisation. We therefore adopt a two-level mapping. The rst level maps a frame-based knowledge representation model, FRM Rei 89;RL 94], to an object data model, COCOON SLR+92], which retains much of the data semantics. The second level then maps COCOON to a relational system which is used as a simple storage system with query and update strategies controlled primarily at the object system level.

Here, we present an overview of how this approach is utilised in the (hybrid) knowledge base system HYWIBAS RRS+93] (the hybrid aspects are not elaborated here). Section 2 introduces the three level architecture and discusses its merits. The mappings from FRM to COCOON and from COCOON to a relational system are discussed in Sections 3 and 4, respectively. Some remarks on the current status of HYWIBAS and future research plans are given in Section 5.

Three Level Architecture

Knowledge base systems research has tended to concentrate on issues of semantic expressiveness and inference mechanisms. For knowledge base systems to be used for large-scale applications, issues of e cient update and retrieval operations on large, shared knowledge bases must be addressed. Database systems research has focussed on these very issues in dealing with e cient, concurrent access to large data sets. The question then becomes one of how best to exploit database technologies in knowledge base systems.

Relational database technologies now have established and well-understood mechanisms to support e cient access to large sets of value tuples with techniques for concurrency control and recovery. The problem of mapping a knowledge model directly to a relational storage structure is the large semantic gap due to the lack of semantic expressiveness of the relational data model. As described in RS 89], this can in part be overcome by mapping a knowledge model to a nested relational model which can represent complex structures directly. However, the nested relational model does not support notions of type inheritance and concept hierarchies which are fundamental to knowledge models such as FRM.

Object data models have been developed to support notions of semantic data modelling and thereby increase the semantic expressiveness of the data model. They have constructs to represent both complex structures and relationships between structures { including those that arise in classi cation structures, often known as isa hierarchies. In addition, a number of object data models have been proposed that specify operations over collections of objects in terms of an object algebra. By mapping the frame knowledge model to an object data model rather than to a relational data model, the semantic gap is reduced. However, object-oriented database management systems are not yet as well established as relational database management systems in terms of e cient processing of set-oriented retrieval and update operations and supported transaction mechanisms. For this reason, we choose to map our object data model to a relational storage system. This mapping is speci cally tailored to support the retrieval and update patterns initiated by the frame model. As a result, we have a three level architecture as indicated in Figure 1. The knowledge model FRM is mapped to the object data model COCOON which in turn is mapped to a relational system. At present, we use the relational data base management system INGRES, but the mapping can easily be altered for other relational systems.

3 From Frames to Objects A discussion of the di erences between the knowledge representation and semantic data modelling approaches is given in Bor 91]. One of the main differences often quoted is that database models tend to be prescriptive rather than descriptive. Thus the underlying assumption is that the database provides a complete, current and consistent description of the application domain; any attempt to input data which is not consistent with the database model will be rejected. Knowledge models tend to be descriptive and it is quite acceptable that the model may have to be revised according to new information received into the system. This is most clearly visible in a knowledge-based system with some learning capabilities (see e.g. Mor 91]).

A further general distinction between data models and knowledge representation languages is the fact that data models have a much clearer separation between intensional and extensional information. Intensional information is given by a database schema which is relatively stable and thus plays a predominant role in determining e cient storage, retrieval and update strategies for operations on extensional data.

Ideally, for the support of knowledge base systems, we wish to have the latter property of database models (i.e. e ciency) but not necessarily the former (i.e. being prescriptive). In this respect the COCOON object data model is a good candidate for the support of the frame model FRM.

In this paper we consider only a subset of FRM which corresponds to the common frame constructs: slots, slot entries, and cardinality restrictions. For example, Skilled-Person _ = (and Person (all has-skills Skill) (exist has-skills Rare-Skill) (atleast has-skills 3)) de nes a frame class Skilled-Person as a subclass of Person with the slot has-skills that represents the relationship has-skills to the class Skill. The slot requires at least 3 values at an associated class instance; one of those entries must be an instance of the class Rare-Skill.

COCOON has a strong in uence from both semantic data models and knowledge representation languages (especially KL-ONE BS 85]) in terms of semantic expressiveness. It supports not only complex object structures but also rich classi cation structures and high-level operations over collections of objects. As a result, the semantic expressiveness of COCOON is at a similar level to that of FRM with the main di erence between the two models stemming from the fact that FRM supports more specialised inference mechanisms. In some sense CO-COON may be considered as lying somewhere between the prescriptive and descriptive paradigms. A COCOON class represents a semantic grouping of objects and may have an associated predicate condition. For example de type de nitions but all of them to COCOON class de nitions. As a consequence, frames of FRM are mapped to some combination of types and classes in COCOON. To increase the possibilities for compiletime optimisation, we designed the mapping such that as much information as possible is provided on the type level.

Figure 2 shows an example of mapping an FRM concept class description to COCOON types and classes. In a rst step the object type comp delivery is derived from the FRM class Comp Delivery such that for every all construct (i.e. for every slot) we have a function with the same name. In case of a slot with a maximal cardinality of 1 the function is single-valued, otherwise set-valued. In a second step the COCOON class Comp Delivery of type comp delivery is generated from the frame class Comp Delivery. With the type reference we ensure that the class will contain only objects with the right functions being applicable. With the associated class predicate we cover the remaining features of the FRM concept class description. As a result, the COCOON class de nes the same necessary and su cient conditions on class membership as the frame class does. Note that the three object-valued functions in the type de nition comp delivery are all of type object. This is because providing more specialised function ranges (e.g. supplier :

set-of Company) would not lead to a simpler class predicate. As this would not reduce the amount of dynamic type checking necessary we decided to keep the mapping to the type level simple and to map always to object-valued functions of type object. For details see LNR+94].

The establishment of the mapping from frames to types and classes has also proved useful in providing an insight into the similarities and di erences in the fundamental concepts of terminological models such as FRM and object data models.

In knowledge base systems a query for objects with certain properties is usually established as a class description. The result of the query is all the objects subsumed by that class so that in this case query evaluation amounts to inferencing. To support such queries on our COCOON-based FRM we have speci ed a second mapping that transforms a frame class description to be interpreted as a query into an equivalent expression of the COCOON object algebra (cf. example in Figure 3). This algebra expression is then evaluated on the COCOON object base derived from the original frame knowledge base. At that point query optimisation techniques, which are highly developed in the database area, can be employed. We hope that this will lead us to a query processing that is much more e cient than evaluating a query frame by the inference mechanism of FRM.

From Objects to Relations

In mapping an object data model onto a relational system, there are many choices to make concerning both the representation of objects and also of classes. For example, all the properties of an object may be stored together in a single relation or split over several relations. In the former case, there are problems of how to represent multi-valued properties. In the latter case, several join operations may be required to reconstruct an object.

With the representation of classes, the choices arise because an object may belong to many classes and the prime decision is whether to store an object only with its most speci c class { or to store it in all classes { or to have some form of compromise between the two extremes. Further, some COCOON classes have associated predicates which specify necessary and su cient conditions for membership of that class. In such a case, there is no need to store In our mapping of COCOON onto a relational storage system, we employ extensive replication to minimise retrieval costs. For example, all classes are represented explicitly even those which could be speci ed in terms of a query expression (view) over other classes. Since an object may belong to many classes, an object representation may be replicated in several relations. The penalty associated with such an approach of massive replication is the cost of update operations; a single update operation on a speci c object may require updates on a large number of relations involved in the representation of that object.

The problem then becomes one of how to speed up the time for updates. This is achieved by implementing the update operation as a number of simpler update operations which can be executed in parallel. The exploitation of intra-transaction parallelism together with multi-level transactions is a key technique towards such improved performance WS 92].

We are currently evaluating the above approach to see under what conditions the overheads of parallelisation are compensated by the corresponding speedup of the operations. In the future, we shall investigate dynamic methods of mapping the object data model COCOON to relational systems such that good performance is attained under various retrieval and update patterns (which nally stem from speci c retrieval and update operations on the knowledge base system).

Conclusions

In the HYWIBAS project, we are using database technologies to support large, shared knowledge bases. We employ a three level architecture corresponding to three semantic levels of frames, objects * For reasons of readability we have slightly simplied the algebra expression: The select statements should apply to classes of objects for which the functions referred to are really de ned, rather than operating on the most general class Objects. This requires an additional meta-schema query, which we have omitted. and relations. The introduction of the object level is bene cial in reducing the semantic gap between the frame level and the relational level and enabling the utilisation of structural semantic information for query and update processing. The mapping from the object level to the relational level allows the use of well-established, e cient mechanisms for data storage, data access, data sharing and recovery under failure.

At present, we have implemented mappings for structural information from the frame model, FRM, to the object model, COCOON and from COCOON to the multiprocessor relational database system, INGRES. We also have a mapping from frame query classes to COCOON algebra. Moreover, there are some early results on the parallelisation of update operations over a COCOON database represented in INGRES Rys 94]. Currently, we are working on the mapping of the remaining operational components and on the mapping of frame class instances to objects.