A new approach to detecting active rule confluence with exclusive rules during an indeterminable rule process

Abstract

Active rules have been employed for enhance self-reaction functionality, but how to detect their confluence property during an indeterminable rule process is intractable. If two rules without priority have been triggered at the same time, then anyone can be firstly chosen to execute at random and two different executive sequences will be arisen. An active rule set is confluence if and only if the same final database state appears no matter which executive sequence has been chosen to execute. The existing methods based on Rule Commutativity are no more effective to detect the confluence case if a rule set has exclusive rules and has no user-defined priority as they do not designed for rules without priority and they do not consider whether two different executive sequences for rules can be satisfied by the same database state. To address these problems, this work proposes the concepts of Exclusive Rule and Confluence Requirement with exclusive rules based on the conditional formula of an executive sequence. Then, a new algorithm for confluence detection is provided. The examples and theoretical analysis clearly show that the proposed method achieves much better detection performance when exclusive rules appear.

Keywords

Active rule rule analysis confluence exclusive rule algorithm

1 Introduction

Recently, active rules have attracted many researchers’ attention and have been applied for many new fields such as XML document [1, 2], RDF [3], Semantics network [4] and sensor database [5], etc. In addition, active database systems provide a convenient platform for large and efficient knowledge-bases and expert systems [6]. Active rules follow the paradigm as Event-Condition-Action. If two rules have been triggered at the same time and there is no priority between their executions, then one of them can be firstly chosen to execute at random and two different executive sequences will be arisen. An active rule set is confluence if and only if the same final database state appears no matter which executive sequence has been chosen to execute. Data consistency is one of crucial aspects to guarantee the data quality of a database. Obviously, the confluence property of rules will maintain the data consistency.

The existing approaches are based on Rule Commutativity to detect whether an active rules set is confluence [6 –9], but they are conservative to some degree. Aiken et al. [6] presented the precondition to guarantee the confluence property based on Rule Commutativity; Comai et al. [7] tried to transform active rules into deductive rules with better-defined terms, then detect the confluence property based on their triggering priorities; Papamarkos et al. [8] presented how to detect the Rule Commutativity of rules on RDF Metadata; Bostan-Korpeoglu et al. [9] inferred a total order of the triggering priorities of a rule set using a fuzzy Petri net model. These approaches have the following inadequacies:

They are specially designed for an active rule set with priority and don’t consider those rules without priority. From the following example 2, we can see that an active rule set without user-defined priority may appears in an application. Also, Baralis et al. [10] considered an active rule set with priority or without priority when addressing the termination detection problem. If an active rules set has a total order of the triggering priorities, its rule processing is deterministic and it is confluent [11]. It is shown that our consideration in this paper is significant, that is, an active rule set without priority is more easily to exhibit the non-confluence property than those rules with priority.

Based on Rule Commutativity, they consider all possible executive sequences (i.e. paths in a executive graph in [6]) which originated from the same initial database state when detecting whether the same final database state appears after whichever executive sequence has been chosen to execute; However, they ignore that such an executive sequence may be not really executed if there is a rule in it cannot be satisfied its condition by the current database state. Obviously, an executive sequence should not affect the confluence property if it is not really executed; that is, the existing approaches would be not effective unless such an executive sequence has been identified and considered.

To address the above inadequacies, the concepts of Exclusive Rule and Confluence Requirement with exclusive rules are proposed in this paper for a rule set without user-defined priority. As discussed later, exclusive rules will usually appear for expressing the control logic just like the switch-case structure in C or C++ programs. Moreover, a new algorithm of confluence detection is provided for an active rule set with exclusive rules, and its complexity is analyzed.

This paper is organized as follows. Section 2 presents a brief review of Confluence Requirement and confluence analysis in existing methods. An example in Section 3, which models the behavior of a control system, illustrates our motivation in this paper. Section 4 defines exclusive rules and prepares a theorem to identify them. After analyzing the inadequacy of the existing methods, Confluence analysis for a rule set without priorities is developed in Section 5. A new algorithm is presented to analyze the confluence of a rule set with exclusive rules in Section 6. The conclusion is shown in Section 7.

2 Preliminary

2.1 Active rule

Active rule follow the paradigm Event-Condition-Action (ECA). Using relational database schema, ECA rules can be expressed as follows [11]:

(1) The Event set is a set of data manipulate operations that are monitored by system; (2) Condition is a sentence which consists of the predicates defined on the current database state and transition values appeared in rules; (3) Action is a set of data manipulate operations.

