@begin(comment)
 sigmod89 paper
 Instructions:
----- install the following as donalp.ref ------
@marker(References,donalphabetic)

@Style(Citations=2,CitationType=Brackets,Stringmax=750)
@Define(L1,LeftMargin 4,Indent -4,Above .3,Break,Group)
@TextForm(TAGGER="[@parm(TEXT)]@ @ ")

@LibraryFile(ISIREF)

@Enter(Text,Spacing .8,Spread 0,Spaces Compact,Justification off)
@Process(Bibliography)
@Leave(Text)

----------------
after compiling and printing
- draw in arrows in 2 figures
- white out footnote numbers (2) for footnote 0
- and white out page numbers
@end(comment)

@device(imagen300)
@comment(imagen.dev)
@specialfont(f1="/usr/local/fonts/raster.8/300/cmsy10.r10")
@specialfont(f2="/usr/local/fonts/raster.8/300/cmasc10.r10")
@Equate(K=Value)
@equate(rem=comment)
@string< Implies="@f1(  )",
	element="@f1(2)",
	Equiv="@f1()",
	neq="@f1()",
	And="@f2(  )",
	Or="@f2(  )",
	Exists="@f1(9)",
	All="@f1(8)",
	leq="@f1()",
	geq="@f1()",
	rarrow="@f1(!)">
@commandstring(iwff="@i[w@hsp{-.5mm}f@hsp{-1mm}f]")
@style(fontfamily computermodernroman10, spacing 0.8, spread .2,
  linewidth 7 inches, leftmargin .75 inches,
  topmargin .7 inches, bottommargin .9 inches, references donalphabetic)
@comment[donalph = isialp except spacing is .8]
@make(article)
@modify(verbatim, above .2 , below .2, spread .2, spacing .8)
@modify(itemize, above .2 , below .2, spread .2, spacing .8)
@modify(fnenv, spread .2, spacing .8)
@modify(notestyle spacing 0.8)
@modify(bodystyle spacing 0.8)
@modify(hd2, above .1 inch)
@modify(hd3, above .1 inch)
@modify(hd4, above .1 inch)
@modify(Plus,Script +0.1 lines)
@modify(Minus,Script -0.1 lines)

@commandstring(ap="AP5")
@comment[Efficient database triggering
on complex conditions]
@majorheading[Compiling complex database
transition triggers]
@center[Donald Cohen
Information Sciences Institute
University of Southern California
4676 Admiralty Way
Marina del Rey, CA 90292
(213) 822-1511
DonC@@vaxa.isi.edu
@blankspace(.2 inches)]

@begin(text, linewidth 3.26 inches, columns 2, columnmargin .33 inches, boxed)

@set(FootnoteCounter= -1)
@foot[This research was supported by the Defense Advanced Research Projects
Agency under contract No. MDA903 81 C 0335.  Views and conclusions
contained in this report are the authors' and should not be interpreted
as representing the official opinion or policy of DARPA, the U.S.
Government, or any person or agency connected with them.
@blankspace(1.1 inch)]
@b(Abstract:) This paper presents a language for specifying database updates,
queries and rule triggers, and describes how triggers can be compiled into 
an efficient mechanism.  The rule language allows specification of 
both state and transition constraints as special cases, but is more general 
than either.  The implementation we describe compiles rules and updates 
independently of each other.  Thus rules can be added or deleted without
recompiling any update program and vice versa.

@section(Introduction)

People often wish to tell a database to watch out for certain
conditions arising in the data, for instance, "whenever an
account's balance drops below a threshhold, notify its owner(s)", or
"do not allow a change that causes more than one employee to occupy the
same office".  Most databases provide little or no support for stating
and reacting to such conditions, in large part because they can provide 
little or no implementation support.  Rather a programmer has to figure out
what updates could possibly cause a condition of interest to arise and
for each such update supply code to recognize that condition.

This paper presents a temporal extension to the language of first order logic
which enables convenient description of a wide variety of rule triggers by
allowing reference to both the state before and the state after a transition.
State and transition constraints are special cases of these more general
conditions.  Although the language is simple, we know of no previous
attempts to express what it expresses.  This includes Postgres@cite(postgres).

The bulk of the paper shows how such specifications can be efficiently
implemented using a network similar to that of the RETE algorithm@cite[forgy].
Of course, triggering, like querying, is not free, and some triggers, like some
queries, simply cannot be implemented cheaply.  However, the cost of triggering
with our method is generally competitive with the result of hand
optimization.  The implementation we describe has been in daily use for several
years by about a dozen users with databases containing thousands of rules.

@subsection (Related work)
Previous work in this area mostly concentrates on integrity constraints, e.g.,
@cite[Eswaran], @cite[HammerMcleod], @cite[Stonebraker], @cite[HammerSarin],
@cite[blaustein], @cite(postgres), @cite[Qian], etc.
Our work is most closely related to that of Nicolas@cite[Nicolas]
and Forgy@cite[forgy].  Our implementation preserves the best features of
both of these approaches.

Nicolas showed how to efficiently enforce "state constraints", which prevent
invalid database states such as employees sharing offices.  Constraints are
represented as well-formed formulae (@b(wffs)) of first order logic.  The
method alters a given program that updates the database to take a given
constraint into consideration.  For instance, the program that assigned an
office to a person would be altered to check that the office was not assigned
to any other person.  This method assumes that the constraint was satisfied
before the update.

Forgy's RETE algorithm is commonly used for implementing expert systems.  It
efficiently maintains a set of "matches" for various "patterns" as a (small)
database changes.  These patterns may be described approximately as
conjunctions with free variables, where a "match" is a tuple representing
an assignment of values to the free
variables that satisfies the conjunction.@foot[Actually, the RETE language is
more general in some ways - it allows relations of variable arity, matching on
relations, and segment variables.  We will ignore these features.]  The RETE
algorithm reacts to a database transition.  It detects any tuples that the
transition causes to start or stop matching any pattern of interest.  Patterns
are compiled into a directed acyclic graph called a "match network".  A node
reads data from incoming edges and writes (different) data on outgoing edges.
The computations at the nodes gradually transform a set of database updates
into a set of assignments that start or stop matching the patterns of interest.

