An event-condition-action language for XML.
XML repositories are now a widespread means for storing and exchanging information on the Web. As these repositories become increasingly used in dynamic applications such as e-commerce, there is a rapidly growing need for a mechanism to incorporate reactive functionality in an XML setting. Event-condition-action (ECA) rules are a technology from active databases and are a natural method for supporting suchfunctionality. ECA rules can be used for activities such as automatically enforcing document constraints, maintaining repository statistics, and facilitating publish/subscribe applications. An important question associated with the use of a ECA rules is how to statically predict their run-time behaviour. In this paper, we define a language for ECA rules on XML repositories. We then investigate methods for analysing the behaviour of a set of ECA rules, a task which has added complexity in this XML setting compared with conventional active databases.
Introduction
XML is becoming a dominant standard for storing and exchanging information. With its increasing
use in areas such as data warehousing and e-commerce [13, 14, 18, 22, 28], there is a rapidly growing
need for rule-based technology to support reactive functionality on XML repositories. Event-condition-
action (ECA) rules are a natural candidate to support such functionality. In contrast to implementing
reactive functionality directly within a programming language such as Java, ECA rules have a high
level, declarative syntax and are thus more easily analysed. Furthermore, many commercial and research
systems based on ECA rules have been successfully built and deployed, and thus their implementation
within system architectures is well-understood.
ECA rules automatically perform actions in response to events provided stated conditions hold.
They are used in conventional data warehouses for incremental maintenance of materialised views, for
validation and cleansing of the input data streams, and for maintaining audit trails of the data. By
analogy, ECA rules can also be used as an integrating technology for providing this kind of reactive
functionality on XML repositories. They can also be used for checking key and other constraints on
XML documents, and for performing automatic repairs when violations are detected. For a 'push' type
environment, they are a mechanism for automatically broadcasting information to subscribers as the
contents of relevant documents change. They can also be employed as a flexible means for maintaining
statistics about document and web site usage and behaviour. In this paper, we present a language in
which ECA rules on XML can be defined.
ECA rules have been used in many settings, including active databases [26, 29], workflow manage-
ment, network management, personalisation and publish/subscribe technology [3, 13, 14, 17, 27], and
specifying and implementing business processes [2, 16, 22]. However, one of the key recurring themes
regarding the successful deployment of ECA rules is the need for techniques and tools for analysing their
behaviour [15, 23]. When multiple ECA rules are defined within a system, their interactions can be
difficult to analyse, since the execution of one rule may cause an event which triggers another rule or set
of rules. These rules may in turn trigger further rules and there is indeed the potential for an infinite
cascade of rule firings to occur. Thus, the second part of this paper explores techniques for analysing the
behaviour of a set of ECA rules defined in our language.
Other ECA rule languages for XML have been proposed in [13, 14, 22] but none of these focus on
analysing the behaviour of the ECA rules. It is proposed in [13] that analysis techniques developed for
conventional active databases can be applied in an XML setting too, but details are not given.
A more recent paper [12] also defines an active rule language for XML, but is not concerned with rule
analysis. The rule syntax it describes is similar to the one we define here, the rule format being based
on the definition of triggers in SQL3. Its rule execution semantics is rather different from the model we
adopt, however. Generally speaking, insertions and deletions of XML data (so-called bulk statements)
may involve document fragments of unbounded size. [12] describes a semantics whereby each (top-level)
update is decomposed into a sequence of smaller updates (which depend on the contents of the fragment
being inserted/deleted) and then trigger execution is interleaved with the execution of these smaller
updates. In contrast, we treat each top-level update as atomic and trigger execution is invoked only after
completion of the top-level update. In general, these semantics may produce different results for the
same top-level update and it is a question of future research to determine their respective suitability in
different applications.
In an earlier paper [7] we described some initial proposals for analysis, and also optimisation, of
XML ECA rules. The language we discussed there was less expressive then the language we propose
here in that it did not allow disjunction or negation in rule conditions. Moreover, here we examine more
deeply the triggering and activation relationships between rules and have derive more precise tests for
determining both of these relationships than the tests we described in [7].
2 The ECA Rule Language
An XML database consists of a set of XML documents. Event-condition-action (ECA) rules on XML
databases take the following form:
on event
if condition
do actions
Rather than introducing yet another query language for XML, we use the XPath [32] and XQuery [33]
languages to specify events, conditions and actions within our ECA rules. XPath is used in a number
of W3C recommendations, such as XPointer, XSLT and XQuery itself, for selecting and matching parts
of XML documents and so is well-suited to the requirements of ECA rules. XQuery is used in our ECA
rules only where there is a need to be able to construct new fragments of XML. We define each of the
components of our ECA rule language below, give some example rules, and describe the rule execution
semantics.
2.1 Rule Events
The event part of an ECA rule is an expression of the form
or
where e is a simple XPath expression (defined in Section 2.4 below) which evaluates to a set of nodes.
The rule is said to be triggered if this set of nodes includes any node in a new sub-document, in the case
of an insertion, or in a deleted sub-document, in the case of a deletion.
The system-defined variable $delta is available for use within the condition and actions parts of the
rule (see below), and its set of instantiations is the set of new or deleted nodes returned by e.
2.2 Rule Conditions
The condition part of an ECA rule is either the constant TRUE, or one or more simple XPath expressions
connected by the boolean connectives and, or, not.
The condition part of an ECA rule is evaluated on each XML document in the database which has
been changed by an event of the form specified in the rule's event part. If the condition references the
system-defined it is evaluated once for each instantiation of $delta for each document.
Otherwise, the condition is evaluated just once for each document.
2.3 Rule Actions
The actions part of an ECA rule is a sequence of one or more actions:
action
These actions are executed on each XML document which has been been changed by an event of the
form specified in the rule's event part and for which the rule's condition query evaluates to True - we
call this set of documents the rule's set of candidate documents.
An ECA rule is said to fire if its set of candidate documents is non-empty.
Each action i above is an expression of the form
INSERT r BELOW e [BEFOREjAFTER q]
or
where r is a simple XQuery expression, e is a simple XPath expression and q is either the constant TRUE
or an XPath qualifier - see Sections 2.4 and 2.5 below for definitions of the italicised terms.
In an INSERT action, the expression e specifies the set of nodes, N , immediately below which new
sub-document(s) will be inserted. These sub-documents are specified by the expression r 1 . If e or r
references the $delta variable then one sub-document is constructed for each instantiation of $delta for
which the rule's condition query evaluates to True. If neither e nor r references $delta then a single
sub-document is constructed 2 .
q is an optional XPath qualifier which is evaluated on each child of each node n 2 N . For insertions
of the form AFTER q, the new sub-document(s) are inserted after the last sibling for which q is True,
while for insertions of the form BEFORE q, the new sub-document(s) are inserted before the first sibling
for which q is True. The order in which new sub-documents are inserted is non-deterministic.
In a DELETE action, expression e specifies the set of nodes which will be deleted (together with their
sub-documents). Again, e may reference the $delta variable.
Example 1 Consider an XML database consisting of two documents, s.xml and p.xml. The document
contains information on stores, including which products are sold in each store:
!store id="s1"?
!product id="p1"/?
!product id="p2"/?
We observe that using the phrase BELOW e to indicate where the update should happen is significant. Without it the
placement of new sub-documents would be restricted to occurring only at the root node of documents.
Thus, both document-level and instance-level triggering are supported in our ECA rule language. If there is no
occurrence of the $delta variable in a rule action, the action is executed at most once on each document each time the rule
fires - this is document-level triggering. If there is an occurrence of $delta in an action part, the action is executed once
for each possible instantiation of $delta on each document - this is instance-level triggering.
The document p.xml holds information on each product, including which stores sell each product:
!product id="p1"?
!store id="s1"/?
!store id="s2"/?
The following ECA rule updates the p.xml document whenever one or more products are added
below an existing store in s.xml:
on INSERT document('s.xml')/stores/store/product
if not(document('p.xml')/products/
product[@id=$delta/@id]/store[@id=$delta/./@id])
do INSERT !store id='-$delta/./@id-'/?
BELOW document('p.xml')/products/
product[@id=$delta/@id] AFTER TRUE
Here, the system-defined $delta variable is bound to the newly inserted product nodes detected by the
event part of the rule. The rule's condition checks that the store which is the parent of the inserted
products in s.xml is not already a child of those products in p.xml. The action then adds the store as a
child of those products in p.xml.
In a symmetrical way, the following ECA rule updates the s.xml document whenever one or more
stores are added below an existing product in p.xml:
on INSERT document('p.xml')/products/product/store
if not(document('s.xml')/stores/
store[@id=$delta/@id]/product[@id=$delta/./@id])
do INSERT !product id='-$delta/./@id-'/?
BELOW document('s.xml')/stores/
store[@id=$delta/@id] AFTER TRUE
The two rules ensure that the information in the two documents is kept mutually consistent.
Example 2 This example is taken from [1] which discusses view updates on semi-structured data. The
XML database consists of two documents, g.xml and m.xml. g.xml contains a restaurant guide, with
information about restaurants, including the entrees they serve, and the ingredients of each entree:
!name?Baghdad Cafe!/name?
!rating?Four stars!/rating?
!name?Cheeseburger Club!/name?
The document m.xml is a view derived from g.xml, and contains a list of those entrees at the Baghdad
Cafe where one of the ingredients is Mushroom:
Suppose now an ingredient element with value Mushroom is added to the second (unnamed) entree of
the Baghdad Cafe in g.xml. The following ECA rule performs the view maintenance of m.xml:
on INSERT document('g.xml')/guide/restaurant/
entree/ingredient
if $delta[.='Mushroom'] and
$delta/.[name='Baghdad Cafe']
do INSERT $delta/. BELOW document('m.xml')/entrees
AFTER TRUE
The resulting m.xml document is:
Note that inserting $delta/. results in the complete entree being inserted, while AFTER TRUE causes
it to be inserted after the last child of entrees.
2.4 Simple XPath Expressions
The XPath and XQuery expressions appearing in our ECA rules are restrictions of the full XPath [32]
and XQuery [33] languages, to what we term simple XPath and XQuery expressions. These represent
useful and reasonably expressive fragments which have the advantage of also being amenable to analysis.
The XPath fragment we use disallows a number of features of the full XPath language, most notably
the use of any axis other than the child, parent, self or descendant-or-self axes and the use of all functions
other than document(). Thus, the syntax of a simple XPath expression e is given by the following
grammar, where s denotes a string and n denotes an element or attribute name:
Expressions enclosed in '[' and `]' in an XPath expression are called qualifiers. So a simple XPath
expression starts by establishing a context, either by a call to the document function followed by a path
expression p, or by a reference to the variable $delta (the only variable allowed) followed by optional
qualifiers q and an optional path expression p. Note that a qualifier q can comprise a simple XPath
expression e.
If we delete all qualifiers (along with the enclosing brackets) from an XPath expression, we are left
with a path of nodes. We call this path the distinguished path of the expression and the node at the end
of the distinguished path the distinguished leaf of the expression.
The result of an XPath expression e is a set of nodes, namely, those matched by the distinguished
leaf of the expression. The (simple) result type of e, denoted type(e), is one of string, element name n or
*, where * denotes any element name. The result type can be determined as follows.
Let p be the distinguished path of e. If the leaf of p is @n or @*, type(e) is string. If the leaf of p is
n or *, type(e) is n or *, respectively. If the leaf is '.' or `.', type(e) is determined from the leaf of a
modified distinguished path 3 which is defined below.
The modified distinguished path is constructed from the distinguished path p of expression e by
replacing each occurrence of '.' and `.' from left to right in p as follows. If p starts with $delta, then
we substitute for $delta the distinguished path of the XPath expression which occurs in the event part
of the rule. If the step is '.' and it is preceded by `a/' (where a must be either an element name or *'),
then replace 'a/.' with `. If the separator preceding the occurrence of `.' or '.' is `//', then replace
the step with '*'. If the step is `.' and the separator which precedes it is '/', then delete the step and its
preceding separator.
Example 3 Consider the condition from the ECA rule of Example 2, namely,
if $delta[.='Mushroom'] and
$delta/.[name='Baghdad Cafe']
The result type of the first conjunct is ingredient because the event part of the rule is
on INSERT document('g.xml')/guide/restaurant/
entree/ingredient
The result type of the second conjunct is restaurant, determined as follows. The distinguished path
after substituting $delta is
document('g.xml')/guide/restaurant/entree/
ingredient/.
So we replace 'ingredient/.' with `.', we delete '/.', we replace `entree/.' with '.', and finally we
delete '/.', leaving the modified distinguished path
document('g.xml')/guide/restaurant
3 The modified distinguished path is simply used to determine the result type; it may not be equivalent to the original
path p.
Type inference is part of the XQuery formal semantics defined in [34]. This allows an implementation
of XQuery to infer at query compile time the output type of a query on documents conforming to a given
input type (DTD or schema). Since XPath expressions are part of XQuery, their result types can also
be inferred. Thus, in the presence of a DTD or XML schema, it is possible to infer more accurate result
types for XPath expressions using the techniques described in [34] 4 .
2.5 Simple XQuery Expressions
The XQuery fragment we use disallows the use of full so-called FLWR expressions (involving keywords
'for,' `let,' 'where' and `return'), essentially permitting only the 'return' part of an expression [33].
The syntax of a simple XQuery expression r is given by the following grammar:
r
c ::= '!' n a (`/?' j ('?' t\Lambda `!/' n '?'))
a ::= (n '= "' (s
Thus, an XQuery expression r is either a simple XPath expression e (as defined in Section 2.4) or an
element constructor c. An element constructor is either an empty element or an element with a sequence
of element contents t. In each case, the element can have a list of attributes a. An attribute list a can
be empty or is a name equated to an attribute value followed by an attribute list. An attribute value is
either a string s or an enclosed expression e 0 . Element contents t is one of a string, an element constructor
or an enclosed expression. An enclosed expression e 0 is an XPath expression e enclosed in braces. The
braces indicate that e should be evaluated and the result inserted at the position of e in the element
constructor or attribute value.
The result type of an XQuery expression r, denoted type(r), is a tree, each of whose nodes is of type
(for element name n), @n (for attribute name n), *, n//*, or string. The types with a suffix
//* indicate that the corresponding node can be the root of an arbitrary subtree. This is necessary to
capture the fact that the results of XPath expressions embedded in r return sets of nodes which may be
the roots of subdocuments. The tree for type(r) can be determined as follows. If r is an XPath expression
e, then type(r) comprises a single node whose type is type(e)//* if type(e 0 ) is n or *, or string if
is string. If r is an element constructor c, then we form a document tree T from c in the usual way,
except that some nodes will be labelled with enclosed expressions. For each such enclosed expression e 0 ,
we determine its result type type(e 0 ) in the same way as for the single XPath expression above. We then
replace e 0 in T by type(e 0 ). Now type(r) is given by the modified tree T .
The result type of an XQuery expression r denotes a set of trees S such that every tree returned by r
is in S (the converse does not necessarily hold because we do not type the results of enclosed expressions
as tightly as possible). We call each tree in S an instance of type(r). Given an XPath expression e and a
tree T , T satisfies e if e(T ) 6= ;. We say that may satisfy e if some instance of type(r) satisfies e.
Given XPath expression e and XQuery expression r, it is straightforward to test whether or not
may satisfy e. The test essentially involves checking whether the evaluation of e on the tree
of type(r) is empty or not. However, since type(r) denotes a set of trees rather than a single tree, the
evaluation needs to be modified as indicated in the following informal description: a node of type string
in type(r) may satisfy any string in e; a node of type * in type(r) may satisfy any element name in e; a
node of type n//* (respectively, *) in type(r) may satisfy any expression in e which tests attributes
or descendants of an element name n (respectively, any element name).
Example 4 Let r be the XQuery expression in the action of the first rule in Example 1, namely
!store id='-$delta/./@id-'/?.
The result type of $delta/./@id is string, so type(r) is store(@id(string)).
As another example, let r be the XQuery expression
4 Although the parent function in [34], which corresponds to a step of '.', always returns the type anyElement?.
and assume that the result type of -$delta/.- is *. Then type(r) is a(b( == ))(c).
2.6 ECA Rule Execution
In this section we describe informally the ECA rule execution semantics, giving sufficient details for our
purposes in this paper. We refer the interested reader to [7] for a fuller discussion.
The input to ECA rule execution is an XML database and a schedule. The schedule is a list of
updates to be executed on the database. Each such update is a pair
(a
The component a i;j is an action from the actions part of some rule r i . The component docsAndDeltas i
is a set of pairs (d; deltas d;i ), where d is the identifier of a document upon which a i;j is to be applied and
deltas d;i is the set of instantiations for the $delta variable generated by the event and condition part of
rule r i with respect to document d.
The rule execution begins by removing the update at the head of the schedule and applying it to the
database. For each rule r i , we then determine its set of candidate documents generated by this update,
together with the set deltas d;i for each candidate document d. For all rules r i that have fired (i.e. whose
set of candidate documents is non-empty) we place their list of actions a at the head of the
schedule, placing the actions of higher-priority rules ahead of the actions of lower-priority rules 5 . Each
such action a i;j is paired with the set docsAndDeltas i consisting of the set of candidate documents for
rule r i with the set of instantiations deltas d;i for each such document d.
The execution proceeds in this fashion until the schedule becomes empty. Non-termination of rule
execution is a possibility and thus rule analysis techniques are important for developing sets of 'well-
behaved' rules.
Analysing ECA Rule Behaviour
Analysis of ECA rules in active databases is a well-studied topic and a number of analysis techniques
have been proposed, e.g. [4, 5, 6, 8, 9, 10, 11, 16], mostly in the context of relational databases. Analysis
is important, since within a set of ECA rules, unpredictable and unstructured behaviour may occur.
Rules may mutually trigger one another, leading to unexpected (and possibly infinite) sequences of rule
executions.
Two important analysis techniques are to derive triggering [4] and activation [10] relationships
between pairs of rules. This information can then be used to analyse properties such as termination
or confluence of a set of ECA rules, or reachability of individual rules. The triggering and activation
relationships between pairs of rules are defined as follows:
A rule r i may trigger a rule r j if execution of the action of r i may generate an event which triggers
r j .
A rule r i may activate another rule r j if r j 's condition may be changed from False to True after the
execution of r i 's action.
A rule r i may activate itself if its condition may be True after the execution of its action.
Thus, two key analysis questions regarding ECA rules are:
1. Is it possible that a rule r i may trigger a rule r j ?
2. Is it possible that a rule r i may activate a rule r j ?
Once triggering and activation relationships have been derived, one can construct graphs which are
useful in analysing rule behaviour:
5 In common with the SQL3 standard for database triggers [24] we assume that no two rules can have the same priority.
This, together with our use of restricted sub-languages of XPath/XQuery, ensures that rule execution is deterministic in
our language, up to the order in which new sub-documents are inserted below a common parent.
A triggering graph [4] represents each rule as a vertex, and there is a directed arc from a vertex r i
to a vertex r j if r i may trigger r j . Acyclicity of the triggering graph implies definite termination of rule
execution. Triggering graphs can also be used for deriving rule reachability information, by examination
of the arcs in the graph.
An activation graph [10] again represents rules as vertices and there is a directed from a vertex r i
to a vertex r j if r i may activate r j . Acyclicity of this graph also implies definite termination of rule
execution.
The determination of triggering and activation relationships between ECA rules is more complex
in an XML setting than for relational databases, because determining the effects of rule actions is not
simply a matter of matching up the names of updated relations with potential events or with the bodies
of rule conditions. Instead, the associations are more implicit and semantic comparisons between sets of
path expressions are required. We develop some techniques below.
3.1 Triggering Relationships between XML
ECA rules
In order to determine triggering relationships between our XML ECA rules, we need to be able to
determine whether an action of some rule may trigger the event part of some other rule. Clearly, INSERT
actions can only trigger INSERT events, and DELETE actions can only trigger DELETE events.
3.1.1 Insertions
For any insertion action a of the form
INSERT r BELOW e 1
[BEFOREjAFTER q]
in some rule r i and any insertion event ev of the form
in some rule r j , we need to know whether ev is independent of a, that is, e 2 can never return any of the
nodes inserted by a.
The simple XQuery r defines which nodes are inserted by a, while the simple XPath expression e 1
defines where these nodes are inserted. So, informally speaking, if it is possible that some initial part of
can specify the same path through some document as e 1
and the remainder of e 2
"matches" r, then
ev is not independent of a. We formalise these notions below, based on tests for containment between
XPath expressions [19, 20, 30].
A prefix of a simple XPath expression e is an expression e 0 such that We
call e 00 the suffix of e and e 0 . Recall from Section 2.5 that, for XQuery r, type(r) denotes the result type
of r, and we can test whether or not type(r) may satisfy an XPath expression e.
Given XPath expressions e 1
and e 2
, we say that
and e 2
are independent if, for all possible XML
documents d, e 1
Now let us return to the action a and event ev defined above. Event ev is independent of action a
if for all prefixes e 0of e 2
, either
and e 0are independent, or
00Equivalently, we can say that rule r i (containing action a) may trigger rule r j (containing event ev) if for
some prefix e 0of e 2
and e 0are not independent and type(r) may satisfy e 00From arbitrary simple XPath expressions e 1
and e 2
, we can construct an XPath expression e
such that for all documents d, e 1
)(d). This is done by converting the distinguished
paths of e 1
and e 2
to regular expressions, finding their intersection using standard techniques [21], and
converting the intersection back to an XPath expression with the qualifiers from e 1
and e 2
correctly
associated with the merged steps in the intersection. The resulting expression for
may have to
use a union of path expressions (denoted
) at the top level, as permitted by XPath [32].
We can test whether e
is unsatisfiable, and hence whether e 1
and e 2
are independent, by
checking whether e
is contained in an unsatisfiable expression, using the containment test developed
in [19] (which allows unions of path expressions).
Example 5 Recall the two rules from Example 1. Let us call them Rule 1 and Rule 2. For the
form of each rule is
on INSERT e i
do INSERT r i BELOW f i AFTER TRUE
where
is !store id='-$delta/./@id-'/? and
is document('p.xml')/products/
product[@id=$delta/@id]
while
is document('p.xml')/products/product/store,
is !product id='-$delta/./@id-'/? and
is document('s.xml')/stores/
store[@id=$delta/@id].
Now let e
document('s.xml')/stores/store,
e 00is product, e 0is document('p.xml')/products/product and e 00is store. So f 2
and e 0are not
independent. Furthermore, type(r 2 ) is product(@id(string)) which may satisfy e 00. We conclude that
Rule 2 may trigger Rule 1. A similar argument shows that Rule 1 may trigger Rule 2.
On the other hand, if event e 1 were modified to
document('s.xml')/stores/store/product[name]
so that the inserted product had to have a name child, then f 2 and e 0are still not independent. However,
now
00since the product node in type(r 2
does not contain a name child. In this
case, we would detect that Rule 2 could not trigger the modified Rule 1.
3.1.2 Deletions
Similarly to insertions, for any deletion action a of the form
belonging to a rule r i , and any deletion event ev of the form
belonging to a rule r j , we have that r i may trigger r j if ev is not independent of a.
The test for independence of an action and an event in the case of deletions is simpler than for
the insertion case above. Let e be the XPath expression e 1 //*. Event ev is independent of action a if
expressions e and e 2
are independent (which can be determined as in Section 3.1.1).
3.2 Activation Relationships between XML
ECA rules
In order to determine activation relationships between ECA rules, we need to be able to determine
(a) whether an action of some rule r i may change the value of the condition part of some other rule r j
from False to True, in which case r i may activate r j ; and
(b) whether all the actions of a rule r i will definitely leave the condition part of r i False; if not, then r i
may activate itself.
Without loss of generality, we can assume that rule conditions are in disjunctive normal form, i.e.
they are of the form
(l 1;1 and l 1;2
or (l 2;1 and l 2;2
(l m;1 and l
where each l i;j is either a simple XPath expression c, or the negation of a simple XPath expression, not
c.
3.2.1 Simple XPath expressions
The following table illustrates the transitions that the truth-value of a condition consisting of a simple
XPath expression can undergo. The first column shows the condition's truth value before the update,
and the subsequent columns its truth value after a non-independent insertion (NI) and a non-independent
deletion
before after NI after ND
rue T rue T rue or F alse
alse T rue or F alse F alse
For case (a) above, i.e. when r i and r j are distinct rules, it is clear from this table that r i can
activate r j only if one of the actions of r i is an insertion which is non-independent of the condition of r j .
Let the condition of r j be the simple XPath expression c.
For c to be True, we require that it returns a non-empty result. Thus, in a sense, the distinguished
path of c plays the same role as an XPath qualifier in that we are interested in the existence of some
path in the document matching the distinguished path. In addition, the insertion of an element whose
name occurs only in a qualifier of c can turn c from False to True. For example, the insertion of a d
element below /a/b can turn condition /a/b[d]/e from False to True. Thus we need to consider all the
qualifiers and the distinguished path in c in a similar way in any test for case (a). Moreover, the use of
'.' in a condition is analogous to introducing a qualifier, so we need to rewrite conditions accordingly.
For example, the condition a/b/./d is equivalent to a[b]/d. This condition can be turned from False
to True if either a d element is added below an a element which has a b element as a child, or a b element
is added below an a element which has a d element as a child.
The procedure for determining non-independence of an insertion from a condition, c, involves constructing
from c a set C of conditions, each of which is an XPath expression without any qualifiers i.e.
a distinguished path. The objective is that condition c can change from False to True as a result of an
insertion only if at least one of the conditions in C can change from False to True as a result of the
insertion. We start with set proceed to decompose c into a number of conditions without
qualifiers, adding each one to C.
A single step of the decomposition is as follows:
1. For any u and w, and v an element name n or *,
ffl if condition c i is of the form uv/.w, then replace c i in C by u./[v]w;
is of the form uv//.w, then replace c i in C by u./[v]w and uv//*].
2. We can delete from c i steps of the form /. and ./, as well as replacing occurrences of //.// by
//, thereby ensuring that . can occur only at the end of c i preceded by //
3. If c i 2 C is of the form u[v]w, where u, v and w are all non-empty, then replace c i in C by u[v] and
uw.
4. If c i 2 C is of the form u[v], where u and v are non-empty, then delete c i from C and add to C the
conditions specified by one of the cases below, depending on the structure of the qualifier v:
nonterminal p from the grammar for simple XPath expressions, then add u=v to
ffl if v matches nonterminal e, then add e to C;
ffl if v matches x 'or' y (where x and y must be qualifiers), then add u[x] and u[y] to C;
ffl if v matches x 'and' y (where x and y must be qualifiers), then add u[x] and u[y] to C;
y, then if x or y match nonterminal p, add u=x or u=y, respectively, to C,
while if x or y match nonterminal e, add x or y, respectively, to C.
The decomposition process continues until all conditions in C are qualifier-free.
Now let one of the actions a from rule r i be
INSERT r BELOW e 1
[BEFOREjAFTER q]
As in Section 3.1.1, we determine type(r) and consider prefixes and suffixes of each condition c
i . Set C of conditions is independent of a if for each c i 2 C and for each prefix c 0 of c,
either
and c 0
are independent, or
If so, then action a cannot change the truth value of condition c in rule r j from False to True. Equivalently,
we can say that rule r i may activate rule r j if for some prefix c 0
i of some c
and c 0
i are not
independent and type(r) may satisfy c 00
Example 6 The conjunction of conditions from the ECA rule in Example 2 can be rewritten as the
single condition c:
$delta[.='Mushroom']/.[name='Baghdad Cafe']
initially comprises just condition c, which, after substituting for $delta (and dropping document('g.xml')
for simplicity), is decomposed into the conditions
/guide/restaurant/entree/ingredient
and
Condition c 2
is further decomposed into
=guide=restaurant=entree=ingredient
Conditions c 3
and c 5
can be interpreted as stating that the only way an insertion can change condition
c from False to True is if an ingredient is inserted as a child of an entree, an entree is inserted as a
child of a restaurant, or a name is inserted as a child of a restaurant. The test described above will
detect these possibilities and will correctly infer the possible activation relationships.
For case (b) above, a rule r i activates itself if it may leave its own condition True. From the above
table, we see that with the analysis that we have used so far this will be the case for all rules. To obtain
more precision, we need to develop the notion of self-disactivating rules, by analogy to this property of
ECA rules in a relational database setting [9]. A self-disactivating rule is one where the execution of its
action makes its condition False.
If the condition part of r i is a simple XPath expression c, the rule will be self-disactivating if all its
actions are deletions which subsume c. For each deletion action
we thus need to test if
For the simple XPath expressions to which our ECA rules are constrained in this paper, and provided
additionally that the only operator appearing in qualifiers is '=', it is known that containment is
decidable [19]. Thus, it is possible to devise a test for determining whether rules are self-disactivating.
The decidability of containment for larger fragments of the XPath language is an open problem [19].
However, even if a fragment of XPath is used for which this property is undecidable, it may still be
possible to develop conservative approximations, and this is an area of further research.
3.2.2 Negations of Simple XPath expressions
The following table illustrates the transitions that the truth-value of a condition of the form not c, where
c is a simple XPath expression, can undergo. The first column shows the truth value of the condition
before the update, and the subsequent columns its truth value after a non-independent insertion (NI)
and a non-independent deletion (ND):
before after NI after ND
rue T rue or F alse T rue
F alse F alse T rue or F alse
For case (a), where rules r i and r j are distinct, it is clear from this table that r i can activate r j only
if one of the actions of r i is a deletion which is non-independent of the condition of r j .
Let the condition of r j be not c. We construct the set of conditions C from c as in Section 3.2.1.
Now let the action from rule r i be
and let e be the query e 1 == . We again use the intersection test from Section 3.1.1 in order to check
whether e is independent of each of the conditions in C. If so, then e cannot change the truth value of c
from False to True. Otherwise, e is deemed to be non-independent of c, and r i may activate r j .
For case (b) above, a rule r i activates itself if it may leave its own condition True. We again need the
notion of a self-disactivating rule. If the condition part of r i is not c, the rule will be self-disactivating if
all its actions are insertions which guarantee that c will be True after the insertion.
Let an insertion action a from rule r i be
INSERT r BELOW e 1
[BEFOREjAFTER q]
and let condition c comprise prefix c 0 and suffix c 00 . Action a guarantees that c will be True after the
insertion if
and each of the trees in the set of trees denoted by r satisfies c 00 . As a result, we need a stronger concept
than the fact that type(r) may satisfy expression c 00 .
Recall the construction of the tree type(r) from Section 2.5. We modify the construction of type(r)
to leave enclosed expressions which are of type string in type(r) instead of replacing them by string. We
then need to define what it means for a node in type(r) to satisfy (rather than may satisfy) part of an
XPath expression e. A node of type n, @n or * in type(r) satisfies element name n, attribute name @n
or expression *, respectively, in e. A node of type n//* (respectively, *) in type(r) satisfies element
name n (respectively, expression *). A node labelled with an enclosed expression e 0 in type(r) satisfies
e 0 in e.
Example 7 Recall the first rule of Example 1. A prefix of the negated condition is identical to the
XPath expression
document('p.xml')/products/product[@id=$delta/@id]
and so clearly contains it. The corresponding suffix of the negated condition, namely
store[@id=$delta/./@id]
is satisfied by each of the trees denoted by the XQuery expression
!store id='-$delta/./@id-'/?
since the value for the id attribute is defined by the same expression as used in the suffix. Hence the
rule is self-disactivating. The second rule of Example 2 is similarly self-disactivating.
3.2.3 Conjunctions
For case (a), if the condition of a rule r j is of the form
l i;1 and l
we can use the tests described in the previous two sections for conditions that are simple XPath expressions
or negations of simple XPath expressions to determine if a rule r i may turn any of the l i;j from False to
True. If so, then r i may turn r j 's condition from False to True, and may thus activate r j .
For case (b), suppose the condition of rule r i is of the form l i;1 and l . There are three
possible cases:
(i) All the l i;j are simple XPath expressions. In this case, r i will be self-disactivating if each of its
actions is a deletion which subsumes one or more of the l i;j .
(ii) All the l i;j are negations of simple XPath expressions. In this case, r i will be self-disactivating if
each of its actions is an insertion which falsifies one or more of the l i;j .
(iii) The l i;j are a mixture of simple XPath expressions and negations thereof. In this case, r i may or
may not be self-disactivating.
3.2.4 Disjunctions
For case (a), if the condition of a rule r j is of the form
(l 1;1 and l
or (l 2;1 and l
(l m;1 and l
we can use the test described in Section 3.2.3 above to determine if a rule r i may turn any of the disjuncts
l i;1 and l
from False to True. If so, then r i may turn r j 's condition from False to True and may thus activate r j .
For case (b), suppose the condition of rule r i is of the form
(l 1;1 and l 1;2
or (l 2;1 and l 2;2
(l m;1 and l
Then r i will be self-disactivating if it leaves False all the disjuncts of its condition. This will be so if
(i) all the l i;j are simple XPath expressions and r i disactivates all the disjuncts of its condition as in
case (i) of Section 3.2.3 above; or
(ii) all the l i;j are negations of simple XPath expressions and r i disactivates all the disjuncts of its
condition as in case (ii) of Section 3.2.3 above.
In all other cases, r i may or may not be self-disactivating.
Conclusions
In this paper we have proposed a new language for defining ECA rules on XML, thus providing reactive
functionality on XML repositories, and we have developed new techniques for analysing the triggering
and activation dependencies between rules defined in this language. Our language is based on reasonably
expressive fragments of the XPath and XQuery standards.
The analysis information that we can obtain is particularly useful in understanding the behaviour
of applications where multiple ECA rules have been defined. Determining this information is non-trivial,
since the possible associations between rule actions and rule events/conditions are not syntactically
derivable and instead deeper semantic analysis is required.
One could imagine using XSLT to transform source documents and materialise the kinds of view
documents we have used in the examples in this paper. However, XSLT would have to process an
entire source document after any update to it in order to produce a new document whereas we invisage
detecting updates of much finer granularity. Also, using ECA rules allows one to update a document
directly, wheareas XSLT requires a new result tree to be generated by applying transformations to the
source document.
The simplicity of ECA rules is another important factor in their suitability for managing XML data.
ECA rules have a simple syntax and are automatically invoked in response to events - the specification
of such events is indeed a part of the Document Object Model (DOM) recommendation by the W3C.
Also, as is argued in [13], the simple execution model of ECA rules make them a promising means for
rapid prototyping of a wide range of e-services.
The analysis techniques we have developed are useful in a context beyond ECA rules. Our methods
for computing rule triggering and activation relationships essentially focus on determining the effects of
updates upon queries - the 'query independent of update' problem [25]. We can therefore use these
techniques for analysing the effects of other (i.e. not necessarily rule-initiated) updates made to an XML
database, e.g. to determine whether integrity constraints have been violated or whether user-defined views
need to be re-calculated. Query optimisation strategies are also possible: e.g. given a set of pre-defined
queries, one may wish to retain in memory only documents which are relevant to computing these queries.
As updates to the database are made, more documents may need to be brought into memory and these
documents can be determined by analysing the effects of the updates made on the collection of pre-defined
queries.
For future work there are two main directions to explore. Firstly, we wish to understand more fully
the expressiveness and complexity of the ECA language that we have defined. For example, we wish to
look at what types of XML Schema constraints can be enforced and repaired using rules in the language.
Secondly, we wish to further develop and gauge the effectiveness of our analysis methods. Techniques such
as incorporating additional information from document type definitions may help obtain more precise
information on triggering and activation dependencies [31]. We also wish to investigate the use of these
dependencies for carrying out optimisation of ECA rules.



--R

Incremental maintenance for materialized views over semistructured data.
Relational transducers for electronic com- merce
Push technology personalization through event correlation.
Static analysis techniques for predicting the behavior of active database rules.
An abstract interpretation framework for termination analysis of active rules.
A dynamic approach to termination analysis for active database rules.
Analysis and optimisation for event- condition-action rules on XML
Improved rule analysis by means of triggering and activation graphs.

An algebraic approach to rule analysis in expert database systems.
An algebraic approach to static analysis of active database rules.
Active XQuery.
Active rules for XML: A new paradigm for e-services
Pushing reactive services to XML repositories using active rules.
Practical applications of triggers and constraints: Success and lingering issues.
Designing Database Applications with Objects and Rules: The IDEA Methodology.

Views in a large scale XML repository.
Containment and integrity constraints for XPath fragments.
Query containment for conjunctive queries with regular expressions.
Introduction to Automata Theory
An active web-based distributed database system for e-commerce
Active database systems: Expectations
Active database features in SQL3.
Queries independent of updates.
Active Rules in Database Systems.
Efficient matching for web-based publish/subscribe systems
Updating XML.
Active Database Systems.
On the equivalence of XML patterns.
Minimising simple XPath expressions.
World Wide Web Consortium.
World Wide Web Consortium.
World Wide Web Consortium.
--TR
Static analysis techniques for predicting the behavior of active database rules
Query containment for conjunctive queries with regular expressions
Relational transducers for electronic commerce
An algebraic approach to static analysis of active database rules
Pushing reactive services to XML repositories using active rules
Updating XML
Introduction To Automata Theory, Languages, And Computation
Compile-Time and Runtime Analysis of Active Behaviors
Incremental Maintenance for Materialized Views over Semistructured Data
One-To-One Web Site Generation for Data-Intensive Applications
Push Technology Personalization through Event Correlation
Practical Applications of Triggers and Constraints
Views in a Large Scale XML Repository
Queries Independent of Updates
An Algebraic Approach to Rule Analysis in Expert Database Systems
Improving Rule Analysis by Means of Triggering and Activation Graphs
Efficient Matching for Web-Based Publish/Subscribe Systems
A Dynamic Approach to Termination Analysis for Active Database Rules
On the Equivalence of XML Patterns
An Abstract Interpretation Framework for Termination Analysis of Active Rules
Active rules for XML: A new paradigm for E-services

--CTR
S. Swamynathan , A. Kannan , T. V. Geetha, Composite event monitoring in XML repositories using generic rule framework for providing reactive e-services, Decision Support Systems, v.42 n.1, p.79-88, October 2006
Martin Bernauer , Gerti Kappel , Gerhard Kramler, Composite events for xml, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA
Ce Dong , James Bailey, Static analysis of XSLT programs, Proceedings of the fifteenth Australasian database conference, p.151-160, January 01, 2004, Dunedin, New Zealand
George Papamarkos , Alexandra Poulovassilis , Peter T. Wood, Event-condition-action rules on RDF metadata in P2P environments, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.10, p.1513-1532, 14 July 2006
James Bailey, Transformation and reaction rules for data on the web, Proceedings of the sixteenth Australasian database conference, p.17-23, January 01, 2005, Newcastle, Australia
Shuichi Kurabayashi , Yasushi Kiyoki, An adaptive active rule system for automatic service discovery and cooperation, Proceedings of the 24th IASTED international conference on Database and applications, p.115-122, February 13-15, 2006, Innsbruck, Austria
Using the composite act frame technique to model 'Rules of Origin' knowledge representations in e-government services, Electronic Commerce Research and Applications, v.6 n.2, p.128-138, Summer 2007
reactive functionality;XML repositories;event-condition-action rules;XML;rule analysis