=Paper=
{{Paper
|id=Vol-1/paper-14
|storemode=property
|title=Frames, objects and relations: three semantic levels for knowledge base systems
|pdfUrl=https://ceur-ws.org/Vol-1/norrie-et-al-long.pdf
|volume=Vol-1
|authors=M.C. Norrie,U. Reimer,P. Lippuner,M. Rys,H.-J. Schek
}}
==Frames, objects and relations: three semantic levels for knowledge base systems==
https://ceur-ws.org/Vol-1/norrie-et-al-long.pdf
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.