A Formal Approach to the Semantics of a Frame Data Model

A FORMAL APPROACH TO THE SEMANTICS OF A FRAME DATA MODEL

Ulrich Reimer I Udo Hahn

Universitaet Konstanz Informationswissenschaft Postfach 5560 D-7750 Konstanz l, w. Germany

base system which forms an essential part of TOPIC, an automatic text understanding and abstracting system (TOPIC 1983) , currently under development at the information science department of the University of Constance, W. Germany.

ABSTRACT

Standard knowledge representation languages are seriously lacking an explicit formal semantic specification. This may cause considerable trouble when applied to large amounts of rapidly changing data.

Based on an abstract data type view of knowledge representation languages a formal definition of a frame data model is presented in terms of a denotational semantics approach using a subset of META-IV. After introducing some basic concepts of the model several semantic integrity constraints are outlined which ultimately lead to the formula­ tion of a set of operations in the frame data

model.

l. Introduction

Standard knowledge representation languages such as KRL (BOBROW/WINOGRAD 1977) or FRL (ROBERTS/ GOLDSTEIN 1977) are almost exclusively charac­ terized by syntactic specifications, but no atten­ tion is paid to the formal specification of their semantics. Recently, several formalisms have been devised which provide explicit semantic specifica­ tions, KL-ONE (as outlined in BRACHMAN 1979) being one of the most promising proposals. Exhaustive formal conditions on the operations on knowledge representation structures clearly lead to an abstract data type view of knowledge repre­ sentation languages (WEINER/PALMER 1981).

The lack of semantic specifications in knowledge representation languages may cause severe problems (e.g. unpredictable side effects and inconsistent changes in .the data base), which obviously become more and more serious when large numbers of knowledge structures are managed. We consider knowledge base systems to be realizations of fermally defined data models. By formally specifying the semantics of the operations of an underlying frame data model we attempt to strictly constrain the actual behavior of a large knowledge The formal specification of our frame data model is based on a denotational semantics approach, applying a subset of the META-IV-Language (e.g. as illustrated in BJORNER 1980). After introduc­ ing basic concepts of our model (section 2) , we shall give some examples of semantic integrity constraints which apply properties of the pre­ viously defined concepts (section 3) and finally indicate the basic operations on objects of the data model (section 4), thus providing a sketch of what the semantics of a frame data model might look like (for an extended version of this paper see (REIMER/HAHN 1983)).

This work was supported by Bundesministerium fuer Forschung und Technologie I Gesellschaft fuer Information und Dokumentation under grant no.

PT 200.08.

2. Basic Concepts of the Data Model

The notion of a frame is defined by a mapping

FRAMES = Fname --> SLOTS

Fname denotes the set of frame SLOTS denotes the set of slots. slot is given by the mapping identifiers and The notion of a

SLOTS = Sname --> SENTRY

Sname denotes the domain of slot identifiers and SENTRY denotes the domain of actual and permitted slot entries. The actual and permitted entries for a slot are given by the mapping

SENTRY = Type --> Entries

The set Type consists of act and ~· The element act is mapped to the set of actual entries while perm is mapped to the set of permitted entries, both sets constituting the set Entries.

A network of relationally connected frames may be constructed from the relations given in the data model. we now consider single elements of the mapping domains defined above.

