Fundamenta Informaticae 33 (1998) 1--34 1

IOS Press
On the Semantics of a Semantic Network

Anastasia Analyti

Institute of Computer Science
Foundation for Research and Technology-Hellas
Iraklio, Greece
analyti@ics.forth.gr

Nicolas Spyratos



Laboratoire de Recherche en Informatique
Universite de Paris-Sud
Orsay Cedex, France
spyratos@lri.fr

Panos Constantopoulos

Institute of Computer Science
Foundation for Research and Technology-Hellas
Iraklio, Greece
Department of Computer Science
University of Crete
Iraklio, Greece
panos@ics.forth.gr
Abstract

We elaborate on the semantics of an enhanced object-oriented semantic network, where multiple
instantiation, multiple specialization, and meta-classes are supported for both kinds of objects:
entities and properties. By semantics of a semantic network, we mean the information (both explicit

and derived) that the semantic network carries. Several data models use semantic networks to
organize information. However, many of these models do not have a formalism defining what the
semantics of the semantic network is.
In our data model, in addition to the Isa relation, we consider a stronger form of specialization
for properties, that we call restriction isa, or Risa for short. The Risa relation expresses property
value refinement. A distinctive feature of our data model is that it supports the interaction between

Isa and Risa relations. The combination of Isa and Risa provides a powerful conceptual modeling
mechanism.



Research conducted while this author was visiting with the Institute of Computer Science, Foundation
for Research and Technology-Hellas.

/ 2
The user declares objects and relations between objects through a program. Reasoning is done
through a number of (built-in) inference rules that allow for derivations both at instance and schema
level. Through the inference rules, new objects and new relations between objects are derived. In our
data model, inherited properties are considered to be derived objects. In addition to the inference
rules, a number of (built-in) system constraints exist for checking the validity of a program.

Keywords: semantic network, semantics, inheritance, inference rules, constraints, conceptual
modeling.

/ 3
1. Introduction

Structure can carry useful and expressive information that can be deduced with high efficiency.
This motivated the development of semantic networks [44, 20, 36] and the design of
several useful structural mechanisms. In a semantic network, real world objects are represented
by means of nodes and links. Here, by real world objects we mean entities, properties,
or relationships that make up the user's perception of the real world.
Nodes and links are used to build semantically rich structures. These structures not
only represent knowledge by themselves but are also used for deriving new information #r
for checking the validity of the existing information. We call the information (both explicit
and derived) that a semantic network carries, the semantics of the network.
Several data models use semantic networks to organize information [12, 21, 39, 43, 7, 23,
34, 30, 19, 22, 9] and their usefulness to conceptual modeling is unquestionable. However,
many of these models do not provide a formalism defining what the semantics of the semantic
network is. This can lead to inconsistencies as (procedurally) derived information cannot
be always validated against the (declaratively) defined semantics. Additionally, derivations
and reasoning are limited, as they are procedurally determined.
In this work, we elaborate on the semantics of an enhanced object-oriented semantic network,
where multiple instantiation, multiple specialization, and meta-classes are supported
for both nodes and links.
The context of our work is the Semantic Index System (SIS) [14, 15, 16, 40]. In fact, the
data model presented in this paper, is a (self-contained) part of the SIS data model. The
SIS is targeted at supporting large descriptive knowledge structures in real applications.
Typical applications include: cultural and scientific documentation systems, repository indexes
for multimedia assets, engineering and software artifacts, laws and cases, organization
structures, and other descriptive applications.
In all semantic network data models, specialization between classes is expressed through
the Isa relation. However, as we demonstrated in [3], two different relations, Isa and

restriction isa (Risa), are needed to express specialization between properties. The Isa

relation between properties expresses inclusion of property extensions. The Risa relation
is a stronger form of Isa and expresses property value refinement.
To get a feeling of Risa, consider the class Art collector that has a property collects

with value in the class Art object, and the class Painting collector that has a property

collects with value in the class Painting. The classes Painting collector and Painting are
subclasses of Art collector and Art object, respectively. The information that some of the
art objects collected by a painting collector are paintings can be expressed through the
usual Isa relation between the two collects properties. However, to express that all art
objects collected by a painting collector are paintings, a stronger form of Isa is needed that
represents property refinement. It is precisely that stronger form of Isa that we call Risa.

In our example, using Risa between the two collects properties, expresses that the property

collects of Art collector restricted to Painting collectors takes values in Painting.

Inheritance is a well-known concept in the area of knowledge representation. However,
it usually lacks formal definition and is defined procedurally. In [3], we formally defined
property inheritance by employing the Risa relation.
The user defines objects and relations between objects through declarations. Specifically,
there are two types of declarations: those that define explicit objects and those that define

explicit relations. Explicit relations relate explicit objects through In, Isa, or Risa relations.
A set of declarations that satisfies certain syntactical conditions, makes up a program.

/ 4
Intuitively, a program corresponds to a semantic network with explicit information only.
Reasoning in our data model is done through a number of (built-in) inference rules that
allow for derivations both at instance and schema level. In addition to the inference rules,
a number of (built-in) system constraints are used for checking the validity of a program.
Through the inference rules, new objects are derived, as well as new In, Isa, and Risa

relations between objects. We shall refer to objects and relations that are not explicit, as

derived objects and derived relations, respectively.
In our data model, inherited properties are considered to be derived objects. This
is important, as inherited properties may not have all the characteristics of the #riginal
properties. In particular, the inherited property may have a finer value domain than the
original property. In fact, the value domain of an inherited property corresponds to the
"intersection" of the value domains of several properties, including the original property.
In addition, the inference rules relate inherited properties to other properties through Isa

and Risa relations. Such relations not only give useful information about the inherited
properties but also refine the values of the inherited properties.
In this paper, we formally define the semantics of a program as follows: Each program

P has a set of models. Intuitively, a model is a semantic network that satisfies the inference
rules and the declarations in P . We define a partial ordering over the models of P and
we prove that P has a least model, say M . If M satisfies the system constraints then we
call it the semantics of P . A program with no semantics is called invalid. Intuitively, the
semantics of a program P corresponds to an expanded semantic network which contains the
explicit information defined in P , as well as additional information derived by the inference
rules.
Thus the main contribution of this paper is to give a formal definition of the semantics
of a semantic network supporting multiple instantiation, multiple specialization, and
meta-classes. Moreover, the present paper provides a formal account for several semantic
constructs introduced in an earlier paper [3].
The rest of the paper is organized as follows: Section 2 describes our view on objects, and
defines the instantiation and specialization relations. Section 3 defines the derived objects
of our data model. Sections 4 and 5 present the inference rules and the system constraints,
respectively. Section 6 defines a program and the program semantics. Section 7 presents a
comparison of our work with related works. Finally, section 8 contains concluding remarks.
All proofs are given in the Appendix.

2. Our View on Objects

In our data model, objects are distinguished with respect to their nature into: individuals,
arrows, and hybrids.

ffl Individuals: These are concrete or abstract entities of independent existence, such
as the concrete entity my-car, and the abstract entity Car.

ffl Arrows: These are concrete or abstract properties/binary relationships

1

of objects.
More precisely, an arrow a represents a property or a relationship from an object o to
an object o

0

. The objects o, o

0

are called the from and to objects of the arrow a, and
are denoted by from(a) and to(a), respectively.

1

We do not make the distinction between property and binary relationship, as our approach is common
to both.

/ 5
Examples of arrows are: (i) the concrete relationship produced from Opel to my-car,

and (ii) the abstract relationship produced from Car-company to Car.

ffl Hybrids: These are abstractions that refer collectively to objects of any kind.
For example, the abstraction Mathematical concept is a hybrid object, as it refers
collectively both to entities (e.g., integer) and relationships (e.g., equal).

In the present work, we consider only arrows whose to object is an individual or a hybrid.
Yet, the from object of an arrow can be of any type. In particular, it can be another arrow.
Objects are also distinguished with respect to their concreteness, into tokens and classes.

ffl Tokens: These are concrete objects, such as the individual my-car, and the arrow

produced from Opel to my-car.

ffl Classes: These are abstract objects, in the sense that they refer collectively to a set
of objects that are considered similar in some respect. Classes that refer collectively
also to classes are called meta-classes.

Examples of classes are: (i) the individual car, and (ii) the arrow produced from Carcompany
 to Car.

All hybrids are classes, as they refer collectively to a set of objects. In contrast, individuals
and arrows can be tokens or classes.
Our view of objects as individuals, arrows, or hybrids on one hand, and as tokens or
classes on the other, follows quite closely the structural part of the knowledge representation
language Telos [30, 24].
The extension of a class c is the set of objects referred to collectively by c. We assume
that the extension of an individual class is a set of individuals. The extension of an arrow
class from a class c to a class c

0

is a set of arrows from objects in the extension of c to
objects in the extension of c

0

. The extension of a hybrid is a set of individuals, arrows, or
hybrids.
Objects can be related to classes through the instance of relation.

Definition 2.1. In relation

If an object o belongs to the extension of a class c then we say that o is an instance of c, and
we denote it by In(o; c). An object can be instance of zero, one, or more classes (multiple
instantiation). \Pi

For an example, refer to Figure 1(a), where the arrow token collects from art collector
X to art object Y is instance of the arrow class collects from Art collector to Art object.
2.1. Two forms of specialization: Isa and Risa

In this subsection, we define two forms of specialization: Isa and Risa (called restriction
isa). The Isa relation relates pairs of classes and expresses inclusion of class extensions.
The Risa relation relates pairs of arrow classes and expresses property value refinement.

Definition 2.2. Isa relation

Let o, o

0

be two classes. We distinguish three cases:

Case 1: o and o

0

are individual classes.

/ 6
(a) (b)
collector
Art
Art
object
art
object Y collector X

collects
collects
collects
collects collects
Art
Art
object
Art
collector
collector
Painting
collector
painting
Only
Painting
Risa
Isa
In
Figure 1. Example of relations between objects
We say that o is subclass of o

0

, denoted by Isa(o; o

0

), if it holds that: for any x, if In(x; o)

then In(x; o

0

).

Case 2: o and o

0

are arrow classes.
We say that o is subclass of o

0

, denoted by Isa(o; o

0

), if it holds that:
(i) Isa(from(o); from(o

0

)), (ii) Isa(to(o); to(o

0

)), and (iii) for any x, if In(x; o) then In(x; o

0

).

Case 3: o is a class and o

0

is a hybrid.
We say that o is subclass of o

0

, denoted by Isa(o; o

0

), if it holds that: for any x, if In(x; o)

then In(x; o

0

).
In all other cases, Isa is undefined.
A class can be subclass of zero, one, or more classes (multiple specialization). \Pi

See for example Figure 1(b), where the class Painting collector refers to art collectors
that collect paintings (but may also collect other art objects). The arrow class collects from

Painting collector to Painting is subclass of the arrow class collects from Art collector to

Art object. This is because every painting collected by a painting collector is an art object
collected by an art collector.
We now give the definition of the restriction isa relation.

Definition 2.3. Risa relation

Let a, a

0

be two arrow classes. We say that a is a restriction subclass of a

0

, denoted by

Risa(a; a

0

), if the following hold:
(i) Isa(a; a

0

), and
(ii) for any x, if In(x; a

0

) and In(from(x); from(a)) then In(x; a). \Pi

