EQUIVALENT
EXPRESSIONS IN P/FDM AND FOL
1) Functional formalisation of object
DB
p1 in
person generator
and
membership
test
name(p1)
= ‘John’ attribute value
test
name(father(p1))
= ‘Joe’
‘Sue’ in parents(p1) member
of relationship
ancestor(p1,p2)
= True derived function
2) Predicate formalisation of object DB
person(P1) generator
and
membership test
name(P1,
‘John”) attribute
value test
father(P1,
X) Ù name(X, ‘Joe’)
parent(‘Sue’,
P1) relationship instance
ancestor(P1,
P2) derived
predicate
RESTRICTION
AND SELECTION
Equality the p such
that
name (p)=‘p2pab’
Inequality ...such that resolution (p)>7.0
...such that resolution (p) > resolution (q)
Conjunction ...such that cname(s)=‘Peter’ and sname(s)=‘Gray’
Disjunction ...such that cname(s)=‘Peter” or
cname(s)=‘John”
Negation ...such that not (cname(s)=‘Fred’)
Existential ...such that some e in
employees (co)
has
age(e)>65 and...
Universal ...such that all c in component(p)
have length(c)>20 or..
3. Overview of CoLan - FDM Constraint
Language
3.1 CoLan Syntax
A
typical constraint expressed in CoLan consists of two parts. The first part, where the variables that are
going to be used are given a domain and are quantified over that domain. The second part is the main part of the
constraint and consists of zero, one or more predicates that should be
satisfied by the instances described by the quantification part. For example, a constraint about the
permissable range of ages for a postgraduate student would look like the
following in CoLan:
constrain
each p in postgrad
to have age(p)>20 and age(p)<45
3.1.1 Attribute Constraints
The
above constraint restricts the range of values that a slot of an instance of a
class can take and is called an attribute constraint. Attribute constraints are conceptually, but not syntactically,
the simplest constraints that are expressible in CoLan and are equivalent to
the attribute-domain constraints in relational database systems.
3.1.2.
Numerically Quantified Constraints
More
complex constraints are the ones that relate the object that received the
update message with the rest of the objects of its class (relation-aggregate
constraints). For example, the
constraint:
constrain at least 3 s in staff
to have position(s)= “security”
restricts
the minimum number of instances of class staff that satisfy the predicate part
of the constraint. To evaluate the
validity of such a constraint in the context of a certain update, we must not
only search for data locally (i.e. instance variables of the recipient object),
but also globally (i.e. instance variables of other instances of the same
class).
Although
the quantification part is mandatory, the predicate part is optional for a
CoLan expression. Some CoLan
expressions quantify only the number of instances in a given domain regardless
of their properties. An example of such
a constraint is the following:
constrain at most 35 p in postgrad to exist
The
use of so that in CoLan expression is
optional. It is mainly as a noise word
before second and subsequent quantifiers.
For example, note that so that
can be omitted but such that cannot:
· constrain each 1 in lecturer such that age(1)>35
to
have
research interest(1) = “Databases”
· constrain each p in postgrad
so
that some 1 in lecturer has
research
interest(1)= research interest(p)
We
note that a constraint with a universal quantifier can always be transformed
into one with the numerical quantifier no
.. to exist, provided the predicate
part is negated and the such that keyword is added:
· constrain each u in
undergrad
to have year(u) > 0 and year(u) =
< 4
· constrain no u in
undergrad
such that year(u) = < 0 or year(u)
> 4
to exist
· constrain no u in
undergrad
to have year(u) = < 0 or year(u)
> 4
Finally
we note that when a quantified variable is further restricted by a predicate
(or an embedded quantified expression), the keyword such that is
obligatory, even with the universal quantifier:
· constrain each s in staff
such that status(s) = “honour”
no s1 in students
advised(s)
has status(s1) <>
“honour”
· constrain each s in student
such that enrollment(s) = “part
time”
to have year(s) = < 6
In
this example, such that is used for the restriction of the domain from students
to part-time students only, while the actual constraint is about the year of
study of those students. As a final
complex example, note that an existential quantifier (some) can occur in a
modifying such that clause:
constrain each s in staff
such
that some f in friends(s) has name(f) = “fred”
at least 2 s1 in students
advised(s)
has status(s1) = “honour”
Here
the quantifier some refers to friends of the staff members being quantified
whilst the inner quantifier at least 2
refers to students advised by the staff; it could also be written so that at least 2.
3.4.
Equivalencies to Logic Form
In
this section we demonstrate how CoLan relates to first order logic (FOL) using some
simple examples. We show how to express
universal implications using constrain
each and not exists.
In
FOL we express that a variable is bound with an entity of a domain through a
unary relationship, i.e. with a predicate of arity one. For example, the CoLan expression:
constrain each 1 in lecturer
to have P(1)
is
translated into FOL thus:
"1 lecturer(1) ®
P(1)
Note
that the predicate:
age(1) > 50
is
translated into FOL as an implication and not as a conjunction:
age(a,1) ® gt(a,50)
because
it reads in English as: “If A is the age of L then a is greater than 50”.
This
is known as a weak translation, since
if we don’t know the age of L then we infer nothing.
Thus
the complete FOL expression for the constraint:
constrain
each 1 in
lecturer
to have age(1) > 50
is
the following:
("1,a) lecturer (1) Ù age (a,1) ® gt (a,50)
º
("1,a) lecturer (1) ®
( age (a,1) ® gt(a,50))
More
complex constraints are the ones that join different classes. These constraints require variable sharing between
different binary relationships of at least two quantified variables. Consider the constraint:
constrain
each 1 in lecturer
so that no s in staff
has phone of 1 = phone of s and
1
< > s
This
translates into pure FOL:
("1,p)lecturer (1) Ù phone(p,1) ® Ø ($s,p1)
staff (s ) Ù phone (p1,s) Ù
eq (p,p1) Ù Øeq(1,s)
or,
("1,s,p,p1) lecturer (1) Ù phone (p,1) Ù staff (s)
Ù phone (p1,s) ® Ø eq (p,p1) Ú eq(l,s)
Note:
predicates representing relationships and attributes of variables which
are universally quantified usually appear on the left of the
implication, immediately following a predicate like lecturer(l) that
instantiates the variable from its domain.
Existential
quantifiers correspond to some or at least 1, for example:
constrain each p
in postgrad
so that some l
in lecturer such that age(l) > 30
has
topic(p) in resinterests(l) and
age(l)
>= age(p)
translates
as:
("p) postgrad(p) Ù age(p,ap) Ù topic(p,at) ®
($l) lecturer(l) Ù age(l, al) Ù (al>30) Ù reinterest(l, at)Ùal>=ap
Note: $ is followed by conjunctions(Ù) never by implication(®), (unless the implication refers to an
enclosing ").
The
multivalued relationship resinterest is represented by a predicate
representing a specific instance of the relship (e.g. resinterest(l,
Spanish),... and not by resinterest(l, [French, Spanish, ...]).