OKeefe.R.A.@EDXA@sri-unix.UUCP (10/06/83)
From: Richard HPS (on ERCC DEC-10) <OKeefe.R.A.@EDXA>
A Problem with Using Retract for Database Update, and a
Suggested Utility for Avoiding the Problem.
It has been shown (I forget by whom) that Prolog augmented
with the setof/3 primitive is relationally complete. (I
do not know if this is true with findall; I suspect that
it may not be.) This means that you can expect it to do
the right thing with data base queries. But what about
data base updates ?
Suppose we have a data base with the following relations:
boss(Worker, /* -> */ Boss)
pay(Worker, /* -> */ Wage)
where Bosses are a kind of Worker, and may have Bosses of their own,
and we want to give any Boss who currently gets less than one of his
own workers a 10% raise. Note that after this update he may still
get less than one of his workers, and he may now get more than his
boss, and his boss may not have got a pay rise. Never mind if this
is sensible, let's just take it as a specification.
We start by defining the new pay relation.
underpaid(Worker) :-
pay(Worker, Wage),
boss(Subordinate, Worker),
pay(Subordinate, Bigger),
Bigger > Wage.
new_pay(Worker, Pay) :-
pay(Worker, Wage),
( underpaid(Worker) -> Pay is Wage*11/10
| Pay = Wage
).
Our task is to replace each pay(W,P) tuple by the corresponding
new_pay(W,P) tuple.
The first approach that occurs to everybody is
:- forall(new_pay(Worker, Pay),
retract(pay(Worker, _)) & assert(pay(Worker, Pay))).
where the standard predicate forall/2 is defined as
forall(Generator, Test) :-
\+ (Generator, \+ Test).
If you thought this would work, GOTCHA! The problem is exactly
like the error in
for i := 1 to n do a[i+1] := a[i];
as a means of shifting the contents of a[]. Some of the new_pay
tuples are calculated using new_pay tuples when they should have
been calculated using pay tuples. (There are specifications
where this is the correct thing to do. But this isn't one of
them.) The operation we really want is: given a way of computing
new tuples, replace an old relation by a new one, where the new
tuples are calculated only from the old ones.
There is another problem where this crops up. If you want to given
everyone a 10% raise,
:- forall(retract(pay(Worker, Old)) & New is (Old*11+5)/10,
assert(pay(Worker, New)) ).
is a very natural and very silly thing to do. Because retract will
see the new clauses, and after giving everyone a 10% raise it will
give them another, and another, and another... The obvious way of
getting round it is to use asserta instead of assertz, which has
the side effect of reversing the order of the tuples. If we had a
solution to the other problem, we could use it here too.
There is bound to be a better solution. It probably won't involve
assert and retract at all. But this one seems to work. The idea
is that we have a relation p(X1,...,Xn) and a rule for computing
new tuples, let's call it new_p(X1,...,Xn). What we do is call
update(p(X1,...,Xn), new_p(X1,...,Xn))
where
:- public update/2.
:- mode update(+, +).
update(Template, Generator) :-
recorda(., ., Ref),
( call(Generator), recorda(., Template, _), fail
; functor(Template, Functor, Arity),
abolish(Functor, Arity), % delete old relation
recorded(., Term, DbRef),
erase(DbRef),
( DbRef == Ref % we've come to the end
; asserta(Term), fail % copy new tuple
)
), !.
This isn't beautiful. It has very nearly the maximum number of
blemishes possible in a single clause. Basically, it works
almost exactly like find_all. It generates the new tuples in a
failure-driven loop, and tucks them away in a safe place in
reverse order. It then deletes the old relation, and in another
failure-driven loop pulls the new tuples out and stores them
in reverse order. The two reversals mean that the new tuples
will appear in the data-base in the order that they were
generated. The final cut is necessary in case there are other
facts stored under '.' and the caller tries to backtrack into
update, otherwise we might delete '.' facts that are none of
our business.
With this new operation, our two examples are easily handled.
:- update(pay(W, P), new_pay(W, P)).
:- update(pay(W, N), pay(W, O) & N is (O*11+5)/10).
Also, it can be used to create new stored relations, E.g.
:- update(coworker(X, Y), boss(X, B) & boss(Y, B)).
Just like findall, setof, bagof, this operation has a horribly
ugly implementation in terms of asserts and retracts, but is
itself a clean abstraction. Also, if you are building a new
Prolog system from scratch, there is no reason why setof, bagof,
or the data collection phase of update have to use the data-base
at all. Only the final replacement in update needs to change
the data base, and replacing an entire relation could have
much less impact on the rest of the implementation than the
current form of assert and retract do.
If you were using retract to implement relational database
update, this will probably replace most of your retracts.
But there are other uses of assert and retract than this,
and I still don't know what to do about them. I thoroughly
enjoy seeing my name in the Prolog Digest, but I'd rather
see other people's solutions than my questions. Please
tell us about the lovely operation you use instead of assert
and retract; I have lots of recordz-s and erase-s I would
dearly like to conceal.