;;; -*- Mode:Lisp; Syntax: Common-Lisp; Package:ONTOLINGUA-USER; Base:10 -*-
#|----------------------------------------------------------------------
THE FRAME ONTOLOGY
Version: 4 (see comments containing "version 4" for changes)
Last Modified: June 30, 1993
This file contains definitions for the frame ontology. It defines
the terms that capture conventions used in many frame systems
(object-centered knowledge representation systems). Since these
terms are built upon the semantics of KIF, one can think of KIF plus
the frame-ontology as a specialized representation language.
One purpose of this ontology is to enable people using different
representation systems to share ontologies that are organized
along object-centered, term-subsumption lines. Translators of
ontologies written in KIF using the frame ontology, such as those
provided by Ontolingua, allow one to work from a common source
format and yet continue to use existing representation systems.
The definitions in this ontology are based on common usage in the
computer science and mathematics literatures. However, there is no
claim that these definitions capture the semantics of existing,
implemented systems in full detail. Nuances of the meaning of terms
that depend on the algorithms for inheritance, for instance, are not
addressed in this ontology. See the acknowledgements at the end of
the file.
This ontology is specified using the definitional forms provided
by Ontolingua. All of the embedded sentences are in KIF 3.0, and
the whole thing can be translated into pure KIF top level forms
without loss of information.
The basic ontological commitments of this ontology are
- Relations are sets of tuples -- named by predicates
- Functions are a special case of relations
- Classes are unary relations -- no special syntax for types
- Extensional semantics for classes -- defined as sets, not descriptions
- No special treatment of slots, just binary relations and unary functions
- KL-ONE style specs are relations on relations
(second-order relations, not metalinguistic or modal)
----------------------------------------------------------------------
Outline
0. Preliminaries: package and theory definitions
1. Basic categories: relations, classes, functions, sets
2. Basic relationships: subclass, instance, subrelation
3. Basic properties of relations: arity, exact-domain, exact-range
4. Special categories of relations: binary, unary, n-ary, single-valued
5. Special relation relationships: inverse, projection,
composition
6. Restrictions on binary relations: domain, domain-of, range, range-of
7. Special restrictions on relations relative to domains:
value-type, slot-value-type, value-cardinality, slot-cardinality, etc.
8. Organizing classes into mutually-disjoint sets.
class-partition, subclass-partition, exhaustive-subclass-partition
9. Special properties and relations on binary-relations:
symmetry, reflexivity, transitivity
10. Derived properties of binary relations:
equivalence, order, one-to-many, etc.
----------------------------------------------------------------------|#
#|----------------------------------------------------------------------
0. Preliminaries: package and theory definitions
A Note on Packages:
This file has been written "in" the ONTOLINGUA-USER package, which uses the
KIF package. The KIF package exports all the symbols defined in the
KIF 3.0 manual. Any exported symbols in the KIF package that overlap
the native lisp namespace will have been imported from there into the
KIF package (see the file packages.lisp). User-defined ontologies can
be defined in the ONTOLINGUA-USER package, or a package that uses the
same packages as the ONTOLINGUA-USER package: (COMMON-LISP, KIF, and
ONTOLINGUA). Thus, in user ontologies, symbols from KIF and the Frame
Ontology may be spelled without the Lisp package prefix. KIF doesn't
include the notion of packages in its mapping from ASCII to nonlinear
form, so this is all the better.
----------------------------------------------------------------------|#
(in-package "ONTOLINGUA-USER")
#|----------------------------------------------------------------------
The Frame-Ontology Theory
The definitions in this file use ontolingua forms, and therefore the
ontology exists as a theory called ONTOLINGUA:FRAME-ONTOLOGY. A user's
ontology can include the frame-ontology using the :included-theories
argument of define-theory.
----------------------------------------------------------------------|#
(define-theory FRAME-ONTOLOGY (kif-relations)
" The frame ontology defines the terms that capture conventions used
in object-centered knowledge representation systems. Since these
terms are built upon the semantics of KIF, one can think of KIF plus
the frame-ontology as a specialized representation language. The
frame ontology is the conceptual basis for the Ontolingua
translators.
One purpose of this ontology is to enable people using different
representation systems to share ontologies that are organized
along object-centered, term-subsumption lines. Translators of
ontologies written in KIF using the frame ontology, such as those
provided by Ontolingua, allow one to work from a common source
format and yet continue to use existing representation systems.
The definitions in this ontology are based on common usage in the
computer science and mathematics literatures. However, there is no
claim that these definitions capture the semantics of existing,
implemented systems in full detail. Nuances of the meaning of terms
that depend on the algorithms for inheritance, for instance, are not
addressed in this ontology. See the acknowledgements at the end of
the file.
This ontology is specified using the definitional forms provided
by Ontolingua. All of the embedded sentences are in KIF 3.0, and
the whole thing can be translated into pure KIF top level forms
without loss of information.
The basic ontological commitments of this ontology are
- Relations are sets of tuples -- named by predicates
- Functions are a special case of relations
- Classes are unary relations -- no special syntax for types
- Extensional semantics for classes -- defined as sets, not descriptions
- No special treatment of slots, just binary relations and unary functions
- KL-ONE style specs are relations on relations
(second-order relations, not metalinguistic or modal)"
:io-package :ontolingua-user)
#|---------------------------------------------------------------------
The following statement only specifies the "current theory" for
this file; it doesn't define the theory.
----------------------------------------------------------------------|#
(in-theory 'FRAME-ONTOLOGY)
#|----------------------------------------------------------------------
1. Basic categories: Relations, Classes, Functions
KIF allows relations of arbitrary and variable arity, defined
as sets of tuples. Classes are unary (one-place) relations.
Functions are relations in which the last item in each tuple is
is the value of the function on the preceding items in the
tuple.
----------------------------------------------------------------------|#
;;; originally defined in the KIF-RELATIONS ontology
(define-class RELATION (?relation)
"A relation is a set of tuples that represents a relationship among
objects in the universe of discourse. Each tuple is a finite, ordered
sequence (i.e., list) of objects. A relation is also an object
itself, namely, the set of tuples. Tuples are also entities in the
universe of discourse, and can be represented as individual objects,
but they are not equal to their symbol-level representation as lists.
By convention, relations are defined intensionally by specifying
constraints that must hold among objects in each tuple. That is, a
relation is defined by a predicate which holds for sequences of arguments
that are in the relation.
Relations are denoted by relation constants in KIF.
A fact that a particular tuple is a member of a relation is denoted
by (<relation-name> arg_1 arg_2 .. arg_n), where the arg_i are the
objects in the tuple. In the case of binary relations, the fact can
be read as `arg_1 is <relation-name> arg_2' or `a <relation-name> of
arg_1 is arg_2.' The relation constant is a term as well, which
denotes the set of tuples.
"
:iff-def (and (set ?relation)
(forall ?tuple
(=> (member ?tuple ?relation)
(list ?tuple))))
; :theory kif-relations
:issues
((:see-also
"In Loom, relations are called relations."
"In CycL, relations are called relationships."
"In KEE, relations are not supported explicitly."
"In Epikit, relations are called relations."
"In Algernon, relations are called slots.")
("What about slots?"
"Slots can be represented with unary functions, binary relations,
or both. In some systems, all slots are unary functions that
take a frame object as an argument and return a set of objects as
the value of the slot. In other systems, slots are always binary
relations that map frames to individual slot fillers. In the
frame ontology, slots are represented by binary relations, some
of which are also unary functions. A single-valued slot may be
used in the functional position of a KIF term expression. In this
case, the constant naming the relation is a KIF function constant.
In other cases, the constant may be a relation constant or a function
constant.")
("What about variable-arity relations?"
"They are allowed, but need to use a sequence variable in the
definition.")))
;;; originally defined in the KIF-RELATIONS ontology
(define-class FUNCTION (?relation)
"A function is a mapping from a domain to a range that associates a
domain element with exactly one range element. The elements of the
domain are tuples, as in relations. The range is a class -- a set of
singleton tuples -- and element of the range is an instance of the
class. Functions are also first-class objects in the same sense that
relations are objects: namely, functions can be viewed as sets of
tuples."
:iff-def (and (relation ?relation)
(forall (?tuple1 ?tuple2)
(=> (member ?tuple1 ?relation)
(member ?tuple2 ?relation)
(= (butlast ?tuple1) (butlast ?tuple2))
(= (last ?tuple1) (last ?tuple2)))))
; :theory kif-relations
:issues ((:see-also single-valued)))
(define-class CLASS (?class)
"A class can be thought of as a collection of individuals.
Formally, a class is a unary relation, a set of tuples (lists) of
length one. Each tuple contains an object which is said to be an
instance of the class. An individual, or object, is any identifiable
entity in the universe of discourse (anything that can be denoted by a
object constant in KIF), including classes themselves.
The notion of CLASS is introduced in addition to the relation
vocabulary because of the importance of classes and types in knowledge
representation practice. The notion of class and relation are merged
to unify relational and object-centered representational conventions.
Classes serve the role of `sorts' and `types'.
There is no first-order distinction between classes and unary
relations. One is free to define a second-order predicate that makes
the distinction. For example, (predicate C) could mean that the unary
relation C should be thought of more as a property than as a
collection of individuals over which one might quantify some
statement. Logically, all such predicates would still be instances of
the metaclass CLASS.
The fact that an object i is an instance of class C is denoted by
the sentence (C i). One may also use the equivalent form
(INSTANCE-OF i C). This is not equivalent to (MEMBER i C).
An instance of a class is not a set-theoretic
member of the class; rather, the tuple containing the instance is a
element of the set of tuples which is a relation.
The definition of a class is a predicate over a single free
variable, such that the predicate holds for instances of the class.
In other words, classes are defined intentionally. Two
separately-defined classes may have the same extension (in this case
they are = to each other). It is possible to define a class by
enumerating its instances, using KIF's set operations. For example,
(define-class primary-color (?color)
(member ?color (set red green blue)))
"
:iff-def (and (relation ?class)
(= (arity ?class) 1))
:issues
((:see-also
"In CycL, classes are called collections."
"In Loom, classes are called concepts."
"In KEE, classes are called classes."
"In Epikit, classes are not explicitly part of the language but are
conventionally denoted by unary relations, or using a binary
relation such as (ISA <instance> <class>).")))
;;; Version 4: moved THING from the KIF ontology into the frame ontology.
;;; It isn't defined in the KIF spec, and mainly serves to clarify the
;;; relationship between sets and classes.
(define-class THING (?x)
"THING is the class of everything in the universe of discourse that
can be in a class. This includes all the relations and objects
defined in the KIF specification, plus all other objects defined in
user ontologies. Every THING is either a set or an individual."
:iff-def (bounded ?x)
:axiom-def (exhaustive-subclass-partition THING
(setof individual set))
:issues (("Why not make THING a primitive?"
"Because it has a well-defined meaning relative to sets;
namely, instances of thing must be capable of being
members of sets (i.e., they are bounded). This definition
is still agnostic about whether classes are sets;
it just says that everything in a class hierarchy must be
bounded."))
)
#|----------------------------------------------------------------------
2. Basic relationships: instance, subclass, subrelation
The basic relationships among classes, functions and other
relations follow from their definitions as sets of tuples and
their semantics as predicates.
----------------------------------------------------------------------|#
(define-relation INSTANCE-OF (?individual ?class)
"An object is an instance-of a class if it is a member of the set
denoted by that class. One would normally state the fact that
individual i is an instance of class C with with the relational
form (C i), but it is equivalent to say (INSTANCE-OF i C).
Instance-of is useful for defining the second-order relations and
classes that are about class/instance networks.
An individual may be an instance of many classes, some of which may be
subclasses of others. Thus, there is no assumption in the meaning
of instance-of about specificity or uniqueness. See
DIRECT-INSTANCE-OF."
:iff-def (and (class ?class)
(holds ?class ?individual))
:equivalent (member (listof ?individual) ?class)
:issues
(("Why not call instance-of `member-of'?"
"Because instance-of is in common usage, and member-of can get confused
with the set and list operators.")
("Why not call instance-of `example-of', or `isa'?" "Because these words
are used to mean many different things in different contexts.")
(:see-also
"In Cyc, instance-of is called #%allInstanceOf."
"In KEE, instance-of is called member.of."
"In Loom, instance-of is implicit in the syntax (unary predicates)."
"In Epikit, there is no notion of instances, although by convention
people use unary relations to denote instance-of relationships.")
(:see-also direct-instance-of)))
(define-function ALL-INSTANCES (?class) :-> ?set-of-instances
"The instances of some classes may be specified extensionally. That
is, one can list all of the instances of the class by definition. For
this case we say (= (all-instances C) (setof V_1 V_2 ... V_n)), where
C is a class and the V_i are its instances.
ALL-INSTANCES imposes a monotonic constraint. Any subclass of C
cannot have any instances outside of the ALL-INSTANCES of C.
Note that this is not indexical or modal: whether something is in
all-instances is a property of the modeled world and does not depend
on the facts currently stored in some knowledge base."
:iff-def (and (instance-of ?class class)
(instance-of ?set-of-instances set)
(forall ?instance
(<=> (member ?instance ?set-of-instances)
(instance-of ?instance ?class))))
:issues (("Is all-instances the inverse of instance-of?"
"No. Instance-of maps indivdual instances to classes,
whereas all-instances maps classes to sets of instances.")
"The name all-instances is borrowed from Cyc."
(:example (all-instances truth-values (setof true false)))))
(define-function ONE-OF (@members) :-> ?class
"ONE-OF is a function for defining classes by enumerating
their instances. It takes a variable number of terms as arguments,
and denotes the class whose instances are exactly those terms.
For example, (one-of yes no) denotes the class containing
the objects called yes or no. (instance-of yes (One-of yes no)) is
true, and (instance-of maybe (one-of yes no) is false. A common
use for one-of is in defining type restrictions. For example,
the relation value-type takes a class as an argument. To specify a
finite set of possible values for a slot, one can use
(value-type ?instance ?slot (one-of a b c))."
:iff-def (forall ?instance
(<=> (instance-of ?instance ?class)
(member ?instance (setof @members)))))
(define-relation SUBCLASS-OF (?child-class ?parent-class)
"Class C is a subclass of parent class P if and only if
every instance of C is also an instance of P. A class may
have multiple superclasses and subclasses. Subclass-of is transitive:
if (subclass-of C1 C2) and (subclass-of C2 C3) then (subclass-of C1 C3).
Object-centered systems sometimes distinguish between a subclass-of
relationship that is asserted and one that is inferred. For example,
(subclass-of C1 C3) might be inferred from asserting (subclass-of C1 C2)
and (subclass-of C2 C3). The functional interfaces to such systems
might call the asserted form something like `parents' and the inferred
form `ancestors'. However, both are logically identical to
subclass-of; distinctions based on inference procedures and the
current state of the knowledge base are not captured in this
ontology."
:iff-def (and (instance-of ?parent-class class)
(instance-of ?child-class class)
(forall ?instance
(=> (instance-of ?instance ?child-class)
(instance-of ?instance ?parent-class))))
:axiom-constraints (transitive-relation subclass-of)
:issues
((:see-also direct-subclass-of)
(:see-also
"In CycL, subclass-of is called #%allGenls because it is a slot from
a collection to all of its generalizations (superclasses)."
"In the KL-ONE literature, subclass relationships are also called
subsumption relationships and ISA is sometimes used for subclass-of.")
("Why is it called Subclass-of instead of subclass or superclass?"
"Because the latter are ambiguous about the order of their arguments. We
are following the naming convention that a binary relationship is read
as an english sentence `Domain-element Relation-name Range-value'.
Thus, `person subclass-of animal' rather than `person superclass
animal'.")))
(define-relation SUPERCLASS-OF (?parent-class ?child-class)
"Superclass-of is the inverse of the subclass-of relation.
It is useful to create an explicit inverse because
there are efficient ways to assert and query superclass and subclass
relationships separately.
In Cyc, superclass-of is called #%allSpecs because it is a slot from
a collection to all of its specializations (subclasses)."
:iff-def (subclass-of ?child-class ?parent-class)
:axiom-def (inverse superclass-of subclass-of)
:issues
("We could have named superclass-of something like
`has-subclasses' or `subclasses'. These look better when displayed as
slots on frames. We opted for `superclass-of' because it is less
ambiguous. Frame editors and related tools are free to alias this
relation."))
(define-relation SUBRELATION-OF (?child-relation ?parent-relation)
"A relation R is a subrelation-of relation R' if, viewed as sets,
R is a subset of R'. In other words, every tuple of R is also a tuple of
R'. In some more words, if R holds for some arguments arg_1, arg_2, ...
arg_n, then R' holds for the same arguments. Thus, a relation and its
subrelation must have the same arity, which could be undefined.
In CycL, subrelation-of is called #%genlSlots."
:iff-def (and (instance-of ?child-relation relation)
(instance-of ?parent-relation relation)
(forall ?tuple
(=> (member ?tuple ?child-relation)
(member ?tuple ?parent-relation))))
:equivalent (=> (holds ?child-relation @arguments)
(holds ?parent-relation @arguments))
:constraints (=> (defined (arity ?parent-relation))
(= (arity ?child-relation) (arity ?parent-relation)))
:issues (("Do the arities of the relations have to match?"
"No. Used to be defined this way, but it was an
unnecessary restriction. If the parent relation
has a (fixed) arity, then the child's arity must
be equal to it. However, the child could be of
fixed arity and the parent undefined (variable) arity.")))
(define-relation DIRECT-INSTANCE-OF (?individual ?class)
"An individual i is an DIRECT-INSTANCE-OF class C if i is an
instance-of C and there is no other subclass of C defined in the
current ontology of which i is also an instance-of. Such a class C is
a `minimal' or `most-specific' parent class for the individual i. The
direct class is not necessarily unique; an individual can have several
most-specific classes. Note that this relation is indexical -- its
truth depends the contents of the current knowledge base rather than
the world.
The distinction between INSTANCE-OF and DIRECT-INSTANCE-OF is not
the same as the relationship between asserting instance-of directly
and having the system infer it. The meanings of both instance-of and
direct-instance-of, and every other object-level relation in a
knowledge base mean, are independent of whether they are asserted
explicitly or inferred.
Cyc makes the distinction between #%instanceOf and #%allInstanceOf.
#%allInstanceOf means the same thing as INSTANCE-OF in our
ontology. However, #%instanceOf is subtlely different from
direct-instance-of. When someone asserts (#%instanceOf i C) to
Cyc, it means the same thing as (#%allInstanceOf i C), but Cyc creates
a pointer between an instance unit and a collection unit. Later,
someone may define a subclass C_sub of C and assert (#%instanceOf i
C_sub), and this is consistent with the earlier #%instanceOf
assertion.
Direct-instance-of is useful for maintaining a class hierarchy
in a modular, canonical form. It is defined here because some systems
maintain direct-instance-of and some applications depend on this."
:def (instance-of ?individual ?class)
:default-constraints ; this generates a default rule
; using KIF's CONSIS operator
(not (exists ?other-class
(and (not (= ?other-class ?class))
(instance-of ?individual ?other-class)
(subclass-of ?other-class ?class))))
:issues
("Some frame-oriented systems organize instance/class relationships in a
way that takes advantage of the direct-instance-of information.
Loom, for instance, runs a classifier procedure that determines the
direct-instance-of relationship, given some instance-of assertions
and knowledge about the subclass-of relationships among existing
terms."))
(define-relation DIRECT-SUBCLASS-OF (?child-class ?parent-class)
"DIRECT-SUBCLASS-OF is the same thing as SUBCLASS-OF with an additional
constraint: there is no other class `between' child and parent class in
the subclass hierarchy of the current knowledge base. In other words, if
(direct-subclass-of C P) then there is no other defined class P' in
the current knowledge base that is a superclass of C and also a
subclass of P.
Note that this relation is indexical -- its truth depends the
contents of the current knowledge base rather than the world. There
certaintly might be a set of tuples in the world that is a superset of
C and a subset of P, but it can't have been defined as a class in the
current knowledge base if (direct-subclass-of C P) is true for that
knowledge base.
The direct-subclass-of of a class is not necessarily unique.
In systems with term classifiers, direct-subclass-of relations are
usually inferred, rather than asserted."
:def (subclass-of ?child-class ?parent-class)
:default-constraints ; this generates a default rule
; using KIF's CONSIS operator
(not (exists ?other-class
(and (not (= ?other-class ?child-class))
(not (= ?other-class ?parent-class))
(subclass-of ?child-class ?other-class)
(subclass-of ?other-class ?parent-class))))
)
#|----------------------------------------------------------------------
3. Basic properties of relations: arity, exact-domain, exact-range
----------------------------------------------------------------------|#
(define-function ARITY (?relation) :-> ?n
"Arity is the number of arguments that a relation can take. If a
relation can take an arbitrary number of arguments, its arity is
undefined. For example, a function such as `+' is of undefined arity;
its last formal argument is specified with a sequence variable. The
arity of a function is one more than the number of arguments it can
take, in keeping with the unified treatment of functions and
relations. The arity of the empty relation (i.e., with no tuples) is
undefined."
:iff-def (and (instance-of ?relation relation)
(not (empty ?relation))
(instance-of ?n integer)
(forall ?tuple
(=> (member ?tuple ?relation)
(= (length ?tuple) ?n))))
:issues
("KIF 2.2 doesn't require one to declare the arity of a relation,
nor does it require one to use a relation with a consistent number
of arguments. However, relations defined with Ontolingua are always
of fixed arity, which Ontolingua asserts as part of the translation.
This is to facilitate sharing over implemented frame systems, most
of which do not support variable-arity relations."
"Asserting that the arity is undefined is not the same as saying that
the arity is unconstrained. The arity can only exist if the relation
is of fixed arity. Asserting (undefined (arity ?relation)) means
that one knows that the relation has variable arity."))
(define-function EXACT-DOMAIN (?relation) :-> ?domain-relation
"The EXACT-DOMAIN of a relation is a relation whose tuples (all of them)
are mapped by the relation to instances of the range. A
binary relation R is defined as a set of tuples of form <x,y>. If we
say (= (exact-domain R) D) then all of the
x's must be in the class D, and for each instance x of class D, the
relation maps x to some y. The exact-domain of a relation of arity other
than 2 is the relation that represents a cross product. For example,
the notation F:A x B -> C, means that function F maps pairs <a,b> onto
c's where a is an instance of A, b is an instance of B, and c is an
instance of C. The exact-domain of F is the set of pairs <a,b> that
occur in some triple <a,b,c> in F.
Some treatments of functions define a function as a mapping from a
domain to a range. This ontology treats functions as relations, and
relations as sets of tuples. Thus, functions and relations are not
defined relative to domains and ranges; the exact-domain is a function
of the set of tuples. It follows that all functions are `total' with
respect to their exact-domains and `onto' with respect to their exact-ranges.
The exact-domain of a variable-arity relation is another variable-arity
relation; the lengths of the tuples in the exact-domain of R is one less
than the corresponding tuples in the relation R. The exact-domain of a unary
relation, or a relation that contains a tuple of length one, is undefined."
:iff-def (and (instance-of ?relation relation)
(instance-of ?domain-relation relation)
(forall (?tuple)
(=> (member ?tuple ?relation)
(not (empty (butlast ?tuple)))))
(forall (?tuple @args)
(<=> (holds ?domain-relation @args)
(and (member ?tuple ?relation)
(= (listof @args) (butlast ?tuple))))))
; :lambda-body (cond ((instance-of ?relation relation)
; (setofall (butlast ?tuple)
; (and (member ?tuple ?relation)
; (not (empty (butlast ?tuple)))))))
;
; :constraints (instance-of ?domain-relation relation)
:issues
((:see-also domain exact-range)
("Doesn't it have to be a class?"
"Only for binary relations.")
("Why require that the complete domain be included; why not allow for
a superset of the true domain?"
"We need to know the exact-domain of a relation for describing
properties such as reflexivity. Supersets of an exact
domain are specified with DOMAIN.")))
(define-function EXACT-RANGE (?relation) :-> ?range-class
"A relation maps elements of a domain onto element of a range.
For each tuple in the relation, the last item is in the range,
and the tuple formed by the preceeding items is in the domain.
The EXACT-RANGE is the class whose instances are exactly those that
appear in the last item of some tuple in the relation.
The EXACT-RANGE of a relation is always a class, while the
exact-domain may be a relation of any arity, including variable
arity (e.g., the + function can take 0 or more arguments, but its
exact-range is some subset of the class NUMBER).
In KIF, functions are a special case of relations. This
definition is based on relational terminology, but applies to
functions as well. In discussions of functions, one often sees the
notation f:X -> Y. Usually, X and Y are sets of elements x and y. In
this ontology, the unary function f is also a binary relation, where X
is the exact-domain of f and Y is the exact-range of f. This
generalizes to cross products. For the function g:A x B x C -> D, the
domain is the ternary relation of tuples (a, b, c) and the range is
the unary relation of tuples (d). The exact-range of just those d's
that are actually the value of g on some (a, b, c).
The EXACT-RANGE of a function is unique, and every function f
maps (exact-domain f) onto (exact-range f). Sometimes the EXACT-RANGE
of f is called the ``image of (exact-domain f) under d.''
The relation RANGE is a constraint on the possible values of a
function. It is a superclass of the EXACT-RANGE, and is not unique."
:iff-def (and (instance-of ?relation relation)
(instance-of ?range-class class)
(forall ?range-instance
(<=> (instance-of ?range-instance ?range-class)
(exists ?tuple
(and (member ?tuple ?relation)
(= (last ?tuple) ?range-instance))))))
:issues (("Some books define the range of the function as the set Y
in f:X->Y. Why is the range defined as a subset of Y?"
"To unify relations and functions, we conceptualized
functions as sets rather than as mappings (as in category
theory). In the category theory sense, the range
of function f is not a property of the function but of a
particular mapping f:X -> Y. This mapping cannot be
specified without its domain and range. In the set
theoretic account of this ontology, the function is
defined extensionally and the range follows.")
(:see-also range exact-domain)))
(define-relation TOTAL-ON (?relation ?domain-relation)
"A relation R is TOTAL-ON a domain class C if there are tuples in the
relation (x,y) for every instance x of C. If the domain is a relation D,
it represents a Cartesian product, and the relation is total on D
if for every tuple (x1, x2, ... xn) in D there is a tuple (x1, x2, ... xn, y)
in R."
:iff-def (subrelation-of (exact-domain ?relation) ?domain-relation))
(define-relation ONTO (?relation ?range-class)
"A relation R is ONTO range class C iff for every element y in C there
is a tuple in R (x1, x2, ... y)."
:iff-def (subclass-of (exact-range ?relation) ?range-class))
#|----------------------------------------------------------------------
4. Special categories of relations: binary, unary, n-ary, single-valued
----------------------------------------------------------------------|#
(define-class N-ARY-RELATION (?relation)
"An N-ary relation is a relation with some FIXED arity."
:iff-def (and (instance-of ?relation relation)
(not (undefined (arity ?relation)))))
;;; originally defined in the KIF-RELATIONS ontology
(define-class UNARY-RELATION (?relation)
"A unary relation is a relation of arity 1.
Unary relations are the same thing as classes.
In this ontology there is no logical distinction between a
monadic predicate (unary relation) and a type (class)."
:iff-def (and (instance-of ?relation relation)
(= (arity ?relation) 1))
:issues ((:see-also class)))
;;; originally defined in the KIF-RELATIONS ontology
(define-class BINARY-RELATION (?relation)
"A binary relation maps instances of a class to
instances of another class. Its arity is 2.
Binary relations are often shown as slots in frame systems."
:iff-def (and (instance-of ?relation relation)
(= (arity ?relation) 2)))
;;; originally defined in the KIF-RELATIONS ontology
(define-class UNARY-FUNCTION (?f)
"A unary function is a functional mapping from instances of a
class to instances of another class. It is a relation of arity 2.
Binary relations are often shown as slots in frame systems."
:iff-def (and (instance-of ?f binary-relation)
(instance-of ?f function)))
(define-relation SINGLE-VALUED (?relation)
"Single-valued relations are binary relations that are functional.
The predicate SINGLE-VALUED is useful for asserting that a slot will
have at most one value without using a function-defining form. It is
restricted to binary relations because it is defined only for slots.
Note that specifying a relation as single valued says that it is
function for all subclasses of its domain."
:iff-def (and (instance-of ?relation binary-relation)
(instance-of ?relation function))
:issues (:see-also locally-single-valued value-cardinality many-to-one))
#|----------------------------------------------------------------------
5. Special relation relationships: inverse, projection,
composition
----------------------------------------------------------------------|#
;;; originally defined in the KIF-RELATIONS ontology
(define-function INVERSE (?binary-relation) :-> ?inverse-relation
"One binary relation is the inverse of another if they are
equivalent when their arguments are swapped."
:iff-def (and (instance-of ?binary-relation binary-relation)
(instance-of ?inverse-relation binary-relation)
(<=> (holds ?binary-relation ?x ?y)
(holds (inverse ?binary-relation) ?y ?x)))
:issues
("Note that INVERSE is a function. It is possible to have more
than one relation constant naming the inverse of a relation, but they
are all = to each other."))
(define-function PROJECTION (?relation ?column) :-> ?projection-relation
"The projection of an N-ary relation on column i is the class whose
instances are the ith items of each tuple in the relation."
:iff-def (and (instance-of ?relation n-ary-relation)
(instance-of ?column positive-integer)
(=< ?column (arity ?relation))
(instance-of ?projection-relation class)
(forall ?projection-instance
(<=> (instance-of ?instance ?projection-relation)
(exists ?tuple
(and (member ?tuple ?relation)
(= (nth ?tuple ?column) ?instance)))))))
;;; originally defined in the KIF-RELATIONS ontology
(define-function COMPOSITION (?R1 ?R2) :-> ?R3
"The composition of binary relations R_1 and R_2 is a relation R_3
such that R_1(x,y) and R_2(y,z) implies R_3(x,z)."
:constraints (and (instance-of ?R1 binary-relation)
(instance-of ?R2 binary-relation)
(instance-of ?R3 binary-relation))
:lambda-body (setofall (listof ?x ?z)
(exists ?y
(and (holds ?R1 ?x ?y)
(holds ?R2 ?y ?z)))))
;;; version 4: new slot on relations
(define-relation COMPOSITION-OF (?binary-relation ?list-of-relations)
"A binary relation R is a COMPOSITION-OF a sequence of binary relations
R_1, R_2, ... R_N iff there exists a relation R' that is a COMPOSITION-OF
the sequence R_1 ... R_{N-1}, and R is the (COMPOSITION R_1 R').
Relations are composed right to left. For example,
if (composition-of R (listof a b c d))
then R = (composition d (composition c (composition b a))).
When the relations are unary functions, the sequence corresponds to
nested parentheses in functional notation. For example, if F is
composition-of functions a, b, and c, (COMPOSITION-OF F (listof a b c))
means (f ?x) is equal to (a (b (c ?x)))."
:iff-def (and (binary-relation ?binary-relation)
(list ?list-of-relations)
(not (null ?list-of-relations))
(=> (item ?r ?list-of-relations)
(binary-relation ?r))
(or
;; (composition-of a (listof a))
(and (single ?list-of-relations)
(= ?binary-relation (first ?list-of-relations)))
;; (composition-of (composition b a) (listof a b))
(and (double ?list-of-relations)
(= ?binary-relation
(composition (second ?list-of-relations)
(first ?list-of-relations))))
;; (composition-of R (listof a b c d)) =>
;; R = (composition d (composition c (composition b a)))
(exists ?left-sub-relation
(and (= ?binary-relation
(composition (last ?list-of-relations)
?left-sub-relation))
(composition-of ?left-sub-relation
(butlast ?list-of-relations))))))
:issues ((:example
(=> (composition-of R (listof a b c d))
(= R (composition d (composition c (composition b a))))))))
;;; version 4 : rewrote to use composition-of. Same meaning as before
(define-function COMPOSE (@binary-relations) :-> ?composed-relation
"arbitrary-arity version of COMPOSITION. The left-to-right
argument order composes relations outside-in.
e.g., (COMPOSE f g h) means (composition h (composition g f)).
If the relations are unary functions, then the composition order
corresponds to nested function terms. For example, if f,g,h are functions,
then (value (COMPOSE f g h) ?arg) is equivalent to (f (g (h ?arg)))."
:iff-def (composition-of ?composed-relation (listof @binary-relations))
:constraints (and (forall ?R
(=> (item ?R (listof @binary-relations))
(instance-of ?R binary-relation)))
(instance-of ?composed-relation binary-relation)))
(define-relation ALIAS (?relation-1 ?relation-2)
"Alias is a way to specify that two relations have
the same extension. It is logically equivalent to the =
relation, except that it is restricted to relations."
:iff-def (and (instance-of ?relation-1 relation)
(instance-of ?relation-2 relation)
(= ?relation-1 ?relation-2))
)
#|----------------------------------------------------------------------
6. Restrictions on relations: domain, range, value-restrictions
----------------------------------------------------------------------|#
(define-relation DOMAIN (?relation ?restriction)
"DOMAIN is short for ``domain restriction''. A domain restriction
of a binary relation is a constraint on the exact-domain of the
relation. A domain restriction is superclass of the exact-domain;
that is, all instances of the exact-domain of the relation are also
instances of the DOMAIN restriction. Thus, the DOMAIN of a relation
is not unique.
In an ontology, specifying a domain restriction of a binary
relation is a way to specify partial information about the objects
to which the relation applies. For example, one can state that
favorite-beer is a relation from beer drinkers to beers as
(domain favorite-beer person). This says that all people who have
a favorite-beer are instances of person, even though there may be some
instances of person who do not have a favorite beer.
Representation systems can use these specifications to classify terms and
check integrity constraints."
:iff-def (and (instance-of ?relation binary-relation)
(instance-of ?restriction class)
(subclass-of (exact-domain ?relation) ?restriction))
:issues ((:see-also
"In Cyc, domain is called makesSenseFor.")))
(define-relation DOMAIN-OF (?domain-class ?binary-relation)
"DOMAIN-OF is the inverse of the DOMAIN relation;
i.e., (domain-of D R) means that D is a domain restriction of R.
A DOMAIN-OF a binary relation is a class to which the binary relation
can be meaningfully applied; i.e., it is possible, but not assured,
that there are instances d of D for which R(d,v) holds. Of course,
every instance i for which R(i,v) does hold is an instance of D.
One interpretation of the assertion (DOMAIN-OF my-class my-relation)
is `the slot my-relation may apply to some of the instances of
my-class.' A less precise but common paraphrase is `my-class has the
slot my-relation'. User interfaces to frame and object systems often
have some symbol-level heuristic for showing slots that `have' or `make
sense for' the class. Keep in mind that DOMAIN-OF is a constraint on
the logically consistent use of the relation, not a relevance
assertion. There are many classes that are DOMAINs-OF a given
relation; namely, all superclasses of the exact-domain. (THING, for
example, is a DOMAIN-OF all relations.) Therefore, it is quite possible
that most of the instances of a domain-of a relation do not `make
sense' for that relation.
Whereever one uses (domain-of D R) it is equivalent to adding D to
the list of domain restrictions on the definition of R. In other words
if R was defined as (define-relation R (?x ?y) :def (and (A ?x) (B ?y)))
then the statement (DOMAIN-OF D R) has the same meaning as changing the
definition to (define-relation R (?x ?y) :def (and (A ?x) (D ?x) (B ?y))).
For modularity reasons DOMAIN-OF is preferred only when R is not given its
own definition in an ontology."
:iff-def (domain ?binary-relation ?domain-class)
:issues ((:see-also
"In Cyc, domain-of is called canHaveSlots.")))
(define-relation RANGE (?relation ?type)
"RANGE is short for ``range restriction.''
Specifying a RANGE restriction of a relation is a way to constrain
the class of objects which participate as the last argument to the
relation. For any tuple <d1 d2 ...dn r> in the relation, if class T is a
RANGE restriction of the relation, r must be an instance of T.
RANGE restrictions are very helpful in maintaining ontologies.
One can think of a range restriction as a type constraint on the value
of a function or range of a relation. Representation systems can use
these specifications to classify terms and check integrity
constraints.
If the restriction on the range of the relation is not captured by
a named class, one can use specify the constraint with a predicate that
defines the class implicitly, coerced into a class. For example,
(kappa (?x) (and (prime ?x) (< ?x 100)))
denotes the class of prime numbers under 100.
It is consistent to specify more than one RANGE restriction for a
relation, as long as they all include the EXACT-RANGE of the relation.
Note that range restriction is true regardless of what the restricted
relation is applied to. For class-specific range constraints, use
slot-value-type."
:iff-def (and (instance-of ?relation relation)
(instance-of ?type class)
(subclass-of (exact-range ?relation) ?type))
:issues ((:see-also slot-value-type)))
(define-relation RANGE-OF (?type ?relation)
"The inverse of RANGE. A class C is a range-of
a relation R if C is a superclass-of the exact range of R."
:iff-def (range ?relation ?type))
(define-relation NTH-DOMAIN (?relation ?n ?type)
"Domain restrictions generalized to n-ary relations.
The sentence (nth-domain rel 3 type-class) says that
the 3rd element of each tuple in the relation REL is
an instance of type-class."
:iff-def (and (n-ary-relation ?relation)
(positive-integer ?n)
(class ?type)
(forall ?tuple
(=> (member ?tuple ?relation)
(and
(>= (length ?tuple) ?n)
(instance-of (nth ?tuple ?n) ?type)))))
:issues (("What about nth-range?"
"A range restriction of a function is the same thing as
an nth-domain restriction on the last element of each
tuple, i.e., the values of the function. Therefore
there is no nth-range relation.")))
;;; version 4: Added.
(define-function RELATION-UNIVERSE (?relation) :-> ?type-class
"A relation-universe of a relation of any arity is a class
from which is drawn every item in every tuple of the relation.
Like EXACT-DOMAIN, it is exactly those items and no other.
Thus, to state that the universe of a relation is covered by
some class, one can state that the relation-universe is a subclass
of the covering class."
:iff-def (and (relation ?relation)
(class ?type-class)
(forall (?x)
(<=> (exists ?tuple
(and (member ?tuple ?relation)
(item ?x ?tuple)))
(instance-of ?x ?type-class))))
:issues (:see-also UNIVERSE))
#|----------------------------------------------------------------------
7. Special restrictions on relations relative to domains:
value-type, slot-value-type, value-cardinality, slot-cardinality, etc.
In many frame-based systems, there are expressions for describing
constraints on the values or types of slots relative to a class.
Slots are binary relations or unary functions (single-valued
slots). These expressions specify restrictions on slot values
local to a class. For example, within the description of a class,
a slot may be declared to be single valued and its values of some
type. These declarations are only in force when the slot is
applied to instances of the class. Thus, they are not equivalent
to general constraints on binary relations, such as single-valued
and range. The relations below offer primitives for describing
restrictions on binary relations that are relative to particular
domains.
Included in the family of relations defined below are primitives
for handling KL-ONE style concept definitions, in which the
meanings of classes (concepts) can be defined with restrictions on
their slots (roles).
First we will define the relationships between slots and
individual domain instances. These relations might show up in
definitions as constraints on the instances of a class. By
convention the names of these relations refer to ``values''.
The ``lot'' versions will be defined following the ``value''
relations.
----------------------------------------------------------------------|#
;;; Version 4: removed VALUES from the ontology, replaced it with HAS-VALUE,
;;; which was formerly defined in the KL-ONE ontology.
(define-relation HAS-VALUE (?instance ?binary-relation ?value)
"HAS-VALUE is a way to state that an instance has a value on some slot.
Its third argument is a single value; one may use HAS-VALUE repeatedly
for each value of a multiple-valued relation.
For example, (HAS-VALUE i R v_1), (HAS-VALUE i R v_2) means that
slot R applied to domain instance i maps to values v_1 and v_2.
In other words, R(i,v_1) and R(i,v_2) hold.
There is no closed-world assumption implied; there may be
other values for the specified slot on a given domain instance."
:iff-def (and (instance-of ?binary-relation binary-relation)
(holds ?binary-relation ?instance ?value))
:issues ((:see-also all-values)
("This is for completeness. In definitions, one could
say (slot ?instance value) instead of
(has-value ?instance slot value).")
(:version-4
"In version 3, this was called VALUES and took a set of
values as a third argument. That didn't make a lot of
sense, since there could be many different sets (all
subsets of the actual set of values), all of which are the
value of this relation on the same instance and class.
The new form also makes it clearer that there is no
closed-world assumption.")))
(define-function ALL-VALUES (?instance ?binary-relation) :-> ?set-of-values
"ALL-VALUES is a way to state all of the the values of a slot
on an instance. Its third argument is a set. If all-values are given
for a slot on an instance, there cannot be any other values for that
slot on that instance. For example, (= (ALL-VALUES i R) (setof v_1 v_2 v_3))
means that R(i,v_1), R(i,v_2), and R(i,v_3) hold, and there is no other
unique v_i for which R(i,v_i) holds."
:iff-def (and (instance-of ?binary-relation binary-relation)
(forall ?value
(<=> (member ?value ?set-of-values)
(holds ?binary-relation ?instance ?value))))
:issues ((:version-4
"In version 3, this was incorrectly defined as a relation.
It should have been a function all along. The definition
remains the same.")))
(define-relation VALUE-TYPE (?instance ?binary-relation ?type)
"The VALUE-TYPE of a binary relation R with respect to a given
instance d is a constraint on the values of R when R is applied to d.
The constraint is specified as a class T such that when R(d,t) holds,
t is an instance of T."
:iff-def (and (instance-of ?binary-relation binary-relation)
(instance-of ?type class)
(forall ?value
(=> (holds ?binary-relation ?instance ?value)
(instance-of ?value ?type))))
:issues ("VALUE-TYPE is convenient for specifying type restrictions
on slots relative to a class by using the class's instance
variable."
(:see-also SLOT-VALUE-TYPE)))
(define-relation SAME-VALUES (?instance ?slot1 ?slot2)
"Two binary relations R1 and R2 have the SAME-VALUES on instance i
if whenever R1(i,v) holds for some value v, then R2(i,v) holds for
the same domain instance i and value v."
:iff-def (and (binary-relation ?slot1)
(binary-relation ?slot2)
(<=> (holds ?slot1 ?instance ?value)
(holds ?slot2 ?instance ?value))))
(define-function VALUE-CARDINALITY (?instance ?binary-relation) :-> ?n
"The VALUE-CARDINALITY of a binary-relation with respect to a given
domain instance is the number of range-elements to which the relation
maps the domain-element. For a function (single-valued relation), the
VALUE-CARDINALITY is 1 on all domain instances for which the function
is defined. It is 0 for those instances outside the exact domain of
the function.
VALUE-CARDINALITY may be used within the definition of a class to
specify a slot cardinality if its first argument is the class's
instance variable."
:lambda-body (cardinality (setofall ?y
(holds ?binary-relation ?instance ?y)))
:constraints (and (instance-of ?binary-relation binary-relation)
(instance-of ?n nonnegative-integer))
:issues ((:see-also slot-cardinality)))
(define-relation MINIMUM-VALUE-CARDINALITY (?instance ?binary-relation ?n)
"Minimum value cardinality is a constraint on the number of values to
which a binary relation can map a domain instance. It implies the existence
of at least N values for a given relation on an instance."
:iff-def (and (instance-of ?binary-relation binary-relation)
(instance-of ?n nonnegative-integer)
(>= (value-cardinality ?instance ?binary-relation) ?n))
:issues ((:see-also value-cardinality minimum-slot-cardinality)))
(define-relation MAXIMUM-VALUE-CARDINALITY (?instance ?binary-relation ?n)
"Maximum value cardinality is a constraint on the number of values to
which a binary relation can map a domain instance. It restrict the relation
to AT MOST N values for a given a domain instance. A cardinality of 0
means that the relation does not hold for that instance."
:iff-def (and (instance-of ?binary-relation binary-relation)
(instance-of ?n nonnegative-integer)
(=< (value-cardinality ?instance ?binary-relation) ?n))
:issues ((:see-also value-cardinality maximum-slot-cardinality)))
#|----------------------------------------------------------------------
Now we will define the ``slot'' versions of these relations.
These describe relationships between classes and slots, rather
than instances and slots. They are a useful canonical form for
translation into frame systems.
----------------------------------------------------------------------|#
(define-relation SLOT-VALUE-TYPE (?class ?binary-relation ?type)
"The SLOT-VALUE-TYPE of a relation R with respect to a domain
class C is a constraint on the values of R when R is applied to
instances of C. The constraint is specified as a class T such that
for any instance c of C, when R(c,t), t is an instance of T."
:iff-def (and (instance-of ?class class)
(instance-of ?binary-relation binary-relation)
(instance-of ?type class)
(forall ?instance
(=> (instance-of ?instance ?class)
(=> (holds ?binary-relation ?instance ?slot-value)
(instance-of ?slot-value ?type)))))
:issues ((:See-also
RANGE
"In Loom and CLASSIC, slot-value-type is called `ALL'."
"In KEE, slot-value-type is called `VALUECLASS'.")))
(define-function SLOT-CARDINALITY (?domain-class ?binary-relation) :-> ?n
"If a SLOT-CARDINALITY of relation R with respect to a domain
class C is N, then for all instances c of class C, R maps c to exactly
N individuals in the range. For single-valued relations, the
slot-cardinality is 1. Specifying a SLOT-CARDINALITY is a constraint
between classes and binary-relations which does not always hold; there
need not be any fixed value-cardinality for R on all instances of C."
:iff-def (=> (instance-of ?instance ?domain-class)
(= (value-cardinality ?instance ?binary-relation) ?n))
:constraints (and (instance-of ?domain-class class)
(instance-of ?binary-relation binary-relation)
(instance-of ?n nonnegative-integer))
:issues ((:see-also
"Specifying that the slot cardinality is = to some integer
is equivalent to using the Loom and CLASSIC `EXACTLY'
operator.")
("Note that slot-cardinality is a function. That means
that for any domain and relation, there is at most one
integer N that can be the slot-cardinality. If there is
no such fixed number, then the value of the function is
undefined for the given domain and relation.")))
(define-relation MINIMUM-SLOT-CARDINALITY (?domain-class ?relation ?n)
"MINIMUM-VALUE-CARDINALITY specifies a lower bound on the number
of range elements to which a given relation can map instance of a
given domain class. In other words, it is the minimum number of slot
values for a slot local to a class."
:iff-def (=> (instance-of ?instance ?domain-class)
(>= (value-cardinality ?instance ?relation) ?n))
:constraints (and (instance-of ?domain-class class)
(instance-of ?relation binary-relation)
(instance-of ?n nonnegative-integer))
:issues ((:see-also
"MINIMUM-SLOT-CARDINALITY is inspired by the CLASSIC
and Loom `AT-LEAST' operator."
"In KEE, MINIMUM-SLOT-CARDINALITY is called
MIN.CARDINALITY.")))
(define-relation MAXIMUM-SLOT-CARDINALITY (?domain-class ?relation ?n)
"MAXIMUM-VALUE-CARDINALITY specifies an upper bound on the number of
range elements associated with any instance of a given domain class.
It is inspired by the CLASSIC and Loom `at-most' operator."
:iff-def (=> (instance-of ?instance ?domain-class)
(=< (value-cardinality ?instance ?relation) ?n))
:constraints (and (instance-of ?domain-class class)
(instance-of ?relation binary-relation)
(instance-of ?n nonnegative-integer))
:issues ((:see-also
"MAXIMUM-SLOT-CARDINALITY is inspired by the CLASSIC
and Loom `AT-LEAST' operator."
"In KEE, MAXIMUM-SLOT-CARDINALITY is called
MAX.CARDINALITY.")))
(define-relation SINGLE-VALUED-SLOT (?class ?binary-relation)
"SINGLE-VALUED-SLOT is a constraint on the second argument of a binary
relation that is conditional on the first argument to the relation being
an instance of a given class. It is like single-valued, except it
is local to the values of the relation on instances of the given subset
of the domain."
:iff-def (= (slot-cardinality ?class ?binary-relation) 1)
:equivalent (and (instance-of ?class class)
(instance-of ?binary-relation binary-relation)
(=> (instance-of ?instance ?class)
(=> (holds ?binary-relation ?instance ?slot-value1)
(holds ?binary-relation ?instance ?slot-value2)
(= ?slot-value1 ?slot-value2)))))
;;; version 4: changed INHERITED-SLOT-VALUES to a relation,
;;; and renamed it to the singular form
(define-relation INHERITED-SLOT-VALUE (?class ?binary-relation ?value)
"AN inherited-slot-value of binary relation R on class C is value V
for which R(i,v) holds on each instance i of C.
There is no closed-world assumption; there may exist other values v_i for which
R(i,v_i) holds. Inherited values are monotonic, not default."
:iff-def (and (instance-of ?class class)
(instance-of ?binary-relation binary-relation)
(forall (?instance ?value)
(=> (instance-of ?instance ?class)
(holds ?binary-relation ?instance ?value))))
:issues ((:see-also all-inherited-slot-values)))
(define-function ALL-INHERITED-SLOT-VALUES (?class ?binary-relation) :-> ?set-of-values
"The all-inherited-slot-values of binary relation R on class C is the set V
of values for which R(c,s) holds on each instance i of C and member v of V.
Unlike inherited-slot-values, there may not exist any other value v_i for which
R(i,v_i) holds. Inherited values are monotonic, not default."
:iff-def (and (instance-of ?class class)
(instance-of ?binary-relation binary-relation)
(forall (?instance ?value)
(=> (instance-of ?instance ?class)
(<=> (member ?value ?set-of-values)
(holds ?binary-relation ?instance ?value))))))
(define-relation SAME-SLOT-VALUES (?class ?slot1 ?slot2)
"Let class C be in the domain of two binary relations R_1 and R_2.
The relation (same-values C R_1 R_2) means that the values of the
two relations are the same when applied to instances of the class."
:iff-def (and (instance-of ?class class)
(instance-of ?slot1 binary-relation)
(instance-of ?slot2 binary-relation)
(forall (?instance ?value)
(=> (instance-of ?instance ?class)
(<=> (holds ?slot1 ?instance ?value)
(holds ?slot2 ?instance ?value))))))
#|----------------------------------------------------------------------
8. Organizing classes into mutually-disjoint sets.
class-partition, subclass-partition, exhaustive-subclass-partition
The following relations are used to succinctly state
that classes are mutually disjoint. A partition may be
given a name using define-instance. Alternatively, one
may define a set of subclasses of a given class that are
mutually disjoint. If the set of subclasses covers the
parent class, then the partition is called exhaustive.
These relations are motivated by the partition tags in the
KRSS specification; in KRSS, however, the partitions are not
first-class objects.
----------------------------------------------------------------------|#
(define-class CLASS-PARTITION (?set-of-classes)
"A set of mutually disjoint classes. Disjointness of
classes is a special case of disjointness of sets."
:iff-def (and (set ?set-of-classes)
(forall ?C
(=> (member ?C ?set-of-classes)
(instance-of ?C class)))
(forall (?C1 ?C2)
(=> (and (member ?C1 ?set-of-classes)
(member ?C2 ?set-of-classes)
(not (= ?C1 ?C2)))
(forall (?i)
(=> (instance-of ?i ?C1)
(not (instance-of ?i ?C2)))))))
:issues (("Why not just use the set machinery?"
"We want to localize the relationship between sets
and classes to just a few axioms, so we use the
instance-of machinery here.")))
(define-relation SUBCLASS-PARTITION (?C ?class-partition)
"A subclass-partition of a class C is a set of
subclasses of C that are mutually disjoint."
:iff-def (and (instance-of ?C class)
(instance-of ?class-partition class-partition)
(forall ?subclass
(=> (member ?subclass ?class-partition)
(subclass-of ?subclass ?C))))
:issues (("Why is the second argument a set, rather than a sequence variable?"
"Interesting design choice. The ``notation'' question
here is not new syntax for a language, it's just the definition of a
particular relation called subclass-partition. In KIF you can define
relations that take an arbitrary number of arguments, using a a
"sequence variable" that acts like &rest in Lisp. So I
could have made the subclass-partition relation take a
variable number of arguments. I decided not to use a
sequence variable because that is not a minimal ontological
commitment; it imposes an extra logical constraint for the
sake of syntactic convenience. A sequence (list) imposes an
order. But a class-partition requires no order among the
classes. And I wanted the second argument to
subclass-partition to be a class-partition -- a thing that
is defined independently as a set of classes.")))
(define-relation EXHAUSTIVE-SUBCLASS-PARTITION (?C ?class-partition)
"A subrelation-partition of a class C is a set of
mutually-disjoint classes (a subclass partition) which covers C.
Every instance of C is is an instance of exactly one of the subclasses
in the partition."
:iff-def (and (subclass-partition ?C ?class-partition)
(forall ?instance
(=> (instance-of ?instance ?C)
(exists ?subclass
(and (member ?subclass ?class-partition)
(member ?instance ?subclass)))))))
#|----------------------------------------------------------------------
9. Special properties and relations on binary-relations:
symmetry, reflexivity, transitivity
Many of these have analogs in the abstract-algebra ontology.
The difference is that these are absolute properties of relations,
whereas the algebraic definitions are relative to domains.
For example, a REFLEXIVE-RELATION is reflexive for its universe,
whereas (REFLEXIVE ?relation ?domain) means that ?relation is
reflexive with respect to the class ?domain.
The motivation for these in the frame ontology is to support
databases where such properties are absolute.
----------------------------------------------------------------------|#
(define-relation ASYMMETRIC-RELATION (?R)
"Relation R is asymmetric if it is not symmetric."
:iff-def (and (instance-of ?R binary-relation)
(not (symmetric-relation ?R))))
(define-relation ANTISYMMETRIC-RELATION (?R)
"Relation R is antisymmetric if for distinct x and y,
R(x,y) implies not R(y,x). In other words, for all x,y,
R(x,y) and R(y,x) => x=y."
:iff-def (and (instance-of ?R binary-relation)
(=> (and (holds ?R ?x ?y) (holds ?R ?y ?x))
(= ?x ?y))))
(define-relation ANTIREFLEXIVE-RELATION (?R)
"Relation R is antireflexive if R(a,a) never holds."
:iff-def (and (instance-of ?R binary-relation)
(not (holds ?R ?x ?x))))
(define-relation IRREFLEXIVE-RELATION (?R)
"Relation R is irreflexive if it is not reflexive."
:iff-def (and (instance-of ?R binary-relation)
(not (reflexive-relation ?R))))
(define-relation REFLEXIVE-RELATION (?R)
"Relation R is reflexive if R(x,x) for all x in the domain of R."
:iff-def (and (instance-of ?R binary-relation)
(=> (instance-of ?x (exact-domain ?R))
(holds ?R ?x ?x))))
(define-relation SYMMETRIC-RELATION (?R)
"Relation R is symmetric if R(x,y) implies R(y,x)."
:iff-def (and (instance-of ?R binary-relation)
(=> (holds ?R ?x ?y)
(holds ?R ?y ?x))))
(define-relation TRANSITIVE-RELATION (?R)
"Relation R is transitive if R(x,y) and R(y,z) implies R(x,z)."
:iff-def (and (instance-of ?R binary-relation)
(=> (and (holds ?R ?x ?y) (holds ?R ?y ?z))
(holds ?R ?x ?z))))
(define-relation WEAK-TRANSITIVE-RELATION (?R)
"Relation R is weak-transitive if R(x,y) and R(y,z) and x /= z
implies R(x,z)."
:iff-def (and (instance-of ?R binary-relation)
(=> (and (holds ?R ?x ?y)
(holds ?R ?y ?z)
(not (= ?x ?z)))
(holds ?R ?x ?z))))
(define-relation ONE-TO-ONE-RELATION (?r)
:iff-def (and (unary-function ?r)
(function (inverse ?r))))
(define-relation MANY-TO-ONE-RELATION (?r)
:iff-def (and (binary-relation ?r)
(function ?r)))
(define-relation ONE-TO-MANY-RELATION (?r)
:iff-def (and (binary-relation ?r)
(function (inverse ?r))))
(define-relation MANY-TO-MANY-RELATION (?r)
:iff-def (and (binary-relation ?r)
(not (function ?r))
(not (function (inverse ?r)))))
#|----------------------------------------------------------------------
10. Derived properties of binary relations:
equivalence, order, etc.
----------------------------------------------------------------------|#
(define-relation EQUIVALENCE-RELATION (?R)
"A relation is an equivalence relation if it is reflexive,
symmetric, and transitive."
:iff-def (and (reflexive-relation ?R)
(symmetric-relation ?R)
(transitive-relation ?R)))
(define-relation PARTIAL-ORDER-RELATION (?R)
"A relation is an partial-order if it is reflexive,
antisymmetric, and transitive."
:iff-def (and (reflexive-relation ?R)
(antisymmetric-relation ?R)
(transitive-relation ?R)))
(define-relation TOTAL-ORDER-RELATION (?R)
"A relation R is an total-order if it is partial-order
for which either R(x,y) or R(y,x) for every x or y in its domain."
:iff-def (and (partial-order-relation ?R)
(=> (and (instance-of ?x (exact-domain ?R))
(instance-of ?y (exact-domain ?R)))
(or (holds ?R ?x ?y)
(holds ?R ?y ?x)))))
#|----------------------------------------------------------------------
11. Miscelleneous: documentation, etc.
----------------------------------------------------------------------|#
(define-relation DOCUMENTATION (?object ?string)
"Documentation is a relation between objects in the domain of discourse
and strings of natural language text. The domain of DOCUMENTATION is
not constants (names), but the objects themselves. This means that
one does not quote the names when associating them with their documentation."
:def (and (individual ?object)
(string ?string)))
#|----------------------------------------------------------------------
ACKNOWLEDGEMENTS
The definitions in this ontology are based on common usage in the
computer science and mathematics literatures. Some of the terminology
of functions and relations is based on the book Naive Set Theory, by
Paul Halmos (Princeton, NJ: D. Van Nostrand, 1960). Reed Letsinger
of Hewlett-Packard and Stanford University proposed the uniform
treatment of relations and functions as sets of tuples, and wrote many
of the definitions of second-order relations. The CYC system (Doug
Lenat and R. V. Guha, 1990) was an inspiration for the utility of
many of the distinctions included. The KRSS specification for
terminological languages (Bob MacGregor, Peter Patel-Schneider, and
Bill Swartout) was the source and motivation for several primitives.
Bob MagGregor contributed to the choice and definitions of several
concepts in the ontology. Richard Fikes and Mike Genesereth lead the
effort to a specification for KIF that is clear and expressive enough
to be a solid foundation for this and future ontologies. Fritz
Mueller made many useful comments and suggestions, and implemented
code to translate from these primitives into existing representation
systems.
----------------------------------------------------------------------|#
This Lisp-to-HTML translation was brought to you by
François Gerbaux and Tom Gruber