Nicolas' algorithm is more general than Forgy's in that it allows arbitrary
wffs, while Forgy's algorithm is more general in that it finds matches (as
opposed to simply checking that there are none).  Another advantage of Forgy's
algorithm is that each pattern is compiled once, whereas Nicolas requires that
every constraint be compiled for every update (so adding a new constraint
requires recompiling many update programs).  However, Forgy's algorithm is only
appropriate for very small databases, e.g., it uses more than enough internal storage to
store every fact in the database (sometimes much more!).
Another problem with RETE is that it prevents "query optimization" - it
compiles a given pattern into a fixed algorithm which may not be anywhere near
the most efficient one.  Nicolas, on the other hand simply compiles constraints
into queries which can be optimized like any other queries.

Our method generalizes both of these in that it finds matches for
arbitrary "transition conditions."@foot[Transition conditions are formally
defined later but are more general than either of the other two.  The low
balance notification is an example.]  Like Forgy, we compile each trigger
once.  New triggers and update programs can both be added independently (at
little cost) while the database is in use.  Finally, our algorithm is, at
worst, almost as efficient as either of the other two (for the cases they
handle), and sometimes much more so.

@comment[
We will refer to the union of state constraints and transition constraints
as "consistency rules".  We will call programs invoked by generalized 
triggering "automation rules".   We refer to the union of these as "rules".
Our method allows rules to be compiled independent of any programs
that update the database.  New rules can be added without thinking
about previously existing updating programs and new updating programs can
be written without thinking about previously declared rules.  Of course,
further optimization may be possible if this independence is given up.
However, with minor exceptions, our method achieves the efficiency of 
Nicolas even while retaining this independence.
]

@subsection(Outline)
Section 2 describes our query language and the extension with which
rules are specified.  Section 3 describes our implementation which
compiles the rule triggers into efficient programs and runs these
programs at appropriate times.  Section 4 deals with efficiency
issues.  It discusses some limitations of our method, implementation
alternatives, and the considerations that make them more or less desirable.

@section(The language)

Our method is implemented as part of @ap, a database oriented extension of
commonlisp@cite[CLtL].  We will insulate the reader from lisp syntax.
The query language of @ap is an extension to first order logic.  It includes 
relations of fixed arity, boolean connectives@k(and)(and),@k(or)(or), 
@r(~) (not), @k(implies) (implies), etc. and quantifiers 
@k(all) (for-all) and @k(exists) (exists).
@ap adds to lisp the following database constructs which we will use freely:
@begin(itemize)
@t[insert] @i(relation) (o@-(1), ..., o@-(i))@*
adds the tuple (o@-(1), ..., o@-(i)) to the (i-ary) relation @i(relation).
It does nothing if the tuple is already present.

@t[delete] @i(relation) (o@-(1), ..., o@-(i))@*
deletes the tuple (o@-(1), ..., o@-(i)) from the (i-ary) relation @i(relation).
It does nothing if the tuple is already absent.

@t[if @iwff ...]@*
is conditional execution, depending on the truth value of @iwff.

@t[iterate over@*
  @i(var)@-(1), ..., @i(var)@-(j) suchthat @iwff ...]@*
where @t[@i(var)@-(1), ..., @i(var)@-(j)] are the variables free in @iwff,
iterates over tuples (o@-(1), ..., o@-(j)) such that the result of substituting
o@-(i) for (free) occurrences of @i(var@-(i)) (1@k(leq)i@k(leq)j) in @iwff 
is true.

