There is a growing number of XML database systems of different kinds now on the market. XML DBMS vendors rushed to enrich their products with more flexible and advanced features to make them satisfy the requirements of modern applications. And the time is ripe for the database research community to study the issues involved with extending XML DBMS with capabilities analogous to those that are popular in traditional DBMS, keeping in mind that XML databases now become a widespread means for storing and exchanging information on the Web, and increasingly used in dynamic applications such as e-commerce. In this paper, being bound for the issues, we provide a definition of triggers for XML based on XQuery and a previously defined update language, and methods to support triggers in XML database systems. This work was partially supported by the grants of the Russian Foundation for Basic Research No. 04-07-08003 and 05-07-90204.
The concept of triggers itself originated from the early
times of relational database systems. Not long after the
idea of integrity constraints in relational databases
appeared, researchers recognized the importance of
automatic ”reactions” to constraint violations, the idea
expanded to the more general concept of triggers [
The uses of triggers also occur in the context of
materialization of views. An important aspect of the data
definition facility of a database system is the ability to
define alternative views of stored data. A view is a data
object that is derived from one or more existing data
objects. Triggers may be used to materialize such views. In
particular, this approach was investigated in the System
R [
Nowadays active rules are often concerned as a mean
to support business logic of e-commerce applications [
The paper is organized as follows. To give a more illustrative overview of the problem we consider an example in Section 1.2. In Section 2 we give our vision of triggers for XML by providing syntax and noting the main points of semantics of triggers. In Section 3 we provide methods to support triggers in XML DBMS. Section 4 proposes a brief survey of a related work. Section 5 concludes the paper. 1.2
This example is borrowed from [
Let us assume a scenario based on the following lib.xml document, that belongs to an XML database of a university library: <library> ... <shelf nr="45"> <book_count>2</book_count> <book id="AO97"> <author>J. Acute</author> <author>J. Obtuse</author> <title>Triangle Inequalities </title> <year>1973</year> </book> <book id="So98"> <author>A. Sound</author> <title>Automated Reasoning</title> <year>1990</year> </book> </shelf> ... <box nr="02"> <book id="XW89"> <author>Michel Foucault</author> <title>The Order of Things</title> <year>1966</year> </book> ... </box> ... <authorIndex> <authorEntry>J. Acute</authorEntry> <authorEntry>J. Obtuse</authorEntry> <authorEntry>Michel Foucault</authorEntry> ... </authorIndex> </library>
The library automatically maintains an index of all authors whose books are published before 1980. The index is a part of the library document, whose complete DTD is: <!ELEMENT lib (shelf+, box+, authorIndex)> <!ELEMENT shelf (book_count, book*)> <!ATTLIST shelf nr #REQUIRED> <!ELEMENT book_count (#PCDATA)> <!ELEMENT book (author+, title, year)> <!ATTLIST book id #REQUIRED> <!ELEMENT author (#PCDATA)> <!ELEMENT title (#PCDATA)> <!ELEMENT authorIndex (authorEntry*)> <!ELEMENT authroEntry (name)> <!ELEMENT name (#PCDATA)>
Suppose triggers are responsible to guarantee the correctness of the index. We do not provide full set of triggers needed to guarantee the correctness as it can involve a reader into an unnecessary complexity. Let us consider only two of them:
Trigger tr1 is triggered when any book that was published before 1980 is replaced. If a new book is published before 1980 and there are no authors of this book in the CREATE TRIGGER tr1 AFTER REPLACE OF document("lib.xml")//book[year<1980] FOR EACH NODE LET $AuthorNotInList := (if (NEW_NODE/year<1980) then for $n in NEW_NODE/author where empty(document("lib.xml") /library/authorIndex/ authorEntry[name=$n]) return $n else () ) WHEN (not(empty($AuthorNotInList))) DO (UPDATE insert for $NewAuthor in $AuthorNotInList return <authorEntry> <name>$NewAuthor</name> <authorEntry> into document("lib.xml")/library/authorIndex ) Trigger tr2 is triggered when any book that was published before 1980 is deleted. If there are no other books that were published before 1980 by this author then his/her entry is deleted from the index.
CREATE TRIGGER tr2 AFTER DELETE OF document("lib.xml")//book[year<1980] /author FOR EACH NODE WHEN (empty(document("lib.xml")// book[year<1980] [author/text()=OLD_NODE/text()])) DO (UPDATE delete document("lib.xml")//
authorEntry[name=OLD_NODE/text()] )
Trigger tr3 has event UPDATE-CONTENT which means that it is triggered when any descendant of element shelf with attribute nr equal 45 is updated. Then the number of books on the shelf is re-counted.
CREATE TRIGGER tr3 AFTER UPDATE-CONTENT OF document("lib.xml")/library /shelf[@nr=45] FOR EACH NODE DO (UPDATE replace document("lib.xml")//shelf[@nr=45] /book_count as $x with <book_count> {count(document("lib.xml")//shelf[@nr=45]/book)} </book_count> )
An example of update to the library is the replacement of book which id is ”AO97” from the shelf number 45 with another book which year of publishing is before 1980. Here is corresponding update statement s0: UPDATE replace document("lib.xml")/library/shelf[@nr=45]/ book[@id="AO97"] as $b with <book id="{$b/@id}"> <author>S. Kuznetsov</author> <title>Database Systems</title> <year>1979</year> </book> This replace statement causes the consideration of all author’ index then new author entry for this author is inof the three triggers: tr1 is associated exactly with the serted into the index. same node that is replaced and the triggering operation is REPLACE; tr2 is associated with the data that is descendant of the replaced node and its triggering operation is DELETE; tr3 is associated with a node that is an ancestor of the replaced node and its triggering operation is UPDATE-CONTENT. In this paper we answer the question which of the triggers are triggered by the given update statement and how are the triggered triggers executed along with the update statement.
The paper provides the following important contributions:
We define triggers for XML by providing its syntax and semantics that is close to SQL triggers semantics except the issues involved with the problems described above.
We provide universal method to support such triggers in XML DBMS.
We provide method to support triggers efficiently under the restriction: in update statements, data to be updated is specified in XPath (not an arbitrarily XQuery expression). The method represents combined execution of update statement and eligible triggers and uses previously built merged execution plan. 2
An XML trigger consists of four components: the
triggering operation, the triggering granularity, the trigger
condition and the trigger action. Consistent with the
terminology of [
OF XPathExpression (,XPathExpression)* [FOR EACH (NODE|STATEMENT)] [XQuery-Let-Clause] [WHEN XQuery-Clause] DO XQuery-UpdateOp
The CREATE TRIGGER clause is used to define a new XML trigger, with the specified name.
The BEFORE/AFTER clause expresses the triggering time relative to the update statement.
Each trigger is associated with a set of update
operations (INSERT, DELETE, REPLACE), adopted from
the update extension of XQuery [
The operation is relative to elements that match an XPath expression specified after the OF keyword, i.e. a step-by-step path descending the hierarchy of documents. One or more predicates (XPath filters) are allowed in the steps to eliminate nodes that fail to satisfy given conditions.
The optional clause FOR EACH NODE/STATEMENT expresses the trigger granularity. A statement-level trigger executes once for each set of nodes extracted by evaluating the XPath expressions mentioned above, while a node-level trigger executes once for each of those nodes. Based on the trigger granularity, it is possible to mention in the trigger the transition variables: – If the trigger is node-level, variables OLD_NODE and NEW_NODE denote the affected XML element in its before and after state. – If the trigger is statement-level, variables OLD_NODES and NEW_NODES denote the sequence of affected XML elements in their before and after state.
An optional XQuery-Let-Clause is used to define XQuery variables whose scope covers both the condition and the action of the trigger.
The WHEN clause represents the trigger condition, and can be an arbitrarily expression legal in the XQuery where clause. If omitted, a trigger condition that specifies WHEN true() is implicit.
The action is expressed by means of the DO clause and can be an arbitrary complex update operation.
For a complete syntax of XQuery refer to [
Below in the paper under update path we mean an XQuery/XPath expression that is the part of an update statement and specifies data that are to be updated. Under trigger path we mean an XPath expression that specifies the data associated with the given trigger (XPath expression appearing after OF in a trigger definition).
Figure 1 illustrates different cases of positional relationship between nodes addressed by update path and nodes addressed be trigger path.
Figure 2 provides the triggering operations. For each cell of the table only triggers with triggering operations from this cell can be triggered by the specified update operation with given trigger path vs. update path length.
Traditionally, to achieve maximal efficiency, a trigger
support method is tightly bound with the architecture of
a particular database system and cannot be regarded in
isolation from the architecture. Methods proposed in this
paper were initially designed to efficiently support
triggers in Sedna XML database system [
We assume that a system supports the XQuery
language and an update language based on XQuery and its
data model [
Optimized method described in Section 3.3 exploits the following two advanced features.
The first one is support for descriptive schema (also
referred to as DataGuide [
The second advanced feature is an extension to the standard XQuery execution model. In the extended execution model items obtained as an intermediate result of execution may be annotated with some metadata. Annotations are used to mark nodes for which triggers might be triggered later during the update execution process. There is also a set of predefined operations for dealing with annotations. The specification of the annotations and operations will be introduced in Section 3.3. Here we only notice that this extension is orthogonal to the XQuery execution model in a sense that marked items are just common items for standard XQuery operations.
Using extensions to the standard XQuery execution
model requires us to turn to implementation-level details
to describe our methods. We need to define a query
logical plan that supports XQuery and the extension as well.
The logical plan used in this paper is very close to that
used in Sedna and defined formally in [
is as follows attribute(descendent(child(doc("foo.xml"), elem(library)),elem(book)),id) where child and descendent are operations implementing the child and descendent-or-self axes respectively; elem(library), elem(book), id are representations of the corresponding node tests.
XPath predicates are represented in logical plan using the select operation that takes a sequence to be filtered and the predicate represented as a function of one parameter. select applies the function to each element of the sequence and returns a new sequence containing items for which the function application results to true. For example, the following XPath expression doc("foo.xml")/library/shelf[@nr=45]
is represented as follows select(child(child(doc("foo.xml"),elem(library)), elem(shelf)),f(x|child(x,elem(@nr)=45))))
The features essential to our methods such as support for descriptive schema and advanced numbering scheme are not Sedna-specific and supported by a number of systems. The mechanism for marking nodes during query execution, though not known to be used in other systems, can be easily implemented due to its property of orthogonality to the standard XQuery execution model. 3.2 The method provided below is a straighforward one. It consists in preliminary evaluation of the update path and trigger paths and identification of the nodes associated with triggers among those affected by given update statement.
The basic steps of this method are the following: Evaluate update-path expression. Thus, we have affected nodes- a set of nodes that are to be updated. For INSERT and REPLACE statements, construct a new fragment of data.
Expanded path is a path-expression that excludes ambiguities: ’//’, ’*’. Using descriptive scheme and the result of evaluation from the previous step build all possible expanded paths without predicates. For a set of expanded update-paths and trigger-paths pick out the triggers that are probably triggered by the update statement (this procedure is described in detail in the 3.3 step 1: searching for probable triggers).
For each trigger picked out on the previous step evaluate its trigger path expressions. From the result set of nodes, applying ancestor-descendant comparison operations introduced in Section 3.1, pick out those that are: – coinciding with some of affected nodes or – the descendants of some of the affected nodes or – the ancestors of some of the affected nodes For each node and its associated trigger pick out the nodes and their associated trigger according to Figure 2. Thus, we have got a set of nodes affected by the update statement on which some triggers are triggered.
Evaluate the update statement and consider triggers on the nodes determined on previous step.
This method does not impose any restrictions on update path, i.e. it can be an arbitrary XQuery expression. But, obviously it has significant disadvantages: the preliminary identification of the nodes that match both update statement and some trigger may lead to working with a great number of triggers that appear to be not considered while given update statement.
Hence, in practice the method that excludes such an inefficiency is strongly needed. Below we provide triggers support method, simplifying the problem by introducing the restriction: in update statements XPath expressions are used (instead of arbitrary XQuery expressions) for determining the data to be updated. 3.3
Below we provide a three-step algorithm to support triggers efficiently. The effectiveness is attained thanks to the building of the specific execution plan that allows identifying the eligible triggers and marks their associated data at the run-time of an update statement execution.
Each step is a sufficiently complicated procedure that can be considered as a separate algorithm, thus, we try to describe it in full detail and carry out the step operations for our example given in Section 1.2. So, we have an update operation and a list of triggers. 3.3.1
Probable triggers are triggers that can be probably triggered while the given update statement. The operations of this step are carried out on triggering operations, trigger path expressions, update operation and update path expression.
1. Parent-expanded path is an XPath expression
rewritten in a way that it excludes ’..’ (parent axes).
Build parent-expanded paths from update-path and
each trigger-path by means of rewriting these path
expressions to avoid ’..’ in the path. A set of
rewriting rules for XPath expressions aimed at avoiding
’..’ is proposed in [
In our example we do not have ’..’ in update path and trigger paths. So, we do not have to rewrite update path and trigger paths. Parent-expanded paths look as follows: parent-expanded-upd-pth = document("lib.xml")/library/shelf[@nr=45]
/book[@id="AO97"] parent-expanded-tr1-pth = document("lib.xml")//book[year<1980] parent-expanded-tr2-pth = document("lib.xml")//book[year<1980]/author 2. Expanded path is a path expression that excludes ambiguities: ’//’, ’*’. Each of these ambiguities can be expanded using descriptive scheme. For example take ’//’: by means of descriptive scheme tree traversal we can obtain a set of paths that match ’//’. Build expanded paths from update path and each trigger path by getting rid of the ambiguities using descriptive scheme. expanded-upd-pth = document("lib.xml")/library/shelf[@nr=45] /book[@id="AO97"] expanded-tr1-pth = {document("lib.xml")/library/shelf /book[year<1980], document("lib.xml")/library/box /book[year<1980]} expanded-tr2-pth = {document("lib.xml")/library/shelf /book[year<1980]/author, document("lib.xml")/library/box /book[year<1980]/author} Thus, now for each trigger we have a set of expanded trigger paths associated with it. 3. Now pick out the probable triggers by means of following two procedures. Only triggers that are picked out in the first procedure below will be considered in the second procedure.
For each trigger and for each expanded trigger path compare the names of the elements (and document function parameter) on each step of path with the corresponding names (names on the same steps of path) in expanded update path until one of the paths is ended. If on some step names are not equal this trigger is not triggered by the considered update operation. If on all steps of these two expanded paths corresponding names are equal (no matter if one of the paths is shorter) pick out this expanded trigger path and its associated trigger (consider it in the next procedure).
In our example we carry out this procedure for two sets of expanded trigger paths that both consist of two expanded trigger paths. For tr1 we pick out expanded-tr1-pth = document("lib.xml")/library/shelf /book[year<1980]
expanded-tr2-pth = document("lib.xml")/library/shelf /book[year<1980]/author The other two expanded trigger pathes expanded-tr1-pth = document("lib.xml")/library/box /book[year<1980] expanded-tr2-pth = document("lib.xml")/library/box /book[year<1980]/author were not picked out because they have names box at the third step of path, but expanded update path has shelf.
The table on Figure 2 provides the triggering operations. For each cell of table only triggers with triggering operations from this cell can be triggered by the specified update operation with given trigger path vs. update path length. For each expanded trigger path according to the table pick out only those expanded trigger paths and its trigger that have associated triggering operations provided in the table.
In our example for tr1 we have expanded update path and expanded trigger path of tr1 of equal length and triggering operation is REPLACE. So, according to the table we pick out this expanded trigger path and its associated trigger. For tr2 we have expanded trigger path longer than expanded update path and triggering operation is DELETE. According to the table this expanded trigger path and its trigger is also suitable to pick out.
Thus, we have a list of triggers that can be probably triggered by the given update operation. For each probable trigger we have pick out a set of expanded trigger paths that address data on which this trigger can be probably triggered. Pass to the Step 2. 3.3.2
The operation of this step are carried out on expanded update path and expanded trigger paths that were pick out on the previous step.
On this step for expanded update path and for each trigger path we build merged execution plan. Merged execution plan is a logical plan for execution expanded update path expression taking into account predicates from expanded trigger path expression. Merged execution plan is constructed in a way that as the result of its execution we retrieve sequence of nodes that are to be updated and identify those nodes in the sequence on which trigger is triggered by the given update operation. Such a sequence with identified nodes we call marked sequence. To mark nodes we use the facilities of extended XQuery execution model described in Section 3.1.
For marking nodes we introduce two logical operations: mark1 and mark2. mark1(unmarked_seq, predicate, trigger_name) — takes unmarked sequence of nodes and marks (with trigger_name) those nodes that satisty the predicate. mark2(marked_seq, predicate, trigger_name) — takes marked sequence of nodes and for each marked node (that was marked with trigger_name) checks the predicate. If marked node satisfies the predicate it remains to be marked, if it does not satifies the predicate it is unmarked.
Thus, to build merged execution plan follow the next instructions: 1. Compare the lengths of expanded trigger paths and update path. If the lengths are not equal divide all of the expanded paths except the shortest one into two parts: common expanded path and a tail expanded path. For each expanded path, except the shortest one, common expanded path is a first part of expanded path of the same length as the shortest expanded path, tail expanded path is the rest of the expanded path. The shortest expanded path is divided into common expanded path that is equal to the shortest expanded path and tail expanded path that is empty.
In our example expanded-tr2-pth is longer than expanded-update-pth, so we get common-expanded-upd-pth = document("lib.xml")/library/shelf[@nr=45] /book[@id="AO97"] tail-expanded-upd-pth = '' common-expanded-tr1-pth = document("lib.xml")/library/shelf /book[year<1980] tail-expanded-tr1-pth = '' common-expanded-tr2-pth = document("lib.xml")/library/box /book[year<1980] tail-expanded-tr2-pth = /author 2. For expanded update path build logical plan by means of operations defined in []. select(child(select(child(child( doc("lib.xml"),elem(library)), elem(shelf)),f(s | attribute(s,nr)=45)), elem(book)),f(b|attribute(b,id)="AO97")) 3. Each predicate from expanded trigger path must be inserted into the logical plan for their corresponding elements by means of logical operations mark1 or mark2. For the first predicate starting from the end of the expanded trigger path mark1 must be inserted, for the rest of the elements mark2 must be inserted.
Thus, for our example we build the following:
Thus, having passed through this step we obtain merged execution plan. Pass to the final step 3. 3.3.3
On this step we provide the procedure for combined execution of update statement and one or more triggers that is triggered by this update statement in an intuitive lanfor each $i in eval(merged_exec_plan) let $what := eval_what(update_tail($i)); let $where := eval_where(update_tail($i)); trigger_func ($i, "before"); update_op ($what, $where); trigger_function ($i, "after"); guage. begin { begin end; } end; { then { } } end;
Function trigger_func executes triggers on marked nodes according to the time variable: BEFORE or AFTER. Function returns nothing. function trigger_func( node $i, string $time ) begin if (marked($i)) then for each $trigger in
{triggers with which $i is marked} if(trigger_time($trigger) == $time) let $old := <determine by the table> let $new := <determine by the table> if <trigger_when_clase($old, $new)> then <trigger_action($old, $new)> function eval( plan ) - evaluates merged plan, builded on the step 2, returns marked sequence of nodes.
function eval_what( update path ) - If update statement is an insert, function constructs data that is inserted. If update statement is a replace, function constructs data to replace with. Functions returns variable $what bound to the constructed data. In case of delete $what is unspecified.
function eval_where( update_path ) - returns a sequence of nodes that are to be updated by means of evaluation of update_path.
function update_op($what, $where) executes update statement.
function trigger_time( trigger ) returns trigger time: before or after.
Our method has the following advantages: 1. During update execution the triggeres that are not triggered by the update are excluded, thus, redundant processing of not triggered triggeres is avoided. The triggeres exclusion is carried out by means of update path and rule path comparison using descriptive schema and, after that, by means of incorporating the evaluation of rule path predicates into the update path execution. 2. All triggered triggeres are processed together along with the update execution, thus, there is no need to consider each triggere separately.
However, we are aware of a disadvantage: the method strongly relies on the fact that update and trigger paths are an XPath expressions. The method needs modifications to be suitable for XQuery expressions that address data in update statements. 4
Active rules to enforce the correctness of update
operations and to automatically maintain views of data has
been extensively studied in database systems [
[
As for the works specifically focused on triggers for
XML, we point out [
Secondly, authors claim their approach leads to a separation between the two system components: trigger subsystem and query engine. But at the same time they note that update statement expansion requires accessing the data affected by the update statement. That confirms our assertion that complete trigger processing is impossible at compile-time, that is the trigger processing requires tight integration of trigger subsystem with query engine.
[
In this paper we proposed the definition of XML triggers and methods to support XML triggers in XML database systems. Methods described in this paper are being prototyped in the Sedna XML database system.
In many implementations of relational database systems triggers have been successfully used to support integrity constraints. In future work we will analyse the trigger capabilities in order to support different kinds of integrity constraints for XML databases.