Example 1. The following ECA rule is abstracted from [11] and used to control a valve: if the temperature parameter of a sensor has been changed or the message “valve opened” has been sent, then the rule r₁ will be triggered.

r₁:

event:

update (sensor.T), sendMessage (‘valve opened’)

condition:

valve.state=‘open’, sensor.T < T₁, valve.lock:=‘on’

action:

valve.lock:= ‘off’, valve.state:= ‘closed’,

sendMessage (‘valve closed’);

2.2 The indeterminable rule process

The rule process will be performed by the following steps [11]:

If there is no triggered rule, then the process ends;

To choose a rule which is triggered and set it untriggered;

To evaluate the condition of the chosen rule;

If the condition of the chosen rule is evaluated as true, then its action will be performed.

A new event may be arisen during the rule’s action execution in step 4) and it may trigger other rules, then the above scheduling sequence as 1)-2)-3)-4) will repeat until no triggered rule is left and the rule process ends.

Maybe more than one rule is triggered in step 2) and they compose the set of conflict rules [11]. If there is no priority between two conflict rules, then anyone of them can be firstly chosen to execute at random and the rule process is indeterminable [11]. Many different executive sequences will be arisen during an indeterminable rule process, thus the confluence or non-confluence property should be detected to show whether the same final database state appears no matter which executive sequence has been chosen to execute. Such a case will be illustrated by the Example 2 in Section 3.

2.3 Confluence analysis based on rule commutativity

Illustrated as Fig. 1 abstracted from Aiken et al. [6], we say that two rules r_i and r_j are commutative if, given any state S in any execution graph for active rules process, considering rule r_i and then rule r_j from state S produces the same state S^′ as considering rule r_j and then rule r_i.

Based on Rule Commutativity, the confluence requirement is presented in [6]. That is, if two different executive sequences can be scheduled at random and any two rules, which are abstracted respectively from them, are commutative, then they can be converted each other through Rule Commutativity. Really, such two executive sequences are equivalence.

To simplify, the following notations will appear in the rest of this paper.

Let R = {r₁, r₂, … , r_n} be a rule set and P = {r_i > r_j, r_k > r₁, ⋯} be the priorities assigned for R, where r_i > r_j means that r_i has priority over r_j in scheduling for execution.

Let Triggers(r) be the set of rules triggered by r’s action (such a rule may be r itself)

Lemma 1.(Lemma 8.1 of [6].) For distinct rulesr_iandr_j, if any of the following conditions hold then they may be noncommutative; otherwise they are commutative:

r_j∈T riggers(r_i), i.e.,r_ican causer_j, to become triggered;

r_ican untriggeredr_j;

r_i’s operations can affect whatr_juses;

r_i’s insertions can affect whatr_jupdates or deletes;

r_i’s updates can affectr_j’s updates;

any of 1–5 withr_iandr_jreversed.

Definition 1. (Confluence Requirement, Definition 8.5 of [6].) Consider any pair of unordered rules r_i and r_j in R. Let R₁ ⊆ R and R₂ ⊆ R be constructed by the following algorithm: $\begin{matrix} R_{1} \leftarrow {r_{i}} \\ R_{2} \leftarrow {r_{j}} \end{matrix}$ repeat until unchanged: $\begin{matrix} R_{1} \leftarrow R_{1} \cup {r \in Triggers (r_{1}), r_{1} \in R_{1} and \\ r > r_{2} \in P, r_{2} \in R_{2}, r \neq r_{j}} \\ R_{2} \leftarrow R_{2} \cup {r \in Triggers (r_{2}), r_{2} \in R_{2} and \\ r > r_{1} \in P, r_{1} \in R_{1}, r \neq r_{i}} \end{matrix}$

For every pair of rules r₁ ∈ R₁ and r₂ ∈ R₂, r₁ and r₂ must commute.

Theorem 1.(Confluence Theorem, Theorem 8.7 of [6].) Suppose the Confluence Requirement holds forRand there are no infinite paths in any execution graph forR. Then any execution graph forRhas exactly one final state, i.e., the rules inRare confluent.

From Theorem 1, it is known that the termination property for execution should hold if a rules set is confluent. How to detect the termination property of a rule set is another crucial issue [10 –16] and is omitted as it goes beyond this paper.

As Aiken et al. [6] mentioned, the Confluence Requirement is not a necessary condition but a sufficient condition to guarantee the conclusion of theorem 1 holds. That is, applying Theorem 1 for confluence analysis is conservative to some degree. If a rules set is not satisfied by the Confluence Requirement, it may be either confluence or non-confluence.