For example, see Figure 1(b), where the class Only painting collector refers to art collectors
that collect only paintings. The arrow collects of Only painting collector is a restriction
subclass of the arrow collects of Art collector. This is because if an art collector collects
an art object and the art collector happens to be an only-painting-collector, then the art
object must be a painting.

/ 7
3. Derived Objects

In our data model, objects are also characterized as explicit or derived. Explicit objects
are declared by the user, whereas derived objects are derived by the system.
There are five kinds of derived objects: meet classes, join classes, exact inherited arrows,

to objects of exact inherited arrows, and approximate inherited arrows.

Intuitively, meet classes are intersections of classes, join classes are unions of classes, and
exact and approximate inherited arrows are properties inherited by subclasses. In particular,
the to object of an approximate inherited arrow is a meet class. The exact inherited arrows
are auxiliary derived objects that are introduced for the derivation of approximate inherited
arrows.

3.1. Meet and Join Classes

In this subsection, we define the meet class and join class of a set of classes.

Definition 3.1. Meet class

Let s be a set of explicit individual or hybrid classes. We define the meet class of s, denoted
by meet(s), to be the class whose extension is the intersection of the extensions of the
classes in s. \Pi

We distinguish two cases, depending on whether s has a least class w.r.t. Isa, or not:

Case 1: The set s has least class, i.e., there exists a class c in s such that c is subclass of
each class in s. Then, it follows that meet(s) = c.

Case 2: The set s has no least class. Then, the system derives the class meet(s) and the
following Isa relations:
(i) For every class c in s, derive Isa(meet(s); c).

(ii) For every class c such that c is subclass of each class in s, derive Isa(c; meet(s)).

Note that if meet(s) is the least class of s (Case 1) then meet(s) is an explicit object
that already satisfies the Isa relations of (i) and (ii). Otherwise (Case 2), meet(s) is a
derived object.
For an example, refer to Figure 3. The set of classes s = fd

0

; d 0 ; d 1 g has no least class,
so meet(fd

0

; d 0 ; d 1 g) is a derived object. This derived object is subclass of d

0

, d 0 , and d 1 .
Similarly to meet classes, we define the join classes.

Definition 3.2. Join class

Let s be a set of explicit individual or hybrid classes. We define the join class of s, denoted
by join(s), to be the class whose extension is the union of the extensions of the classes in

s. \Pi

We distinguish two cases, depending on whether s has a greatest class w.r.t. Isa, or
not:

Case 1: The set s has greatest class, i.e., there exists a class c in s such that each class in

s is subclass of c. Then, it follows that join(s) = c.

Case 2: The set s has no greatest class. Then, the system derives the class join(s) and the
following Isa relations:
(i) For every class c in s, derive Isa(c; join(s)).

(ii) For every class c such that each class in s is subclass of c, derive Isa(join(s); c).

/ 8
3.2. Arrow Inheritance

Let a

0

be an arrow class from a class c

0

to a class d

0

. Let c be a subclass of c

0

. Our purpose
is to define the arrow inherited by c from a

0

. We motivate our definition as follows (see
Figure 2).
Isa
derived Risa

Art Art
object
Only
painting
collector

collects
c
c' d'
a'
a_inh(c,a')
e_inh(c,a')
d (c,a')

collector
Figure 2. Exact and approximate arrow inheritance
The arrow a

0

is an arrow from c

0

to d

0

that refers collectively to a set, say E

0

, of arrows.
The from objects of arrows in E

0

are instances of c

0

, and their to objects are instances of

d

0

. The question is what "part" of a

0

expresses an arrow with from object c. It is this
part that we shall call the arrow inherited by c from a

0

. Obviously, the extension E of this
inherited arrow is the set of arrows in E

0

whose from objects are instances of c. It now
remains to determine the to object of this inherited arrow. Let d(c; a

0

) be the class referring
to the to objects of the arrows in E. We take d(c; a

0

) to be the to object of the inherited
arrow. We refer to this kind of inherited arrow, as the exact inherited arrow. Later in the
section, we introduce the approximate inherited arrow that, in a sense, "approximates" the
exact inherited arrow.

Definition 3.3. Exact inherited arrow

Let a

0

be an arrow class from a class c

0

to a class d

0

and let c be a subclass of c

0

. Let

d(c; a

0

) be the class whose extension consists of the to objects of the arrows x such that

In(from(x); c) and In(x; a

0

) hold.
We define e inh(c; a

0

) to be the arrow class from c to d(c; a

0

) whose extension consists
of the arrows x such that In(from(x); c) and In(x; a

0

) hold. The arrow e inh(c; a

0

) is called
the exact arrow inherited by c from a

0

. \Pi

Every exact inherited arrow e inh(c; a

0

) is a derived arrow. Additionally, d(c; a

0

) is a
derived class. It easily follows that e inh(c; a

0

) is restriction subclass of a

0

. For example, in
Figure 2, e inh(c; a

0

) is a derived arrow which is restriction subclass of a

0

.
We would like to emphasize that we do not know what exactly the class d(c; a

0

) is.
What we do know are Isa and Risa relations of a

0

with other arrows, as well as Isa

relations of c with other classes (as declared by the user). Based on these relations and
using inference rules, we can derive Isa relations of inh(c; a

0

) to other arrows. If we derive
that inh(c; a

0

) is subclass of an arrow a, then we can derive that d(c; a

0

) is subclass of to(a).

In this way, although we do not know what exactly the class d(c; a

0

) is, we can derive a set

/ 9
of explicit classes which are superclasses of d(c; a

0

). This set is denoted by cand cl(c; a

0

)
and is computed in subsection 4.3. We can say that the "intersection" of the classes in

cand cl(c; a

0

) provides an "approximation" of the class d(c; a

0

).
Roughly speaking, as the classes in cand cl(c; a

0

) are explicit, their meet class is known
(in contrast to the class d(c; a

0

) which is unknown). Therefore, we would like to define
an inherited arrow that "approximates" e inh(c; a

0

) and its to object is the meet class of
the classes in cand cl(c; a

0

). We denote this arrow by a inh(c; a

0

) and call it approximate
inherited arrow or inherited arrow, for short. Obviously, a inh(c; a

0

) should be an arrow
from c to meet(cand cl(c; a

0

)) whose extension is the same as that of e inh(c; a

0

). In [3], we
prove that there is a unique arrow with these properties. Thus, a inh(c; a

0

) is well defined.

Definition 3.4. Inherited arrow

Let a

0

be an explicit arrow class from a class c

0

to a class d

0

and let c be a subclass of c

0

.
We define a inh(c; a

0

) to be the arrow class from c to meet(cand cl(c; a

0

)) whose extension
consists of the arrows x such that In(from(x); c) and In(x; a

0

) hold. The arrow a inh(c; a

0

)
is called the approximate arrow inherited by c from a

0

, or arrow inherited by c from a

0

, for
short. \Pi

Similarly to e inh(c; a

0

), a inh(c; a

0

) is a derived arrow which is restriction subclass of

a

0

.

Examples

In Figure 2, we have cand cl(c; a

0

) = fArt objectg. Therefore, as Art object is the least
object of cand cl(c; a

0

), it follows that the to object of a inh(c; a

0

) is Art object. Note that

a inh(c; a

0

) is a derived arrow which is restriction subclass of a

0

.
Art
object
Isa
Risa
derived Isa
derived Risa

collector
Painting
collector
Art
Expensive art
object

collects
art collector
collector
painting
Rich
Rich

collects
collects a'
c'

Painting

a
a

1
0

d

1
derived arrow

1 0
derived individual

c

0

d
d'
a_inh(c,a')
e_inh(c,a')
d(c,a')
meet(d',d , d )
Figure 3. Example of arrow inheritance
For another example, refer to Figure 3, where we have that cand cl(c; a 0 ) = fd

0

; d 0 ; d 1 g.

The to object of a inh(c; a

0

) is the derived class meet(cand cl(c; a

0

)).

/ 10
An extended discussion and illustrative examples regarding inherited arrows and their
usefulness can be found in [3].

4. Inference Rules

As we mentioned earlier, the In, Isa, and Risa relations are either declared or derived.
Relation derivations are performed using certain inference rules. Additionally, inference
rules are used for generating derived objects. All inference rules of our model are sound.
The soundness of the Isa, Risa, and Exact Inheritance Rules is proved in [3]. The soundness
of the rest of the inference rules is proved, similarly.
O: set of objects
H: set of hybrids
I: set of individuals
IC: set of individual classes
AC: set of arrow classes
E: set of explicit objects
EA: set of explicit arrows
and hybrid classes
L: powerset of explicit individual
T: set of tokens
A: set of arrows
C: set of classes
EAC: set of explicit arrow classes
Figure 4. Notations of object sets
We use O to denote the set of all objects. We use I , H , A, T , C, and E to denote
the sets of individuals, hybrids, arrows, tokens, classes, and explicit objects, respectively.
We use IC = I " C, AC = A " C, EA = E " A, and EAC = E " AC to denote the sets
of individual classes, arrow classes, explicit arrows, and explicit arrow classes, respectively.
We use L = P((IC [ H) " E) to denote the powerset of explicit individual and hybrid
classes. These notations are shown in Figure 4.

4.1. Isa and Risa Rules

The Isa Rules are used for deriving (i) new Isa relations based on given Isa relations, and
(ii) new In relations based on given In and Isa relations.
ISA RULES

Rule 1: 8 c 2 C; Isa(c; c)

Rule 2: 8 c 1 ; c 2 ; c 3 2 C; Isa(c 1 ; c 2 )  Isa(c 2 ; c 3 ) ) Isa(c 1 ; c 3 )

Rule 3: 8 o 2 O, c; c

0

2 C; In(o; c)  Isa(c; c

0

) ) In(o; c

0

)
The Risa Rules are used for deriving (i) new Isa and Risa relations based on given Isa

and Risa relations, and (ii) new In relations (between arrows) based on given In and Risa

relations.
RISA RULES

/ 11
Rule 1: 8 a; a

0

2 AC; Risa(a; a

0

) ) Isa(a; a

0

)

Rule 2: 8 x 2 A, a 1 ; a 2 2 AC, Risa(a 1 ; a 2 )  In(x; a 2 )  In(from(x); from(a 1 )) ) In(x; a 1 )

Rule 3: 8 a 2 AC; Risa(a; a)

Rule 4: 8 a 1 ; a 2 ; a 3 2 AC; Risa(a 1 ; a 2 )  Risa(a 2 ; a 3 ) ) Risa(a 1 ; a 3 )

Rule 5: 8 a 1 ; a 2 ; a 3 2 AC,
Isa(a 1 ; a 3 )  Risa(a 2 ; a 3 )  Isa(from(a 1 ); from(a 2 ))  Isa(to(a 1 ); to(a 2 )) ) Isa(a 1 ; a 2 )

Rule 6: 8 a 1 ; a 2 ; a 3 2 AC, Isa(a 1 ; a 2 )  Isa(a 2 ; a 3 )  Risa(a 1 ; a 3 ) ) Risa(a 1 ; a 2 )
Risa Rules 1 and 2 reflect the definition of Risa. We refer to [3], for illustrative examples
and discussions regarding the Risa Rules.

4.2. Meet and Join Rules

The Meet Rules derive meet classes and relate them to other objects. Recall that L is the
powerset of explicit individual and hybrid classes and meet : L ! C.
MEET RULES

Rule 1: 8 s 2 L, c 2 IC [ H, c 2 s  (8 c

0

2 s; Isa(c; c

0

)) ) meet(s) = c

Rule 2: 8 s 2 L, c 2 IC [ H, c 2 s ) Isa(meet(s); c)

Rule 3: 8 s 2 L, c 2 IC [ H, (8 c

0

2 s; Isa(c; c

0

)) ) Isa(c; meet(s))

Rule 4: 8 s 2 L, o 2 O, (8 c

0

2 s; In(o; c

0

)) ) In(o; meet(s))

Rule 5: 8 s; s

0

2 L, Isa(meet(s); meet(s

0

))  Isa(meet(s

0

); meet(s)) ) meet(s) = meet(s

0

)
Note that Meet Rules 2 and 3 derive Isa relations for meet(s), where s 2 L. From
Meet Rule 1, it follows that if c is the least class of s then meet(s) is the explicit class c.

