Analysis and optimization of active databases.
We introduce a new formal semantics for active databases that relies on a transaction rewriting technique. A user-defined transaction, which is viewed here as a sequence of atomic database updates forming a semantic atomic unit, is translated by means of active rules into induced one(s). These transactions embody active rule semantics which can be either immediate or deferred. Rule semantics, confluence, equivalence and optimization are then formally investigated and characterized in a solid framework that naturally extends a known model for relational database transactions.
Introduction
Active databases are based on rules that allow us to specify actions to be taken by the
system automatically, when certain events occur and some conditions are met. It is widely
recognized that these active rules provide a powerful mechanism for the management of
several important database activities (e.g., constraint maintenance and view materialization
[6, 7]), and for this reason, they are now largely used in modern database applications
and have been extensively studied in the last years [2, 4, 5, 9, 12, 14, 21, 22, 23].
However, in the various approaches, active rule execution is generally specified only by
informal, natural-language descriptions. It follows that very often, when the number of
rules increases, active rule processing becomes quickly complex and unpredictable, even
for relatively small rule sets [23].
The goal of this paper is to provide a formal approach to active rule processing that
relies on a method for rewriting user defined transactions to reflect the behavior of a set of
active rules, and to show how known results for transaction equivalence can be extended
in this framework to pre-analyze properties of transactions and rules.
We start by introducing a simple transaction language, based on a well known model
for relational databases [1] in which a transaction is viewed as a collection of basic update
operations forming a semantic unit, and a quite general active rule language, whose computational
model is set-oriented (like in [23] and differently from other approaches [22]).
We consider two different execution models for active rules: immediate and deferred (or
delayed) [8, 14]. The former has no temporal decoupling between the event, condition and
action parts. The latter has a temporal decoupling between the event part on one side
and the condition and action parts on the other side. We then define in this context a
rewriting process that takes as input a user defined transaction t and a set of active rules
and produces a new transaction t 0 that "embodies" active rule semantics, in the sense that
explicitly includes the additional updates due to active processing. Under the deferred
modality, the new transaction is the original one augmented with some induced actions,
whereas, under the immediate modality, the new transaction interleaves original updates
and actions defined in active rules. It follows that the execution of the new transaction
in a passive environment corresponds to the execution of the original transaction within
the active environment defined by the given rules. Other approaches consider rewriting
techniques [11, 22], but usually they apply in a restrictive context or are not formal. Con-
versely, we believe that this formal and simple approach can improve the understanding
of several active concepts and make it easier to show results.
As we have said, the execution model of our transactions extends a relational trans-action
model which has been extensively investigated [1]. The reason for this choice is
twofold. Firstly, we wish to use a well known framework having a formal setting and a
solid transaction execution model. Secondly, we wish to take full advantage of the results
already available on transaction equivalence and optimization [1, 13]. In this way, we are
able to formally investigate statically several interesting properties of active rule process-
ing. First, we can check whether two transactions are equivalent in an active database.
Then, due to the results on transaction equivalence, we are also able to provide results
on confluence. Finally, optimization issues can be addressed. As a final remark, we note
that, with this approach, active rule processing does not require any specific run-time
support, and so it is simpler to implement than others which are built from scratch [10].
The remainder of this paper is organized as follows. In Section 2, a detailed overview
Relational Database System
Confluence/Optimization
Transaction Rewriting
Loop Checking

Figure