3 Motivation

Here, the motivation example is used to model the behavior of a control system where active rules are shown as the form as the Example 3.4 in [11].

Example 2. It is illustrated as Fig. 2 that a valve control system concerned with oil flowing into or out of a tank, where the valve v₁ is used to adjust the flux speed into or out of the tank and the valve v₂ is used to control the flux speed into or out of the pipe and a Sensor detects the pressure change of the pipe. Each valve is characterized by the position (opened, closed, or semi opened) represented in attribute State. tank.H represents the current height of oil in the tank and sensor.P represents the current pressure of the pipe. The direction of the flux (into or out of the tank) is represented in attribute pipe.State. Message can be set to the operator, and the flag Done represents whether the current pressure alarm has been handled (false or true).

1) r₁ is used for the generation of an alarm when the pressure of the pipe is high and falls into the scope to be control.

event: update (sensor.P)

condition:

sensor . P ≥ p₁, h₁ < tank . H < h₂, Done= false

action: sendMessage (‘Pipe pressure is high’);

2) r₂ and r₃ are used for the operations reacting to the case that the pressure of pipe is high when the oil flows into the tank. Once the height of the oil exceeds the defined threshold, all valves should be closed to stop the oil flowing into the tank.

r₂:

event: sendMessage (‘Pipe pressure is high’)

condition:

pipe.State= ‘in’, v₁.State = ‘semiopened’

action:

v₁.State= ‘open’, v₂.State= ‘semiopened’

sendMessage(‘the regulation valve v₁ is open’)

Done= true, sendMessage (‘the regulation is done’);

r₃:

event:

sendMessage (‘the regulation valve v₁ is open’), update (tank.H)

condition: pipe.State= ‘in’, tank . H ≥ h₂

action:

v₂.State= ‘closed’, v₁.State= ‘closed’

Done= false, sendMessage (‘stop oil flowing into the tank as its height is overhigh’);

3) r₄ and r₅ are used for the operations reacting to the case that the pressure of pipe is high when the oil flows out of the tank. Once the height of oil is under the defined threshold, all valves should be closed to stop oil flowing out of the tank.

r₄:

event: sendMessage (‘Pipe pressure is high’)

condition:

pipe.State= ‘out’, v₁.State= ‘open’

action:

v₁.State= ‘semiopened’, v₂.State= ‘open’

sendMessage(‘the bypass valve v₂ is open’)

Done=true, sendMessage (‘the regulation is done’);

r₅:

event:

sendMessage (‘the bypass valve v₂ is open’), update (tank.H)

condition: pipe.State= ‘out’, tank . H ≤ h₁

action:

v₁.State=‘closed’, v₂.State= ‘closed’

Done = false, sendMessage (‘stop oil flowing out of the tank as its height is too low’);

Figure 3 represents the triggering graph of the above rule system R = {r₁, r₂, r₃, r₄, r₅}.

In Fig. 3, r₂ and r₄ are both triggered by r₁ and they form a conflict set. No priority is assigned between r₂ and r₄, so there are two different executive sequences: 1) if r₂ is firstly chosen to execute, the executive sequence will be the form as r₁ → r₂ → r₃ → r₄ → r₅; 2) if r₄ is firstly chosen to execute, the executive sequence will be the form as r₁ → r₄ → r₅ → r₂ → r₃.

Obviously, r₂ and r₄ are a pair of unordered rules represented in Definition 1. Through Definition 1, R₁ and R₂ are initiated with R₁ = {r₂} and R₂ = {r₄}. During the process of computing R₁ and R₂, some a rule will be triggered but it isn’t electable as it has not been assigned any priority. According to (3) and (5) of Lemma 1, r₂ and r₄ are noncommutative as v₁.State appears in the conditions and actions of both r₂ and r₄. Based on Theorem 1, R = {r₁, r₂, r₃, r₄, r₅} is non-confluent.

Really, r₂ and r₄ are exclusive rules because their conditions can not be both satisfied according to the following logic expression: (pipe.State=‘in’) ∩ (pipe.State=‘out’)=false. There is at most one of exclusive rules can be satisfied by the same database state. However [6 –9], implicitly approved that r₂ and r₄ are both satisfied by the same database state and eligible for execution when identifying whether they are commutative rules. r₂ and r₄ are located respectively in two different executive sequences which represent the operational reactions when oil flows into or out of the tank, but the direction of flux in pipe cannot both flows into and flows out of the tank at the same time. That is, at most one of such two different executive sequences can be executed at the same database state. Thus, the rule set R = {r₁, r₂, r₃, r₄, r₅} in Fig. 3 is really confluence: there is exact one final database state after R has been executed completely no matter which one of r₂ and r₄ is firstly chosen to execute.