Additionally, it will follow from the definition of the program semantics that the inverse is
also true. Specifically, if meet(s) is an explicit class c then c is the least class of s. Therefore,
it follows that if meet(s) is an explicit class c then the Isa relations derived by Meet Rules
2 and 3, are already holding for c. Thus, these rules do not derive new Isa relations for
explicit classes.
Note that the inverse of Meet Rule 3 follows from Meet Rule 2 and Isa Rule 2. Additionally,
the inverse of Meet Rule 4 follows from Meet Rule 2 and Isa Rule 3.
Consider a set s 2 L such that o; o

0

2 s and o is subclass of o

0

. It holds that

meet(s)=meet(s - fo

0

g), as expected. This result is an easy consequence of Meet Rules
2,3,5 and Isa Rule 2. For example, in Figure 3, it holds that meet(d

0

; d 0 ; d 1 ) = meet(d

0

; d 0 ).
Similarly to the Meet Rules, the Join Rules derive join classes and relate them to other
objects.

/ 12
JOIN RULES

Rule 1: 8 s 2 L, c 2 IC [ H, c 2 s  (8 c

0

2 s; Isa(c

0

; c)) ) join(s) = c

Rule 2: 8 s 2 L, c 2 IC [ H, c 2 s ) Isa(c; join(s))

Rule 3: 8 s 2 L, c 2 IC [ H, (8 c

0

2 s; Isa(c

0

; c)) ) Isa(join(s); c)

Rule 4: 8 s; s

0

2 L, Isa(join(s); join(s

0

))  Isa(join(s

0

); join(s)) ) join(s) = join(s

0

)
4.3. Inheritance Rules

In this subsection, we present two sets of inference rules: Exact Inheritance Rules and Approximate
Inheritance Rules. The Exact Inheritance Rules derive exact inherited arrows

2

and relate them to other arrows. Based on derivations for exact inherited arrows, the to

object of inherited arrows is computed.
EXACT INHERITANCE RULES

Rule 1: 8 a

0

2 EAC, c 2 C,
Isa(c; from(a

0

)) , 9 e inh(c; a

0

) 2 AC

9 e inh(c; a

0

) 2 AC ) from(e inh(c; a

0

)) = c

Rule 2: 8 a

0

2 EAC, c 2 C; Risa(e inh(c; a

0

); a

0

)

Rule 3: 8 a

0

2 EAC, c 2 C, a 0 ; a 1 2 AC,
Isa(e inh(c; a

0

); a 1 )  Risa(a 0 ; a 1 )  Isa(c; from(a 0 )) ) Isa(e inh(c; a

0

); a 0 )

Rule 4: 8 a

0

2 EAC, c 2 C, a 2 AC, Isa(e inh(c; a

0

); a) ) Isa(to(e inh(c; a

0

)); to(a))

Rule 5: 8 a

0

2 EAC, d 2 C " E, c 2 C, Isa(to(e inh(c; a

0

)); d) ) d 2 cand cl(c; a

0

)

Rule 6: 8 a

0

2 EAC, c 2 C, x 2 A, In(x; e inh(c; a

0

)) ) In(to(x); to(e inh(c; a

0

)))

Rule 7: 8 a

0

; a

00

2 EAC, c 2 C,
Isa(e inh(c; a

0

); e inh(c; a

00

))  Isa(e inh(c; a

00

); e inh(c; a

0

)) ) e inh(c; a

0

) = e inh(c; a

00

)
Exact Inheritance Rule 4, refines the class to(e inh(c; a

0

)). That is, it relates the to

object of e inh(c; a

0

) to its superclasses through the Isa relationship. Exact Inheritance
Rule 5, puts the superclasses of to(e inh(c; a

0

)) into the candidate class set for c and a

0

(i.e.,

cand cl(c; a

0

)). As this rule is the only rule that defines cand cl(c; a

0

), the set cand cl(c; a

0

)
includes all superclasses of to(e inh(c; a

0

)).
For an example of Exact Inheritance Rule 3, refer to Figure 3. First, observe that arrow

e inh(c; a

0

) is a restriction subclass of a

0

(Exact Inheritance Rule 2). Additionally, observe

2

Note that e inh : C \Theta EAC ! AC is a partial function. In the inference rules, the expression

9 e inh(c; a

0

) 2 AC evaluates to true, if e inh(c; a

0

) is defined (in other words, if the arrow e inh(c; a

0

)
is derived).

/ 13
that a

0

is subclass of a 1 . Thus, from Isa Rule 2 (transitivity), we derive that e inh(c; a

0

) is
subclass of a 1 . On the other hand, arrow a 0 is restriction subclass of a 1 . As c is subclass
of from(a 0 ), we have all three conditions of Exact Inheritance Rule 3 satisfied. Thus, we
obtain that e inh(c; a

0

) is subclass of a 0 .
For an example of Exact Inheritance Rule 4, we continue with our previous example
(Figure 3). As e inh(c; a

0

) is subclass of a

0

, the to object of e inh(c; a

0

) (denoted by d(c; a

0

))
is subclass of d

0

. As e inh(c; a

0

) is subclass of a 1 , d(c; a

0

) is subclass of d 1 . Additionally, as

e inh(c; a

0

) is subclass of a 0 , d(c; a

0

) is subclass of d 0 . As no other superclass of d(c; a

0

) can
be derived, it follows that cand cl(c; a

0

) = fd

0

; d 0 ; d 1 g. Additionally, it follows from Meet
Rule 3 that d(c; a

0

) is subclass of meet(fd

0

; d 0 ; d 1 g).

The Approximate Inheritance Rules derive inherited arrows and relate them to other
arrows.
APPROXIMATE INHERITANCE RULES

Rule 1: 8 a

0

2 EAC, c 2 C,
Isa(c; from(a

0

)) , 9 a inh(c; a

0

) 2 AC

9 a inh(c; a

0

) 2 AC ) from(a inh(c; a

0

)) = c
Rule 2: 8 a

0

2 EAC, c 2 C; Risa(a inh(c; a

0

); a

0

)

Rule 3: 8 a

0

; a

00

2 EAC, c 2 C,
Isa(a inh(c; a

0

); a inh(c; a

00

))  Isa(a inh(c; a

00

); a inh(c; a

0

)) ) a inh(c; a

0

) = a inh(c; a

00

)

Rule 4: 8 a

0

2 EAC, c 2 C, 9 a inh(c; a

0

) 2 AC ) to(a inh(c; a

0

)) = meet(cand cl(c; a

0

))
For example, in Figure 3, a inh(c; a

0

) is restriction subclass of a

0

and the to object of

a inh(c; a

0

) is meet(fd

0

; d 0 ; d 1 g).
5. System Constraints

The following system constraints guarantee the validity of the information base. Though
suitable forms of these constraints could be used as inference rules, we have decided to use
them as constraints for checking the validity of explicitly declared information.
For example, the inference rule corresponding to the Isa Antisymmetry Constraint (below)
is the following: If c is a subclass of c

0

and c

0

is a subclass of c then (infer that) c and c

0

coincide. Obviously, to infer that two explicitly declared classes coincide may lead to wrong
conclusions. Thus, in this case, we thought it more appropriate to indicate the problem to
the user, rather than inferring that the two classes coincide.
SYSTEM CONSTRAINTS
ISA CONSTRAINTS

/ 14
1. Isa Domain Constraint: Isa ` C \Theta C

2. Isa Antisymmetry Constraint: 8 a; b 2 O; Isa(a; b)  Isa(b; a) ) a = b

3. Arrow Isa Constraint: 8 a; a

0

2 A; Isa(a; a

0

) ) Isa(from(a); from(a

0

)) 

Isa(to(a); to(a

0

))
IN CONSTRAINTS
1. In Domain Constraint: In ` O \Theta C

2. Arrow In Constraint: 8 x; a 2 A; In(x; a) ) In(from(x); from(a))  In(to(x); to(a))
CONCRETENESS CONSTRAINTS
1. Concreteness Constraint: T " C = ;
The Arrow In and Isa Constraints are used for typechecking (as we shall see in section
7).
6. Semantics of Declaration Programs

We first define the notion of program and then give its formal semantics. Roughly speaking,
the semantics of a program is expressed by means of what we call a model. We prove that
every program P has a least model, say M . If M satisfies the system constraints then M

is considered to represent the semantics of P . Otherwise, P is considered to be invalid.
6.1. Declaration Programs

The user interacts with the system by declaring the objects of interest, as well as the
relationships between these objects. A set of declarations is what we call a "program". A
program is "interpreted" by the system in order to build the information base (expanded
semantic network).
To name the objects of interest and their relationships, the user uses a set of naming
symbols, denoted by N .
Intuitively, each explicit individual and hybrid has a name in N , and each explicit arrow
has a label in N . The name of an explicit arrow a is formed by the name of from(a) and
the label of a. Specifically, if f is the name of from(a) and l is the label of a then the name
of a is f=l. For example, if an arrow a has label produced and the name of its from object
is Car-company then the name of a is Car-company/produced.

Definition 6.1. Object names

We define the arrow names Anam and object names Onam , as follows:

