Doctor of Philosophy
Department of Computer Science
Kim, Chae-Kyu, Hybrid concurrency control for prioritized rules in active database systems, Doctor of Philosophy thesis, Department of Computer Science, University of Wollongong, 1997. http://ro.uow.edu.au/theses/1296
In active database systems, rule processing occurs when an external transaction generates events. Certain rules are initially triggered by the events, and they are executed automatically when certain conditions are satisfied. Their execution can trigger other rules or the same rules, and so on-conceivably resulting in a finite set of triggered rules. The seemingly unpredictable activation of rules, however, produces two main problems: termination and confluence problems.
So far, most research efforts to solve these problems have concentrated on compiletime rule analysis. In compile-time rule analysis, it is difficult to determine which rules will be executed and what events will occur. It is therefore necessary to solve those problems at run-time. This thesis introduces a new transaction management protocol that allows not only deterministic execution but also terminated execution of rules in active database systems.
To solve the confluence problem, a strategy is introduced that eliminates the situation where different executions of rules in the finite set produce different results. This strategy is based on an assumption that there should only be one execution semantic for a given system of rules in the finite set. A unique execution semantic can be easily enforced by associating with each rule a priority that determines a global execution order. A property that execution of rules in the finite set is equivalent to execution of respective database transactions suggests a solution based on one of the transaction management techniques. The transaction management protocol enforces serializable executions of rules such that the respective serial execution order is consistent with an order determined by the rule priorities.
To solve the termination problem, this thesis uses a directed graph called a rooted graph. The rooted graph has a set of ordered pairs, called edges, representing the trigger relationship between two rules. A n infinite cyclic execution is detected when the resulting rooted graph contains a cycle.
This thesis suggests a solution to the question: what should be done when a transaction attempts to access a data object in a mode that has the potential to violate a given serial execution order? The solution is to replicate both data and processes. Replication of data is a well known technique that requires a multiversion concurrency control mechanism. Replication of process is achieved by transaction cloning.
This thesis proposes two hybrid approaches to the construction of concurrency control algorithms for transactions in active database systems.
1. H(n,k) concurrency control algorithms for external transactions in active database systems.
2. H(l,m) concurrency control algorithms for respective transactions of rules in the finite set.
The parameter n of H(n,k) determines the acceptable size of cascading abort of external transactions and the parameter k determines the total number of external transactions that execute concurrently with a particular external transaction. The parameter I of H(l,m) determines the maximum number of clone transactions of a rule transaction and the parameter m determines the maximum probability that the database state on which a command is executed is changed in the future by other commands.
The two hybrid approaches have the ability to dynamically adjust the behaviour of concurrency control algorithms to changing environmental parameters. It is proved that for extreme values of parameters:
- as far as the concurrency control of external transactions is concerned, the H(n,k) algorithm reduces itself either to strict two-phase locking algorithm or serialization graph testing.
- as far as the concurrency control of respective transactions of rules is concerned, the H(l,m) algorithm reduces itself either to altruistic locking approach or to serialization graph testing.