4 Exclusive rules

Just like the switch-case structure in C or C++ which is used to express many operational options in a program, two or more rules are exclusive as they are used to react with many different cases. Such as Example 2, two groups of rules are designed respectively for the oil flowing into or out of the tank.

Definition 2. Let r_i and r_j be an arbitrary pair of unordered rules in a rule set R. r_i and r_j are mutual exclusive if an arbitrary executive sequence of R must not include r_j when it includes r_i, and vice versa.

In Definition 2, exclusive rules refine the meaning of unordered rules and will contribute to more precise confluence detection than Aiken et al. [6] (this can be seen from Example 2).

The complexity of rules process results in the complexity of the exclusive rule detection. As the Rule Commutativity detection in [6], a sufficient condition will be provided here to detect whether a pair of unordered rules are exclusive.

Using the method presented in [17, 18], we can construct the conditional formula for two rules to detect whether they are exclusive. In [17, 18], the predicates, concerned with non-updatable variables of a rule set, will be chosen from the conditions of all rules in an executive sequence and they form the conditional formula for such an executive sequence. Non-updatable variables of a rule set R must not be updated by any rule of R and it is intuitive that there must exist a rule which cannot be executed in an executive sequence Sq if the conditional formula for Sq is false. That is, there is at least a contradiction between the conditions of two rules in Sq and at least one of such two rules can not be satisfied during the rule process of Sq. For example, r₂ and r₄ in Example 2 are such two rules because pipe.State is a non-updatable variable of {r₁, r₂, r₃, r₄, r₅} and the conditions of {r₂, r₄} can not be both satisfied by the contradiction: (pipe.State=‘in’)∩(pipe.State=‘out’) = false.

Definition 3. A variable q is a non-updatable variable of a rule set R, if q appears in the condition of a rule in R but not in the action of any rule r such that r ∈ R or r ∉ R but r can be triggering reachable from R.

Theorem 2.Letr_iandr_jbe an arbitrary pair of unordered rules in a rule setR. Let formula(r_i) and formula(r_j) be the conditional formula e constructed respectively forr_iandr_jbased on all non-updatable variables ofR. If formula(r_i)∩formula(r_j)=false, r_iandr_jmust be mutual exclusive.

Proof. The conclusion can be proven by contradiction. Assuming that r_i and r_j are not mutual exclusive, then there must be an executive sequence of R which includes both r_i and r_j. Thus, the conditions of both r_i and r_j can be satisfied and they can be executed in the same executive sequence; that is, it holds that formula(r_i)∩formula(r_j)=true. This contradicts the precondition that formula(r_i) ∩ formula(r_j)=false. So the conclusion holds. ■

5 Confluence detection of rules without priorities

5.1 The inadequacy of the existing methods

Confluence Requirement in Defintion1 and Confluence Theorem in Theorem 1 are both presented in Aiken et al. [6] and they aim at a rule set with priority. If analyzing a rule set without priority as Baralis et al. [10], those techniques in [6 –9] will be no more effective.

The following corollaries are presented in [6] for summarizing the characteristics of a rule set with confluence.

Corollary 1.(Lemma 8. 8 of Aiken et al. [6].) IfRis found to be confluence andr_iandr_jare unordered rules inR, thenr_iandr_jcommute.

Corollary 2.(Lemma 8. 9 of Aiken et al. [6].) If R is found to be confluence andP = φ(i.e., there are no user-defined priorities between any rules in R), then every pair of rules inRcommutes.

Corollary 3.(Lemma 8. 10 of Aiken et al. [6].) IfRis found to be confluence andr_iandr_jinRare such thatr_imay triggerr_j(or vice-versa), thenr_iandr_jare ordered.

Obviously, Corollary 2 will help us in the design of a rule set with confluence. Unfortunately, an contradiction can be deduced when these corollaries are applied. Assuming that R is found to be confluence and P = φ and r_i and r_j in R such that r_i may trigger r_j, then r_i and r_j are found to be ordered through Corollary 3 and they are commutative according to Corollary 2. However, it can be deduced that r_i and r_j may be noncommutative according to the condition (1) of Lemma 1. Also, we can see that the rule set R in Example 2 is confluence and r₂ and r₄ are noncommutative although they are a pair of unordered rules. That is, Corollary 1 and Corollary 2 can not be validated when they are applied for rules in Example 2. Thus, how to detect the confluence of a rule set without user-defined priorities is pending and will be addressed in this paper.

