Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!linus!philabs!seismo!hao!hplabs!sri-unix!OKeefe.R.A.@EDXA From: OKeefe.R.A.@EDXA@sri-unix.UUCP Newsgroups: net.lang.prolog Subject: More On Retract Message-ID: <12377@sri-arpa.UUCP> Date: Thu, 6-Oct-83 05:16:36 EDT Article-I.D.: sri-arpa.12377 Posted: Thu Oct 6 05:16:36 1983 Date-Received: Mon, 10-Oct-83 09:40:58 EDT Lines: 142 From: Richard HPS (on ERCC DEC-10) 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.