Frames, Objects and Relations: Three Semantic Levels for Knowledge Base Systems M. C. Norrie1, U. Reimer2, P. Lippuner2, M. Rys1, H.-J. Schek1 1 Dept. of Computer Science, Swiss Federal Institute of Technology (ETH), CH-8092 Zurich, Switzerland fnorrie, rys, schekg@inf.ethz.ch 2 Swiss Life, Informatik-Forschungsgruppe, CH-8022 Zurich, Switzerland freimer, lippunerg@swssai.uu.ch Abstract elaborated here). Section 2 introduces the three level architecture and discusses its merits. The mappings We propose an architecture for large-scale from FRM to COCOON and from COCOON to a knowledge base systems based on database relational system are discussed in Sections 3 and 4, technologies and the three levels of seman- respectively. Some remarks on the current status of tic construct - frames, objects and rela- HYWIBAS and future research plans are given in tions. The intermediate object level retains Section 5. the structural semantics of the frame level and is therefore bene cial in bridging the semantic gap between the frame and re- 2 Three Level Architecture lational levels and enabling the use of se- Knowledge base systems research has tended to con- mantic information in query optimisation. centrate on issues of semantic expressiveness and in- Speci cally, we outline how this approach ference mechanisms. For knowledge base systems to has been adopted in the hybrid knowledge be used for large-scale applications, issues of ecient base system, HYWIBAS. update and retrieval operations on large, shared knowledge bases must be addressed. Database sys- tems research has focussed on these very issues in 1 Introduction dealing with ecient, concurrent access to large data For knowledge base systems to be e ective for large- sets. The question then becomes one of how best to scale applications, it is essential that they support exploit database technologies in knowledge base sys- ecient retrieval and update operations on large, tems. shared knowledge bases. Database system research Relational database technologies now have estab- has focussed on issues of performance and concur- lished and well-understood mechanisms to support rent access to large data sets and we wish to exploit ecient access to large sets of value tuples with tech- the resulting technologies for the storage and man- niques for concurrency control and recovery. The agement of knowledge bases. problem of mapping a knowledge model directly to Past research in this area has tended to use rela- a relational storage structure is the large semantic tional systems for the persistent storage of knowl- gap due to the lack of semantic expressiveness of edge bases. While this strategy does meet the re- the relational data model. As described in [RS 89], quirements of controlled data sharing, the large se- this can in part be overcome by mapping a knowl- mantic gap between the knowledge representation edge model to a nested relational model which can structures and the relational structures makes it represent complex structures directly. However, the more dicult to utilise data semantics in query opti- nested relational model does not support notions of misation. We therefore adopt a two-level mapping. type inheritance and concept hierarchies which are The rst level maps a frame-based knowledge rep- fundamental to knowledge models such as FRM. resentation model, FRM [Rei 89; RL 94], to an ob- Object data models have been developed to sup- ject data model, COCOON [SLR+92], which retains port notions of semantic data modelling and thereby much of the data semantics. The second level then increase the semantic expressiveness of the data maps COCOON to a relational system which is used model. They have constructs to represent both com- as a simple storage system with query and update plex structures and relationships between structures strategies controlled primarily at the object system { including those that arise in classi cation struc- level. tures, often known as isa hierarchies. In addition, a Here, we present an overview of how this approach number of object data models have been proposed is utilised in the (hybrid) knowledge base system that specify operations over collections of objects in HYWIBAS [RRS+93] (the hybrid aspects are not terms of an object algebra. By mapping the frame knowledge model to an object data model rather * The work presented here was supported by the than to a relational data model, the semantic gap Swiss Priority Programme in Computer Science under is reduced. However, object-oriented database man- Grant No. 5003-34347. agement systems are not yet as well established as relational database management systems in terms of and update strategies for operations on extensional ecient processing of set-oriented retrieval and up- data. date operations and supported transaction mecha- Ideally, for the support of knowledge base sys- nisms. For this reason, we choose to map our object tems, we wish to have the latter property of data- data model to a relational storage system. This map- base models (i.e. eciency) but not necessarily the ping is speci cally tailored to support the retrieval former (i.e. being prescriptive). In this respect the and update patterns initiated by the frame model. COCOON object data model is a good candidate for As a result, we have a three level architecture as the support of the frame model FRM. indicated in Figure 1. In this paper we consider only a subset of FRM which corresponds to the common frame constructs: slots, slot entries, and cardinality restrictions. For FRM Knowledge Base System example, Skilled-Person =_ (and Person frames (all has-skills Skill) (exist has-skills Rare-Skill) COCOON Object Data Management (atleast has-skills 3)) System de nes a frame class Skilled-Person as a subclass types classes 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 INGRES Relational instance; one of those entries must be an instance of Database the class Rare-Skill. System COCOON has a strong in uence from both se- mantic data models and knowledge representation languages (especially KL-ONE [BS 85]) in terms of semantic expressiveness. It supports not only com- plex object structures but also rich classi cation relations structures and high-level operations over collections of objects. As a result, the semantic expressiveness Figure 1: Three Level Architecture of COCOON is at a similar level to that of FRM with the main di erence between the two models stem- The knowledge model FRM is mapped to the ob- ming from the fact that FRM supports more spe- ject data model COCOON which in turn is mapped cialised inference mechanisms. In some sense CO- to a relational system. At present, we use the rela- COON may be considered as lying somewhere be- tional data base management system INGRES, but tween the prescriptive and descriptive paradigms. A the mapping can easily be altered for other relational COCOON class represents a semantic grouping of systems. objects and may have an associated predicate con- dition. For example 3 From Frames to Objects de ne class Y oungsters : person some Persons where age < 30; A discussion of the di erences between the knowl- de nes a class Youngsters which contains objects of edge representation and semantic data modelling ap- type person and is a subclass of Persons; further proaches is given in [Bor 91]. One of the main dif- there is an associated predicate condition that spec- ferences often quoted is that database models tend i es that its members should be less than 30 years to be prescriptive rather than descriptive. Thus the old. The object type person declares what functions underlying assumption is that the database provides are applicable to an object of that type and may look a complete, current and consistent description of like the following the application domain; any attempt to input data de ne type person = age : integer, which is not consistent with the database model will name : string, has-skills : set-of skills; be rejected. Knowledge models tend to be descrip- tive and it is quite acceptable that the model may A formal mapping from frame structures to ob- have to be revised according to new information re- ject structures and from query operations on frame ceived into the system. This is most clearly visible knowledge bases to object bases has been de ned in a knowledge-based system with some learning ca- and implemented. While concept class descriptions pabilities (see e.g. [Mor 91]). in FRM are based on a single representation struc- A further general distinction between data models ture { the frame, COCOON has two basic represen- and knowledge representation languages is the fact tation structures { the type and the class. Types that data models have a much clearer separation be- describe what properties and relationships to other tween intensional and extensional information. In- objects an object can have whereas, as stated above, tensional information is given by a database schema classes deal with semantic groupings of objects. which is relatively stable and thus plays a predom- Only a small number of the frame constructs for con- inant role in determining ecient storage, retrieval cept class descriptions can be mapped to COCOON FRM concept class description: Comp Delivery =_ (and (all supplier Company) (exist supplier Computer Company) (all recipient Company Person) (atmost recipient 1) (all ispart Workstation) (all price [0; 100]) (atmost price 1)) Corresponding COCOON type de nition: de ne type comp delivery = supplier : set-of object; recipient : object; ispart : set-of object; price : integer; Corresponding COCOON class de nition: de ne class Comp Delivery : comp delivery where supplier  Company and ;=6 (supplier \ Computer Company) and recipient  (Company [ Person) and ispart  Workstation and ; = select [(i < 0) or (i > 100)] (i : price); Figure 2: Example of Mapping an FRM Concept Class Description to COCOON Types and Classes type de nitions but all of them to COCOON class In knowledge base systems a query for objects de nitions. As a consequence, frames of FRM are with certain properties is usually established as a mapped to some combination of types and classes in class description. The result of the query is all the COCOON. To increase the possibilities for compile- objects subsumed by that class so that in this case time optimisation, we designed the mapping such query evaluation amounts to inferencing. To sup- that as much information as possible is provided on port such queries on our COCOON-based FRM we the type level. have speci ed a second mapping that transforms a Figure 2 shows an example of mapping an FRM frame class description to be interpreted as a query concept class description to COCOON types and into an equivalent expression of the COCOON ob- classes. In a rst step the object type comp delivery ject algebra (cf. example in Figure 3). This algebra is derived from the FRM class Comp Delivery such expression is then evaluated on the COCOON object that for every all construct (i.e. for every slot) we base derived from the original frame knowledge base. have a function with the same name. In case of a At that point query optimisation techniques, which slot with a maximal cardinality of 1 the function are highly developed in the database area, can be is single-valued, otherwise set-valued. In a second employed. We hope that this will lead us to a query step the COCOON class Comp Delivery of type processing that is much more ecient than evalu- comp delivery is generated from the frame class ating a query frame by the inference mechanism of Comp Delivery. With the type reference we en- FRM. sure that the class will contain only objects with the right functions being applicable. With the as- sociated class predicate we cover the remaining fea- 4 From Objects to Relations tures of the FRM concept class description. As a re- In mapping an object data model onto a relational sult, the COCOON class de nes the same necessary system, there are many choices to make concerning and sucient conditions on class membership as the both the representation of objects and also of classes. frame class does. Note that the three object-valued For example, all the properties of an object may be functions in the type de nition comp delivery are stored together in a single relation or split over sev- all of type object. This is because providing eral relations. In the former case, there are problems more specialised function ranges (e.g. supplier : of how to represent multi-valued properties. In the set-of Company) would not lead to a simpler class latter case, several join operations may be required predicate. As this would not reduce the amount of to reconstruct an object. dynamic type checking necessary we decided to keep With the representation of classes, the choices the mapping to the type level simple and to map al- arise because an object may belong to many classes ways to object-valued functions of type object. For and the prime decision is whether to store an object details see [LNR+94]. only with its most speci c class { or to store it in The establishment of the mapping from frames to all classes { or to have some form of compromise be- types and classes has also proved useful in providing tween the two extremes. Further, some COCOON an insight into the similarities and di erences in the classes have associated predicates which specify nec- fundamental concepts of terminological models such essary and sucient conditions for membership of as FRM and object data models. that class. In such a case, there is no need to store Query Frame: (and (all supplier Company) (all recipient Company) (exist recipient Insurance Company) (all product (and W orkstation (all has-cpu Sparc) (atleast has-cpu 2)))) Corresponding Algebra Expression: select[supplier(o1)  Company](o1 : Objects)\ select[recipient(o1 )  Company](o1 : Objects)\ select[recipient(o1 ) \ Insurance Company 6= ;](o1 : Objects)\ select[product(o1)  select[has-cpu(o2)  Sparc] \ select[#(has-cpu(o2))  2](o2 : Workstation)](o1 : Objects) Figure 3: Example of Mapping a Query Frame to an Object Algebra Expression (still to be Optimised)* the class explicitly as it can be derived at access time. and relations. The introduction of the object level The trade-o here is between fast access to explicitly is bene cial in reducing the semantic gap between stored classes versus high update overheads if data the frame level and the relational level and enabling is replicated unnecessarily. the utilisation of structural semantic information for In our mapping of COCOON onto a relational query and update processing. The mapping from the storage system, we employ extensive replication to object level to the relational level allows the use of minimise retrieval costs. For example, all classes well-established, ecient mechanisms for data stor- are represented explicitly even those which could age, data access, data sharing and recovery under be speci ed in terms of a query expression (view) failure. over other classes. Since an object may belong to At present, we have implemented mappings for many classes, an object representation may be repli- structural information from the frame model, FRM, cated in several relations. The penalty associated to the object model, COCOON and from COCOON with such an approach of massive replication is the to the multiprocessor relational database system, cost of update operations; a single update operation INGRES. We also have a mapping from frame query on a speci c object may require updates on a large classes to COCOON algebra. Moreover, there are number of relations involved in the representation of some early results on the parallelisation of update that object. operations over a COCOON database represented The problem then becomes one of how to speed in INGRES [Rys 94]. Currently, we are working on up the time for updates. This is achieved by imple- the mapping of the remaining operational compo- menting the update operation as a number of simpler nents and on the mapping of frame class instances update operations which can be executed in paral- to objects. lel. The exploitation of intra-transaction parallelism together with multi-level transactions is a key tech- nique towards such improved performance [WS 92]. References We are currently evaluating the above approach to [Bor 91] A. Borgida, \Knowledge Representa- see under what conditions the overheads of paralleli- tion, Semantic Modeling: Similarities sation are compensated by the corresponding speed- and Di erences", In Entity-Relationship up of the operations. In the future, we shall inves- Approach: The Core of Conceptual tigate dynamic methods of mapping the object data Modelling, ed. H. Kangassalo, North- model COCOON to relational systems such that Holland, 1991, pp. 1-24. good performance is attained under various retrieval [BS 85] R. J. Brachman and J. G. Schmolze, and update patterns (which nally stem from spe- \An overview of the KL-ONE knowl- ci c retrieval and update operations on the knowl- edge representation system", Cognitive edge base system). Science, Vol. 9, No. 2, 1985, pp. 171-216. [LNR+94] P. Lippuner, M. Norrie, U, Reimer and 5 Conclusions M. Rys, \Mapping a Frame Model, In the HYWIBAS project, we are using database FRM, to an Object Data Model, CO- technologies to support large, shared knowledge COON", HYWIBAS Working Paper, bases. We employ a three level architecture corre- 1994. (in preparation) sponding to three semantic levels of frames, objects [Mor 91] K. Morik, \Underlying Assumptions of Knowledge Acquisition and Machine * For reasons of readability we have slightly simpli- Learning", Knowledge Acquisition, Vol. ed the algebra expression: The select statements should 3, 1991, pp. 137-156. apply to classes of objects for which the functions re- ferred to are really de ned, rather than operating on the [Rei 89] U. Reimer, \FRM: Ein Frame-Reprasen- most general class Objects. This requires an additional tationsmodell und seine formale Seman- meta-schema query, which we have omitted. tik. Zur Integration von Datenbank- und Wissenreprasentationsansatzen", Springer, 1989. [RL 94] U. Reimer, P. Lippuner, \Syntax und Semantik von FRM", Working Paper, 1994, Informatik-Forschungsgruppe, Swiss Life, CH-8022 Zurich). [RRS+93] U. Reimer, M. Rys, H.-J. Schek and R. Marti, \Datenbankbasierung eines Frame-Modells: Abbildung auf ein Ob- jektmodell und eziente Unterstutzung komplexer Operationen", Beitrag zum Workshop \Verwaltung und Verar- beitung von strukturierten Objekten" wahrend der KI 93, (also available as Technical Report 5/93, Informatik- Forschungsgruppe, Swiss Life, CH-8022 Zurich). [RS 89] U. Reimer and H.-J. Schek, \A Frame- Based Knowledge Representation Model and its Mapping to Nested Relations", Data and Knowledge Engineering, Vol. 4, No. 4, 1989, pp. 321-352. [Rys 94] M. Rys, \Parallelising Generic Update Operations in COCOON Using Multi- level Transactions". (in preparation) [SLR+92] M. H. Scholl, C. Laasch, C. Rich, H.-J. Schek and M. Tresch, \The COCOON Object Model", Technical Report 211, Dept of Computer Scince, ETH Zurich, CH-8092 Zurich, Switzerland. [WS 92] G. Weikum, H.-J. Schek, \Concepts and Applications of Multilevel Transac- tions and Open Nested Transactions", In Database Transaction Models for Ad- vanced Applications, ed. A.K. Elma- garmid, Morgan Kaufmann, 1992.