sanjay@arizona.edu (Sanjay Manchanda) (03/17/88)
I have worked on doing database updates in Prolog in a "logical" fashion. A database update is essentially an assignment on the database. If we are going to update the database, why not first develop a logic for reasoning about database assignments, and then mechanize it in the true logic programming tradition? A dynamic logic is a reasonable choice for this task, since dynamic logics were developed to reason about programs which explicitly manipulate their state (i.e. do assignment). I have developed a dynamic logic for reasoning database updates that doesn't look much like the dynamic logic's that you may have seen, but it leads to a simple extension of Prolog. Instead of going into the logic, I will briefly explain the extension of Prolog. Richard introduced it rather well in a previous message, so let me borrow some of his words. >Roughly speaking, there are three classes of predicates: > > pure predicates (don't depend on things that change) > > state predicates (depend on things that change, but change nothing) > > transition (or dynamic) predicates (express a relation between states) > >For example, we might say > > p(X) :- > <-fred(X)> q(X). > >p(X) is true in a world W if there is a world W1 such that > -(fred(X), W, W1) -- roughly, retract >and q(X) is true in W1. > >Note that this doesn't change W. There are two sets of predefined dynamic predicates, +p and -p for every pure predicate p. Actually, to avoid some thorny implementation and semantic problems, p is restricted to be a pure predicate that is defined entirely by ground Prolog facts. For obvious reasons, such a predicate is called a database predicate. New dynamic (or transition) predicates can be defined by means of Update Rules. For example, we might say add_flight(Fno, Src, Dest) <-- airport(Src), airport(Dest), <+flight(Fno, Src, Dest)>. The use of the `<--' instead `:-' signals that a dynamic predicate is being defined. Here the semantics of add_flight(Fno, Src, Dest) is a transition from a world W to a world W1, such that (airport(Src), airport(Dest)) is true in W, and W1 is obtained from W by adding the fact flight(...) to W. Thus, viewed as an operator, + is roughly equivalent to assert. The rule may be used in a top level query like: :- <add_flight(20, 'LA', 'OHARE')>reachable('LA', 'JFK') which is true in a current world W if there exists W1 accessible through the meaning of add_flight(..), and reachable('LA','JFK') is true in W1. Assume that reachable is the transitive closure of the flight relation. The execution of the query is not very different from Prolog execution. Thus the call <+flight(..)> will return a new (world) database in which reachable(...) will be evaluated. If this evaluation fails, backtracking will cause the inserted fact flight(...) to be removed. Similarly, deletion on the database is undone on backtracking. If the query succeeds, it will return a new updated database and display to the user, all the changes that have been made to the current database. The user can then choose to commit these changes and make them permanent, or reject them and leave the database unchanged. The language has a well-defined declarative semantics, and a syntax that reflects this semantics. This makes it considerably better than using assert and retract for database updates. As an example, note that in my proposed extension, updates are statically scoped. If p(X) is pure predicate or a state predicate, the database is guaranteed to remain unchanged after it is executed. This can be quite significant for compiler and database query optimization. I did not allow updates to rule-defined predicates because I wanted to guarantee that (not p(a)) was true after executing <-p(a)>. However, I think that can extend the treatment if I use a weaker semantics. I will mail copies of [1], [2] and [3] to anyone who requests them. My apologies to Richard for forgetting to mail him a copy of my paper. --sanjay (sanjay@arizona.edu) References: [1] Sanjay Manchanda and David Scott Warren. A Language for Database Updates. In Jack Minker, editor, Foundations of Deductive Databases and Logic Programming, Morgan-Kaufmann, Los Altos, CA, 1987. [2] Sanjay Manchanda, Soumtira Sengupta, and David S. Warren. Concurrent Updates in a Prolog Database System Technical Report 86/28, Department of Computer Science, SUNY at Stony Brook, Stony Brook, NY 11794, December 1986, Revised Feb 1987. [3] Sanjay Manchanda A Dynamic Logic Programming Language for Relational Updates. Phd Thesis, SUNY at Stony Brook, Stony Brook, NY 11794, December 1987.