Anam = fn=l 1 =:::=l k j n; l 1 ; :::; l k 2 Ng
Onam = N [ Anam \Pi

With names, the user can refer only to explicit objects. In order to refer to both explicit
and derived objects, the user needs references. In fact, references were introduced for the
external identification of derived objects. Each object has an associated set of references.

/ 15
Intuitively, references are formed from (explicitly defined) names. The name of an explicit
object o is always a reference to o.

Let s be a set of explicit classes. References to meet(s) and join(s) are formed from
the names of objects in s. For an example, refer to Figure 3. Note that Painting, Expensive
art object, and Art object are the names of the objects d

0

, d 0 , and d 1 , respectively.
Therefore, a reference to meet(fd

0

; d 0 ; d 1 g) is meet(fPainting, Expensive art object,
Art objectg).

A reference to e inh(c; a

0

) is formed from a reference to c and the name of a

0

. Specifically,
if r is a reference to c and n is the name of a

0

then e inh(r; n) is a reference to e inh(c; a

0

).
Similarly, if r is a reference to c and n is the name of a

0

then a inh(r; n) is a reference to

a inh(c; a

0

).
Arrow references A ref and object references O ref are defined in steps as follows:

Definition 6.2. Object references

We first define the step i arrow references A

i
ref and object references O

i
ref , as follows:
for i = 0:

A

0

ref = Anam ; O

0

ref = Onam [ meet(P(N)) [ join(P(N))

for i ? 0:

A

i
ref = fe inh(r; n) j r 2 O

i\Gamma1
ref

; n 2 Anam g [
fa inh(r; n) j r 2 O

i\Gamma1
ref

; n 2 Anam g

O

i
ref = A

i
ref [ fd(r; n) j r 2 O

i\Gamma1
ref ; n 2 Anam g

We now define the arrow references A ref and the object references O ref :

A ref =

[

i0

A

i
ref ; O ref =

[

i0

O

i
ref \Pi
Intuitively, the object references of step 0 are the object names and the references to
meet classes. The arrow references of step i are the references of exact and approximate
arrows inherited by a class c from an arrow a, where the reference to c was constructed
at step i \Gamma 1. The object references of step i are (i) the arrow references of step i, and
(ii) the references to the to objects of the arrows e inh(c; a

0

), where the reference to c was
constructed at step i \Gamma 1.
The user declares the objects of interest and their relationships through the following

declarations.

Definition 6.3. Declarations

A declaration is one of the following expressions:

ffl indiv(n), where n 2 N . It declares an individual with name n.

ffl hybrid(n), where n 2 N . It declares a hybrid with name n.

ffl arrow(f; l; t), where f 2 Onam , l; t 2 N . It declares an arrow with label l that goes
from an object with name f to an individual or hybrid with name t.

ffl token(n), where n 2 Onam . It declares that the object with name n is a token.

ffl class(n), where n 2 Onam . It declares that the object with name n is a class.

/ 16
ffl in(n; n

0

), where n; n

0

2 Onam . It declares an object with name n to be instance of an
object with name n

0

.

ffl isa(n; n

0

), where n; n

0

2 Onam . It declares an object with name n to be subclass of an
object with name n

0

.

ffl risa(n; n

0

), where n; n

0

2 Anam . It declares an arrow with name n to be restriction
subclass of an arrow with name n

0

. \Pi

We now give the definition of declaration program.

Definition 6.4. Declaration program

We call declaration program or simply program, any set of declarations such that the
following conditions hold:
1. There is no pair of declarations indiv(n), hybrid(n).

2. There is no pair of declarations arrow(f; l; t) and arrow(f; l; t

0

), for t 6= t

0

.
3. For every name n that appears in P ,

ffl if n 2 N then there is a declaration indiv(n) or hybrid(n),

ffl if n = n

0

=l, where l 2 N , then there is a declaration arrow(n

0

; l; t). \Pi

All conditions above are syntactical. Condition 1 expresses that there cannot be an
individual and a hybrid with the same name. Condition 2 expresses that arrow labels
should be unique within their from object. Condition 3 expresses that if a name n appears
in a program then an object with name n should have been declared.
In the SIS system [14], we have developed a higher-level data entry language. Commands
in this higher-level language are translated into a set of declarations which in case they
satisfy the above conditions, they form a declaration program.

6.2. Semantic Structures

The system "interprets" a program in order to build the information base of the application.
To do this, the system needs to create objects, associate names and references to these
objects, and build relations between these objects. The intended interpretation of a program
is defined by means of what we shall call a semantic structure.

Definition 6.5. Semantic structure

A semantic structure is defined by a tuple: S =! O; from; to; Rel; DerObj; Ref ?;

where: Rel =! In; Isa; Risa ?, DerObj =! meet; e inh; a inh ?; and

Ref =! name; label; obj ?; such that:

ffl O is the set of objects of S. O contains three mutually disjoint subsets I , A, H , whose
elements are called individuals, arrows, and hybrids of S, respectively. Additionally,

O contains the sets T , C, and E whose elements are called tokens, classes, and explicit
objects of S, respectively. In what follows, we use the notations shown in Figure 4.

ffl from : A ! O and to : A ! I [ H are total functions that associate each arrow
with its from and to objects.

/ 17
ffl In ` (I \Theta I) [ (A \Theta A) [ (O \Theta H) is a relation expressing the instance relation
between objects.

ffl Isa ` (I \Theta I) [ (A \Theta A) [ (O \Theta H) is a relation expressing the subclass relation
between objects. Isa must satisfy the Isa Rules (see subsection 4.1).

ffl Risa ` A \Theta A is a relation expressing the restriction subclass relationship between
arrows. Risa must satisfy the Risa Rules (see subsection 4.1).

ffl meet : L ! C is a total function that associates a set s 2 L with the class meet(s).

The function meet must satisfy the Meet Rules (see subsection 4.2).

ffl e inh : C \Theta EAC ! AC is a partial function that associates a class c and an explicit
arrow class a

0

with the exact arrow inherited by c from a

0

. The function e inh must
satisfy the Exact Inheritance Rules (see subsection 4.3).

ffl a inh : C \Theta EAC ! AC is a partial function that associates a class c and an explicit
arrow class a

0

with the arrow inherited by c from a

0

. The function a inh must satisfy
the Approximate Inheritance Rules (see subsection 4.3).

ffl name : E ! Onam is a total, one-to-one function that associates an explicit object
with its name. The function name must satisfy the Name Rules (see further on).

ffl label : EA ! ARR is a total function that associates an explicit arrow with its label.

ffl obj : O ref ! O is a partial, surjective function that associates object references to
objects. The function obj must satisfy the Reference Rules (see further on).
NAME RULES

Rule 1: 8 a 2 EA; f 2 Onam ; l 2 ARR, name(from(a)) = f  label(a) = l ) name(a) = f=l
REFERENCE RULES

Rule 1: 8 o 2 E; n 2 Onam name(o) = n ) obj(n) = o

Rule 2: 8 s 2 L; obj(meet(fname(o) j o 2 sg) = meet(s)

8 s 2 L; obj(join(fname(o) j o 2 sg) = join(s)

Rule 3: 8 a

0

2 EAC; c 2 C; r 2 O ref ; n 2 Anam ,

9 e inh(c; a

0

) 2 AC  obj(r) = c  name(a

0

) = n )

obj(e inh(r; n)) = e inh(c; a

0

)  obj(d(r; n)) = to(e inh(c; a

0

))

Rule 4: 8 a

0

2 EAC; c 2 C; r 2 O ref ; n 2 Anam ,

9 a inh(c; a

0

) 2 AC  obj(r) = c  name(a

0

) = n ) obj(a inh(r; n)) = a inh(c; a

0

)

/ 18
We define the reference set of an object o 2 O to be the set of references of o. Specifically,

ref(o) = fr 2 O ref j obj(r) = og. As obj is surjective, ref(o) 6= fg.

It is possible that, though two structures are different, they represent the same semantic
network. In this case, we say that S and S

0

are equivalent.

Definition 6.6. Structure equivalence

Let S, S

0

be two structures with sets of objects O, O

0

, respectively. We say that S and S

0

are equivalent, denoted by S j S

0

, iff there is a bijective mapping F : O ! O

0

such that
the structure that results after replacing every object o 2 O with F(o) is identical to S

0

. \Pi

It is easy to see that j is an equivalence relation over structures.

6.3. Program Semantics

In this subsection we define the models, as well as the semantics of a program.

Definition 6.7. Satisfaction of declarations

Let S be a semantic structure and let D be a declaration. We define S to satisfy D, denoted
by S j= D, as follows:

ffl S j= indiv(n) iff there is i 2 I " E such that name(i) = n.

ffl S j= hybrid(n) iff there is h 2 H " E such that name(h) = n.

ffl S j= arrow(f; l; t) iff there is a 2 A " E such that name(from(a)) = f , label(a) = l,

and name(to(a)) = t.

ffl S j= token(n) iff there is o 2 T " E such that name(o) = n .

ffl S j= class(n) iff there is o 2 C " E such that name(o) = n .

ffl S j= in(n; n

0

) iff In(obj(n); obj(n

0

)).

ffl S j= isa(n; n

0

) iff Isa(obj(n); obj(n

0

)).

ffl S j= risa(n; n

0

) iff Risa(obj(n); obj(n

0

)). \Pi

Definition 6.8. Model of a program

Let P be a program and let M be a semantic structure. We say that M is a model of P if

M satisfies every declaration of P . \Pi

We now introduce an ordering over the models of a program that allows to compare
them with respect to their information content. We will then prove that every program P

has a least model.

Definition 6.9. Model ordering

Let M and M

0

be two models

3

of P . We say that M is less than or equal to M

0

, denoted

M  M

0

, iff there is a mapping F : O ! O

0

such that

3

Symbols of structure components with a prime, such as O

0

, name

0

, denote components of M

0

.

/ 19
1. 8 o 2 E; name(o) = name

0

(F(o)).
2. 8 o 2 O; ref(o) ` ref

0

(F(o)).
3. 8 c; a

0

2 O; if cand cl(c; a

0

) is defined then

fF(x) j x 2 cand cl(c; a

0

)g ` cand cl

0

(F(c); F(a

0

)).
4. 8 o; o

0

2 O; Rel 2 fIn; Isa; Risag; if Rel(o; o

0

) then Rel

0

(F(o); F(o

0

)). \Pi

Proposition 6.1. Let P be a program. The relation "" is a partial ordering over the
models of P (up to model equivalence).

The following theorem is the main theorem of the paper.

Theorem 6.1. Every program P has a least model.

We shall call this least model the semantics of the program if it satisfies the system
constraints (see Section 5).

Definition 6.10. Semantics of a program

Let P be a program and let M be the least model of P . We say that P is a valid program
and M is the semantics of P if M satisfies the system constraints. Otherwise, we say that

P is invalid. \Pi

In the rest of the section, we consider only valid programs P . Moreover, symbols of
structure components, such as O, e inh, refer to the semantics of P .

Proposition 6.2. Let P be a valid program. Then, for each o 2 E, it holds that either

o 2 I, or o 2 A, or o 2 H.

As we have seen in Section 2, each object is either a token or a class. In the semantics
of a program, however, an object o may be neither a token (i.e., o 62 T ) nor a class (i.e.,

o 62 C). This is possible if the object is neither declared as instance of Token or Class

(through the program) nor this is derived. Note that, due to Concreteness Constraint, an
object cannot be both token and class.
In the rest of the section, we prove several properties of exact and approximate inherited
arrows. The following proposition says that each exact inherited arrow is restriction subclass
of its corresponding inherited arrow.

Proposition 6.3. Let P be a valid program. Let a

0

be an arrow class and let c be a subclass
of from(a

0

). Then, the arrow e inh(c; a

0

) is restriction subclass of a inh(c; a

0

).
A consequence of the above proposition is that the arrows e inh(c; a

0

) and a inh(c; a

0

)
share the same instances. This is derived as follows: From the above proposition, Risa Rule
1, and Isa Rule 3, it follows that every instance of e inh(c; a

0

) is also instance of a inh(c; a

0

).
Note that the two arrows have the same from object. Therefore, from Risa Rule 2, every
instance of a inh(c; a

0

) is also instance of e inh(c; a

0

).
The following proposition expresses that if an arrow a 0 is restriction subclass of an arrow

a 1 then e inh(c; a 0 ) coincides with e inh(c; a 1 ), and a inh(c; a 0 ) coincides with a inh(c; a 1 ).

/ 20
Art
object
Risa
Isa
derived Risa

collector
Art

collects
collector
Painting
Only
oil-painting
collector

collects

Only
painting

0 d

Art
object

d 1
c

0
1 0

a 1
a 0
1
0
1

a_inh(c,a )
a_inh(c,a )
e_inh(c,a )
e_inh(c,a )
d(c,a )
d(c,a )

collector
Art

collects
Painting
collector

a'
Only
oil-painting
collector

collects

a_inh(c,a') c
Painting
(a) (b)
Figure 5. (a) Example of inherited arrows that coincide, (b) Example of an explicit arrow
being subclass of an inherited arrow
Proposition 6.4. Let P be a valid program. Let a 0 , a 1 be explicit arrow classes and let

c be a class. If Risa(a 0 ; a 1 ) and Isa(c; from(a 0 )) then e inh(c; a 0 ) = e inh(c; a 1 ) and

a inh(c; a 0 ) = a inh(c; a 1 ).
For an example, refer to Figure 5(a). Intuitively, the arrow a 0 refines the value of the
arrow a 1 . This refinement is expressed by the Risa relation. Thus, the value of the arrow
inherited by c from a 1 is, in general, the same or finer than the value of a 0 (in this example,
it is to(a 0 )). This corresponds to property refinement

4

in object-oriented data models.
The following proposition gives an interesting property of inherited arrows. Specifically,
it expresses that if the arrow inherited by a class c from an arrow a

0

is restriction subclass of
an arrow a, then the arrows inherited by c from a and a

0

coincide. Intuitively, this expresses
that a and a

0

"agree" on c.

Proposition 6.5. Let P be a valid program. Let a

0

be an explicit class and let c be a
subclass of from(a

0

). If the arrow a inh(c; a

0

) is restriction subclass of an explicit arrow a

then e inh(c; a

0

) = e inh(c; a) and a inh(c; a

0

) = a inh(c; a).

The following proposition expresses that there are no explicit objects which are subclasses
of the to objects of exact inherited arrows.

Proposition 6.6. Let P be a valid program. There is no explicit class or meet class d such
that d is subclass of the to object of an exact inherited arrow.

Note that the to object of an explicit arrow is an explicit object and the to object of an
inherited arrow is a meet class. Therefore, from the above proposition and the Arrow Isa
Constraint, it follows that no explicit arrow or inherited arrow can be subclass of an exact
inherited arrow. In contrast, inherited arrows can have subclasses which are explicit arrows
or inherited arrows. An example is shown in Figure 5(b).

4

Also called type refinement.

/ 21
6.4. Discussion

We want to emphasize that though the formalization of Isa, Risa, and Exact Inheritance

could be done using first order logic, the same is not true for Approximate Inheritance.

This is because the Approximate Inheritance Rule 4 that determines the to object of an
approximate inherited arrow, is not monotonic. Obviously, as additional information augments
the candidate class set cand cl(c; a

0

), the to object of the approximate inherited arrow

a inh(c; a

0

) is modified. In other words, a inh(c; a

0

) is computed based on the information
currently in the information base, and it may be changed as new information is added.
Thus, the computation of a inh(c; a

0

) is based on an implicit closed world assumption.
Our inference rules are sound but not complete. For example, there are Isa relations
derived from the following (sound) inference rule:

8 a 1 ; :::; an 2 AC,
Isa(a 1 ; a 2 )  Risa(a 3 ; a 2 )  Isa(a 3 ; a 4 )  Risa(a 5 ; a 4 )  :::  Isa(an\Gamma2 ; an\Gamma1 )  Risa(an ; an\Gamma1 ) 

(8i 2 f3; :::; ng; Isa(from(a 1 ); from(a i )))  Isa(to(a 1 ); to(a n ))

) Isa(a 1 ; an )

that cannot be derived through our inference rules. However, we claim that our inference
rules can give a large number of interesting schema derivations, as shown in [3]. Note
that Risa Rule 5 is a special case of the above inference rule (n = 3). We suspect that
completeness is achieved if Risa Rule 5 is replaced by the above inference rule.
Isa Risa

Non-painting
collector
collector
Art

collects
collects

Non-painting
Art
object
art object

d
d'
Disj(d,Painting)
Join(d,Painting)=d' (a)

flying
flying

Bird
Penguin
Manner
(b)
Children
Cafeteria
Alcoholic
drink
cafeteria

serves
serves
(c)
Figure 6. Expressing exceptions and negative information through our model
Our model can also express exceptions and negative information. For example, it can
express that cafeterias for children do not serve alcoholic drinks, or that penguins do not
fly, through the declarations shown in Figures 6(a) and 6(b). This is because there cannot
be an instance of the arrow class serves of Cafeteria whose from object is instance of

Children cafeteria. Indeed, if there is such an arrow x then x should also be instance of the
arrow class serves of Children cafeteria. However, this is impossible because to(x) cannot
be instance of the class ?

5

. For similar reasons, there cannot be an instance of the arrow
class f lying of Bird whose from object is instance of Penguin.

As another example, our model can express that a non-painting collector is an art
collector that collects art objects other than paintings, through the declarations shown in

5

The class ?, called empty class, is the class whose extension is empty.

/ 22
Figure 6(c). In the figure, the declaration Disj(d; Painting) expresses that the extensions of
the classes Non-painting art object and Painting are disjoint. Additionally, the declaration

join(d; Painting) = d

0

expresses that the extension of the class Art object is the union of
the extensions of the classes Non-painting art object and Painting.

7. Comparison with Related Work

Specialization hierarchies and inheritance play an important role in knowledge representation
systems based on semantic networks and frames [23, 34], as well as in object-oriented
and some extensible database systems [27, 13]. Yet, many of these systems define their
semantics and, in particular, property inheritance, in a procedural way. A detailed comparison
between our approach to inheritance and that of several systems, such as ORION
[5], O 2 [17], ODE [2], POSTGRES [35, 37], EXODUS [10], is given in [3].
In this section, we review systems that define their semantics based on logic. We first
establish a common framework and vocabulary for comparing our data model with related
ones.
Let p be a property of a class c with value d. We say that p is a typing property of c, if c

refers collectively to properties of instances of c with value in d. The typing property p not
only expresses information about the class c and its instances but is also used for checking
the validity of a program through the Typing Constraint: the properties that are referred
collectively by p should have value in d.

The set of typing properties of a class c is called the type of c [11]. A type T is a subtype

of a type T

0

iff T supports all properties of T

0

with the same or more refined value domain
(property refinement). T may have additional properties. If a class c is subclass of a class

c

0

then the type of c should be subtype of the type of c

0

(Subtyping Constraint). Checking
of the Typing and Subtyping Constraints is usually referred to as typechecking.

The typing properties of a class c are either local in c or inherited from superclasses of

c. Thus, the type of a class depends on the inheritance semantics of the particular data
model. In fact, as we show in [3], not all data models satisfy the Subtyping Constraint.
In our data model, typing properties are modeled by arrow classes and, conversely every
arrow class models a typing property. The local typing properties of c are the explicit arrow
classes of c which are not restriction subclasses of any other arrow class. The inherited
typing properties of c are the (approximate) arrows inherited by c.

In our data model, we indicate that a property x is referred to by a typing property

p by declaring that x is an instance of p. Thus, the typing constraint is expressed by
the Arrow In Constraint. As the to object of an inherited arrow is always subclass of the

to object of the original arrow, every program in our data model satisfies the Subtyping
Constraint. Thus, no checking of the Subtyping Constraint is needed. However, our data
model enforces the Arrow Isa Constraint which says that if an arrow a is subclass of an
arrow a

0

then from(a) must be subclass of from(a

0

) and to(a) must be subclass of to(a

0

).
Though it is not required that the Arrow Isa Constraint be enforced by a data model, we feel
that it imposes a discipline that protects against the declaration of erroneous information.
Many object-oriented data models that define their semantics based on logic, such as
[29, 8, 6, 31, 18], do not consider inheritance of typing properties

6

. Yet, in many applications,
reasoning on the structural definitions of the data is a necessity [32]. A property inherited
by a class provides information about the class that may not be obvious by just browsing

6

These data models consider non-monotonic inheritance.

/ 23
through the specialization hierarchy. In our data model, the arrows inherited by a class
and their Isa and Risa relations give useful information about the class semantics (many
examples supporting this claim are given in [3]).
Only
factory
car
Only
factory
boat
Isa

factory
Vehicle
Car

produces Vehicle
Boat

produces produces
factory
Amphibious
Class level
x y

produces

In

Token Level

p p'
p"
c c'
Figure 7. Example of typing properties having same label and same semantics
We will compare our approach to typing property inheritance and typechecking with
that of F-logic [26], terminological languages [7, 33, 28, 4], DOT [41, 42], QUIXOTE [45],
and LOGIN [1]. First, we present common limitations of these data models:
(i) These data models support Risa only implicitly, based on property labels. Specifically,
if two classes c, c

0

have each a property with the same label, then it is assumed
that the two properties have same semantics (for common subclasses of c, c

0

). In our data
model, this is translated to either (a) the two properties are related through Risa, in the
case that c, c

0

are related through Isa, or (b) the two properties are related through Risa

to a common, more generic property, in the case that c, c

0

are not related through Isa. For
example, in Figure 7, it is assumed that the properties p, p

0

have same semantics. In our
data model, this information could have been expressed explicitly by declaring the relations

Risa(p; p

00

) and Risa(p

0

; p

00

).
Isa

Class level
x y

produces

In

Token Level

Car Boat

produces produces p p'
c c'

Car Boat
factory factory
Car-boat
factory
Figure 8. Example of typing properties having same label but not same semantics
Clearly, the approach followed by the other data models may not always give the desir-

/ 24
able results. For an example, refer to Figure 8, where the properties p, p

0

have the same
label produces. In our data model, the properties p, p

0

are not considered to have same semantics
(for common subclasses of c, c

0

), as they are not related through Risa to a common,
more generic property. Thus, the class Car-boat-factory inherits two different properties:
one from p, and another from p

0

. This expresses that a car-boat factory can produce both
cars and boats (and not that a car-boat factory produces only objects that are both car and
boat). In contrast, the other data models will derive that the value of the inherited property
 produces of Car-boat-factory is subclass of both Car and Boat, meaning that a car-boat
factory produces only objects that are both car and boat (clearly, not the desirable result).
Additionally, consider a car-boat factory x with a property produces whose value is y. The
other data models can only express the case where y is both car and boat. This case can
also be expressed in our data model by declaring that the property produces of x is instance
of both properties p and p

0

. However, the case where y is not a boat cannot be expressed
in the other data models, whereas it can be expressed in our data model (by declaring that
the property produces of x is instance of the property p, only).
Additionally, in our data model, derived Risa relations (through the Risa Rules) may
relate properties with different labels. Obviously, this is not possible in the other data
models.
(ii) The other data models do not support Isa relations between properties

7

. Additionally,
the Isa and Risa relations between properties do not interact to refine the value of the
inherited property. For example, in Figure 3, the other data models will not derive that the
value of the property collects inherited by Rich painting collector from Painting collector

is subclass of Expensive art object. Thus, our data model provides a finer value for the inherited
property. Additionally, in our data model, derived Isa and Risa relations between
the inherited property and other properties provide useful information.
(iii) In the other data models, the value of an inherited property is not a known class

8

.
This implies that, in contrast to our data model, no reasoning can be done based on the
"specific" value of the inherited property. For an example, refer to Figure 7. In the other
data models, the value of the inherited property produces of Amphibious factory is an

unknown class (with superclasses Car and Boat). In contrast, in our data model, the value
of the inherited property produces of Amphibious factory is meet(Car; Boat), which is a

known class.
We now present the approaches followed by F-logic, terminological languages, DOT, and
QUIXOTE, with respect to typing property inheritance and typechecking.

F-LOGIC [26]

F-logic is a powerful deductive object-oriented language that supports inheritance of typing
properties. Let c be a class having a typing property with label l. Then, the statement

c[l ) fd 1 ; :::; d n g] asserts that if an instance of c has a property with label l then its value
is instance of each class d 1 ; :::; d n . Typing property inheritance is supported by the F-logic
rules:

(i) If c

0

[l ) D

0

] and Isa(c; c

0

) then c[l ) D

0

].
(ii) If c[l ) D], c[l ) D

0

] then c[l ) D [ D

0

].
The fact that an object o has a non-typing property with label l and the value of the
property is d, is asserted by the statement o[l ! d].

7

We should mention that the Isa relation between properties is supported by TELOS [30], NIAM [43],
and OSAM* [38]. However, these models do not formalize typing property inheritance based on logic.

8

We say that a class is known if it is an explicit class or the meet of explicit classes.

/ 25
For example, in F-logic, the information in Figure 7, is expressed as follows:

Isa relations between classes, are declared as shown in the figure,

V ehicle factory[produces ) fV ehicleg], Only car factory[produces ) fCarg],

Only boat factory[produces ) fBoatg], In(x; Amphibious factory),
x[produces\Gamma ? y].

From the F-logic rules, it is derived that: Amphibious factory[produces )
fCar; Boatg]. This indicates that if an instance of the class Amphibious factory has a
property produces then the value of the property should be an instance of both Car and

Boat. F-logic enforces the Typing constraint. Thus, in Figure 7, if object y is not an
instance of both Car and Boat then the corresponding program is considered to be invalid.
Due to F-logic rule (ii), every F-logic program satisfies the Subtyping Constraint and
no checking of the constraint is needed. No analog to Arrow Isa Constraint exists in
F-logic. For example, in Figure 7, assume that Car is not subclass of V ehicle. In
contrast to our data model, this will not cause any constraint violation in F-logic, and

Only car factory[produces ) fCar; V ehicleg] will be derived.

Terminological Languages

Data models based on terminological languages

9

, such as [7, 33, 28, 4], support the taxonomic
representation of concepts (correspond to individual simple-classes, in our data
model), and typing property inheritance. Concepts are described in terms of other concepts
and necessary and sufficient conditions on their properties (called roles), through a set of
operators. Concepts are put into a hierarchy where a concept is below the concepts it specializes.
Concepts inherit properties and property value constraints from the concepts above
in the hierarchy. Local and inherited property value constraints are combined to refine the
value of the property. In fact, our comments on F-logic with respect to typing property
inheritance, Typing and Subtyping constraints, apply also to terminological languages.
In contrast to our data model, terminological languages do not treat concepts and their
properties in a uniform way. Specifically, they do not consider properties to be concepts,
on their own. Therefore, properties are not organized in an inheritance hierarchy, and do
not have properties. Additionally, terminological languages do not support meta-concepts.
Therefore, they cannot support uniform querying at instance and schema level. We consider
this to be a severe limitation, as adding meaning to the data, should be accompanied by
convenient ways of querying the schema (through a meta-schema).

DOT [41, 42]

The knowledge representation model DOT describes property values using the Isa relation
and supports typing property inheritance. In this model, the In relation is not distinguished
from Isa (for this reason, instead of the term subclass, we will use the term specialization).

For example, in Figure 7, the In relation should be replaced by Isa. The value of a property
with label l of an object c is denoted by c:l. Property inheritance is supported by the DOT
rule: If Isa(c; c

0

) then Isa(c:l; c

0

:l).

In DOT, the information in Figure 7, is expressed as follows:

Isa relations between classes, are declared as shown in the figure,

Isa(V ehicle factory:produces; V ehicle), Isa(Only car factory:produces; Car),
Isa(Only boat factory:produces; Boat), Isa(x; Amphibious factory),
Isa(y; x:produces).

9

Terminological languages are sometimes refer to as description logics.

/ 26
From the DOT rule, it follows that Amphibious factory inherits the property
 produces, and the object Amphibious factory:produces is a specialization of

Car, Boat, V ehicle, Only car factory:produces, Only boat factory:produces, and

V ehicle factory:produces. Additionally, it follows that the object x:produces is a specialization
of Amphibious factory:produces. From this, it follows (due to Isa transitivity)
that y is a specialization of both Car and Boat. However, it will not be derived that

Amphibious factory.produces = meet(Car,Boat), as in our data model.
We would like to mention an important difference between DOT and our data model.
In DOT, in the case that the relations Isa(y; Car) and Isa(y; Boat) have not been explicitly
declared, they are derived from the DOT rule. Therefore, no checking of the Typing
Constraint is needed. In contrast, in our data model, in F-logic, and in terminological
languages, if In(y; Car) and In(y; Boat) have not been explicitly declared then the Typing
Constraint will be violated. Additionally, due to DOT rule, every DOT program satisfies
the Subtyping constraint. Therefore, similarly to F-logic and to terminological languages,
no checking of the Subtyping Constraint is needed.

QUIXOTE [45]

QUIXOTE is a deductive object-oriented language that supports typing property inheritance.
As in DOT, the In relation is not distinguished from Isa. Property inheritance is
supported by the QUIXOTE rules:
(i) if Isa(c; c

0

) then Isa(c:l; c

0

:l), and
(ii) if Isa(c:l; d) and Isa(c:l; d

0

) then Isa(c:l; meet(d; d

0

)).
Rule (i) refines the value of the inherited properties, and rule (ii) refines them further.
For an example, in Figure 7, it will be derived that Isa(Amphibious factory:produces;
meet(Car; Boat)). However, it will not be derived that Amphibious factory:produces =

meet(Car; Boat), as in our data model. Similarly to DOT, every QUIXOTE program satisfies
the Typing and Subtyping Constraints. Thus, no typechecking is needed.

LOGIN [1]

LOGIN is a logic programming language that supports specialization hierarchies and typing
property inheritance through a unification algorithm. Similarly to DOT and QUIXOTE,
LOGIN does not distinguishes between the In and Isa relations. Additionally, similarly to
QUIXOTE, LOGIN assumes that the set of explicit objects with the Isa relation forms a
lattice.
If an object c has a property p with value d then this is expressed with the statement
(called /-term

10

) c(p ) d). Let c

0

be an object. If c

0

has a property p then the
unification of the /-terms c(p ) d) and c

0

(p ) d

0

) gives the /-term meet(fc; c

0

g)(p )

meet(fd; d

0

g)). Otherwise, the unification of the /-terms c(p ) d) and c

0

() gives the /-term
meet(fc; c

0

g)(p ) d). For example, in LOGIN, the information in Figure 7, is expressed as
follows:
The Isa relations between classes, as shown in the figure,

V ehicle factory(produces ) V ehicle), Only car factory(produces ) Car),
Amphibious factory(produces ) Boat), Isa(x; Amphibious factory),
x(produces ) y).

Note that the meet of Only car factory and Only boat factory is Amphibious factory

10

/-terms are in general much more expressive, as they support nested sub-/-terms and coreference

constraints.

/ 27
and the meet of Car and Boat is Amphibious. Therefore, the unification
of Amphibious factory with Only car factory and Only boat factory gives

Amphibious factory(produces ) Amphibious).

LOGIN checks the Typing Constraint, as not all programs satisfy it. For example, in
Figure 7, if y is not declared as a specialization of both Car and Boat the the program
will be considered to be invalid. Note that, in LOGIN, the analogous to both the Arrow
In Constraint and Arrow Isa Constraint is the T#ping Constraint. This is because, LOGIN
does not differentiate between the In and Isa relations. For example, in Figure 7, if Car is
not declared as a specialization of V ehicle then the Typing Constraint will be violated.

8. Conclusions

In this paper, we elaborated on the semantics of an enhanced object-oriented semantic network,
where multiple instantiation, multiple specialization, and meta-classes are supported
for both entities and properties.
The user defines objects and relations between objects through declarations. A set of
declarations that satisfies certain syntactical conditions makes up a program.

Reasoning in our data model is done through a number of (built-in) inference rules

that allow for derivations both at instance and schema level. In addition to the inference
rules, a number of (built-in) system constraints exist for checking the validity of the program.
Through the inference rules, new objects are derived, as well as new In, Isa, and

Risa relations between both explicit and derived objects. In particular, these rules relate
inherited properties to other properties through Isa and Risa relations. Such relations not
only give useful information about the inherited properties but also refine the value of these
properties.
Specifically, each program P has a set of models that satisfy the inference rules and the
declarations in P . We defined a partial ordering between the models of P and proved that

P has a least model, say M . If M satisfies the system constraints then we consider it as
the semantics of P .
In this paper, properties are inherited from classes to subclasses. However, property
inheritance can also take place from a class to its instances. This kind of inheritance is
called instance inheritance. For example, assume that class Art collector has a property

collects with value Art object and let p denote this property. Every instance o of Art
collector can instance-inherit a property from p indicating that o collects art objects. A
possible value of the instance-inherited property is Art object. However, this value can
be refined based on relations of p with other properties. Other information declared by
the user, may be utilized for this purpose as well. We currently investigate new relations
allowing the user to express information about the class of the values of properties of o. In
particular, the new relations should be able to express that (i) all properties of o which are
instances of a property p have value in a class d, and (ii) there is a property of o which is
instance of p and has value in d. This will allow the representation of incomplete knowledge,
as the specific values of the properties of o may be unknown.

/ 28
APPENDIX

Here, we give the proofs of all Propositions and Theorems.

Proposition 6.1 Let P be a program. The relation "" is a partial ordering over the
models of P is a partial order (up to model equivalence).

Proof:

Obviously,  is reflexive and transitive. We will now prove that  is antisymmetric (up to
model equivalence). Let M , M

0

be two models of P such that M  M

0

and M

0

 M . We
will prove that M j M

0

.
In the proof, we will use the usual symbols to denote components of M and the same
symbols with a prime to denote the corresponding components of M

0

.
As M  M

0

, there is a mapping F : O ! O

0

that satisfies the conditions of Definition
6.9. Additionally, as M

0

 M , there is a mapping F

0

: O

0

! O that satisfies the conditions
of Definition 6.9. First, we will show that F

0

is the inverse of F .
Let o 2 O and o

0

= F(o). We will show that F

0

(o

0

) = o. Assume that F

0

(o

0

) = o 1 . As

M  M

0

, it holds that ref(o) ` ref

0

(o

0

). As M

0

 M , it holds that ref

0

(o

0

) ` ref(o 1 ).
Thus, ref(o) ` ref(o 1 ). As ref(o) 6= fg, there is r 2 O ref such that obj(r) = o and

obj(r) = o 1 . As obj is a function, it follows that o = o 1 .
Let o

0

2 O

0

and o = F

0

(o

0

). We can similarly show that F(o) = o

0

. Thus, F

0

is the
inverse of F . From this, it follows that F is a bijective mapping.
From condition 4 of Definition 6.9 and Domain Rule 3, it follows that: o is in I , A, H ,

T , and C iff F(o) is in I

0

,A

0

, H

0

, T

0

, and C

0

, respectively.
Let o 2 E and let o

0

= F(o). As name is a total function on E, name(o) is defined. It
follows from condition 1 of Definition 6.9 that name

0

(o

0

) is defined. Thus, o

0

2 E

0

.
Let a 2 EA and let a

0

= F(a). From the above, it follows that a

0

2 EA

0

. As label

is total function on EA, label(a) is defined. Similarly, label

0

(a

0

) is defined. From Name
Rule 2 and the fact that name(a) = name

0

(a

0

), it follows that label(a) = label

0

(a

0

). Thus,

8 a 2 EA; label(a) = label

0

(F(a

0

)).
From condition 2 of Definition 6.9 and the fact that F = F

0 \Gamma1

it follows that 8 o 2

O; ref(o) = ref

0

(F(o

0

)).
From condition 1 of Definition 6.9 and the fact that obj is function, it follows that

8 s 2 L, F(meet(s)) = meet

0

(F(s)).
We will now prove the following statements:
1. 8 c; a

0

2 O, if e inh(c; a

0

) is defined then F(e inh(c; a

0

)) = e inh

0

(F(c); F(a

0

)) and

F(to(e inh(c; a

0

))) = to

0

(e inh

0

(F(c); F(a

0

)))
2. 8 c; a

0

2 O, if a inh(c; a

0

) is defined then F(a inh(c; a

0

)) = a inh

0

(F(c); F(a

0

)).
Let EM 0 = E [ meet(L). Recall that einh(c; a

0

) is defined iff Isa(c; from(a

0

)). From
this and condition 4 of Definition 6.9, it follows that 8 c 2 EM 0 ; a

0

2 EA, e inh(c; a

0

) is
defined iff e inh

0

(F(c); F(a

0

)) is defined. Similarly, 8 c 2 EM 0 ; a

0

2 EA, a inh(c; a

0

) is
defined iff a inh

0

(F(c); F(a

0

)) is defined.
From condition 2 of Definition 6.9, the Reference Rules, and the fact that obj is a function,
it follows that (i) 8 c 2 EM 0 ; a

0

2 EA, if e inh(c; a

0

) is defined then F(e inh(c; a

0

)) =

e inh

0

(F(c); F(a

0

)) and F(to(e inh(c; a

0

))) = to

0

(e inh

0

(F(c); F(a

0

))), and (iii) 8 c 2

EM 0 ; a

0

2 EA, if a inh(c; a

0

) is defined then F(a inh(c; a

0

)) = a inh

0

(F(c); F(a

0

)).

/ 29
Obviously, the previous statements now hold if we replace EM 0 by EM 1 =

e inh(EM 0 ; EA)[ a inh(EM 0 ; EA). We can continue like that recursively. Thus, we have
proved statements 1, 2.
From condition 3 of Definition 6.9, it follows that 8 c; a

0

2 O; if cand cl(c; a

0

) is defined
then F(cand cl(c; a

0

)) = cand cl

0

(F(c); F(a

0

)). From this and Approximate Inheritance
Rule 4, it follows that F(to(a inh(c; a

0

))) = to

0

(a inh

0

(F(c); F(a

0

))).
From the above, it now easily follows that 8 a 2 A, F(from(a)) = from

0

(F(a)) and

F(to(a)) = to

0

(F(a)).
From condition 4 of Definition 6.9 and the fact that F = F

\Gamma1

it follows that 8 o; o

0

2

O; Rel 2 fIn; Isa; Risag; Rel(o; o

0

) holds iff Rel

0

(F(o); F(o

0

)) holds.
It now follows that M j M

0

. \Pi 2
Theorem 6.1 Every program P has a least model.

Proof:

We will prove the theorem in two steps.

Step 1: We will construct a structure M and show that M is a model of P .
First, according to indiv(), hybrid(), and arrow() declarations of P , we construct objects,
insert them in E, I , H , A, and name them. Then, we relate these objects according
to the isa(), risa(), and in() declarations of P .
We execute all the inference rules except Approximate Inheritance Rule 4, until the
fixpoint (rules with $ are executed in both directions). Call the result F . Then, we
execute Approximate Inheritance Rule 4. This will assign a meet class to the to object
of inherited arrows. Then, we execute again all the inference rules except Approximate
Inheritance Rule 4 until fixpoint. Call the result M . To show that M satisfies all the
inference rules, it is enough to show that 8 c; a

0

2 O, cand(c; a

0

) is the same in F and M .
Assume that there exist c, a

0

such that cand(c; a

0

) is different in F and M . Thus,
there is an explicit arrow a, such that to(a) is in cand(c; a

0

) with respect to M but not
with respect to F . Thus, there a relation Isa(e inh(c; a

0

); a) that is not derived in F and
is derived in M using Exact Inheritance Rule 3. This implies that there is a relation

Risa(a inh(c

0

; a

00

); a 0 ), where c

0

; a

00

; a 0 2 O, which is not derived in F and is derived in M

using the Risa Rules 5 and 6. This relation is needed in order to derive Isa(e inh(c; a

0

); a).

However, if this is the case then Risa(e inh(c

0

; a

00

); a 0 ) should have been derived in F using
Exact Inheritance Rule 3 and Risa Rule 6

11

. From Risa(e inh(c

0

; a

00

); a 0 ), the relation

Isa(e inh(c; a

0

); a) would have been derived in F , in the same way Isa(e inh(c

0

; a

0

); a) is
derived from Risa(a inh(c

0

; a

00

); a 0 ) in M . However, this is impossible because we have
assumed that Isa(e inh(c; a

0

); a) is not derived in F .
Thus, M satisfies all inference rules. Due to conditions 1 and 2 of Definition 6.4 (Declaration
program), name is a function. Additionally, all other constraints of a structure are
satisfied. Thus, M is a model.

Step 2: We will now show that M is the least model of P .
Let M

0

be any model

12

of P . We will show that M  M

0

.

11

Note that Exact Inheritance Rule 3 is a special case of Risa Rule 5 (arrow a1 in Risa Rule 5 is replaced
by e inh(c; a

0

) and the condition on the to objects is eliminated).

12

Symbols of structure components with a prime, denote components of M

0

.

/ 30
It is easy to see from the construction of M that for each o 2 O, there is an object

o

0

2 O

0

with the same reference. We consider the mapping F : O ! O

0

that maps every
object o 2 O to an object o

0

2 O

0

such that ref(o) " ref

0

(o

0

) 6= ;. From the fact that obj is
a function, there is only one such o

0

. Obviously, F satisfies conditions 1 and 2 of Definition
6.9.
From the fact that 8 o 2 O, name(o) = name

0

(F(o)) and the fact that obj is function,
it follows that 8 s 2 L, F(meet(s)) = meet

0

(F(s)).
We will now show the following statements:
1. 8 c; a

0

2 O, if e inh(c; a

0

) is defined then F(e inh(c; a

0

)) = e inh(F(c); F(a

0

)) and

F(to(e inh(c; a

0

))) = to

0

(e inh

0

(F(c); F(a

0

)))
2. 8 c; a

0

2 O, if a inh(c; a

0

) is defined then F(a inh(c; a

0

)) = a inh(F(c); F(a

0

)).
Let EM 0 = E [ meet(L). From the construction of M , if Isa(o; o

0

) holds, for o; o

0

2

EM 0 then Isa

0

(F(o); F(o

0

)) holds. From this and the fact that einh(c; a

0

) is defined iff

Isa(c; from(a

0

)). it follows that 8 c 2 EM 0 ; a

0

2 EA, if e inh(c; a

0

) is defined then

e inh

0

(F(c); F(a

0

)) is defined. Similarly, 8 c 2 EM 0 ; a

0

2 EA, if a inh(c; a

0

) is defined then

a inh

0

(F(c); F(a

0

)) is defined.
From the Reference Rules, and the fact that obj is a function, it follows that (i) 8 c 2

EM 0 ; a

0

2 EA, if e inh(c; a

0

) is defined then F(e inh(c; a

0

)) = e inh

0

(F(c); F(a

0

)) and

F(to(e inh(c; a

0

))) = to

0

(e inh

0

(F(c); F(a

0

))), and (iii) 8 c 2 EM 0 ; a

0

2 EA, if a inh(c; a

0

)
is defined then F(a inh(c; a

0

)) = a inh

0

(F(c); F(a

0

)).
Obviously, the previous statements now hold if we replace EM 0 by EM 1 =

e inh(EM 0 ; EA)[ a inh(EM 0 ; EA). We can continue like that recursively. Thus, we have
proved statements 1, 2.
From the above and the construction of M , it follows that F also satisfies conditions 3
and 4 of Definition 6.9. Thus, Theorem 6.1 follows. \Pi 2
Proposition 6.2 Let P be a valid program. Then, for each o 2 E, it holds that either

o 2 I , or o 2 A, or o 2 H .

Proof:

As M is the least model of P , each object in E has been created through a declaration

indiv(), arrow(), or hybrid(). Therefore, E ` I [ A [H . Statement 1 now follows directly
from the fact that the sets I , A, and H are disjoint. 2
Proposition 6.3 Let P be a valid program. Let a

0

be an arrow class and let c be a subclass
of from(a

0

). Then, the arrow e inh(c; a

0

) is restriction subclass of a inh(c; a

0

).

Proof:

From Exact Inheritance Rule 2, it follows that Risa(e inh(c; a

0

); a

0

). From Approximate
Inheritance Rule 2, it follows that Risa(a inh(c; a

0

); a

0

). Therefore, it follows from Exact
Inheritance Rule 3, Isa(e inh(c; a

0

); a inh(c; a

0

)). As Risa(a inh(c; a

0

); a

0

), it follows from
Risa Rule 6 that Risa(e inh(c; a

0

); a inh(c; a

0

)). \Pi 2
Proposition 6.4 Let P be a valid program. Let a 0 , a 1 be arrow classes and c be a class.
If Risa(a 0 ; a 1 ) and Isa(c; from(a 0 )) then e inh(c; a 0 ) = e inh(c; a 1 ) and a inh(c; a 0 ) =

a inh(c; a 1 ).

/ 31
Proof:

We will first prove that e inh(c; a 0 ) = e inh(c; a 1 ). As Risa(e inh(c; a 1 ); a 1 ) (from Exact
Inheritance Rule 2) and Risa(a 0 ; a 1 ) (from hypothesis), it follows from Exact Inheritance
Rule 3 that Isa(e inh(c; a 1 ); a 0 ). As Risa(e inh(c; a 0 ); a 0 ), it follows from Exact Inheritance
Rule 3 that Isa(e inh(c; a 1 ); e inh(c; a 0 )).
As Isa(e inh(c; a 1 ); a 0 ), Risa(a 0 ; a 1 ), and Risa(e inh(c; a 1 ); a 1 ), it follows from Risa
Rule 6 that Risa(e inh(c; a 1 ); a 0 ). As Isa(e inh(c; a 0 ); a 0 ), it follows from Exact Inheritance
Rule 3, that Isa(e inh(c; a 0 ); e inh(c; a 1 )). Therefore from Exact Inheritance Rule
7, it follows that e inh(c; a 0 ) = e inh(c; a 1 ).
We will now prove that a inh(c; a 0 ) = a inh(c; a 1 ). As e inh(c; a 0 ) = e inh(c; a 1 ), it
follows that cand cl(c; a 0 ) = cand cl(c; a 1 ). Thus, to(a inh(c; a 0 )) = to(a inh(c; a 1 )). Additionally,
from Exact Inheritance Rule 5, it follows that to(a 0 ) 2 cand cl(c; a 1 ). Thus, it
holds that Isa(to(a inh(c; a 1 )); to(a 0 )). From Approximate Inheritance Rule 2, it holds
that Risa(a inh(c; a 1 ); a 1 ). As Risa(a 0 ; a 1 ), it now follows from Risa Rule 5 that

Isa(a inh(c; a 1 ); a 0 ). As Risa(a inh(c; a 0 ); a 0 ), it now follows from Risa Rule 5, that

Isa(a inh(c; a 1 ); a inh(c; a 0 )). Similarly, it follows that Isa(a inh(c; a 0 ); a inh(c; a 1 )).
Therefore from Approximate Inheritance Rule 3, it follows that a inh(c; a 0 ) = a inh(c; a 1 ).

\Pi 2
Proposition 6.5 Let P be a valid program. Let a

0

be an explicit class and let c be a
subclass of from(a

0

). If the arrow a inh(c; a

0

) is restriction subclass of an explicit arrow a

then e inh(c; a

0

) = e inh(c; a) and a inh(c; a

0

) = a inh(c; a).

Proof:

We will first prove that e inh(c; a

0

) = e inh(c; a).

As Risa(e inh(c; a

0

); a inh(c; a

0

)) (Proposition 6.3) and Risa(a inh(c; a

0

); a) (from hypothesis)
, it follows that Risa(e inh(c; a

0

); a). From Exact Inheritance Rule 2, it
holds that Risa(e inh(c; a); a). Thus, from Exact Inheritance Rule 3, it follows that

Isa(e inh(c; a

0

); e inh(c; a)). Similarly, from Exact Inheritance Rule 3, it follows that

Isa(e inh(c; a); e inh(c; a

0

)). Therefore, it follows from Exact Inheritance Rule 7 that

e inh(c; a

0

) = e inh(c; a).

We will now prove that a inh(c; a

0

) = a inh(c; a). As e inh(c; a

0

) = e inh(c; a), it
follows that cand cl(c; a

0

) = cand cl(c; a). Therefore, to(a inh(c; a

0

)) = to(a inh(c; a)).

From hypothesis, it follows that Risa(a inh(c; a

0

); a). From Approximate Inheritance
Rule 2, it holds that Risa(a inh(c; a); a). Thus, from Risa Rule 5, it follows
that Isa(a inh(c; a

0

); a inh(c; a)). Again, from Risa Rule 5, it follows that

Isa(a inh(c; a); a inh(c; a

0

)). Therefore, it follows from Approximate Inheritance Rule
3 that a inh(c; a

0

) = a inh(c; a). \Pi 2
Proposition 6.6 Let P be a valid program. There is no explicit class or meet class d such
that d is subclass of the to object of an exact inherited arrow.

Proof:

Assume that there is such a class d and exact inherited arrow a. To derive that Isa(d; to(a)),

the Exact Inheritance Rule 4 should have been used. This implies that the d should be the

to object of an exact inherited arrow e inh(c; a

0

). However, this is impossible because d is
an explicit class or meet class. \Pi 2

/ 32
References

[1] Ait-Kaci, R. Nasr, LOGIN: A Logic Programming Language with Built-in Inheritance, Journal
of Logic Programming, 3(3), 187-215, (1986).
[2] R. Agrawal, N.H. Gehani, Ode (Object Database and Environment): The Language and the
Data Model, Proc. of the ACM SIGMOD Intern. Conference on the Management of Data,

36-45, (1989).
[3] A. Analyti, P. Constantopoulos, N. Spyratos, Restriction by Specialization and Schema Derivations,
Technical Report TR176, Institute of Computer Science, Foundation for Research and
Technology-Hellas, October, (1996). Available from ftp.ics.forth.gr, tech-reports/1996/
1996.TR176.Specialization Restriction Schema Derivations.ps.gz.
[4] F. Baader, B. Hollunder, KRIS: Knowledge Representation and Inference System, SIGART
Bulletin, 2(3), 8-14 (1991).
[5] J. Banerjee, H. Chou, J.F. Garza, W. Kim, D. Woelk, N. Ballou, H. Kim, Data Model Issues for
Object-Oriented Applications, ACM Transactions on Office Information Systems, 5(1), 3-26,
(1987).
[6] E. Bertino, D. Montesi, Towards a Logical-Object Oriented Programming Language for
Databases, Proc. of the Third Intern. Conference for Databases, pp. 168-183, (1992).
[7] R.J. Brachman, J.G. Schmolze, An Overview of the KL-ONE Knowledge Representation System,
 Cognitive Science, 9(2), 171-216, (1985).
[8] S. Brass, U.W. Lipeck, Semantics of Inheritance in Logical Object Specifications, C. Delobel,
M.Kifer, Y. Masunaga (eds.), Proc. of the 2nd Intern. Conference on Deductive and ObjectOriented
 Databases, pp.411-430, (1991).
[9] G.H.W.M. Bronts, S.J. Brouwer, C.L.J. Martens, H.A. Proper, A Unifying Object Role Modelling
Theory, Information Systems, 20(3), 213-235, (1995).
[10] M.J. Carey, D.J. DeWitt, S.L. Vandenberg, A Data Model and Query Language for EXODUS,

Proc. of the ACM SIGMOD Conference on the Management of Data, 413-423, (1988).
[11] A. Cardelli, P. Wegner, On Understanding Types, Data Abstraction, and Polymorphism, ACM
Computing Surveys, 1(4), 471-522, (1985).
[12] , P.P. Chen, The Entity-Relationship Model: Toward a Unified View of Data, ACM Transactions
on Database Systems, 1(1), pp. 9-36, (1976).
[13] Communications of the ACM, Special Issue on Next Generation Database Systems, 34(10),
(1991).
[14] P. Constantopoulos, M. Doerr, The Semantic Index System: A brief presentation, TR Institute
of Computer Science Foundation for Research and Technology-Hellas, (1994).
Available from http://www.ics.forth.gr/proj/isst/Systems/sis/.
[15] P. Constantopoulos, M. Theodorakis, Y.Tzitzikas, Developing Hypermedia Over an Information
Repository, Proc. of the 2nd Workshop on Open Hypermedia Systems at Hypertext'96, (1996).
[16] P. Constantopoulos, Y.Tzitzikas, Context-Driven Information Base Update, Proc. of the 8th
Intern. Conference on Advanced Information Systems Engineering (CAiSE'96), 319-344, (1996).
[17] O. Deux et al. The story of O 2 , IEEE Transactions on Knowledge and Data Engineering, 2(1),
91-108, (1990).
[18] G. Dobbie, R. Topor, Resolving Ambiguities caused by Multiple Inheritance, Proc. of the Fourth
Intern. Conference on Deductive and Object-Oriented Databases, pp. 265- 280, (1995).
[19] G. Engels, et al., Conceptual Modeling of Database Applications using an Extended ER Model,

Data & Knowledge Engineering, 9(4), pp. 157-204, (1992).

/ 33
[20] Associative Networks, New York: Academic Press, N. Findler (ed.), (1979).
[21] M. Hammer, D. McLeod, Database Description with SDM: A Semantic Database Model, ACM
Transactions on Database Systems, 6(3), pp. 351-386, (1981).
[22] A.H.M. ter Hofstede, Th.P. van der Weide, Expressiveness in Conceptual Data Modelling, Data
& Knowledge Engineering, 10(1), 65-100, (1993).
[23] R. Hull. R. King, Semantic Database Modelling, ACM Computing Surveys, 19(3), 202-260,
(1987).
[24] M. Jarke, S. Eherer, R. Gallersdorfer, M. A. Jeusfeld, M. Staudt, ConceptBase - A Deductive
Object Base Manager, Journal of Intelligent Information Systems, Special Issue on Advances
in Deductive Object-Oriented Databases, 4(2), 167-192, (1995).
[25] M.H. Jamil, L.V.S. Lakshmanan, ORLOG: A Logic for Semantic Object-Oriented Models,

Proc. of the First Intern. Conference on Information and Knowledge Management, pp. 584592,
(1992).
[26] M. Kifer, G. Lausen, J. Wu, Logical Foundations of Object-Oriented and Frame-Based Languages,
 Journal of the Association for Computing Machinery, 42(4), 741-843, (1995).
[27] W. Kim, Object-Oriented Databases:Definition and Research Directions, IEEE Transactions
on Knowledge and Data Engineering, 2(3), 327-341, (1990).
[28] A. Kobsa, First experiences with the SB-ONE knowledge representation workbench in naturallanguage
applications, SIGART Bulletin, 2(3), 70-76 (1991).
[29] K. Lee, S. Lee, An Object-Oriented Approach to Data/Knowledge Modeling Based on Logic,

Proc. of the 1990 IEEE Sixth Intern. Conference, pp.289-294, (1990).
[30] J. Mylopoulos, A. Borgida, M. Jarke, M. Koubarakis, Telos - a Language for Representing
Knowledge about Information Systems, ACM Transactions on Information Systems, 8(4), 325362,
(1990).
[31] F.G. McCabe, Logic and Objects, Prentice Hall, (1992).
[32] M.P. Papazoglou, Unraveling the Semantics of Conceptual Schemas, Communications of the
ACM, 38(9), pp.80-94, (1995).
[33] P.F. Patel-Schneider, D.L. McGuinness, R.J. Brachman, L.A. Resnick, A. Borgida, The CLASSIC
Knowledge Representation System: Guiding Principles and Implementation Rationale,

SIGART Bulletin, 2(3), 108-113 (1991).
[34] J. Peckham, F. Maryanski, Semantic Data Models, ACM Computing Surveys, 20(3), 153-189,
(1988).
[35] L. Rowe, M. Stonebraker, The POSTGRES Data Model, Proc. of the Intern. Conference on
Very Large Data Bases, 83-96, (1987).
[36] Principles of Semantic Networks: Explorations in the Representation of Knowledge, J.F. Sowa
(ed.), Morgan Kaufmann, (1991).
[37] M. Stonebraker, G. Kemnitz, The POSTGRES Next-Generation Database Management System,
 Communications of the ACM, 34(10), 79-92, (1991).
[38] S.Y. W. Su, V. Krishnamurthy, H. Lam, An object-oriented semantic association model
(OSAM*), AI in Industrial Engineering and Manufacturing: Theoretical Issues and Applications,
S. Kumara, et al. (eds.) (1989).
[39] T.J. Teorey, D. Yang, J.P. Fry, A Logical Design Methodology for Relational Databases Using
the Extended Entity-Relationship Model, ACM Computing Surveys, 18(2), 197-222, (1986).
[40] M. Theodorakis, P. Constantopoulos, Context-Based Naming in Information Bases, International
Journal of Cooperative Information Systems, 6(3&4), 269-292, (1997).

/ 34
[41] M. Tsukamoto, S. Nishio, M. Fujio, DOT: A Term Representation using DOT Algebra for
Knowledge-bases, Proc. of the Second Intern. Conference on Deductive and Object-Oriented
Databases, pp. 391-410, (1991).
[42] M.Tsukamoto, S. Nishio, Inheritance Reasoning by Regular Sets in Knowledge-bases with Dot
Notation, Proc. of the Fourth Intern. Conference on Deductive and Object-Oriented Databases,

pp. 246-264, (1995).
[43] G.M.A. Verheijen, J. van Bekkum, NIAM: an Information Analysis Method, Information Systems
Design Methodologies: A Comparative Review, T.W. Olle, et al. (eds.), pp.537-590, (1982).
[44] W.A. Woods, What's in a Link: Foundation for Semantic Networks, Representation and Understanding:
Studies in Cognitive Science, D. Bobrow, A. Collins (eds.), pp. 35-82, (1975).
[45] K. Yokota, H. Tsuda, Y. Morita, Specific Features of a Deductive Object-Oriented Database
Language QUIXOTE, Proc. of the Workshop on Combining Declarative and Object-Oriented
Databases, pp. 89-99, (1993).