5.2 The detection of unordered rules

Indeed, it is implied in [6] that any pair of rules without user-defined priorities between them are unordered rules; thus, Corollary 1 and Corollary 2 would be valid once the confluence is detected by Theorem 1. Howerver, it is can be seen from Corollary 3 that a pair of rules should be ordered if there are no user-defined priorities between them but one of them may trigger the other. So the detection of unordered rules is a critical issue for the confluence detection.

As mentioned as [11], a triggering graph implies all triggering relations of a rule set. Base on a triggering graph, the following theorem indicates the properties that should be satisfied by unordered rules in a rule set.

Theorem 3.For any distinct rules of a rule set, if any of the following conditions holds then they are unordered:

In the associated triggering graph, such rules that there are no incoming arcs; That is, such rules can not be triggered by any rule;

In the associated triggering graph, such rules that their incoming arcs are originated from the same rule; That is, such rules can be triggered by the same rule;

Letr₁andr₂be a pair of unordered rules. Ifr_iandr_j, are triggered respectively byr₁andr₂, such two rules that one is abstracted from {r₁, r_i} and the other is abstracted from {r₂, r_j};

Proof. It is intuitive that the executive order of any two rules in a rule set R is decided by their triggering relation. If there is no triggering relation between two rules, such two rules must be unordered as each of them need not be triggered by the other prior to itself.

For those rules that there are no incoming arcs in the associated triggering graph of R, each of them need not wait a rule of R to be triggered prior to it if it wants to be triggered. Thus, such rules must be unordered.

For those rules whose incoming arcs are originated from the same rule r, they will compose a set of conflict rules after r has been triggered and then r triggers them (refer to the rule process in the Section 1.2). As there are no user-defined priorities assigned for the rules of R, the rule process associated with R is indeterminate [11] and each of such rules can be firstly chosen at random for execution. Thus, such rules must be unordered.

Let r₁ and r₂ be a pair of unordered rules and r_i and r_j are triggered respectively by r₁ and r₂. So we consider r₁ and r₂ have been triggered at the same time and form a conflict set as {r₁, r₂}. Assuming that r₁ is chosen to execute prior to r₂, r₁ must be executed prior to r_j but r_i may be executed: i) prior to {r₂, r_j} if r_i has been immediately chosen to execute; ii) subsequent to r₂ or r_j if r_i has been deferred to execute; that is, {r_i, r₂} and {r_i, r_j} are unordered; Assuming that r₂ is chosen to execute prior to r₁, r₂ must be executed prior to r_i but r_j may be executed either prior to {r₁, r_i} or subsequent to r₁ or r_i, that is, {r_j, r₁} and {r_j, r_i} are unordered. That is, that r₁ and r₂ are unordered causes that there are no executive order between such two rules that one is abstracted from {r₁, r_i} and the other is abstracted from {r₂, r_j}. ■

5.3 Confluence analysis for a rule set without priorities

In Theorem 3, the case (3) is used for the derivation of all unordered rules based on the triggering relations originated from a pair of unordered rules found by the case (1) and the case (2). Based on Theorem 3, the following definition is presented for Confluence Requirement of a rule set without priority. If not special specified, it is should be reminded that unordered rules indicate those rules detected by the case (1) and the case (2) of Theorem 3 in the rear of this paper, while the case (3) of Theorem 3 can guarantee that the following definition will derive all pair of unordered rules and these unordered rules should be commute to guarantee the confluence of all rules.

Definition 4. (Confluence Requirement without Priorities) Consider any pair of unordered rules r_i and r_j in a rule set R such that R has no user-defined priorities. Let R₁ ⊆ R and R₂ ⊆ R be constructed by the following algorithm: $\begin{matrix} R_{1} \leftarrow {r_{i}} \\ R_{2} \leftarrow {r_{j}} \end{matrix}$ repeat until unchanged: $\begin{matrix} R_{1} \leftarrow R_{1} \cup {r \in Triggers (r_{1}) and r_{1} \in R_{1}} \\ R_{2} \leftarrow R_{2} \cup {r \in Triggers (r_{2}) and r_{2} \in R_{2}} \end{matrix}$

For every pair of rules r₁ ∈ R₁ and r₂ ∈ R₂, r₁ and r₂ must commute.

Theorem 4.(Confluence Theorem without Priorities) Suppose the Confluence Requirement without Priorities holds for a rule setRsuch thatRhas no user-defined priorities and there are no infinite paths in any execution graph forR. Then any execution graph forRhas exactly one final state, i.e., the rules inRare confluent.