Is-a= { <f,f 1 > I f, f 1 E: dan FRAMES 11 " - 3 f" ~ dan FRAMES: [ T<f, f"> ' Is-a v - v <f",f> £ Is-a ] 11 II f" £ dan (FRAMES (f)) ] 11 1\ dan (FRAMES (f)) 2 dan (FRAMES (f 1 )) A " V s ' dan (FRAMES (f)) n dan (FRAMES (f 1 )) : FRAMES(f) (s) (~)c= FRAMES(f 1 ) (s) (~) }

The Is-a hierarchy requires that a hyponym frame have at least the same slot identifiers as its superordinate frames and maximally the same set of permitted slot entries for corresponding slots of its superordinate frames.

A frame which is element of an Is-a tuple is called prototype:

A prototype f defines an equivalence class of frames:

The elements in ecf are called instances of f. The equivalence class of a prototype frame con­ sists of instance frames whose slot identifiers and sets of permitted entries are the same as those of the prototype. Only the actual slot entries may differ among the frames in the equiv­ alence class.

The relation E-is-a (extended is-a) uses the concept of equivalence classes:

Parts := { <f,f 1 > 1 f, f 1 e dan FRAMES 11

1\ [ f £dan (FRAMES(f 1 )) v

v 3 s T dan (FRAMES ( f 1 ) ) :

f E: FRAMES(f 1 ) (s) (act) ] 11

1\ ]f" £ dan FRAMES: <f ,f">-;<f 1 ,f"> £ E-is-a }

The Parts relation holds for two frames if the identifier of one frame is a slot identifier of the other or is a slot entry of the other frame and both frames have a common superordinate frame in the Is-a hierarchy.

3. Semantic Integrity Constraints

The properties of the relations defined above not only put severe restrictions on the possible relational connection between two frames, but require the existence of a relational tuple, if two frames share appropriate properties. Further restrictions are included in the data model in terms of explicit semantic integrity constraints (viewing the properties of the relations as implicit semantic integrity constraints).

As an ex~le the following constraint holds for 1nstances:

Distinguishing two types of slots allows for a more stringent control of slot filling:

1. The set of non-terminal slots is given by NTSLOTS = -- = [ s --> SENTRY I s c dan FRAMES l n SLOTS
2. All other slots are called terminal slots TSLOTS = SLOTS \ NTSLOTS

The mapping SENTRY gives for each slot the set of actual and the set of permitted slot entries. The permitted slot entries for terminal slots must be specified by the user of the data model, the permitted slot entries for non-terminal slots cannot be defined externally, but are given by the following model-dependent integrity constraint which states that permitted slot entries of slot s are hyponyms of the frame with the identifier s with respect to the E-is-a relation:

The following constraint states that a prototype may not have a slot entry:

1. f is prototype ==> V s € dom (FRAMES (f)) : FRAMES (f) (s) (act)

4. Basic Operations in the Data Model:

In the following the basic operations are given (to simplify the notation variables are not prefixed with c in order to get their contents, as is required by-META-IV) ·

1. Get all frame identifiers: dan FRAMES
2. Get all slot identifiers: dan (FRAMES(f))
3. Get all permitted slot entries: FRAMES(f) (s) (~)
4. Get all actual slot entries: FRAMES (f) (s) (act)
5. Add a frame: FRAMES U [ f --> [] ]
6. Add a slot: FRAMES (f) U [ s --> [ act --> ¢, ~ --> ¢ ] ]
7. Add an element to the set of permitted slot
8. entries: s £ TSLOTS ==> FRAMES (f) (s) (~) U {pe}

1. Fill a slot: ] f' £ dom FRAMES: f G ecf' A A e € FRAMES(f) (s) (~) ==> FRAMES(f) (s) (act) U {e}
2. Delete a frame: sfunc := FRAMES(f) FRAMES \ [ f --> sfunc
3. Delete a slot: efunc := FRAMES(f) (s) FRAMES(f) \ [ s --> efunc
4. Delete an element of the set of permitted slot entries: s £ TSLOTS ==> FRAMES (f) (s) (~) \ {pe}
5. Delete a slot entry: FRAMES(f) (s) (act) \ {e}

The existence of a relational edge between two frames depends only on the existence of two frames with the properties required by the relation. Therefore operations to insert or delete relation tuples need not be defined. Applying the defini­ tional properties of the Is-a and Parts relation and the properties of the equivalence class for each prototype, the semantically correct insertion and deletion of relation tuples and instance frames will be controlled and executed by the knowledge base system which realizes the frame data model.

5. Conclusion

We have outlined some basic ideas for the formal definition of a frame data model by applying a denotational semantics approach. Next, emphasis will be given to an extension of world-dependent and model-dependent integrity constraints.

Subsequently an axiomatic specification of the frame data model will be developed. After a comparison of both approaches, further refinement of the frame data model will be based on the most appropriate approach.