@t{atomic [@i(program@-(1)); ...; @i(program@-(k))]}@*
executes the programs in order, but delays all database updates (insert's 
and delete's) until the end.  They are then combined into a single
transition.  If the updates cannot @i(all) be done for some reason (see 
below), then @i(none) of the updates are done.
@end(itemize)

In addition to these programming constructs, there are rules which are
declared with syntax described below.  Semantically there are several disjoint
classes of rules.  When a transition is proposed, "consistency rules"
ensure consistency with any integrity constraints.  These rules may cause the
transition to be altered or rejected.  This process is described in more
detail below.  For now we merely note that all accepted transitions satisfy all
constraints.  The rule preventing shared offices is a consistency rule.
The rule triggering mechanism is also used to maintain "materialized views",
but that will not be described in detail here.

When a transition is accepted, it invokes "automation rules", so called because
they are used to automate such activities as sending low balance notifications.
It is not inconsistent to have a low balance, or even to have a low balance and
not yet have been notified.  Automation rules may cause further database transitions.  
@ap does not specify the
order in which automation rules are executed.  It only promises that every
automation invoked by a transition will run before control returns to the
program that requested the transition.

The atomic construct is especially relevant for rule triggering, because
it defines the observable states of the database.  Constraints apply only
to these observable states.  For instance, if every employee were required 
to have a unique office, and the employee Joe had Office11 then@*
@t[insert Office(Joe, Office12)] would not be allowed since that would
cause him to have two offices.  Likewise@*
@t[delete Office(Joe, Office11)] would not be allowed since that would 
cause him to have no offices.  However,@*
@verbatim{atomic [insert Office(Joe, Office12);
        delete Office(Joe, Office11)]}
would be allowed, unless it violated other constraints.
Similarly, automation rules react to entire database transitions, not to
"parts" of transitions.  In the low balance rule,
suppose each account had its own threshhold.  Then, reducing the balance from 
100 to 10 in the same atomic transition as reducing the threshhold from 20 
to 5 would not cause a notification.

@subsection(Language extension)
@label(extension)
We now introduce a simple language extension that allows us to specify triggers
such as that of the low balance rule.  The extension
allows us to talk about two adjacent database states: the state before the
transition under consideration and the (proposed) state after.  In the
context of a transition, queries may use two temporal operators.  Either could 
be defined in terms of the other, but it is convenient to have both:@*
@t[Previously @iwff  ]@*
is true if @iwff was true before the update.@*
@t[Start @iwff  ]@*
is true if @iwff was false before the update and is true after.@*
In the context of a (proposed) transition, any wff not in the scope of
a Start or Previously is evaluated in the new state.
Since we only provide access to two states, we do not allow nested
temporal references.  This extension does @i(not) allow
general temporal reference, for instance we cannot notify owners only the first
time in any month that their accounts fall below threshold.  @foot[Of course,
this can be "programmed" by introducing additional data.  The point is that
the trigger cannot be directly expressed in our language.]

We also introduce a syntactic construct called a @b[Description] of the 
form "@w{@i[variables] @t[suchthat] @iwff}", as illustrated above in the 
loop construct.  @i[Variables] are the variables free in @iwff.  
A tuple @b(satisfies) a description if substitution of 
the values in the tuple for (free) occurrences of @i(variables) in @iwff 
is true.  In the special case where @iwff has no free variables,
the empty tuple satisfies "@w[@t(nil suchthat) @iwff]" if @iwff is true.@*
(Note: "nil" denotes the empty variable list, not a single variable named nil!)
We refer to the set of such tuples as the @b(matches) of the description.  
We refer to the process of computing this set as @b(matching) the description.

@paragraph(Declaring automation rules)
We are now in a position to introduce syntax for the rules described above.  
Automation rules are declared as follows:

@begin(group)
@verbatim{
AutomationRule notify-low-balance
  trigger: person, acct suchthat 
       owns(person, acct)@k(and)
       Start [@k(exists) bal, min
               [balance(acct, bal)@k(and)
                threshhold(acct, min)@k(and)
                balance<min]]
  Response: notify(person, acct)}
@end(group)
On every database transition @ap must find every tuple (person, acct) satisfying 
the trigger, in this case, every person and acct such that person owns acct
and in this transition it became the case that acct's balance is less than its
threshhold.  For every such tuple @ap must call the notify procedure on person 
and acct.

Notice that the position of the start, like the position of quantifiers,
allows fine control over when the response will be executed.  For instance,
this trigger will not notify a person who becomes an owner of an account
that already has a low balance.  We could get that affect by moving the
@t(owns) inside the start.

Automation triggers describe database @i(transitions) rather than states - they
always refer to both the old and new states.  The reason is that we want to
detect matches by only reacting to updates of the relations in the trigger.
This won't work for a trigger like @t[x suchthat P(x)] - it can be satisfied
even when we make updates unrelated to P.  
Formally, our current implementation requires triggers to have a property we call
@b(relevance): they must only be satisfied during transitions that update some
relation that they use.  This condition is slightly stronger than simply
referring to both the old and new states.  For instance@*
@w{@t{x suchthat [P(x)@k(or) Start Q(x)]}}@*
is not relevant, since any tuples in
P will satisfy it even during transitions that don't update P or Q.
It is possible to match such
descriptions by storing the set of matches, but the need never seems to arise
in languages that support the notion of atomic database transitions.

@paragraph(Declaring consistency rules)

We can think of consistency rules in two parts:  first, the rule must not be
violated when it is declared.@foot[In @ap we allow users to declare that the
rule need not be checked at declaration.  Although usually "just an
optimization", this is sometimes necessary - some constraints cannot be
checked and yet @i(can) be incrementally enforced!]  Otherwise the data must be
fixed first.  Second, it must be enforced incrementally.  We can think of this
part as an automation that gets to run before the transition is accepted and is
allowed to abort the transition in its response.  We use the word
ConsistencyRule instead of AutomationRule to indicate that the rule runs before
the transition is accepted, and the word "abort" to mean the transition should
be rejected.  We incrementally enforce the constraint by aborting any
transition in which it becomes violated:

@group{
@verbatim"
ConsistencyRule no-office-sharing
  trigger: nil suchthat 
       Start [@r(~)@k(all) emp1, emp2, off
                 [[office(emp1, off)@k(and)
                   office(emp2, off)]
                 @hsp(4 points)@k(implies)emp1=emp2]]
  Response: abort"}

Although this is sufficient for implementing all consistency rules, we
mention a few refinements.

First, while the straight forward translation of the constraint is to
abort whenever it is violated, it is often more useful to respond with
an attempt to repair the violation.  The repair normally depends on the
particular instantiation(s) at fault.  @ap provides an elaborate
consistency repair mechanism which is beyond the scope of this paper.
However, we offer an annotated example to convey its flavor.

First, suppose we had written the following rule instead of the one above:

@group{
@verbatim"
ConsistencyRule no-office-sharing
  trigger: emp1, emp2, off suchthat
       Start [@r(~)[[office(emp1, off)@k(and) 
                  office(emp2, off)]
                @hsp(4 points)@k(implies)emp1=emp2]]
  Response:
       if Previously office(emp1, off)
	  delete office(emp1, off)"}

This would mean that on every proposed transition, @ap should find all
tuples (emp1, emp2, off) such that emp1 and emp2 are distinct employees
(proposed to be) in the same office, off.  It should then execute the
response for each such tuple.  If, for instance, Joe occupies office 14 and
we try to assign Jim to office 14, we get two such tuples:  (Jim,
Joe, Office14) and (Joe, Jim, Office14).  For the first of these the
response has no effect, since Jim did not previously occupy
Office14.  The second results in removing Joe from Office14.  

Of course, there is no guarantee that this results in a consistent transition.  
@ap interprets consistency rules to mean that (1) no transition in which the 
trigger is satisfied is consistent, but also (2) that executing the repair on
tuples that satisfy the trigger is a permissible way to augment attempted 
transitions that violate
the constraint.  @ap finds all such tuples and executes the repairs.
(It arranges for the repairs to run independently of one another - their order
doesn't matter.)  The repairs are themselves constrained, for instance they
may not "undo" the original updates.  If they do propose additional updates,
these are added to the original set, and the resulting transition is proposed
in place of the original.  It is in turn checked for consistency.  The process
continues until either consistency is achieved or @ap can tell that consistency
cannot be achieved.  In the example above, our attempt to put Jim in office 14
would, in the absence of any other rules, have the same effect as atomically
putting Jim in office 14 and removing Joe.

As another refinement, we can exploit the fact that no constraints were
violated in the previous state.  When consistency triggers have the form@*
@t(@i(variables) suchthat Start @iwff), we replace the Start with a new syntactic
construct, Start*.  This means the same thing as Start except that it tells
the implementor (in this case a program) that the wff was false before the
transition, which allows some optimization.  @foot{This "specification" of
start* can be formalized as follows:@* 
[Previously @r(~)P]@k(implies)[Start P @k(equiv) Start* P].  This permits many 
"implementations" of Start*.  The one we show below appears to give the same 
results as Nicolas if his quantifiers are optimally ordered.} 
We are now in a position to characterize the set of triggers handled by Nicolas.  
They are, in our language, the descriptions of the form@* 
@t[nil suchthat Start* @iwff], where @iwff has no free variables or temporal operators.

Finally, since so many consistency triggers look like the one above
(except that Start is replaced by Start*), we provide a more direct
syntax which elides the "Start* @r(~)" and allows the constraint to be 
stated directly:

@group{
@verbatim"
AlwaysRequire no-office-sharing
  @k(all) emp1, emp2, off
    [[office(emp1, off)@k(and) 
      office(emp2, off)]
    @hsp(4 points)@k(implies)emp1=emp2]
  Response:
      if Previously office(emp1, off)
	 delete office(emp1, off)"}
This is equivalent to the rule above - every instantiation of the 
leading universal variables satisfying Start* of the rest of the wff
causes an invocation of the response.

@section[Implementation]

When presented with a rule declaration, @ap tries to build a piece of match
network for its trigger.  In some cases this is impossible, e.g., the
description is irrelevant or certain transitions would cause infinitely many
tuples to satisfy the description.  In other cases @ap can determine that
it is unnecessary, since the
trigger is unsatisfiable.  In other cases the desired piece of network will be
built and added to the existing match network, after which the rule will be
triggered by appropriate database transitions.

@comment[
On each database transition (in the case of consistency rules, each proposed
transition), @ap must find all matches of every rule trigger.  It then executes
the corresponding response for each.  The basic idea is to use the actual
updates being attempted to focus the search for matches.  The updates are
classified by the relation being updated and whether the update is an insert or
delete.  The rules are classified according to which such classes of updates
could impact them. <<*** wrong - ++P does not impact start P and start Q>>
Thus if no rules could be triggered by a particular class
of updates, e.g., deletion of a tuple from the Office relation, then no work
is wasted trying.  Other forms of discrimination will be evident from the more
formal description of the matcher below.
]

When database transitions are proposed, @ap must find all tuples that satisfy
all rule triggers.  This process requires three inputs: the previous database, 
P, the set of proposed database updates, U, with no-ops removed, and a set of
relevant descriptions, D, used as rule triggers.  The output is, for each 
d@k(element)D, the tuples satisfying d.  Of course, by the time a transition
is proposed, D has been compiled into a network of @b"matchnodes", N.  Each 
matchnode, n,
has an associated description, d@-(n), and a program, p@-(n), and is
"connected" to other nodes, its predecessors and successors.  D is a subset of
@w[{d@-(n) | n@k(element)N}].  (This set also contains some "intermediate
results" which are not in D.)

Tuples satisfying d@-(n) are computed at n and are used as the inputs to the
successors of n.  If n has predecessors, p@-(n) is run on each tuple produced
as output of any predecessor to compute a set of tuples that satisfy d@-(n).
The set of all tuples satisfying d@-(n) (the output of n) is simply the union
of all sets computed by p@-(n).  The only nodes without predecessors are those
that correspond to database updates, e.g.,@*
@t[x, y suchthat Start office(x, y)].@*
Their outputs are computed directly from U.

@comment[The programs at matchnodes, unlike RETE matchnodes, access P as well as U.]
@end(text)
@newpage()
@begin(figure)
@begin(verbatim)
@hpos(2.5 inches)        @b(node 1)
@hpos(2.5 inches)@r(output description:)
@hpos(2.5 inches) emp, off suchthat
@hpos(2.5 inches) start Office(emp, off)


     @b(node 2)@hpos(4.4 inches)     @b(node 3)
@r(program:)@hpos(4.4 inches)@r(program:)
 accept emp1, off (from node 1)@hpos(4.4 inches) accept emp2, off (from node 1)
 iterate over emp2 suchthat@hpos(4.4 inches) iterate over emp1 suchthat
  Office(emp2, off)@k(and)emp1@k(neq)emp2@hpos(4.4 inches)  Office(emp1, off)@k(and)emp1@k(neq)emp2
  produce emp1, emp2, off@hpos(4.4 inches)  produce emp1, emp2, off
@r(output description:)@hpos(4.4 inches)@r(output description:)
 emp1, emp2, off suchthat@hpos(4.4 inches) emp1, emp2, off suchthat
 [start Office(emp1, off)]@k(and)@hpos(4.4 inches) [start Office(emp2, off)]@k(and)
 Office(emp2, off)@k(and)emp1@k(neq)emp2@hpos(4.4 inches) Office(emp1, off)@k(and)emp1@k(neq)emp2


@hpos(2.5 inches)        @b(node 4)
@hpos(2.5 inches)@r(program:)
@hpos(2.5 inches) produce union of outputs
@hpos(2.5 inches) of nodes 2 and 3
@hpos(2.5 inches)@r(output description:)
@hpos(2.5 inches) emp1, emp2, off suchthat
@hpos(2.5 inches) start [Office(emp1, off)@k(and)
@hpos(2.5 inches)        Office(emp2, off)@k(and)
@hpos(2.5 inches)	emp1@k(neq)emp2]
@end(verbatim)
@caption(match network for office constraint)
@end(figure)

@begin(text, linewidth 3.33 inches, columns 2, columnmargin .33 inches, boxed)
@subsection(Example)
@begin(group)
To enforce the constraint:
@verbatim{
@k(all) emp1, emp2, off
   [[office(emp1, off)@k(and)
     office(emp2, off)]
   @hsp(4 points)@k(implies)emp1=emp2]}
@group{(in the style of the last consistency rule, with the repair)
@ap builds a node for:
@verbatim"emp1, emp2, off suchthat 
  Start* @r(~)[[office(emp1, off)@k(and)
             office(emp2, off)]
           @hsp(4 points)@k(implies)emp1=emp2]"
This simplifies to:
@verbatim"emp1, emp2, off suchthat 
  Start* [office(emp1, off)@k(and)
          office(emp2, off)@k(and)
          emp1@k(neq)emp2]"}
The @k(neq) relation is known to be @b"static" (never updated), so we don't need
to worry about it @i(becoming) true.  This description 
compiles into four nodes as shown in the figure above.  
@end(group)
@comment[This is compiled (and optimized) by the @ap compiler.  Notice this program 
accesses the "new" state, a combination of P and U.]
Note that the programs access the "new" state of the database, so that
atomically replacing one occupant with another will not cause a match.
The implementation of this is discussed later.

@subsection(Compiling the match network)

The "matchnode compiler", a program for constructing nodes, takes as
input a variable list and a simplified wff.@foot[The simplifier reduces
all connectives to {and, or, not}, pushes negations all the way inward
and does "obvious" simplifications, e.g., @r(~)@r(~)P = P.]  
We will assume that all Previously's have been translated into Start's:@*
Previously P @k(equiv) (Start @r(~)P@k(or)(P@k(and)@r(~)Start P))

The result is either a node that computes tuples satisfying the description, an
indication that the description is unsatisfiable, e.g., @*@t[x, y suchthat
Start x=y], or an indication that the description cannot be compiled, e.g, it's
"irrelevant".  Another reason a description cannot be compiled is that its
program cannot be compiled (see @cite[compiler]).  @foot[In @ap,
"optimizations" such as Start* and static relations sometimes influence
whether a description can be compiled.  For instance, they may "optimize out"
something that is uncompilable.]

The matchnode compiler builds matchnodes that can be understood
in four levels, described below.  The matchnodes in any level have
predecessors only in earlier levels.

@para[Input nodes]

Input nodes are the simplest.  Their descriptions have two forms:
@verbatim[x@-(1),...,x@-(n) suchthat Start R(x@-(1),...,x@-(n))
x@-(1),...,x@-(n) suchthat Start @r(~)R(x@-(1),...,x@-(n))]
where R is an n-ary relation.  A node with the first description computes
the set of tuples added to R, while a node with the second description
computes the set of tuples deleted from R.

@para[Starts of other literals]
@label(otherlits)

More general literals (non-compound wffs and their negations) differ from those
above only in that their argument lists may contain constants and duplicated 
variables, and that the variables in the arguments and in the variable list 
may appear in different orders.
Starts of such literals are handled by successors of input nodes, as illustrated 
by the nodes described below.
These examples all take input from the node for
@verbatim[x, y suchthat Start office(x, y)]

@begin(itemize)
@i(Constants:) The node for @*
@t[y suchthat Start office(John, y)]@*
has this program:@*
@t[if x=John produce y]

@i(Repeated variables:) The node for @*
@t[x suchthat Start office(x, x)] @*
has this program:@*
@t[if x=y produce x]

@i(Permutations:) The node for @*
@t[y, x suchthat Start office(x, y)]@*
has this program:@*
@t[produce y, x]
@end(Itemize)

As an example that combines all these cases, suppose we have an input node,
@verbatim[x, y, z, w suchthat Start R(x, y, z, w)]
and we want a node for
@verbatim[x, y suchthat Start R(2, y, x, x)]
For purposes of exposition we rename the variables to match the input node:
@verbatim[z, y suchthat Start R(2, y, z, z)]
To obtain such a node we start with the constant:
@verbatim[y, z, w suchthat Start R(2, y, z, w)
program: if x=2 produce y, z, w]
Next the repeated variable:
@verbatim[y, z suchthat Start R(2, y, z, z)
program: if x=2 if z=w produce y, z]
Finally the permutation gives:
@verbatim[z, y suchthat Start R(2, y, z, z)
program: if x=2 if z=w produce z, y]

@para[Conjunctions containing a Start of a literal]
@label(conjuncts)@label(existentials)

An example is
@verbatim{emp1, emp2, off suchthat
  [[Start office(emp1, off)]@k(and)
   office(emp2, off)@k(and)
   emp1@k(neq)emp2]}
These nodes have one predecessor which computes tuples satisfying the Start conjunct:
@verbatim[emp1, off suchthat
    Start office(emp1, off)]
(This is really the same input node that we saw before.  We rename the variables
for purposes of exposition.)
The program is constructed from these two descriptions.  It accepts as
inputs the variable list of the predecessor node's description, @i[inputs], 
and does the following:
@verbatim[iterate over @i[outputs - inputs] suchthat
  @i[remainder-of-conjunction] 
  produce @i[outputs]]
where @i[outputs] is the variable list of this node's description,
@i[outputs - inputs] is the set difference (order is immaterial) and
@i[remainder-of-conjunction] is the conjunction to be matched with the
Start conjunct removed.  In this case the program is:
@verbatim{iterate over emp2 suchthat 
  [office(emp2, off)@k(and)emp1@k(neq)emp2]
  produce emp1,emp2,off}
When @i[outputs - inputs] is empty, the loop
simplifies to a test:@*
@t"if @i[remainder-of-conjunction] produce @i[outputs]"@*
If several conjuncts are Start's, a choice can be made on grounds 
of efficiency.

This level also handles outer existential quantifiers, e.g.,
@verbatim{
emp1 suchthat
   @k(Exists) emp2, off 
    [[Start office(emp1, off)]@k(and)
     office(emp2, off)@k(and)
     emp1@k(neq)emp2]}
The program is almost the same as if the existential variables were in @i[outputs] 
but the existential variables are no longer produced,
and they remain quantified unless they're in @i(inputs):
@verbatim{if @k(Exists) emp2
    [office(emp2, off)@k(and)emp1@k(neq)emp2]
   produce emp1}

@comment[This has the same program, except that the existential variables
are no longer produced.  Recall that duplicate produced tuples are removed,
so if instead of producing the two tuples (a,b,c) and (a,c,b) we produce the
two tuples a and a, the second will be discarded.]

@comment[Up to here it should be obvious that the programs produce the 
"right" set of tuples.]

@para[Other compound wffs]
@label(disjuncts)

An example is
@verbatim{emp1, emp2, off suchthat
   Start* [office(emp1,off)@k(and)
           office(emp2, off)@k(and)
           emp1@k(neq)emp2]}
Such descriptions, "@t[@i(vars) suchthat @iWff]",
are translated into equivalent descriptions in disjunctive normal form (@b[DNF]),@*
"@w{@t[@i(vars) suchthat @i[W@-(1)]@k(or)...@k(or)@i[W@-(n)]]}"
where each @i[W@-(i)] takes the form described in @ref(conjuncts).
Intuitively, @i[W@-(i)] corresponds to one occurrence of a non-static
literal, L, in @iWff, and has the meaning that @iWff becomes true, at least
in part, due to L becoming true.  @i(W@-(i)) contains @t[Start @r"L"] as one conjunct.
Informally, we call "the rest of" @i[W@-(i)]
the @b(residue) of @iWff with respect to L.

The matchnode for "@t[@i(vars) suchthat @iWff]" simply computes the
union of the matches of its predecessors, which match the descriptions
"@t[@i(vars) suchthat @i[W@-(i)]]".  Unless all disjuncts use all of @i(vars)
there will be infinitely many matches, which will prevent compilation.

The desired form is achieved by applying distributive laws such as:
@verbatim{@k(Exists)x[P@k(or)Q] = @k(exists)xP@k(or)@k(exists)xQ}
In general this should be done from the outside in - wffs of the wrong
form may appear as subwffs of acceptable wffs, in which case they need
not be rewritten.  For instance
@verbatim{y suchthat
  [Start R(y)]@k(and)@k(Exists)x[P(x,y)@k(or)Q(x,y)}
matches the pattern of @ref(conjuncts).

When a conjunction must be rewritten it
must be distributed over @i(some) conjunct, C, with the property that 
@t[@i(variables) suchthat @r(C)]
is relevant, where @i(variables) is a list of variables free in C.
@verbatim[P@k(and)(Q@k(or)R) = (P@k(and)Q)@k(or)(P@k(and)R)
P@k(and)@k(exists)xQ = @k(exists)x(P@k(and)Q)]
Usually there's no choice - only one conjunct contains Start.
If no such conjunct leads to a compilable program, the description cannot be matched.

Start's are pushed inward (only as needed) by using the following identities:
@begin[group]
@begin(Verbatim)
[Start [P@k(and)Q]] = 
   [[Start P]@k(and)Q]@k(or) [[Start Q]@k(and)P]
[Start [P@k(or)Q]] = 
   [[Start P]@k(and)@r(~)[Previously Q]]@k(or)
   [[Start Q]@k(and)@r(~)[Previously P]]
[Start @k(all)xP] = @k(exists)x[Start P]@k(and)@k(all)xP
[Start @k(exists)xP] = 
   @k(exists)x[Start P]@k(and)@r(~)[Previously @k(exists)xP]

[Start* [P@k(and)Q]] = 
   [[Start* P]@k(and)Q]@k(or)[[Start* Q]@k(and)P]
[Start* [P@k(or)Q]] = 
   [Start* P]@k(or)[Start* Q]
[Start* @k(all)xP] = @k(exists)x[Start* P]@k(and)@k(all)xP
[Start* @k(exists)xP] = @k(exists)x[Start* P]@r{@foot"This definition
of Start* has the properties that [Start P] @k(implies) [Start* P] and that
[Start* P] @k(implies) P.  It thus meets the requirements of Start*,
since @w([Previously @r(~)P]) @k(implies) [[Start P] @k(equiv) P]."}
@end(verbatim)
@end(group)
Note that, for literals, Start* is the same as Start.

Notice that outer @k(all)'s cannot be matched.  
Such descriptions look like 
@verbatim[x suchthat @k(All)y Start office(x, y)]
@ap assumes a world with infinitely many objects.@comment[, e.g.,
all numbers are objects.]  Therefore this describes
a transition with infinitely many updates.@foot{The 
example can be altered to be satisfied by finite transitions, e.g.,
@t{nil suchthat @k(All)y [Q(y)@k(implies)Start P(y)]}
but this is "irrelevant" if Q is ever empty.
For quantifying over fixed finite sets,@k(and)seems
more appropriate than @k(All).  In any case, outer @k(All)'s have not arisen in
practice.}

Note the result contains at most one disjunct per literal occurrence
in the original wff.

@subsection(Detailed example)
@begin(group)
We now illustrate by carrying out the procedure for the automation trigger:
@verbatim{person, acct suchthat 
  owns(person, acct)@k(and)
  Start @k(exists) bal, min
         [balance(acct, bal)@k(and)
          threshhold(acct, min)@k(and)
          bal<min]}
@end(group)
@begin(group)
Since this is a conjunction but not in the desired form, it will have to be
distributed over a relevant conjunct.  Only one conjunct contains a start,
but that start is on the outside, so it must be pushed inward:
@verbatim{
owns(person, acct)@k(and)
@k(exists) bal, min 
   [Start [balance(acct, bal)@k(and)
           threshhold(acct, min)@k(and)
           bal<min]]
@k(and)
@r(~)Previously @k(exists) bal, min
              [balance(acct, bal)@k(and)
	       threshhold(acct, min)@k(and)
	       bal<min]}
@end(group)
@begin(group)
Now we have three conjuncts, only one of which (an existential) contains start.
We can push the conjunction inside the existential:
@verbatim{
@k(exists) bal, min 
  [Start [balance(acct, bal)@k(and)
          threshhold(acct, min)@k(and)
          bal<min]]
 @k(and)owns(person, acct)
 @k(and)
  @r(~)Previously @k(exists) bal, min
                [balance(acct, bal)@k(and)
	         threshhold(acct, min)@k(and)
	         bal<min]}
@end(group)
@begin(group)
This still has the wrong form because the conjunction in the existential
does not contain start of a literal.  The conjunction must again be pushed
inside a relevant conjunct.  Again, only one conjunct contains start, and
since that start is on the outside, it must be pushed in:
@verbatim{
@k(exists) bal, min 
  [[Start balance(acct, bal)@k(and)
    threshhold(acct, min)@k(and)
    bal<min]
  @k(or)
   [balance(acct, bal)@k(and)
    Start threshhold(acct, min)@k(and)
    bal<min]]
 @k(and)owns(person, acct)
 @k(and)
  @r(~)Previously @k(exists) bal, min
                [balance(acct, bal)@k(and)
	         threshhold(acct, min)@k(and)
	         bal<min]}
Note that @t(<) never changes so its Start conjunct simplifies to false.
@end(group)
@begin(group)
We can now move the conjunction and quantifier inside the disjunction
to achieve the desired form:

@verbatim{
@k(exists) bal, min
   [owns(person, acct)@k(and)
    Start balance(acct, bal)@k(and)
    threshhold(acct, min)@k(and)
    bal<min@k(and)
    @r(~)Previously 
        @k(exists) bal, min
         [balance(acct, bal)@k(and)
	  threshhold(acct, min)@k(and)
	  bal<min]]
@k(or)
@k(exists) bal, min 
   [owns(person, acct)@k(and)
    balance(acct, bal)@k(and)
    Start threshhold(acct, min)@k(and)
    bal<min@k(and)
    @r(~)Previously
        @k(exists) bal, min
         [balance(acct, bal)@k(and)
	  threshhold(acct, min)@k(and)
	  bal<min]]}
@end(group)
@begin(group)
The match network is shown below.  Node 3 produces (person, account) tuples that
satisfy the first disjunct above while node 4 produces those that satisfy the
second.  The program for node 3 accepts (acct, bal) pairs that have just been added
and does the following:
@verbatim{iterate over person suchthat
  @k(exists) min 
   [owns(person, acct)@k(and)
    threshhold(acct, min)@k(and)
    bal<min@k(and)
    @r(~)Previously
        @k(exists) bal, min
         [balance(acct, bal)@k(and)
          threshhold(acct, min)@k(and)
	  bal<min]]
 produce person,acct}
@end(group)
@begin(figure)
@begin(verbatim)

     @b(node 1)@hpos(1.7 inches)     @b(node 2)
@r(output description:)@hpos(1.7 inches)@r(output description:)
 acct, bal suchthat@hpos(1.7 inches) acct, min suchthat
 start@hpos(1.7 inches) start
  Balance(acct, bal)@hpos(1.7 inches)  Threshhold
@hpos(1.7 inches)     (acct, min)


     @b(node 3)@hpos(1.7 inches)     @b(node 4)
@r[program: (see text above)]@hpos(1.7 inches)@r[(similar to node 3)]
@r[output description:@hpos(1.7 inches)
 (see text above)]@hpos(1.7 inches)


@hpos(.55 inches)          @b(node 5)
@hpos(.55 inches)@r(program:)
@hpos(.55 inches) produce union of outputs
@hpos(.55 inches) of nodes 3 and 4
@hpos(.55 inches)@r(output description:)
@hpos(.55 inches) person, acct suchthat 
@hpos(.55 inches)  owns(person, acct)@k(and)
@hpos(.55 inches)  Start @k(exists) bal, min
@hpos(.55 inches)         [balance(acct, bal)@k(and)
@hpos(.55 inches)          threshhold(acct, min)@k(and)
@hpos(.55 inches)          bal<min]
@end(verbatim)
@caption(match network for low balance rule)
@end(figure)
A good query optimizer (see @cite[compiler]) can make this query
reasonably cheap: if the balance is less than the threshold
and this was not previously true, iterate over all owners of the account.

@section(Discussion)

@subsection (Large atomic updates)

One possible way to match atomic transitions involving several updates is
to consider the updates in some order, and match each separately.  This is 
what RETE does.  Our algorithm exploits the fact that the resulting "intermediate
states" are of no interest, which in some cases saves a lot of effort.
For example, consider matching@*
@t{x, y suchthat Start [P(x)@k(and)Q(x)@k(and)R(y)]}@*
in response to@*
@t{atomic [insert P(1); delete Q(1)]}.  This uses the matchnode for@*
@t{x, y suchthat@*
  [[Start P(x)]@k(and)Q(x)@k(and)R(y)]}, containing the program:@*
@t{iterate over y suchthat [Q(x)@k(and)R(y)]@*
  produce x,y}@*
Normally the query optimizer will decide to
test Q before generating R.  In the update above, this is false, so R 
needn't be generated.  If the atomic were treated as
an addition to P followed by a deletion of Q, a tuple for every element
of R would have to be created for the intermediate state and then discarded.

Notice that our algorithm accesses the database in both the previous and new
states.  Our implementation actually divides "the database" into a large
previous database and a smaller database of updates.  All code that accesses
the database is therefore slightly more expensive: code to iterate over tuples
of a relation first iterates through the tuples added in the current
transition, and then iterates through tuples in the previous database, skipping
any removed in the current transition.  Classifying the updates by relation
makes the extra cost nearly negligible for relations that are not being
changed.  Hashing the changes further reduces the cost for accessing relations
that are being changed.  Of course, queries inside Previously are trivial.

@subsection (Sharing code)
@label(similarity)

One way in which a human programmer might achieve more efficiency
is to share code among several rules.  One could imagine
trying to transform wffs in order to obtain common subexpressions and
then matching those subexpressions only once.  There are several reasons
not to do this.  One is that it would be quite expensive.  This argument
is relevant to @ap since rules are frequently added and deleted
while the database is in use.  Thus the expense would be paid
at "run time" rather than "compile time".  A more interesting reason not
to factor out common subexpressions is that efficiency can suffer
due to limitations this places on query optimization.  In extreme 
cases the result may even be uncompilable.  

For example, suppose we want to match these two triggers:@* 
@verbatim{x y suchthat 
    Start [P1(x, y)@k(and)[Q(x)@k(or)R(y)]]
x y suchthat 
    Start [P2(x, y)@k(and)[Q(x)@k(or)R(y)]]}@*
We might try to "share" the common disjunction by producing a matchnode for@*
@t{x y suchthat Start [Q(x)@k(or)R(y)]}@*
But this is impossible - 
a single addition to Q would produce infinitely many matches (almost none
of which will satisfy either P1 or P2).  The current algorithm generates
two matchnodes to react to additions to Q.  They have similar programs:
@verbatim{iterate over y suchthat
  [P1(x, y) and @r(~)Previously R(y)]
  produce x,y}
The compiler can handle this by generating P1 and testing R.  By not 
overspecifying we allow the query optimizer to find a good algorithm.

The RETE algorithm does try to achieve maximal sharing of common 
subexpressions, although it does not rewrite expressions to increase
sharing.  However, since it does no query optimization this sharing can only help it.

Our present implementation does exploit a few opportunities for sharing.
Rather than building two different matchnodes for the same description,
it connects the same matchnode to additional outputs (thus saving the
computation that would be done in the copy).  This sharing occurs mainly
at input nodes, but occasionally at nodes described in @ref(otherlits),
which is the main reason for building such nodes.  Sharing at other nodes
is, of course, rare.

Another source of sharing is defined relations.  When meaningful expressions
recur, programmers tend to invent a new relation, using the expression as
its definition.  @ap supports this activity.
The default in @ap is to build matchnodes to detect tuples
that start or stop satisfying these definitions.  The optimization decision
of when to override this default is the programmer's responsibility.
Fortunately, this does not seem to arise often.
@comment[Users could thus control the exploitation of
structural similarity, should that ever become desirable, by defining
new relations or overriding the default.]  
Other than these special cases, we have found that sharing common 
subexpressions seems not to help much in practice.

@subsection(Alternative residues)

The residues@foot[see @ref(disjuncts) for the meaning of "residue"] 
computed above may seem obvious, but others are possible.
For instance, Start* can be defined in many different ways.
Residues of course must filter out non-matches, but they can also
provide efficient, though logically redundant, filters.  This presents 
interesting choices.  Consider the example:
@verbatim{x, y suchthat
     Start [P(x, y)@k(and)[@r(~)Q(x)@k(or)R(y)]]}
When R(y) becomes true we execute:
@verbatim{iterate over x suchthat
  [Previously Q(x)@k(and)P(x, y)] 
  produce x,y}
If the description were known to be previously unsatisfied, the program for 
Start* would seem better:
@verbatim[iterate over x suchthat
  P(x, y) produce x,y]
since it avoids testing a redundant condition.  But the redundant condition
does not necessarily indicate wasted effort!  Suppose P were indexed on x, 
i.e., it's easy to generate @w"y suchthat P(x, y)" but hard to generate 
x suchthat P(x, y).  It might be faster
to generate Q and test P.  @AP allows users to choose (and even invent) 
representations for relations.  If @w[P(x, y)] is represented by a pointer 
from x to y, so x suchthat P(x, y) cannot be generated at all, we've 
"optimized out" what was needed to match the description!
@foot[Notice that this constraint can be incrementally enforced even
though it cannot be totally checked.]

We have tried to factor out query optimization concerns from the matchnode 
compiler.  It therefore does not know which of these alternatives will
actually be better.  It seems best for Start* to not actually discard
the extra conjuncts that would have been produced by Start, but mark them as
"optional", so the query optimizer can use them only if they help.
This facility could be put to good use in other contexts as well, e.g., 
optimizing queries in contexts where certain constraints can be assumed.  
This appears straight forward, although we have not yet done it in @ap.

The next example shows that query optimization can
depend on rather esoteric information.
Consider the constraint that some person has no spouse:
@verbatim{@k(exists)x [P(x)@k(and)@k(all)y @r(~)S(x, y)]}
We would trigger on
@verbatim{Start* [@k(all)x [@r(~)P(x)@k(or)@k(exists)y S(x,y)]]}
Our algorithm indicates that whenever S(x,y) is added we should
optionally check Previously P(x).  If it's true (or we didn't
bother to check) then recheck the original constraint.  The optional
check is likely to be much cheaper than rechecking the constraint
(unless we maintain some additional information, such as the unmarried
people or their number).  The remaining question is how effective the
optional filter will be, i.e., the likelihood that a person with a new
spouse is also a new person.  This kind of data describing update patterns
is rarely available to query optimizers.

@begin(comment)
- always true - what makes a variant "syntactic" - it's undecidable whether
2 wffs are equivalent, so we cannot expect equivalent wffs always to be eval'd
the same way.

Finally we point out that syntactic variants can lead to different residues.
@verbatim{nil suchthat 
     Start [@k(All) x [@r(~)P(x)@k(and)@r(~)Q(x)]]}
is equivalent to (but might not simplify to)
@verbatim{nil suchthat 
     Start [@k(All) x @r(~)P(x)@k(and)@k(all) x @r(~)Q(x)]}
On deleting @t[P(x)] for the former trigger our algorithm produces a
test of @t[Q(x)] in addition to rechecking the whole constraint.  This
test is not produced for the second trigger.  While both are correct, one
might be more efficient.  Thus in principle one might consider
syntactic variants in order to find a good algorithm.  
@end(comment)

@subsection("Compiling in" more context)

Another way to improve efficiency is to make use of more
contextual information.  For example, if we can detect that one
constraint implies another, the weaker one (may) not need to be enforced.
@foot[In @ap this is semantically equivalent only if the weaker constraint
has no repair!]
Similarly, we might prove at compile time that atomically creating two
new people and asserting they are married cannot violate the constraint 
that some person must be unmarried.

While neither Nicolas nor Forgy do the kind of reasoning required for
the examples above, Nicolas uses one piece of information 
that @ap does not use:
constants in updates.  Suppose @w{P(2)} were prohibited.  For the update
@w{@t[insert P(x)]} both Nicolas and @ap would have to check that x@k(neq)2.  
However, for the update @w{@t[insert P(1)]}, Nicolas would detect at 
compile time that the constraint could not be violated,
while @ap would have to verify at run time that 1@k(neq)2.  Of course,
such interaction between updates and rules is unusual, and the cost of
failing to notice it is small.  @ap cannot make this optimization
because it does not compare particular updates to particular rules, but 
compiles each rule once
for all updates.  This reduces the cost of compiling N rules and M updates
from O(NM) to O(N+M), but it prevents any optimization that relies on the
interactions between particular rules and particular updates.

Similarly, the example above of one constraint implying another involves
interactions among rules, and one can imagine other complicated reasoning
involving updates and flow of control in the program.  Such a high degree
of optimization, though difficult, might be worthwhile for programs that
rarely change.  We have not concentrated on such
optimizations because in our typical use of @ap the programs and rules
are extremely volatile.

@section[Summary]
First we presented some small query language extensions, viz. descriptions,
Start and Previously, which permit convenient specification of triggers
involving database transitions.  This language, while far short of general
temporal reference, is much more expressive than first order logic
without any temporal reference.  Next we showed how such
specifications could be compiled into a matcher that efficiently detects
when the triggers are matched and by what data.  In the special case of
state constraints, the matcher compiles algorithms similar to those of
Nicolas.  However, it has some significant advantages, even in this
restricted context: it produces matches that can be used to repair
violations and it compiles rules independenly of any particular database
transition, which makes it much easier to change the application program.

@section[Acknowledgements]
In addition to the RETE algorithm, @ap has been greatly influenced by
its predecessor, AP3 and the gist specification language.
These in turn are the work of my colleagues at ISI, notably Neil Goldman.
He also deserves credit for complaining about previous versions of this
paper until an opaque algorithmic description became a set of 
logical manipulations whose correctness is almost obvious.
I also thank Dennis McLeod for helping to give the presentation more
of a database orientation.

@newcolumn()
@heading(References)
@bibliography()
@end(text)

@comment[relation to Nicolas:
(see other refs)

other start example shows that Nicolas is wrong that start*
 is always cheaper than the whole constraint?
no but in this case, while the original and start* are both
 impossible to check, start is possible!!

Nicolas points out that for large transactions, batch checking may be 
better...

treat as a variant of rete that does not store much more than the
entire databaswe

art as an extension to rete that provides or, not, all, exists
- first, quantifiers are not real, but only set union and difference
- second or is really just 2 rules, it doesn't remove dups
 i.e., to be notified when start(p or q) you'd have to do some programming
]