Proof. The conclusion can be proven by contradiction. Assuming that the rules in R are not confluent, then there must exist two nonequivalent executive sequences denoted as Sq₁ and Sq₂. That is, Sq₁ can not be permuted to Sq₂ without affecting the final state through the commutation of some unordered rules in R, and vice versa.

Now suppose that there are two rules in Sq₁ which can not be commutative and cause Sq₁ can not be permuted to Sq₂. All rules in R are not assigned user-defined priorities, so the rule process for R is indeterminate [11]. Thus, Sq₁ and Sq₂ are obtained by two different schedules for the set of conflict rules during the rule process of R. Consequently, such two rules are in the set of conflict rules consisted of unordered rules that are all eligible for consideration at the same state. From the proof of Theorem 3, it is known that every pair of unordered rules in R must be commutative if the Confluence Requirement without Priorities holds for R. Thus, such two rules are unordered and commutative. This contradicts the above assumption. So the conclusion holds. ■

6 Confluence analysis for a rule set with exclusive rules

Based on Confluence Theorem without Priorities, next we want to determine whether the rule set with exclusive rules is confluent.

Theorem 5.Letr_iandr_jbe a pair of unordered rules in a rule setRand they are exclusive rules. If there is an executive sequence denoted asSq₁wherer_iis triggered with precedence overr_jas the form as {… r_i, r_j …} andSq₂is obtained by exchangingr_iandr_jinSq₁, thenSq₁andSq₂are equivalent with respect to the unique final state.

Proof. As r_i and r_j are exclusive rules, there is at most one of them can be eligible for execution in a state S. That is, there is no more than one of them whose condition can be satisfied with the state S. Suppose that r_i can be eligible for S but r_j can not, then r_i can be omitted from Sq₁ and Sq₂ without affecting the unique final state. Thus, Sq₁ takes the same form as Sq₂. So Sq₁ and Sq₂ are equivalent. The conclusion holds. ■

Definition 5. (Confluence Requirement with exclusive rules) Consider any pair of unordered rules r_i and r_j in a rule set R such that R has no user-defined priorities. If r_i and r_j are not exclusive rules, then let R₁ ⊆ R and R₂ ⊆ R be constructed by the following algorithm: $\begin{matrix} R_{1} \leftarrow {r_{i}} \\ R_{2} \leftarrow {r_{j}} \end{matrix}$ repeat until unchanged: $\begin{matrix} R_{1} \leftarrow R_{1} \cup {r \in Triggers (r_{1}) and r_{1} \in R_{1}} \\ R_{2} \leftarrow R_{2} \cup {r \in Triggers (r_{2}) and r_{2} \in R_{2}} \end{matrix}$

For every pair of rules r₁ ∈ R₁ and r₂ ∈ R₂, r₁ and r₂ must commute.

Theorem 6.(Confluence Theorem with exclusive rules) Suppose the Confluence Requirement with exclusive rules holds for a rule set R such that R has no user-defined priorities and there are no infinite paths in any execution graph for R. Then any execution graph for R has exactly one final state, i.e., the rules in R are confluent.

Proof. In Definition 5, r_i and r_j are a pair of unordered rules in R; if they are exclusive rules, then every pair of rules such as r₁ ∈ R₁ and r₂ ∈ R₂, r₁ and r₂ must be exclusive rules. To prove this, we suppose that r_i can be eligible for execution in a state S but r_j can not, then every rule r₁ in R₁ can be triggered by an executive sequence originated by r_i and every rule r₂ in R₂ can not be triggered as its original rule r_j can not be triggered. Thus, for every pair of rules r₁ ∈ R₁ and r₂ ∈ R₂, r₁ and r₂ must be exclusive rules. By Theorem 5, we know that two executive sequences are equivalent if they are obtained by exchanging two exclusive rules r_i and r_j. So every pair of rules r₁ ∈ R₁ and r₂ ∈ R₂ are not required for examining whether they are really commutative and they can be always regarded as the commutative rules except that r_i and r_j are not exclusive.

The conclusion can be proven by contradiction. Assuming that the rules in R are not confluent, then there must exist two nonequivalent executive sequences denoted as Sq₁ and Sq₂. That is, Sq₁ can not be permuted to Sq₂ without affecting the final state through the commutation of some unordered rules in R, and vice versa.