1: Components of the approach
of the approach is presented by using several practical examples. In Section 3 we define
the basic framework. In Sections 4 and 5, we introduce, in a systematic way, the notion
of active database and the rewriting transaction technique, respectively. The property of
equivalence is investigated in Section 6. From this study, several results on active rule
processing are derived in Section 7. Finally, in Section 8, we draw some conclusions.
An overview of the approach
In this section we informally present our approach. As described in Figure 1, the basic
idea is to express active rule processing as a four step computation. Given a user defined
transaction t and a set of active rules P , the first step checks whether P presents some
kind of recursion. For the time being, we present a simple characterization and we will
not address this issue in detail in the present paper. The second step takes P and t,
and transforms the transaction t into an induced one(s) that "embodies" the semantics
of the rules in P . In general, during this step several transactions can be generated.
These different induced transactions take into account the fact that an update of the
original transaction may trigger several rules at the same time, and so the corresponding
actions can be executed in different orders yielding different results. In the third step,
confluence and optimization issues of active rule processing are investigated by analyzing
the transactions computed during the second step. This is done by extending known
techniques for testing equivalence of database transactions [1, 13]. Then, in the last step,
according to the results of this analysis, one transaction is finally submitted to a relational
database management system.
We point out two important aspects of this approach. Firstly, it relies on a formal basis
that allows us to derive solid results. Secondly, the rewriting and confluence/optimization
steps can be done statically, without accessing the underlying database, and therefore they
can be performed very efficiently at compile time.
As we have said, we will consider the immediate and deferred active rule execution
models: the immediate modality reflects the intuition that rules are processed as soon as
they are triggered, while deferred modality suggests that a rule is evaluated and executed
after the end of the original transaction [14]. Thus, two different rewriting procedures
will be given. Specifically, consider a user defined transaction as a sequence of updates:
This transaction is transformed under the immediate modality into an
induced one:
i denotes the sequence of updates computed as immediate reaction of the update
with respect to a set of active rules P . This reaction can be derived by "matching"
the update u i with the event part of the active rules. Clearly the obtained updates can
themselves trigger other rules, hence this reaction is computed recursively. As noted
above, several transactions can be obtained in this way. Note that under the immediate
modality the induced transaction is an interleaving of user defined updates with rule
actions.
Under the deferred modality, the induced transaction has the form:
Hence the reaction is deferred (or postponed) until the end of the user transaction. Here
again the induced updates can themselves trigger other rules, and so the reactions of the
original updates are recursively computed, but using the immediate modality.
We now give a number of practical examples to clarify the above discussion. The following
active rules react to updates to a personnel database composed by two relations:
emp(name,dname,sal) and dep(dname,mgr). Rules are expressed here in a generic language
that does not refer to any specific system but whose intended meaning should be
evident (indeed, those rules can be easily expressed in any practical active rule language).
r1: When DELETED d FROM dep
Then DELETE FROM emp WHERE dname=d.dname
r2: When INSERTED new-e INTO emp
Then
WHERE name=new-e.name AND dname!?new-e.dname
r3: When INSERTED new-e INTO emp
new-e.sal ? 50K
Then INSERT INTO dep
VALUES (dname=new-e.dname, mgr=new-e.name)
Intuitively, the first rule states that when a department is deleted then all the employees
working in such a department must be removed (cascading delete). The second
one serves to enforce the constraint that an employee can work in one department only,
and states that when an employee tuple, say (john,toy,40K) is inserted into the relation
emp, then the old tuples where john is associated with a department different from toy
must be deleted. Finally, the last rule states that if an inserted employee has a salary
greater than 50k then he is eligible to be a manager of the department in which he works
and so, according to that, a tuple with the name of the department and the new employee
is inserted in the relation dep.
Now, we provide the following simple user defined transaction where first the toy
department is removed and then an employee is added to this department with a salary
of 60K.
INSERT INTO emp VALUES (name='bill',dname='toy',sal=60K);
By inspecting the given active rules, we can easily realize that, at run time, the first
update in t1 will trigger rule r1, whereas the second update will trigger rules r2 and
r3. Therefore, under immediate modality, t1 can be rewritten, at compile time, into
the following transaction t1I (where I denotes immediate modality), by "unfolding" t1
with respect to the active rules. In this new transaction, the prefix * denotes an induced
update.
INSERT INTO emp VALUES (name='bill',dname='toy',sal=60K);
*INSERT INTO dep VALUES (dname='toy',name='bill');
The obtained transaction describes the behavior of the transaction t1 taking into
account the active rules under the immediate modality. Note that there is another possible
translation in which the last two updates are switched. This is because the second update
of the original transaction triggers two rules at the same time (namely r2 and r3) and
therefore we have two possible execution orders of the effects of these rules. It follows
that, in general, a user defined transaction actually induces a set of transactions. One of
the goals of this paper is to show that, in many cases, it is possible to statically check
whether these transactions are equivalent. If all the induced transactions are equivalent
we can state that the active program is "confluent" with respect to the transaction t1.
In this case the execution of one of the obtained transactions implements the expected
behavior of the user defined transaction within the active framework. Note that we do
not assume the presence of a (partial) ordering on the rules, but the framework can be
easily extended to take it into account.
Let us now turn our attention to the deferred execution model. Assume that we
want to move the employee John from the toy to the book department. This can be
implemented by means of the following transaction.
t2: INSERT INTO emp VALUES (name='john',dname='book',sal=50K);
By inspecting transaction and rules, we can statically decide that the first update in
t2 will not trigger rule r3 since its condition will not be satisfied (the salary of the new
employee is not greater than 50K). Thus, if we rewrite this transaction taking into account
our active rules under the deferred modality, we have the following possible translation
t2D (D denotes deferred modality), in which the effect of the rules is postponed to the end
of the transaction.
before executing the above transaction, we can observe the fact that the second
update can be discarded without altering the overall effect of the transaction, since its
effect is "included" in the effect of the third update. This shows how some optimization
can be performed on those induced transactions. The transaction that implements the
expected behavior is then as follows.
In contrast to a user defined transaction, the updates in the induced transactions
are not independent, as some updates are indeed "induced" by others. This fact has a
consequence on the execution semantics of an induced transaction. Assume for instance
that at run-time the execution of an update u in a induced transaction t has a null effect on
the database (because, for example, its condition does not hold or its effect is invalidated
by a subsequent update). Then, it is reasonable that the updates in t induced (directly
or indirectly) by u are not executed as well. Under this interpretation, we need to define
a new transaction semantics that takes into account the inducer/induced relationship
among updates. Clearly, the techniques to achieve confluence and optimization must take
into account this fact.
To clarify the point, consider the transformation of the transaction t1 under the
deferred modality. According to the previous discussion, the rewriting process should
generate the following transaction.
INSERT INTO emp VALUES (name='bill',dname='toy',sal=60K);
*INSERT INTO dep VALUES (dname='toy',name='bill');
However, it is easy to see that the third update invalidates the effect of second one.
It follows that the last two updates of the transaction t1D, which are induced by such an
update, must not be executed at run time. So, the rewriting of the transaction t1 under
the deferred modality can be simplified as follows:
Thus, we need to develop specific techniques to check equivalence and to optimize
induced transactions. This will be done by extending an already existing framework for
equivalence and optimization in relational databases.
The rest of the paper is devoted to the formalization and characterization of the issues
discussed in this section.
3 A model for Transactions
The notion of transaction we use in this paper is based on a model for relational transactions
introduced by Abiteboul and Vianu [1]. Informally, for transaction we mean a
sequence of basic update operations (namely, insertions and deletions of tuples) viewed
as a semantic unit. Specifically, we will restrict our attention to the important class of
"domain-based" transactions, where the selection of tuples involves the inspection of individual
values for each tuple. Differently from the model described in [1], we also allow
comparisons predicates.
3.1 Preliminaries
Let U be a finite set of symbols called attributes and, for each A 2 U , let dom(A) be an
infinite set of constants called the domain of A. As usual, we use the same notation A to
indicate both the single attribute A and the singleton fAg. Also, we indicate the union
of attributes (or sets thereof) by means of the juxtaposition of their names. Moreover,
we assume, for technical reasons, that the domains are disjoint and totally ordered. A
relation scheme is an object R(X) where R is the name of the relation and X is a subset of
U . A database scheme S over U is a collection of relation schemes fR 1 (X
with distinct relation names such that the union of the X i 's is U .
A tuple v over a set of attributes X is a function from X to the union of all the
domains such that, for each A 2 X, v(A) is in dom(A). A relation over a relation scheme
R(X) is a finite set of tuples over X. A database instance s over a database scheme S is
a function from S such that, for each R(X) 2 S, s(R(X)) is a relation over R(X). We
will denote by Tup(X) the set of all tuples over a set of attributes X and by Inst(S) the
set of all database instances over a database scheme S.
Throughout the rest of the paper, we will always refer to a fixed database scheme
over a set of attributes U .
3.2 Conditions
Let X be a set of attributes and A be an attribute in X. An atomic condition over X is
an expression of the form: (1) A'c, where c 2 dom(A) and ' is a comparison predicate
(=; 6=; !; -; ?), or (2) A 2
. The meaning of the symbols \Gamma1 and +1 is evident: A 2 (\Gamma1; c 2 ) is
equivalent to A ! c 2 . The reason for allowing this form of atomic condition will be
clarified shortly.
Definition 3.1 (Condition) A complex condition (or simply a condition) over a set
of attributes X is a finite set of atomic conditions over X. A tuple v over X satisfies
an atomic condition A'c
condition C if it satisfies every atomic condition occurring in C.
We assume that conditions are always satisfiable, that is, they do not contain atomic
conditions that are always false (e.g., A 2 there is no c 2 dom(A) such that
atomic conditions that are mutually exclusive (e.g., both
A condition C over a set of attributes X uniquely identifies a set of tuples over X:
those satisfying the condition. This set is called the target of C.
Definition 3.2 (Target of a condition) The target of a condition C over a set of attributes
X, denoted by Targ(C), is the set of tuples fv 2 Tup(X) j v satisfies Cg.
Note that Targ(C) is not empty if and only if C is satisfiable. We say that a condition
specifies a complete tuple if
a
3.3 Transactions
Let us first introduce the basic update operations.
Definition 3.3 (Insertion) An insertion over a relation scheme R j is an expression
of the form +R j [C], where C is a condition over X j that specifies a complete
tuple. The effect of an insertion +R j [C] is a mapping Eff (+R j [C]) from Inst(S) to
Inst(S) defined, for each R i
Definition 3.4 (Deletion) A deletion over a relation scheme R j is an expression
of the form \GammaR j [C], where C is a condition over X j . The effect of a deletion \GammaR j [C]
is a mapping Eff (\GammaR j [C]) from Inst(S) to Inst(S) defined, for each R i
An update over a relation scheme is an insertion or a deletion. Note that, for sake of
simplicity, we do not consider modify operations here. Actually, similarly to [1], modifications
can be accommodated in our framework but the complexity of notation would
increase dramatically.
Update operations are generally executed within transactions, that is, collections of
data manipulation operations viewed as a semantic atomic unit.
Definition 3.5 (User transaction) A user transaction is a finite sequence of updates.
The effect of a transaction is the composition of the effects of the updates
it contains, that is, is the mapping: Eff
Example 3.1 The SQL transactions described in Section 2 can be easily expressed using
the notation introduced above. For instance, transaction t1 at page 6, can be expressed as
follows:
Two user transactions are equivalent when they always produce the same result if
applied to the same database instance, that is, when they have the same effect.
Definition 3.6 (Equivalence of user transactions) Two user transaction t 1 and t 2
are equivalent (denoted it is the case that Eff (t 1
3.4 Normalization of transactions
According to [1], we describe and characterize in this section transactions satisfying a
property called normal form. In such transactions, syntactically distinct updates have
disjoint targets (and therefore do not interfere). This is a very convenient form since
it simplifies results and algorithms. Moreover, it will make easier the specification of
the reaction of active rules to updates involved in a transaction. We also show that any
transaction can be brought to this special form by means of a "preprocessing" phase called
normalization, and that this operation can be performed in polynomial time.
Definition 3.7 (Normal form) A transaction t is in normal form if, for each pair of
updates u i and u j in t that are over the same relation and have conditions C i and C j such
that C i 6= C j , it is the case that Targ(C i
The following result easily follows by definitions and states that, in a transaction
in normal form: (1) if two updates have different targets, then these targets have an
empty intersection, and (2) if two updates have the same target, then they have the same
condition.
Lemma 3.1 In a transaction in normal form: (1) the targets of a pair of updates are
either identical or disjoint, and (2) the conditions of a pair of updates having the same
target are syntactically equal.
Proof. (1) Assume by way of contradiction that in a transaction in normal form there are
two updates u i and u j with conditions C i and C j such that Targ(C i
the targets of u i and u j are different, C i 6= C j , but by
Definition 3.7, this implies that their targets are disjoint - a contradiction.
(2) Assume that in a transaction in normal form two updates with the same target have
different conditions. By definition of transaction in normal form, this implies that their
targets are indeed disjoint - a contradiction. 2
Each transaction can be transformed into an equivalent transaction in normal form
by "splitting" the target of each condition into sufficiently many targets. To this end, we
now introduce a number of axioms, called Split Axioms, that can be used to transform a
transaction into an equivalent transaction in normal form. Intuitively, these axioms show:
(1) how we can transform a transaction in an equivalent transactions that contains only
atomic conditions of the form (axioms SA2-SA4), and (2) how
we can further transform a transaction in such a way that possible interferences between
pair of updates of these two forms can be avoided (axioms SA5 and SA6). 1 Axioms SA1
and SA7 are useful in order to apply the others. Specifically, the former shows how we can
generate conditions composed by singletons over the various attributes, the latter shows
how we can add a condition over an attribute to a condition that does not mention it.
Definition 3.8 (Split Axioms) In the following axioms, called the Split Axioms, C is
a condition over X, A 2 X, and Cj Y denotes the set of atomic conditions in C that are
1 Clearly, this is just one of the possible way to enforce the normal form.
A g]
A g and C (i)
A , for is an atomic condition.
cg.
cg.
cg.
c is the only element in dom(A) such that c 1
The following result can be easily proved.
Lemma 3.2 The split axioms are sound, that is,
Proof. Let us consider, for instance, axiom SA2. Let
and let
It is easy to see that
Definitions 3.4 and 3.5, we have that Eff
Similar considerations apply to the other axioms. 2
We now show how these axioms can be practically used to normalize transactions. Let
us first introduce a property of conditions to be used in the algorithm that follows.
Property 3.1 Let C be a condition over X, Z be a set of attributes and C be a finite
set of constants. Then, for each attribute A 2 X " Z (1) CjA has the form
)g, then there is no c 2 dom(A) " C such that
The split algorithm that can be used to normalize transactions is reported in Figure 2.
We have the following result.
Theorem 3.1 Let t be a transaction, C be the set of all constants appearing in t, and Z
be the set of all attributes mentioned in t. Then, (1) Algorithm Split terminates over t,
C and Z and generates a transaction t split in polynomial time, 2 (2) t split - t, and (3) t split
is in normal form.
2 Hereinafter, polynomial time means time polynomial with respect to the length of the transaction.
Algorithm Split
Input: A transaction t, a set of constants C and a set of attributes Z;
Output: A new transaction t split ;
begin
while (there is an update u over R i whose condition does
not satisfies Property 3.1 for the sets of attributes X i and Z and
the set of constants C)
the transaction obtained from t i by splitting u
according to some split axiom;
\Gammafupdates with unsatisfiable conditionsg
end.

Figure

2: Algorithm Split
Proof. (1) Assume that contains just one update). By the structure of
the split axioms, at each iteration of the loop in Algorithm Split, we have jt
Moreover, the algorithm tries to enforce Property 3.1 that allows only updates having
atomic conditions of the form It follows that the number of
different forms that each atomic condition in t i+1 can take during the execution of the
algorithm is bounded by:
2. This corresponds to the number of ordered pairs of k symbols (for
the atomic conditions of the form A 2 plus the cardinality of C (for the atomic
conditions of the form A = c). Since each update is not split more than once with respect
to the same constant, it follows that for every i, jt i j is bounded by m jU j , that is, by
the number of complex conditions over the universe U of attributes that can be formed
with m different atomic conditions. Thus, the sequence of the t i 's is strictly increasing
and bounded and therefore the algorithm terminates. If t contains multiple updates, the
Split algorithm can be applied separately to each update in t and the results can be
then concatenated to obtain t split . It follows that Algorithm Split terminates over any
transaction and generates the output transaction in polynomial time.
(2) This part can be easily shown on the basis of Lemma 3.2, by induction on the number
of transformations applied to t by Algorithm Split.
(3) By way of contradiction, assume that t split is not in normal form, that is, there is a
pair of updates over the same set of attributes X with syntactically different conditions,
say C whose targets are not disjoint. Now let A be an attribute in X such that
Condition (1) of Property 3.1 (being the output of the
algorithm Split) we have that both C i j A and C j j A are of the form
Then, we have two possible cases : (a) C i j A has the form A has the form
the targets would be disjoint), and (b) C i j A has
the form A 2 (c A has the form A 2 (c (as above). In
both cases, at least one of the two conditions does not satisfy Condition (2) of Property
3.1, and this contradicts that t split is the output of Algorithm Split. 2
Example 3.2 Let domains over the integers and consider
the transaction This transaction is not in normal form
since the tuple is in both the targets of the two updates it contains.
By applying Algorithm Split we obtain:
1.
2.
(by axiom
The algorithm terminates at the second step and outputs
which is in normal form.
Let us now consider the transaction t which is not
in normal form. Note that t 0 does not satisfies Property 3.1 since the first update does not
even mention attribute B. By applying Algorithm Split we then obtain:
1. t 0
The algorithm terminates at the first step and outputs t 0
1 which is indeed in normal
form.
4 Active Databases
In this section we introduce formally the notions of active rule and program. We will
consider a simple form of active rules that however captures a considerable portion of
rules described in the literature and implemented in the systems. In particular, in [19] we
have considered the core of several concrete active rule languages whose rule execution
is specified only by informal descriptions, and have shown that with our framework it is
possible to describe the main features of these languages.
4.1 Active Rules and Programs
We represent an active rule by using the same notation introduced to express transactions.
This allows us to easily describe the way in which updates and active rules interact.
Specifically, the event and the condition parts of a rule are described by an update whereas
the action part is described by a transaction according to the definitions of Section 3.3,
with the only difference that variables can be used in the place of constants. These
variables are used to describe bindings that are passed from the event and the condition
to the action of a rule.
3 For simplicity, in this example we write A ! 1
Thus, let us fix a set of symbols called variables. We call generalized update an update
having a condition in which variables can occur in the place of constants, and generalized
transaction a transaction composed by generalized updates. Active rules are then defined
as follows.
Definition 4.1 (Active rule) An active rule has the form:
where: (1) u e is a generalized update such that, in the case of an insertion, the condition
does not necessarily specify a complete tuple; and (2) t a is a generalized transaction such
that each variable occurring in t a also occurs in u e .
The left hand side and the right hand side of the rule are also called the event part
and the action part , respectively.
Definition 4.2 (Active database) An active program P is a set of active rules. An
active database is a pair (s; P ) where s is a database instance and P is an active program.
Note that, the event part of an active rule allows us to specify both the update
triggering the rule and the condition to be met for the effective execution of the rule [23].
The intuitive semantics of a rule as above is then as follows: if an update u "matching"
with u e is executed on the database, then perform the transaction t a using the bindings
of the matching between u and u e .
Example 4.1 The active rules described in Section 2 (page 5) can be easily expressed
using the notation introduced above:
As we have said, one important point here is the temporal relationship between the
execution of the components of a rule. The event and the action have a temporal decoupling
under the deferred execution model, whereas, under the immediate execution model
there is no temporal decoupling. In our approach, the semantics of an active database
with respect to a transaction t is given in terms of the execution of a new transaction
induced by t, and so it will be defined in Section 5 along with the definition of the
rewriting technique.
4.2 Triggering of rules
We now describe how updates and active rules interact. We first introduce some preliminary
notions.
Let D be the union of all the domains of the attributes in U and V be the set of
variables. A substitution oe is a function from D [ V to D [ V that is the identity on
constants. Then, the matching between atomic conditions is defined as follows: a ground
atomic condition CA (that is, an atomic condition without variables) over A matches with
a generalized atomic conditions C 0
A over the same attribute if: either (1) C 0
A contains
variables and there is a substitution oe, called binding, such that
A ), or (2) C 0
A
is ground and there is at least one tuple v over X, such that v satisfies both CA and C 0
A
(that is, Targ(CA
Let C 1 be a (ground) condition and C 2 be a generalized condition over the same set
of attributes X. We say that for each attribute A 2 X occurring
in both of them, C 1 j A matches with C 2 j A . If so, the composition of the bindings (if any)
of the various atomic conditions forms the binding of C 1 and C 2 . It is easy to show that
if two condition match, then the matching is unique up to renaming of variables.
Definition 4.3 (Triggering) Let be an update and r be an active rule u e ) t a ,
where we say that (that is, u and u e perform
the same type of operation on the same relation), and (2) C matches with C e . If an update
u triggers a rule r : u e ) t a and oe is their binding, then we say that u induces the sequence
of updates oe(t a ) because of the rule r.
Note that because of the condition on the variables in an active rule (see Definition
4.1), a ground update always induces ground updates.
Example 4.2 The update +emp[name=bill,dname=toy,sal=60k] triggers the following
active rule:
because of the binding that associates bill to the variable N and toy to the variable D
(note that sal=60k matches with sal?50k). It follows that the update induces the update
+dep[dname=toy,mgr=bill].
5 Transaction transformation
In this section we present the algorithms that transform a user defined transaction into
an induced one that embodies the active rules behavior. We consider both the immediate
and deferred cases.
5.1 Transaction transformations
In

Figure

3 is reported the recursive algorithm that computes the reaction of a single
update. In the algorithm, the symbol ffl denotes the concatenation operator of sequences.
Note that, in general, different outputs can be generated by this algorithm depending
on the order in which triggered rules are selected in the first step of the while loop. Clearly
the algorithm can be generalized in such a way that all the possible reactions of an update
are generated. Moreover, according to several approaches described in the literature, the
algorithm can me modified (first step of the while loop) in order to take into account a
(partial) order on rules.
Unfortunately, the algorithm is not guaranteed to terminate over any possible input
since some kind of recursion can occur in the active program. However, syntactical restriction
can be given so that Algorithm Reaction is guaranteed to terminate. The
result that follows is based on the construction of a special graph G P describing the relationship
between the rules of P . The construction of this graph is based on the notion
of "unification" between updates that generalizes the notion of matching as follows. We
Algorithm Reaction
Input: An update u, an active program P , a set of constants C, and
a set of attributes Z.
Output: A sequence - P of updates induced directly or indirectly by u and P .
begin
Triggered triggered by ug;
while Triggered (u; P ) is not empty do
pick a rule r a from Triggered (u; P ) and let oe be
the binding of u and u e ;
for each u i in t do - ffl
end.

Figure

3: Algorithm Reaction
say that two generalized updates u 1 and u 2 (possibly both containing variables) unify if
there is a ground substitution oe (called unifier) such that Targ(oe(u 1
Then, in the graph G P the nodes represent the rules in P and there is an edge from a
a to a rule r
a if there is an update in t a that unifies with u 0
e .
Lemma 5.1 If the graph G P is acyclic then the algorithm Reaction is guaranteed to
terminate over P and any update u k .
Proof. Algorithm Reaction performs a recursive call for each update oe(u), where u in
an update that occurs in the action part of a triggered rule r and oe is the matching that
causes the triggering. This call causes in turn the triggering of a set of rules and, for
each of these rules, a number of further recursive calls of the Algorithm Reaction. Let
a be a rule triggered by oe(u). By Definition 4.3, this means that there is a
substitution oe 0 such that the targets of oe(u) and oe 0
e ) have a nonempty intersection.
Since we can assume that all the rules have different variables, we have that oe ffi oe 0 is a
unifier of r and r 0 . Therefore, two rules of P cause a recursive call if there is an edge from
r to r 0 in G P . Since G P is acyclic, it follows that the number of recursive calls is always
finite and so the algorithm terminates. 2
Hereinafter, we consider only active program P such that the graph G P is acyclic.
Indeed, less restrictive conditions can be given to achieve termination. Also, the algorithm
can be modified in order to take into account the presence of some kind of recursion. We
have discussed these issues elsewhere [18].
We are now ready to present the notion of induced transactions.
Definition 5.1 (Induced transaction) Let t be a user defined transaction, P be an
active program, C be a set of constants that includes the constants occurring in t and the
constants occurring in P , Z be a set of attributes that includes the attributes mentioned
in t and the attributes mentioned in P , and t be the output of Algorithm
t, C and Z. Then, consider the following transactions:
We say that t I and t D are induced by t because of P , under the immediate and deferred
modality respectively.
Actually, in the following we will refer to induced transactions without making any explicit
reference to the modality under which the transaction transformation has been computed
since the various results hold independently from this aspect.
For induced transactions, the following property holds.
Lemma 5.2 Let t be a user defined transaction and P be an active program. Then, any
transaction induced by t because of P is in normal form and can be computed in polynomial
time.
Proof. By Definition 5.1, each update occurring in a transaction t 0 induced by t is split,
using Algorithm Split, either in the preprocessing step or during the execution of Algorithm
Reaction, with respect to a set of constants and a set of attributes that include
those occurring in t. Therefore, by Theorem 3.1, t 0 is in normal form. Let us now consider
the complexity of the construction of t 0 . By the hypothesis on the acyclicity of the graph
G P , it easily follows that one execution of Algorithm Reaction requires, in the worst
case, a number of recursive calls equals to jP j
the number of rules in P , and so bounded by jP j 2 . Moreover, each call of Algorithm
Reaction involves one execution of Algorithm Split, which requires polynomial time
by Theorem 3.1, and a number of concatenation operations bounded by the maximum
number of updates occurring in the action part of a rule of P . It follows that Algorithm
Reaction requires polynomial time and, since this algorithm is used once for each up-date
occurring in the original transaction, we have that an induced transaction can be
computed in polynomial time. 2
We point out that given a user defined transaction and an active program, we may
have several different induced transactions, depending on the possible different outputs
of Algorithm Reaction, and even if the number of those induced transactions is always
finite, it may be very large. However, this number can be reduced by checking for instance
when certain ones are "obviously" equivalent, e.g., when certain rules trivially commute.
The problem of the efficient generation of induced transactions and their management is
beyond the goal of this paper and has been addressed elsewhere [18].
5.2 Semantics of induced transaction
As we have said in Section 2, an induced update in an induced transaction is executed only
if: (1) the inducing update has been effectively executed or (2) it has not been invalidated
afterwards. Then, a new notion of effect of a transaction needs to be defined according to
that. We call this new semantics the active effect of an induced transaction since it takes
into account the relationship between "inducing" updates and the "induced" ones due
to the active rules. This relationship has to be known always and can be made explicit,
during the generation of the induced transaction, in several ways, for instance, by means
of a labeling technique, as described in [18].
let u be an update and s be a database instance. We say that the effect of u is
visible in s if:
Also, let be a transaction and 1 - j - n. We denote by tj j the transaction
composed by the first j components of t.
Definition 5.2 (Active effect) The active effect Eff ff of an induced transaction
is a mapping Eff ff (t) from Inst(S) to Inst(S), recursively defined as follows, for
is induced by an update u i
in t and the effect of u i
is
not visible in Eff ff
We are finally ready to define the semantics of a transaction with respect to an active
database.
Definition 5.3 (Effect of a transaction in an active database) A potential
effect of a user transaction t in an active database (s; P ) coincides with Eff ff (t 0 )(s), where
t 0 is a transaction induced by t because of P .
6 Equivalence of active databases
Many interesting problems can be systematically studied in the formal framework we have
defined. Among them: equivalence, optimization and confluence of active databases. In
this section we shall consider equivalence and show that this property is decidable in
polynomial time.
6.1 Equivalence of induced transactions
Transaction equivalence has been extensively investigated in the relational model [1, 13].
The major results of this study concern deciding whether two transactions are equivalent
and transforming a transaction into an equivalent, but less expensive one. Unfortunately,
these results cannot be directly used within our framework because of the different semantics
defined for transactions. So, let us introduce a new definition of equivalence that
refers to induced transactions.
Definition 6.1 (Equivalence of induced transactions) Two induced transactions t 1
and t 2 are equivalent (denoted t 1 - ff t 2 ) if it is the case that Eff ff
Algorithm Summary
Input: An induced transaction
Output: The summary \Sigma
t ) of t.
begin
for each do
if (u i is induced by u not embedded in
then \Sigma i := \Sigma
else
case u i of
end.

Figure

4: Algorithm Summary
We now present a simple method for testing equivalence of induced transaction. Actu-
ally, the method works for any transaction in normal form and is based on a representation
of the behavior of a transaction that we call summary.
An annotated condition has the following syntax: hR; Ci, where R is a relation and
C is a complex condition. Then, the summary of an induced transaction t is a pair
t ) of sets of annotated conditions generated by the Summary algorithm
reported in Figure 4.
In the algorithm we make use of the following notion: given a summary \Sigma
we say that an update u with condition C is embedded in \Sigma t if either
t or
t .
The summary \Sigma
describes, in a succinct way, the behavior of an induced
transaction t. Specifically, let m and n be the cardinalities of \Sigma
t and \Sigma \Gamma
respectively
and consider a transaction b t defined as follows: for each hR; Ci 2
has an update
\GammaR[C] in one of its first n positions, and for each hR; Ci
has an update +R[C]
in one of the positions from m. Actually, since both \Sigma
t and \Sigma \Gamma
are sets,
we have several different way to build b t ; however, since the transactions we obtain have
always the same deletions followed by the same insertions, their (non-active) effects are
always the same. Thus, the order in which the updates occur in b t is immaterial and we
can consider deterministic its construction. We now have the following.
Lemma 6.1 Eff ff
Proof. The proof proceeds by induction on the length n of t. The basis
since in this case it is easy to see that and so, by Definition 5.2, Eff ff
With regard to the induction step, assume that Eff ff
Definition 5.2, for any instance s, the update u j is not executed on Eff ff (tj j \Gamma1 )(s) if and only
if it is induced by an update u i occurring in tj j \Gamma1 that is not visible on Eff ff
this condition, by the inductive hypothesis u i is not visible also on Eff ( b t
construction, this simply implies that u i does not occur in b tj j \Gamma1 . But this means that u i is
not embedded in so, in the execution of the Algorithm Summary, the annotated
condition corresponding to u j is not included in \Sigma j and therefore u j does not occur in b t j j .
It follows that, for any instance s, u j is effectively executed on Eff ff under the
active effect semantics if and only if u j occurs in b tj j , and so we have: Eff ff (tj
this completes the induction part. For
Theorem 6.1 Let t 1 and t 2 be two induced transaction over the same set of constants
and the same set of attributes. Then, we have that t 1 - ff t 2 if and only if \Sigma t 1
Proof. (If) Let \Sigma t 1
. We can assume, without loss of generality, that b
by Lemma 6.1, Eff ff
(Only if) Let Eff ff be an instance and, for some relation scheme R(X),
let v be a tuple in s(R(X)) such that v 62 Eff ff (t 1 )(s)(R(X)). Clearly, we have also
that v 62 Eff ff (t 2 )(s)(R(X)). Now consider the transactions b
there is an update u
and an update u
are induced transaction over the same set of constants and the same set of
attributes and therefore their concatenation t 1 t 2 is a transaction in normal form. Since
have a non empty intersection, by Lemma 3.1, it follows that
. Thus, the annotated condition hR; C 1 i occurs
in both \Sigma \Gamma
and
. The same considerations apply for insertions. It follows that, by
. 2
An interesting aspect to point out is that the notion of active effect of an induced
transaction indeed generalizes the notion of effect of a user-defined transaction. This
implies that the above characterization of equivalence also hold for ordinary transactions
in passive environments.
6.2 Equivalence of user transactions
The notion of equivalence of user transactions, can be naturally extended in an active
environment. Since we have seen that a transaction can potentially produces different
results on an active database (depending on the different induced transactions that can
be generated from it), we can assume that two transactions are equivalent when they are
able to produce always the same results on any database instance.
Definition 6.2 (Equivalence of transactions in an active framework) Two user
transactions t 1 and t 2 are equivalent with respect to an active program P if for each
transaction t 0
induced by t 1 because of P there is a transaction t 0
induced by t 2 because
of P such that t 0
2 , and vice versa.
By the results of the above section, we can state the following result.
Theorem 6.2 The equivalence of two user transactions in an active framework can be
decided in polynomial time.
Proof. Given a user transaction t, by Lemma 5.2 we can construct the transactions it
induces in polynomial time. The number of transactions that can be induced by a single
update because of an active program P is bounded by a constant that depends only on
the size of P . Specifically, it is bounded by
denotes the cardinality of P . Then, the number of transactions that can be induced by
t is bounded by k \Theta jtj. By Definition 6.2, the equivalence of two user transactions t 1
and t 2 requires a test for the equivalence of each pair of transactions induced by t 1 and t 2
respectively, that is, a number of tests bounded by k 2 \Theta jt 1 j \Theta jt 2 j. Now, by Theorem 6.1,
equivalence of two induced transactions requires: (1) the construction of their summaries
by means of Algorithm Summary, which requires time linear with respect of the length of
the transaction (bounded by jtj \Theta jP j 2 ), and (2) the test for the equality of two summaries,
which requires time proportional to jt 1 j \Theta jt 2 j \Theta jP j 4 . It follows that the equivalence of t 1
and t 2 can be decided in polynomial time. 2
6.3 Axiomatization of transaction equivalence
Before closing this section, we present two simple and intuitive axioms for proving equivalence
of induced transactions, which provide much insight into the relationship between
updates in an induced transaction. Since these axioms show how transactions can be
manipulated without altering their overall effect, we call them Manipulation Axioms. We
will also show that these axioms suggest a way to optimize efficiently transactions in an
active environment.
In order to present those axioms, we need to introduce some preliminary notions.
First, we use the notation Induced(u) to denote the updates induced directly or indirectly
by the update u in an induced transaction. Moreover, we say that two updates collide
if they are over the same relation scheme and their conditions are identical. Finally, we
introduce the notion of validity of an update in a transaction, which is the syntactical
counterpart of the notion of visibility and is recursively defined as follow: an update u i
in an induced transaction t is valid if: (1) it is not induced, or (2) it is induced directly
by an update u j preceding u i in t, and there is not a valid update u k in t between u j and
that collides with u j .
Definition 6.3 (Manipulation Axioms) The following axioms are called Manipulation
Axioms and involve induced transactions in which - 1 and - 2 are (eventually empty)
subtransactions:
[Switching Axiom]
where: (1) u i and u j do not collide, (2) u i is a valid update, and (3) u j does not
collide with any update u k occurring in - 1 such that u
[Merging Axiom]
where: (1) u i and u j collide, (2) u j is a valid update, and (3) - 0
the updates in Induced(u i
Intuitively, axiom (MA1) states that if the updates u i and u j do not collide, and u j
cannot invalidate the effect of the updates inducing u i (if any), then they can be switched.
Instead, Axiom (MA2) states that if u i collides with u j then their execution is equivalent
to execute only u j , provided that: (1) all the updates induced (directly or indirectly) by
are not executed as well, and (2) the updates induced (directly or indirectly) by both
are however executed (this happens when u j is induced by u i and so
Lemma 6.2 The manipulation axioms are sound, that is t 1 - man t 2 implies t 1 - ff t 2 .
Proof. Let us first consider MA1: since u i and u j do not collide, u i cannot invalidate u j if
we execute the latter first. Moreover, by Definition 5.2, before the switching the effective
execution of u i depends on the updates occurring in - 1 and if u j does not collide with
any update inducing u i , we have that after the switching the execution of u i still depends
on the updates occurring in - 1 . Finally, before the switching the effective execution of u j
depends on the updates occurring in - 1 ; u i . Therefore, if u j is not induced by u i , after
the switching the effective execution of u j still depends on the updates occurring in - 1 .
On the other hand, if u j is induced by u i , no problem arises since u i is valid and so u j
has to be executed anyway. It follows that, under the given conditions, the active effect
of coincides with the active effect
Let us now consider MA2: since u i and u j collide and u j is valid, we have that u j
invalidates u i and therefore u i can be deleted without altering the effect of the transaction
. Moreover, since u i is invalidated by u j , its effect is not visible during the
execution of - 2 , and so all the updates induced directly or indirectly by u i can be deleted
from - 2 , except those induced also by u j (in the case in which u j is induced by u
under the given conditions, we have that the active effect of - coincides with
the active effect
Theorem 6.3 MA is a sound and complete set of axioms for proving equivalence of
induced transactions.
Proof. By Lemma 6.2, MA is sound. To prove the completeness of these axioms, consider
two induced transaction t 1 and t 2 such that t 1 - ff t 2 . Then, using the manipulation
axioms, we can transform these transactions in two new transactions t 0
all the deletions are performed before all the insertions. This can be done in two steps:
in the first one all the updates in the transaction that collide with another update are
deleted and in the second one all the deletions are moved to the front of the transaction,
before all the insertions. The first step can be performed by using the manipulation
axioms as follows. Starting from the second update and iterating over the updates in the
transaction, we move forward, using axiom MA1, the updates preceding the one currently
under consideration that collide with it. Then, these updates are deleted using axiom
MA2. It is easy to show that this work can always be done. After the first step, there is
no pair of updates in the transaction that collide and so, in the second step, we can easily
move the deletions to the front of the transaction using axiom MA1. Since the axioms
are sound by Lemma 6.2, we have
2 and so t 0
. Also, since no
pair of updates in both t 0
collide, it easily follows that t 0
since t 0
, by Theorem 6.1 we have \Sigma t 0= \Sigma t 0. Then, by construction, we have that b
coincide up to a permutation of the deletions and a permutation of the insertions.
It follows that b
1 can be transformed into b
using repeatly axiom MA2. In sum we have:
man t 0
man
man t 2 . 2
7 Analysis of active rule processing
On the basis of the results on transaction equivalence, we derive in this section a number
of results about important properties of active databases.
7.1 Confluence
Confluence is a strong property and some applications may actually need a weaker notion
[2]. We then propose two notions of confluence. The former is weaker than the latter
since refers to a specific transaction. However, this notion can be nicely characterized and
turns out to be of practical importance.
Definition 7.1 (Weak confluence) An active program P is confluent with respect to
a user transaction t if all the transactions induced by t because of P are equivalent.
Definition 7.2 (Strong confluence) An active program P is (strongly) confluent if it
is confluent with respect to any user transaction.
The following result show that there is a practical method for testing weak confluence.
Theorem 7.1 Weak confluence is decidable and can be tested in polynomial time.
Proof. Given a user transaction t, by Lemma 5.2, we can construct the transactions
induced by t in polynomial time. By Definition 7.1, the confluence of t with respect to P ,
requires to test for equivalence of each pair of transactions induced by t. The number of
tests to be done is bounded by the square of the maximum number of transactions that
can be induced by t, that is, by k 2 \Theta jtj 2 , where k is a constant that depends only on the
size of P (see the proof of Theorem 6.2). Since, by Theorem 6.1, testing for equivalence
of two induced transactions requires polynomial time, it follows that the confluence of t
with respect to P can be also performed in polynomial time. 2
We now introduce another interesting notion of confluence that is independent of a
specific transaction.
Let P be an active program, C be the set of constants occurring in P and r : u e ) t a
be a rule of P . We denote by U r the set of updates obtained from r as follows. For each
atomic condition CA in u e involving a variable x, let A be the
set of intervals and (2) there is no
constant c 2 CA such that c 2 since CA is finite, \Psi A is actually a
finite partition of dom(A). Now, let K / be a set of constants that contains one element
(whichever it be) in every . Note that since \Psi A is a
finite partition of dom(A), KA is always finite. Then, the set U r contains all the possible
updates that can be obtained by applying to u e a substitution that, for each attribute A
occurring in u e , maps variables of u e occurring in CA to constants in KA .
Intuitively, the set U r contains all the "representatives" of triggering updates for the
rule r, and specify the different ways in which the rule r can be triggered by an update.
Definition 7.3 (Local confluence) An active program P is locally confluent on a rule
confluent with respect to any update in U r . An active program P is locally
confluent if it is confluent on every rule in P .
Note that, by Theorem 7.1, it follows that we can check for local confluence of an active
program in polynomial time. The following result states that local confluence, although
restrictive, is a desirable property for an active program.
Theorem 7.2 If an active program is locally confluent then it is strongly confluent.
Proof. Let t be a user transaction in normal form with respect to the set of constants
occurring in t and P and the set of attributes mentioned in t and P . Note that this is
not a restrictive hypothesis since, by Theorem 3.1, any transaction can be transformed
in a transaction satisfying this property using Algorithm Split. The proof proceeds by
showing that, for each update u in t triggering a rule r 2 P and each sequence of updates
- induced by u, there is a mapping over constants ' such that: (1) '(u) 2 U r , and (2) '(u)
induces a sequence of updates - 0 such that - 0 ). Specifically, this mapping is defined
as follows: for each atomic condition CA occurring in u, ' is the identity on the constants
in KA and maps each constant c 62 KA to the constant c 0 2 KA that belongs to the interval
containing c. Clearly, '(u) 2 KA . Moreover, by Definition 4.3 (triggering) and
by Algorithm Split, it is easy to show, by induction on the number of step of Algorithm
Reaction, that for each sequence of updates - generated by this algorithm starting from
u, the same algorithm is able to generate the sequence '(-) starting from '(u). But, by
definition of local confluence, we have that all the sequences of updates induced by '(u)
are equivalent. It easily follows that all the sequences of updates induced by u are also
equivalent. Thus, we have that P is confluent with respect to each sequence of updates
induced by an update in t (if any). Now it can be easily shown that, given a transaction
t, if there is a partition of t in sequences of adjacent updates
is confluent with respect to each - i , confluent with respect to t.
Therefore, by Definition 5.1 of induced transaction, it follows that, independently from
the modality, for any transaction t, P is confluent with respect to t and so P is strongly
confluent. 2
It is possible to show that, while local confluence implies strong confluence, the converse
in not true in general even for weak confluence. That is, there are active programs
that are not locally confluent but are confluent with respect to certain transactions.
The notion of local confluence gives us a sufficient condition for confluence that can
be checked very efficiently. Let P be an active program and P conf
be the set of rules on
which P is locally confluent. Note that this set can be derived one for all, at definition
time. The following characterization of weak confluence simply requires, for each update
in a transaction, one test of matching with the event part of the rules in P .
Corollary 7.1 Let P be an active program and t be a user defined transaction. Then, P
is confluent with respect to t if each update in t triggers only rules in P conf
Proof. P conf
is indeed a strongly confluent program and therefore, by Theorem 7.2, t is
confluent with respect to P conf
and so with respect to P . 2
7.2 Optimization
A major objective of our research is to provide tools for optimizing induced transac-
tions. This is particularly important since, in our approach, an optimization technique
for induced transactions yields a method for optimizing the overall activity of active rule
processing.
According to [1], two types of optimization criteria for transactions can be considered.
The first is related to syntactic aspects (e.g., length and complexity of updates) of a
transaction, whereas the second is related to operational criteria such as the number of
atomic updates performed by a transaction. Both criteria are formally investigated in
this section.
Let us first introduce a preliminary notion. Let P be a partition of the tuple space,
that is, a partition of the set of all tuples v 2 Tup(X) for every R(X) in the scheme S:
we say that a transaction t is based on P if, for each condition C occurring in an update
of t, Targ(C) 2 P.
According to most implementations, we assume that a deletion operation is more
complex than an insertion operation (denoted u ordering may be
invalid for certain implementation of the updates. However, changing the ordering does
not affect the results that follow.
Definition 7.4 A transaction based on P is syntactically optimal if for
every transaction t 0 based on P equivalent to t, t
exists a permutation - of
Given a transaction t, we denote by Nop(t) a mapping from Inst(S) to IN \Theta IN that
associates to an instance s the pair (i; d) where i is the number of tuples inserted by t
into s, and d is the number of tuples deleted by t from s. Moreover, we denote by - the
order relation on IN \Theta IN defined as follows:
where k is the ratio between the cost of an insertion operation and the cost of a deletion
operation. Intuitively, the order relation - takes into account the number of update
operations, together with the preference attributed to insertions over deletions.
Definition 7.5 A transaction t based on P is operationally optimal if for every transaction
based on P equivalent to t, for each instance s 2 Inst(S).
Note that the above definitions do not refer to any possible pair of equivalent transactions
but rather to transactions that are based on the same partition of the tuple space.
This however is a more convenient form since it is possible to show that if the transactions
are not based on the same partition, syntactically and operationally optimality cannot be
attained simultaneously in general.
Definition 7.6 A transaction t is optimal if it is operationally and syntactically optimal.
Let us consider the manipulation axioms introduced in the previous section (Defini-
tion 6.3). It is easy to see that one application of the Merging Axiom yields a strictly
simpler transaction, whereas the Switching Axiom does not affect the complexity of the
translation, but is however useful in order to apply the Merging Axiom. This simple observation
leads to a method for optimizing induced transactions. Intuitively, this method
consists of applying a number of times the Switching Axiom followed by an application
Algorithm Optimize
Input: An induced transaction
Output: A new transaction t opt .
begin
repeat
if collides with some update u j (j ! i) that precedes u i in t i )
then t i+1 := the transaction obtained from t i by deleting u j and
all the updates in Induced(u j
else t
until (all the updates in t i have been examined)
end.

Figure

5: Algorithm Optimize
of the Merging Axiom, until no modification can be performed. The method can be effectively
implemented in a very simple way by means of the algorithm in Figure 5 (recall
that Induced(u) denotes, in an induced transaction, all the updates induced directly or
indirectly by the update u).
The following theorem confirms that the algorithm always terminates (in polynomial
time) and produces an optimal transaction.
Theorem 7.3 Let t be an induced transaction. Then, (1) Algorithm Optimize terminates
over t and generates a transaction t opt in polynomial time, (2) t opt - ff t, and (3)
t opt is optimal.
Proof. (1) The algorithm simply involves an iteration over the updates in t and so requires,
in the worst case, time linear in the length of the transaction. Note however that some
step can involve a reduction of t and so, on the average, the execution of the algorithm is
even more efficient.
(2) This part can be proved by showing that, at each step of the loop in the algorithm,
when the new transaction (t i+1 ) it is not equated to transaction of the previous step (t i ),
it can be obtained from it through a number of applications of the Switching Axiom (to
move close to u i ) followed by one application of the Merging Axiom. To show this,
we note that the algorithm eliminates collisions between updates as soon as they are
encountered while iterating over the updates of the transaction. This implies that, at
each step, in the sequence of updates - 1 preceding the update u i under consideration,
there is no pair of updates that collide and so all the updates are valid. Therefore, at each
step, we can freely use the Switching Axiom in - 1 (see Definition 6.3) and, in particular,
if there is an update u j in - 1 that collides with u i , we can move u j close to u i . Then, we
can apply the Merging Axiom thus obtaining exactly the transaction t i+1 . By Lemma 6.2,
it follows that, for each i, t i - ff t and so, at termination, t opt - ff t.
(3) First note that, as a consequence of what shown in part (2), in t opt there is no pair of
updates that collide. Now assume, by way of contradiction, that t opt is not syntactically
optimal and let t 0 be a transaction based on the same partition P and equivalent to t opt
that has less update operations than t opt (according to the order -). This implies that, for
each update u of t opt with condition C that is visible on Eff ff (t opt )(s), for some instance
s, there must be an update u 0 with condition C 0 in t 0 such that
Therefore, since t opt has more updates than t 0 , there is at least an update u x in t opt that
is not visible on s, and this is possible only if u x is invalidated by another update in t opt .
But t opt is in normal form as it is obtained by just deleting updates from a transaction in
normal form. By Lemma 3.1, this implies that there are two updates in t opt that collide
- a contradiction.
Assume now, again by way of contradiction, t opt is not operationally optimal and let t 0 be
a transaction based on the same partition P and equivalent to t opt such that Nop(t 0
opt )(s) for some instance s 2 Inst(S). This implies that t opt either perform two
times the insertion/deletion of the same tuple or a tuple is first inserted (or deleted) and
then deleted (inserted). But t opt is in normal and so, by Lemma 3.1, this is possible only
if there are two updates in t opt that collide - again a contradiction. 2
Conclusions
We have presented a formal technique that allows us to reduce, in several important cases,
active rule processing to passive transaction execution. Specifically, user defined transactions
are translated into new transactions that embody the expected rule semantics under
the immediate and deferred execution modalities. We have shown that many problems
are easier to understand and to investigate from this point of view, as they can be tackled
in a formal setting that naturally extends an already established framework for relational
transactions. In fact, it turns out that several important results derived for transactions
in a passive environment can be taken across to an active one. Firstly, we have been able
to formally investigate transaction equivalence in the framework of an active database.
Secondly, results on transaction equivalence have been used to check for interesting and
practically useful notions of confluence. Finally, optimization issues have been addressed.
We believe that this approach to active rule processing is suitable for further interesting
investigations. From a practical point of view, we have studied efficient ways to generate
and keep induced transactions, in the context of an implementation of the method on the
top of a commercial relational DBMS [18]. From a theoretical point of view, we believe
that the various results can be extended in several ways to take into account more general
frameworks. Finally, the rewriting technique can be applied to other data models such as
one based on objects [16].



--R

Equivalence and optimization of relational transactions.
Static analysis techniques for predicting the behavior of active database rules.
A model for active object-oriented database
Automatic generation of production rules for integrity maintenanace.
Chimera: a model and language for active DOOD Sys- tems
Deriving production rules for constraint maintenance.
Deriving production rules for incremental view maintenance.
A structured approach for the definition of the semantics of active databases.
ODE as an active database: constraints and triggers.
Design and implementation of Chimera's active rule language.
Combining theory and practice in integrity control: a declarative approach to the specification of a transaction modification subsystem.
Rule processing in active database systems.
Simplification rules and complete axiomatization for relational update transactions.
The architecture of an active data base management system.
Active databases as a paradigm for enhanced computing environ- ments
A rewriting technique for implementing active object systems.
A rewriting technique for the analysis and the optimization of active databases.
A transaction transformation approach to active rule processing.
A framework for the specification of active rule language semantics.
Implementing large production systems in a DBMS environment: concepts and algorithms.
The integration of rule systems and database systems.
On rules

--TR
Equivalence and optimization of relational transactions
The architecture of an active database management system
A theory for rule triggering systems
Deriving production rules for constraint maintenance
Set-oriented production rules in relational database systems
On rules, procedure, caching and views in data base systems
Simplification rules and complete axiomatization for relational update transactions
Rule processing in active database systems
Termination and confluence of rule execution
Automatic generation of production rules for integrity maintenance
Static analysis techniques for predicting the behavior of active database rules
A structured approach for the definition of the semantics of active databases
A logic-based integration of active and deductive databases
Design and implementation of Chimera active rule language
Active rule analysis and optimisation in the rock MYAMPERSANDamp; roll deductive object-oriented database
Foundations of Databases
The Integration of Rule Systems and Database Systems
Refined Triggering Graphs
A Transaction Transformation Approach to Active Rule Processing
A Rewriting Technique for the Analysis and the Optimization of Active Databases
Expressiveness and Complexity of Active Databases
Ode as an Active Database
Deriving Production Rules for Incremental View Maintenance
On Implementing a Language for Specifying Active Database Execution Models
An Algebraic Approach to Rule Analysis in Expert Database Systems
Using Delta Relations to Optimize Condition Evaluation in Active Databases
Investigating Termination in Active Database Systems with Expressive Rule Languages
A Rewriting Technique for Implementing Active Object Systems
A Framework for the Specification of Active Rule Language Semantics
Combining Theory and Practice in Integrity Control
Termination Analysis in Active Databases

--CTR
Burcin Bostan-Korpeoglu , Adnan Yazici, A fuzzy Petri net model for intelligent databases, Data & Knowledge Engineering, v.62 n.2, p.219-247, August, 2007
optimization;rule semantics;confluence;active databases;transaction equivalence