Now suppose that there are two rules in Sq₁ which can not be commutative and cause Sq₁ can not be permuted to Sq₂ by exchanging them. All rules in R are not assigned user-defined priorities, so the rule process for R is indeterminate [11]. Thus, Sq₁ and Sq₂ are obtained by two different schedules for the set of conflict rules during the rule process of R. Consequently, such two rules are in the set of conflict rules consisted of unordered rules that are all eligible for consideration at the same state. If the Confluence Requirement with exclusive rules holds for R, every pair of unordered rules in R is either exclusive or commutative. If such two rules are exclusive, then Sq₁ and Sq₂ are equivalent by Theorem 5 and this contradicts the above assumption that Sq₁ and Sq₂ are not equivalent; if such two rules are not exclusive, then they must be commutative by Definition 5 and this contradicts the above assumption. So the conclusion holds. ■

We define an algorithm as follows, called Confluence detection with exclusive rules, to detect the confluence of a rule set without user-defined priorities. Here, our algorithm adopts the following structures similar to the ones in Baralis [11]. Let R be an arbitrary active rule set such that R has no user-defined priorities, and let TG be its associated Triggering Graph; let Out (r_i) denote the endpoints of arcs originating from r_i in TG; also let r_i . T denote the counters of arcs incoming into r_i in TG. Finally, let L denote a list of rules.

At the beginning of preparing our algorithm on Table 2, we define a function on Table 1, called as Trigger _ Set (), which is used for computing the rule set R₁ and R₂ during the examination of Confluence Requirement with exclusive rules for R.

Complexity Analysis. Let m be the number of rules in R, and let n be the number of symbols in an analysis symbol table of the satisfiability algorithm [19]: the worst-case complexity of the algorithm is O (m⁵ + m⁴ * n²). To see this, consider firstly the construction of sets R₁ and R₂ for a given unordered rules r₁ and r₂. The total complexity of the construction is O (m³) [6]. Checking each pair of rules in R₁ and R₂ for commtativity takes complexity O (m²) [6]. Checking each pair of rules in R₁ and R₂ for exclusive rules takes complexity O (m² * n²) if the satisfiability algorithm presented in Urban [19] is adopted for testing the satisfiability of conditional triggering formulae (the number of vectors in Urban [19] corresponds to the number of pairs of rules in R₁ and R₂ with complexity O (m²)). For a given unordered rules r₁ and r₂ in R, the construction of sets R₁ and R₂ and checking each pair of rules in R₁ and R₂ for exclusive rules and commtativity take complexity O (m³ + m² + m² * n²). The above process in the algorithm must be executed for every unordered pair of rules in R, that is, it may occur O (m²) times [6], bringing the complexity of the entire analysis to O (m² * (m³ + m² + m² * n²)). The complexity becomes equivalent to O (m⁵ + m⁴ * n²).

Example 3. Consider again the rule set of Example 2 and its corresponding triggering graph as Fig. 3 using the algorithm 1. (1) The first class of unordered rules (i.e., the rules without incoming arcs) does not exist, that is, Q₁ = φ. (2) In Fig. 3, only r₁ has multi-outgoing arcs. That is, Out (r₁) = {r₂, r₄}. Then, Q₂ = {r₂, r₄}. As (pipe.State=‘in’)∩ (pipe.State=‘out’)=false, that is, formula(r₂)∩formula(r₄)=false, r₂ and r₄ are exclusive rules. (3) Finally, algorithm 1 terminates with returning back true. That is, the algorithm 1 determines the rule set of Example 2 is confluent as its Confluence Requirement with exclusive rules holds.

As v₁.State appears in both the conditions and the actions of r₂ and r₄, r₂ and r₄ are determined as noncommutative rules since the conditions (3) and (5) of Lemma 1 hold for them. That is, the existing methods [6 –9] determine the rule set of Example 2 is not confluent; but this conclusion contradicts the fact mentioned above.

7 Conclusions

We deduced a contradiction from the corollaries presented in Aiken et al. [6] when they summarized the characteristics of a rule set with confluence; thus, how to detect the confluence of a rule set without priorities is still pending. The concept of unordered rules is introduced in Aiken et al. [6], but how to detect a pair of unordered rules is still pending. And we found that the existing methods [6 –9] based on Rule Commutativity can not detect the confluence case if a rule set has exclusive rules and has no user-defined priority. To address these problems, this work proposes the concepts of Exclusive Rule and Confluence Requirement with exclusive rules based on the conditional formula of an executive sequence; and the proposed method provides more accurate analysis than the existing methods [6 –9]. The main question this paper leaves open is that the proposed method is not necessary but sufficient, though it can improve the quality of confluence analysis.

Schmolze [20] presented a formal definition of production rule redundancy and an algorithm for detecting redundant production rules; Tan [21] addressed when and how ECA rules determine to react to different kinds of events. In future, we would consider rule redundancy and composite events to refine our method.

Footnotes

Acknowledgments

This work was supported by the Research Foundation of Shanghai Science and Technology Commission under Grant 14391901400.

References

Bonifati

, Ceri

, and Paraboschi

, Active rules for XML. A new paradigm for e-services, VLDB Journal10(1) (2001), 39–47.

Mansour

, Dube

, and Wu

, AIM: An XML-based ECA Rule Language for Supporting a Framework for Managing Complex Information, Proceedings of International Symposium (RuleML 2007)2007, pp. 232–241.

Bae

, and Yu

Y.-W.

, Auto-Triggering of RFID-based Logistic Process in Inter-workflow Using Complex Event, Springer, pp, Dynamics in Logistics (2011), 329–339.

Behrends

, Fritzen

, May

, and Schenk

, Embedding event algebras and process for ECA rules for the semantic web, Fundamenta Informaticae82(3) (2008), 237–263.

Öztarak

, Akkaya

, and Yazici

, Providing Automated Actions in Wireless Multimedia Sensor Networks via Active Rules, Computer and Information Sciences II, Springer, 2012, pp. 185–190.

Aiken

, Hellerstein

, and Widom

, Static analysis techniques for predicting the behavior of active database rules, ACM Transactions on Database Systems20(1) (1995), 3–41.

Comai

, and Tanca

, Termination and confluence by rule prioritization, IEEE Transactions on Knowledge and Data Engineering15(2) (2003), 257–270.

Papamarkos

, Poulovassilis

, and Wood

P.T.

, Event-condition-action rules on RDF metadata in P2P environments, Computer Networks, Elsevier50(10) (2006), 1513–1532.

Bostan-Korpeoglu

, and Yazici

, A fuzzy Petri net model for intelligent databases, Data & Knowledge Engineering62 (2007), 219–247.

10.

Baralis

, Ceri

, et al.,Improved Rule Analysis by Means of Triggering and Activation Graphs, Improved Rule Analysis by Means of Triggering and Activation Graphs, Proceedings of Int’l Second Workshop Rules in Database Systems (RIDS), Athens, Greence, Lecture Notes in Computer Science, Volume 985, 1995, pp. 163–181.

11.

Baralis

, Ceri

, et al.,Compile-time and runtime analysis of active behaviors, IEEE Transactions on Knowledge and Data Engineering10(3) (1998), 353–370.

12.

Xiong

, Zhao

, Huang

, He

, and Wang

, Active rules termination analysis based on activation path and enhanced formula, International Journal of Intelligent Information and Database Systems7(1) (2013), 53–78.

13.

Wei

, Ye

, Zhen

, and Qiu-Yun

, Termination analysis for active rule set based on triggering path, Chinese Journal of Computers35(1) (2012), 65–75.

14.

Latifa

, and Hafida

, The priority of rules and the termination analysis using Petri nets, The International Arab Journal of Information Technology4(2) (2007), 177–183.

15.

Hao

, and Xiong

, An efficient algorithm about computing an irreducible rule set in active database, Journal of Computer Rearch and Development43(2) (2006), 281–287.

16.

Wang

, Zhang

, Dou

, and Hu

, Fuzzy colored time Petri net and termination analysis for fuzzy Event-Condition-Action rules, Information Sciences232 (2013), 225–240.

17.

Lee

S.Y.

, and Ling

T.W.

, Refined Termination Decision in Active Databases, Proceedings of Int’l Conf On Database and Expert Systems Applications (DEXA), Toulouse, France, 1997.

18.

Lee

S.Y.

, and Ling

T.W.

, A path removing technique for detecting trigger termination, Proceedings of Int’l Conf On Extended Database Technology (EDBT), Valencia, Spain, 1998.

19.

Urban

S.D.

, Tschudi

M.K.

, Dietrich

S.W.

, and Karadimce

A.P.

, Active rule termination analysis: An implementation and evaluation of the refined triggering graph method, Journal of Intelligent Information Systems12(1) (1999), 27–60.

20.

Schmolze

J.G.

, and Snyder

, Detecting redundancy among production rules using term rewrite semantics, Knowledge-Based Systems12(1-2) (1999), 3–11.

21.

Tan

C.W.

, and Goh

, Implementing ECA rules in an active database, Knowledge-Based Systems12(4) (1999), 137–144.