I would like to thank my supervisor, Professor T.H. Merrett, for his support and advice throughout the period of my studies at McGill. Also I would like to thank Professor Luc Devroy, Director, School of Computer Science, for his financial support.

I would also like to thank the following Aldat team members, Heping Shang and Xiaoyan Zhao, who provided much assistance and advice while I was trying to untangle some of the Relix code. Rebecca Lui, whom I assisted for a while developing procedures in Relix. Also my thanks goes to all other members of the Aldat team. A special thanks goes to my friend Ramzi Baroody, who proof read a major part of this thesis, and to Bernard Desruisseaux and Pung Hay, for their help in the translation of the abstract to French.

A special thanks goes to my mother and father, who encouraged and urged me to continue my studies.

Last but not least a special thanks goes to my wife to be Rana, to whom I dedicate this thesis, her support and encouragement were a driving force for me.

This thesis introduces active database concepts to a relational database system. Event handlers are introduced as user defined procedures. An event is the procedure call by the system, triggered in our case by an update statement.

Event handlers for the Relix (Relational database on UNIX) update statement have been implemented. These event handlers are of two types: the first type is that which runs before an update statement. The second type runs after an update statement. Also, event handlers have states. An event handler can be either active or inactive. Event handlers are executed when they are in the active state.

Event handlers have the property of being "one-to-many", i.e., for a single event more than one event handler can be defined. Another property is non-determinism, i.e., event handlers are executed with no pre-specified order.

In this thesis we present the design and implementation of event handlers in Relix. The mechanism that we introduced in Relix is equivalent to the EA model.

Cette thèse introduit les concepts de base de données active à un système de base de données relationnelles. Les gestionnaires d’événements sont introduits comme des procédures définies par l’utilisateur. Un événement est un appel de procédure par le système, déclenché dans notre cas par un énoncé de mise à jour.

Les gestionnaires d’événements pour Relix (système de base de données relationnelle pour UNIX) mettent à jour les énocés qui ont été implémentés. Il existe deux types de gestionnaires d’événements, ceux qui s’exécutent avant un énonce de mise à jour et ceux qui s’exécutent après. D’autre part, les gestionnaires d’événements ont des états. Les événements peuvent être actifs ou inactifs. Les gestionnaires d’événements sont exécutés lorsqu’ils sont dans l’état actif.

Les gestionnaires d’événements la propriété d’être un-à-plusieurs, c’est-à-dire pour un seul événement plusieurs gestionnaires d’événements peuvent être defini. Une autre propriété est le non-déterminisme, c’est-à-dire que les gestionnaires sont exécutes dans un ordre non prédéterminé.

Dans cette thèse nous présentons la conception et l’implémentation des gestionnaires d’événements dans Relix. Le mécanisme que nous introduisons dans Relix est équivalent au modèle EA.

The work presented in this thesis deals with transforming a relational database system from a passive to an active one. Event programming is the basis of the work presented in this thesis. First we will introduce event programming and then move on to discuss event programming in database systems. In particular we will discuss active databases and trends in active database research. Finally we will present the thesis outline.

In conventional programming, a program is defined as being inert [MS88]. An inert program does nothing until it is invoked. Once invoked, the program performs its task and then returns to its inert state. Another approach to programming is event-driven programming. In this approach, programs can be invoked by a variety of ways such as a mouse click, a keyboard stroke, etc. .

In event-driven programming, the programmer specifies an event and the action to be performed when this event occurs. In what follows, we will refer to the action as the event handler. The particular programming language used will have a facility to monitor the running program, detect occurrence of events, and then perform the specified event handler. The event handler performed in response to an event can be expressed as a procedure. Let us consider the following example:

Suppose that we have a GUI with 2 buttons: START and EXIT,

and that we define the following event handlers:

procedure mouse.leftbutton.down.START

begin

print ("hello")

return

end

procedure mouse.leftbutton.down.EXIT

begin

halt

end

In Visual Basic [SK+94] these event handlers would be defined as sub routines in the following way:

Sub StartButton_Click ()

messageLabel.Caption = "hello"

End Sub

where StartButton is the name given to the button labelled START.

Sub ExitButton_Click ()

Stop

End Sub

where ExitButton is the name given to the button labelled EXIT.

Now if the user presses the left button of the mouse down over the START button, then the procedure mouse.leftbutton.down.START will be invoked and executed. Similarly, if the left mouse button is pressed down over the EXIT button, then the procedure mouse.leftbutton.down.EXIT will be invoked and executed.

Currently, a lot of object-oriented programming environments (Delphi, Visual Basic, HyperTalk) have event-programming as an essential component. In Delphi [DEL95], events are defined to be either user actions or internal system occurrences which the application can recognize. The part which specifies how to respond to this event is called an event-handler, and event-handlers are defined to be procedures. An event is responded to by calling its event-handler(s). Thus a response to an event is basically a procedure call.

How does event programming work?

In an event-driven programming language, the programmer will define the events and their associated event handlers. A user of an event-driven environment will cause events to occur and the system will respond to these events. A response to the events is performed by invoking all those event handlers which are associated with the occurring event. These event handlers are invoked by system generated calls. Thus we can consider an event handler to be a system generated procedure call.

In the next section we will introduce the concept of event-driven programming in relational database systems.

Conventional database systems work by receiving requests and processing these requests. These requests can be received either from an interactive interface or through application programs. Such systems lack the capability to respond to happenings of interest without user intervention. This has prompted research in the field of active databases. Active database systems stress the point that a body of information is dynamic and should respond in non-trivial ways to the user [MOR83]. An active database system is a system which is capable of automatically detecting the occurrence of user-defined events and initiating the appropriate response. One can say that active databases function in both request-driven and event-driven modes, whereas a conventional database functions only in request-driven mode [MUE94].

The basic idea of active databases is triggers. A trigger is a construct which initiates reactions of an active database pre-defined situations. A situation can be viewed as a combination of an event detected by the database and state description. A state description is a predicate defined over elements of the database schema and is evaluated for a particular information base at event time [MUE94].

In what follows we will discuss, in brief, methods used to express triggers (rules) in different active database systems.

POSTGRES supports a query language, POSTQUEL, which allows commands to be modified to become rules [SR86, SHP88]. Commands are modified by tagging them with three special modifiers. These modifiers are "always", "refuse", and "one-time". Consider the following POSTQUEL command, which sets the salary of Mike to the salary of Bill:

replace EMP (salary = E.salary) using E in EMP

where EMP.name = "Mike" and E.name = "Bill"

this command can be tagged with the keyword "always" and thus becomes a rule.

always replace EMP (salary = E.salary) using E in EMP

where EMP.name = "Mike" and E.name = "Bill"

This rule ensures that any user retrieving the salary of Mike will see a value equivalent to Bill’s salary. POSTGRES implements the above rule by delaying its evaluation until a user requests the salary of Mike. Rules in POSTGRES utilize a form of lazy evaluation. Similarly, commands can be tagged with the "refuse" and "one-time" modifiers. A command tagged with a "refuse" modifier implies that such a command should never be run. A command tagged with a "One-time" implies that the command is to run only once.

The HiPAC project [HLM88, CHA93], uses the concept of Event-Condition-Action (ECA) rules to express triggers. In the ECA model, a rule consists of a triggering event, a condition to be evaluated, and an action to be executed if the condition evaluates to true. ECA rules have a number of coupling modes which specify when the condition is evaluated relative to the triggering event, and when the action is executed relative to condition evaluation. ECA rules will be discussed in more detail in a later section.

A variation of ECA rules is EA rules [GJS92b]. In EA rules, the condition is part of the event specification. EA rules have a single coupling mode, but are capable of having the coupling modes described in the ECA model. EA rules will be presented in more detail in the following section.

The REFLEX system proposes extending the ECA model to cover omissions in the standard ECA model [NI94]. The Extended-ECA (EECA) model has the possibility of representing multiple actions and fail-action clauses for a single event. In addition the model presents looser coupling modes than those suggested in the ECA model.

Yet another approach is by extending a deductive database language, RDL1, by rules which react to events [SKM92]. In RDL1, triggering events are not provided by the user but instead are derived from rules. A single coupling mode is defined in this rule system. Either a rule is evaluated when the triggering event occurs (immediate), or evaluated when the transaction containing the triggering event reaches a commit point (deferred). Consider the following example which defines a referential integrity constraint between relations EMP and DEPT:

module ref_constraint_emp_dept;

base EMP (name string, emp_no integer, dept_no integer, salary integer);

DEPT (mgr_no integer, dept_no integer);

rules

r is DEFERRED // indicating deferred coupling mode//

if EMP (x) and not exists y in DEPT (x.dept_no = y.dept_no) then - EMP(x)

end module

where

the "- " before EMP(x) implies delete from relation EMP.

In the above rule, tuple variable x ranges over relation EMP, and y is a quantified variable ranging over relation DEPT. Intuitively, this module defines an active rule which is activated whenever the EMP or DEPT relations are modified. Here, EMP and DEPT always refer to the current values of the relations. Thus, if an employee with no dept_no is inserted, it will be rejected. If a department which has employees working in it is deleted then all its employees will be deleted. Here, the triggering event is not specified by the user, but rather it is derived from the rule conditions.

Alert is an extension architecture designed for transforming a passive SQL database system into an active database system [SPM91]. Alert introduces active queries to express triggers and unifies them with passive queries so that active queries may be expressed in SQL with minimal additions to the language. Alert rules are production rules which are fired when their conditions are satisfied. Syntactically, Alert rules are named active queries. They are defined by specifying rule conditions in the SQL FROM and WHERE clauses, and by specifying the rule actions in the SELECT clause. The SQL view mechanism is used for naming the rules. A rule will have the following form:

Create rule <RULE_NAME>

SELECT <SELECT_CLAUSE>

FROM <TABLE>

WHERE <CONDITION>

Since a rule definition is an SQL view, then it can be referred to in any other query.

To activate and deactivate rules, two new SQL commands are introduced:

Activate < RULE_NAME>,

Transcoupling = Same | Separate,

Timecoupling = Sync | Async,

Assertion = Immediate | Deferred

The Activate command returns a unique rule_id for each rule activation. This rule_id is used in the Deactivate command:

Deactivate <rule_id>

Transcoupling indicates if the triggered action is to be performed in the triggering transaction (Same), or as a separate transaction (Separate).

Timecoupling indicates if the triggered action is executed, after which control is returned to the triggering transaction (Synchronous), or if the triggered action is executed in parallel to the triggering transaction (Asynchronous).

Assertion indicates if the rule is triggered as soon as the condition is satisfied ( Immediate), or is to be executed in a special region of the triggering transaction indicated by Begin_assert and End_assert (Deferred).

Finally, the Heraclitus [HJ91, GH+93] system supports a type called delta (delayed update). The value of a delta represent proposed insertions into, and deletions from, the values of relation variables. In Heraclitus, a rule can be represented as a function which takes deltas as input and produces deltas, representing contributed modifications, as output. During rule firing, the original database state remains unchanged, and a virtual state is represented and manipulated using deltas. One of the main objectives of the Heraclitus system is the ability to represent different execution models of active databases. The system can model transaction boundary rule firing, interleaved rule firing, concurrent rule firing and other execution models for active databases.

Before proceeding any further we will give formal definitions of the event, condition, and action used in the ECA model [MD89] and the EA model [GJS92b]:

An event is the occurrence of pre-defined state which triggers the rule and causes the system to evaluate the condition. An event can be defined as having typed formal parameters. These formal parameters are mapped to actual parameters when the event is detected. Events can be either a single primitive event or a combination of primitive events. Primitive events can be one of the following: database operations (data definition, data manipulation, or transaction control), temporal events (absolute, relative, or periodic), or external notification (application defined events). These primitive events can be combined using disjunction and sequence operators to specify composite events. Finally, an event specification can be omitted from the rule definition. In this case the event specification can be derived from the condition.

A condition is a collection of queries which are evaluated when the associated event is triggered. A condition is formed of queries expressed in a data manipulation language. These queries can refer to the arguments in the associated event. The condition is considered to be satisfied if the queries return non-empty results. The results of the queries can be passed to the action along with the arguments of the associated event.

An action is a sequence of operations which are executed when the condition of the triggering event is satisfied. These operations can be either database operations or requests to application programs.

Another two concepts that we will define before proceeding are: transactions and processes. The reason for defining these two concepts is that they are basic for the execution models is the ECA and EA models.

A transaction can be considered as a collection of actions with the following properties [GR93]:

Atomicity : the changes a transaction performs are atomic; either all happen or none happen.

Consistency : a transaction is a correct transformation of the state of the database. The actions taken as a group do not violate any integrity constraints associated with the state.

Isolation : although transactions execute concurrently, it appears to each transaction, T, that other transactions execute either before T or after T, but not both.

Durability : Once a transaction completes successfully ( commits), its changes to the state survive failures.

A process is a virtual processor [GR93]. It has an address space that contains the program the process is executing and the memory space the process reads and writes. processes provide an ability to execute programs in parallel. They also provide a way of structuring computations into independent execution streams. Also they provide a protection entity. Thus processes provide a form of fault containment in case a program fails.

Processes are building blocks for transactions, but the two concepts are orthogonal. Parts of a transaction can be executed by many processes, and a process can execute many different transactions over time [GR93].

In the following sections we will present the EA and ECA models in more detail. Then we will present a comparison, between the two models, in which we show how transactions and processes reflect on each model.

The work that led to the development of the EA model focused on event specification in active database systems [GJS92a, GJS92b]. The EA model was integrated in O++, the database programming language for the Ode object database developed by AT&T Bell Labs [AG89, GJ91]. The EA model constructs a formal model and a language for specifying and detecting composite events. The language is equivalent, in terms of expressive power, to regular expressions over strings of logical events. The language differs from regular expressions in that it focuses on sequences and sub-sequences, rather than on strings and sub-strings. Arbitrary composite event specifications can be compiled into finite automata, thereby rendering event detection efficient.

Triggers in O++ are defined as follows:

class name {

. . .

trigger :

trigger_list

. . .

};

where trigger_list is a list of triggers each specified as follows:

trigger_name(parameters) : [perpetual] event ==> trigger_action

where

trigger_action is any O++ statement block and perpetual means that once the trigger is activated it remains active forever unless explicitly deactivated.

In an object-oriented database, events are related to actions which happen to objects and the state of the object. Events happen at a specific point in time. There are three types of events in the EA model [GJS92b]: basic events, logical events, and composite events . Each of these types will be discussed next.

Basic Events

Basic events are considered to be the starting point of any event specification system. In Ode, the basic events are:

1. Object State Events

- Immediately after an object is created.

- Immediately before an object is deleted.

- Immediately before or after an object is updated, read, or accessed through a public member function.

2. Method Execution Events

Immediately before or after the specified member function is applied to an object.

3. Time Events

- at time_specification

- every time_period

- after time_period

4. Transaction Events

- Immediately after a transaction begins.

- Immediately before a transaction attempts to commit.

- Immediately after a transaction commits.

- Immediately before a transaction aborts.

- Immediately after a transaction aborts.

The following O++ keywords in conjunction with before and after are used to specify some basic events:

• create : object creation
• delete : object deletion
• update : object update
• read : object read
• access : object access
• tbegin : transaction begin
• tcomplete : execution of the transaction code is complete but the transaction has not attempted to commit.
• tcommit : transaction commit
• tabort : transaction abort

e.g.

the event

after read

specifies an event which occurs immediately after the execution of a public member function which accesses an object for reading only. And the event

before tcomplete

specifies an event which occurs just before a transaction attempts to commit. The event

before tcommit

is not allowed because you cannot be sure that a transaction is going to commit until it actually commits. The event

after Withdraw (Item I, int q)

is an event specifying an event after the execution of the function Withdraw. Formal parameters can be used to distinguish between overloaded function with the same name belonging to the same class.

Logical Events

In Ode every basic event is a logical event. In addition a basic event qualified with a mask is a logical event. A mask is a predicate which is used to hide the occurrence of an event. Consider the event:

after Withdraw (Item i, int q) && q > 1000

This describes a logical event representing a withdrawal of item i greater than 1000. Predicates associated with a logical event may use the parameters of the basic event being masked.

Composite Events

Using logical operators and event specification operators logical events can be combined to form composite events. Basic and logical events occur instantaneously at specific points in time. However, a composite event is said to occur at the point of occurrence of the last logical event which was needed to make it happen.

Composite events can be masked with a predicate to form composite logical events. A composite event has no parameters even if the basic events forming it have. Below we will present the BNF which summarizes the event composition mechanism in O++ :

logical-composite-event = composite-event [&& mask]

composite-event = logical-event

| (composite-event)

| composite-event & composite-event

| composite-event | composite-event

| !composite-event

| relative(composite-event-list)

| relative+(composite-event)

| relative const-integer-expression(composite-event)

| prior(composite-event-list)

| prior const-integer-expression (composite-event)

| composite-event ; composite-event

| sequence (composite-event-list)

| sequence const-integer-expression (composite-event)

| choose const-integer-expression (composite-event)

| every const-integer-expression (composite-event)

| fa (composite-event, composite-event, composite-event)

| faAbs (composite-event, composite-event, composite-event)

composite-event-list = composite-event{, composite-event}

logical-event = basic-event [&& mask]

where

mask is a boolean valued expression,

const-integer-expression is an expression which can be computed at compile time,

the symbol | denotes union,

the symbol & denotes intersection,

the symbol + denotes infinite repetition

e.g., relative+(E) = relative(E) | relative(E,E) | relative (E,E,E) | ...

&& denotes logical conjunction of O++ masks, and

basic-event is one of the events listed above.

The keywords relative, prior, sequence, choose, every, fa, and faAbs are event composition operators, which are discussed in the next section.

In this section, we will present event combinators defined in the EA model. First we will define the concept of event history introduced in the EA model. As define by [GJS92a], an event history, or history, is a finite set of event occurrences in which no two event occurrences have the same event identifier (event identifier, eid, is used to define a total ordering on event occurrences). When the set is empty, the history is referred to as null history. The event occurrences in a history are called points. A special logical event start occurs at the beginning of the system history. Its eid is less than all other event occurrences eid’s.

In the following examples, all events referred to are composite events.

relative (E, F) implies that the last logical event of E occurs before the first logical event in F. The relative operator takes any number of arguments. relative (E) means E.

prior (E, F) implies that E occurs before F, i.e., last logical event of E occurs before the last logical event of F. The prior operator takes any number of arguments. prior(E) means E.

prior (E, F, G) = prior ( prior (E, F), G)

sequence (E₁, E₂, ..., E_n) implies that event E_i occurs immediately following event E_i-1 (at the next logical event), 2 £ i £ n. For example,

sequence ( after tbegin, before access, after access, before tcomplete)

describes a transaction attempting to commit after accessing an object, and causing no other events to be posted to the object.

prior+(E) and sequence+(E) are both equivalent to event E.

In addition to infinite repetition using the ‘+’ modifier, limited repetition is obtained by using a constant integer as on argument to the above operators. For example :

relative n (after E)

implies the composite event which consists of the nth and any subsequent "after E" events.

choose n (E) is used to specify which occurrence of an event is to be selected. For example,

choose n (after tcommit)

is posted by the commit of the nth transaction.

every n (E) is used to specify events which occur periodically. For example ,

every n (after tcommit)

is posted by the commit of multiple of n transactions. If n = 3, then the event is posted by the 3^rd transaction, 6^th transaction, 9^th transaction,... .

fa ( E, F, G) (firstAfter) is defined as:

the first occurrence of event F (at some logical event p) relative to an event E, with no intervening event G relative to E taking place prior to the occurrence of the logical event p. For example,

fa ( after tbegin, prior ( after update, after tcommit), (after tcommit | after tabort))

specifies the commit of a transaction which updated an object, since there are no intervening aborts or commits after the tbegin.

faAbs (E, F, G) (firstAfter Absolute) is defined as:

the first occurrence of event F ( at some logical event p) relative to an event E, with no intervening event G relative to the whole history taking place prior to logical event p.

The difference between fa and faAbs is that G is defined relative to E in fa, and relative to the beginning of the history in faAbs.

Now we will present an example of the O++ specification of triggers [GJS92b]. Consider we have an object type, StockRoom, which track a number of items. Type StockRoom is defined as:

#define day_begin at time (HR=9)

#define day_end at time (HR=17)

#define 5th_large_Wthd choose 5 (after withdraw(i,q) && q > 100)

class StockRoom {

. . .

Item items[max];

int n;

public:

StockRoom ();

. . .

void deposit (Item i, int q);

void withdraw (Item i, int q);

int authorized (UserId);

void log ();

void order (Item i);

void print_log ();

void reorder (Item i);

void report ();

void summary ();

UserId user();

void update_average();

trigger:

trigger_one : perpetual before withdraw && !authorized(user()) ==> tabort;

trigger_two : after withdraw(i,q) && i.balance<reorder(i) ==> order(i);

trigger_three : perpetual day_end ==> summary;

trigger_four : perpetual relative (day_begin,prior ( choose 5 ( after tcommit) , after tcommit) & !prior (day_begin, after tcommit)) ==> report();

trigger_five : perpetual every 5 (after access) ==> update_average();

trigger_six : perpetual after withdraw( i, q) && q > 100 ==> log();

trigger_seven : perpetual fa (day_begin, 5th_large_Wthd, day_begin) ==> summary();

trigger_eight : perpetual sequence (after deposit, before withdraw, after withdraw) ==> print_log();

};

trigger_two is not defined to be a perpetual trigger which means that after it is fired it should be activated again. While all other triggers do not have to be activated after they are fired because they remain active.

Some of the triggers defined above are:

trigger_one : an item can be withdrawn only by authorized users, otherwise the transaction is aborted.

trigger_three : at the end of each day, print a summary.

trigger_four : every transaction after the 5^th transaction within the same day is to be reported.

trigger_five : after every 5 operations on an object, the average is to be updated.

trigger_seven : after the 5th large withdraw in a day, print a summary.

trigger_eight : print the log when a deposit is immediately followed by a withdrawal.

All triggers must be activated explicitly. This activation can be done in the constructor part of the class.

As mentioned before, since logical events can be expressed as a regular expression, then their occurrence can be detected using a finite automata. An automaton can be defined for each event. This automaton reaches its final state whenever the event occurs. The automaton takes as input the sequence of logical events which constitute the event history for the object which the automaton is associated with.

Events are monitored in the following way:

whenever a basic event is posted to an object, the active triggers are checked to determine whether or not logical events have occurred. If a logical event has occurred, then for each active trigger which satisfies the occurring logical event, move the automaton to the next state. If any of the automatons reaches a final state, all triggered events which occurred are determined and fired. In case multiple triggers are fired, the EA model does not specify an order of firing, but it mentions that the firing is implementation dependent.

The action associated with a trigger is executed immediately in the same transaction which detected the triggering event. But two special cases must be considered here : after tabort and after tcommit. Here the transaction responsible for these two events has finished just prior to the events occurring. Hence, these events must be posted by a special system transaction. If these events lead to the firing of a trigger, then the action is executed in the same system transaction.

One of the important properties of a transaction is atomicity, i.e., either the transaction commits and all its effects are reflected in the database or it is aborted and none of its effects are in the database. The EA model poses a question on whether logical events which correspond to the activity of an aborted transaction are to be viewed as part of the event history. The model suggests that the answer to the question can be either yes or no. A true history contains operations on behalf of aborted transactions which may be useful in dynamically modifying system parameters. For example, if the ratio of aborts to commits exceeds q, then reduce the number of concurrent transactions allowed. On the other hand, a history comprised of actions on behalf of committed transactions might be desirable. For example, at the object level one would like to see the trail of real actions and not ones which were undone.

To implement committed history, the event monitoring automata state is considered as part of the object data structure and hence restored correctly upon abort. The true history is implemented using an automata whose state is not part of the object and hence not restored upon abort.

The EA model produced an event specification system which folds the condition part of the trigger in the event part, resulting in a model with one kind of coupling. But different coupling modes as those described by the ECA model can be achieved by the EA model. We will present this feature of the EA model in a later section.

ECA rules were proposed as part of the knowledge model in the HiPAC project [ DAY88, DB+88, MD89, RCB89, DHL90]. ECA semantics are relatively easy and straightforward: when an event occurs, the associated condition is evaluated. If the condition evaluates to true, the action is executed. Using ECA rules integrity constraints, alerters, access constraints, derived data and other database system features can be represented. In the following subsections we will discuss ECA rule attributes, operations, and architectural implications.

ECA rules have the following attributes:

Event, Condition, Action (as defined in section 1.2) and

E-C coupling is the specification of when the condition is evaluated relative to the transaction in which the triggering event occurs. E-C coupling is a relationship between the triggering event and the condition evaluation relative to transaction boundaries. There exist four possible coupling modes:

immediate : when the triggering event occurs, the condition is evaluated immediately in the same transaction, preempting (suspending) the remaining steps of the transaction.

deferred : when the triggering event occurs, the condition is evaluated in the same transaction but after it terminates.

separate - independent : when the triggering event occurs, the condition is evaluated in a separate transaction whose commit is independent of the commit of the transaction which spawn it.

separate - dependent : when the triggering event occurs, the condition is evaluated in a separate transaction whose commit is dependent (commits if and only if the transaction spawning it commits) on the commit of the transaction which spawn it .

C-A coupling is the specification of when the action is executed relative to the transaction in which the condition evaluation occurs. C-A coupling is a relationship between the evaluation of the condition and the execution of the action relative to transaction boundaries. There exist four possible coupling modes:

immediate : when the condition is evaluated, the action is executed immediately in the same transaction, preempting the remaining steps of the transaction.

deferred : when the condition is evaluated, the action is executed in the same transaction but after it terminates.

separate - independent : when the condition is evaluated, the action is executed in a separate transaction whose commit is independent of the commit of the transaction which spawn it.

separate - dependent : when the condition is evaluated, the action is executed in a separate transaction whose commit is dependent on the commit of the transaction which spawn it.

Defining a rule in the ECA model involves the following:

1. defining the event which triggers the rule, the condition to be evaluated when the triggering event is detected, and the action to be executed if the condition is satisfied.

2. the coupling mode of event detection and condition evaluation relative to the triggering event and its process boundaries.

3. the coupling mode of condition evaluation and action execution relative to the condition evaluation and its process boundaries.

4. whether separate triggered processes, if any, are to be processed as independent processes or as effects of the triggering process.

A transaction may contain any number of nested transactions [MOS85, GR93]. A nested transaction is fully contained within another transaction (its parent). A nested transaction can have as its parent either another nested transaction or a top level transaction. Also a single transaction can have more than one transaction, and sibling transactions can execute concurrently. While sibling transactions are executing, the parent transaction is suspended. A nested transaction may be aborted without causing its parent transaction to abort. The parent transaction can either go on with another computation or create another transaction to retry the aborted computation.

Top level transactions are atomic, serializable, and permanent. Nested transactions are atomic. When executing a nested transaction, its effects do not become permanent until it and all its ancestors commit through a top level transaction. Finally when a transaction aborts, its effects and the effects of all its descendants are ignored.

In the HiPAC project [HLM88, DHL90, DHL91], the nested transaction model was extended to model rule execution. In the HiPAC execution model, when a rule is executed, it is executed as a nested transaction of the transaction in which the rule was triggered. A rule is executed in the following manner: when a triggering event occurs, a nested transaction to evaluate the condition of the rule is created. If this nested transaction commits, then a new nested transaction to execute the action is created.

The extension of the nested transaction model is done by allowing the creation of three more types of nested transactions:

• deferred nested transaction : the execution of this nested transaction is delayed until the end of the user’s top transaction.
• nested top transactions : a nested top transaction can be created inside another transaction; such a transaction, unlike nested transactions, has no special privileges relative to its parent (e.g. can not read an object modified by its parent). The commit of a nested top transaction is not related to a commit by its parent but rather independent.
• causally-dependent-top-transaction ( nested CD top transaction) : a nested CD top transaction differs from a nested top transaction in which is commits only if its parent commits through a top transaction. Also, aborting a nested CD top transaction will have no effect on its parent.

Now let us consider the following:

An event E occurs in transaction T, and E is the triggering event for a rule with condition C and an action A. If condition C is satisfied, action A will be executed. In addition, action A does not have to be executed at the same point where C is evaluated. C can be evaluated immediately after the triggering event, while A can be executed in a separate transaction. The condition and action parts are considered separately as long as they follow the constraint: an action cannot be executed before condition evaluation. With this constraint the following coupling modes arise:

1. evaluate C and execute A immediately when E occurs and before the next operation in T ( immediate - immediate).

2. evaluate C immediately when E occurs and execute A after the last operation in T and before T commits ( immediate - deferred).

3. evaluate C and execute A after the last operation in T and before T commits (deferred - deferred).

4. evaluate C immediately when E occurs and execute A in a separate transaction T¢ (immediate - separate).

5. evaluate C after the last operation in T and before T commits, and execute A in a separate transaction T¢ ( deferred - separate).

6. evaluate C and execute A in a separate transaction T¢ ( separate - immediate).

7. evaluate C in one separate transaction T¢ and execute A in another separate transaction T¢ ¢ (separate - separate).

note : separate can be either "separate independent" or "separate dependent".

The extended nested transaction model was selected to represent the execution model in the HiPAC project for the following reasons:

1. its structure accommodates nicely the hierarchical relation between the triggering transaction and the triggered activity.

2. it allows a set of rules to run concurrently within a transaction.

3. it supports the modularity property of rule execution.

examples:

Event Register_Course (course C, student S)

Condition course_current_capacity (course C) < course_max_capacity(course C)

Action update_course (course C)

E-C coupling immediate

C-A coupling immediate

In this example a student wishes to register for a course C. Before updating the student record, we should first check that the course can accommodate an extra student. If that is the case, then we should immediately increase the course capacity by one ensuring that the student has reserved a place in the course. The condition and action should be evaluated and executed in the same transaction which updates the student record.

Event update_stock_price (stock X)

condition stock_price (stock X) = Y

Action buy_stock (stock X, amount A, customer C)

E-C coupling immediate

C-A coupling deferred - separate independent

In this example when the price of a stock reaches a certain price, a customer wishes to buy a certain amount of it. The condition is evaluated immediately when the event occurs, but the action is performed by spawning a commit independent transaction after the commit of the triggering transaction.

Event update_user_accounts( user U)

Condition true

Action Insert_Into_Security_log (user U, timestamp)

E-C coupling immediate

C-A coupling immediate

In this example, action is executed immediately when the event is detected. The action is executed in a new concurrent commit independent transaction.

Supporting ECA rules requires that the system implementing them have the ability to detect when events occur. The system must have the ability to detect primitive database events, external events, and temporal events. Also, it must have the ability to infer complex events from primitive ones and match event detection to rule specification to be able to determine rules to be triggered. In addition, the system must, after detecting an event, schedule condition evaluation and action execution according to the rule’s coupling modes. Finally the system must provide efficient condition evaluation, using such techniques as multiple query optimization, incremental evaluation, and materialization of derived data. All the above operations are performed by the functional components of the HiPAC project. These components and their functions will be described below:

• Object Manager : provides for necessary data management, calls the transaction manager to obtain lock, and detects events, reporting them to the rule manager.
• Transaction Manager : responsible for implementing the nested transaction model. It creates and terminates transactions, and provides for concurrency control. Also it acts as an event detector.
• Event Detector : detects primitive database events, temporal events, and application defined events, reporting them to the rule manager. It is also responsible for event definition, deletion, enabling, and disabling.
• Rule Manager : when an event is detected, it is the responsibility of the rule manager to fire the appropriate rules. The rule manager calls the transaction manager to create the required transactions for condition evaluation and action execution. Also it calls the condition evaluator to determine which conditions are satisfied.
• Condition Evaluator : responsible for efficiently determining which of the triggered rule’s conditions are satisfied.

Researchers in the field of active databases argue that object-orientation is the proper platform for implementing active database systems [IK93, DM94, BZ+95]. Rules in an object-oriented active database system are first class objects [DAY88]: each rule can be represented as an instance of a system-defined class "rule" providing all necessary functionality. For such a class, all object-oriented characteristics are available like for any other class. The integration of object-oriented and active features in one system provides a higher degree of expressive power than current database products can offer [GGD91].

In the work presented in this thesis, we will show that we can integrate active concepts in a non object-oriented database programming language. For this reason we will not discuss integrating object oriented features with active features in the frame work of this thesis.

An important consideration when discussing active databases is transaction control. Transaction control has to do with the execution model of the active database. The selection of a specific execution model reflects on the complexity of the system. In this section, we will compare the execution models presented in the ECA and the EA model.

The execution model used in the ECA model is an extended nested transaction model.

The ECA model allows the user to specify coupling modes between event occurrence and condition evaluation, and condition evaluation and action execution. These coupling modes allow for synchronization and processes. The immediate / deferred is used to provide for synchronization, while separate (dependent / independent ) is used to specify whether the fired rules should be coupled within the same transaction as the triggering event. In addition, the nested transaction model allows for rules to be fired and executed concurrently.

In the nested transaction model, subtransactions, are not totally equivalent to flat transactions. Subtransactions are valid only within the confines of the surrounding higher-level transaction. They are atomic, consistency preserving with respect to the local function they implement, and isolated from all other activities inside and outside the parent transaction. As far as durability is concerned, they are not durable because of their commit rule. The effects of a subtransaction do not become permanent until it and all its ancestors commit through a top level transaction. As mentioned in [GR93], parts of single transaction may be executed by many processes. Thus we might consider that subtransactions are basically processes which have the atomicity, consistency, and isolation properties of flat transactions. Except for the top level nested transaction, the other extensions to the nested transaction model (deferred nested transaction and nested CD top transaction) are atomic, consistent, and isolated but not durable.

The complexity of the HiPAC execution model is due to the fact that the model attempts to provide for concurrent processing of rules by using the nested transaction model. The complexity arises from the intertwined use of the concepts of transactions and processes.

The EA model uses a simple execution model. Once an event is detected the associated action is executed immediately in the same transaction. The action may be executed as part of the same process executing the transaction, or as a separate process. The EA model has one coupling mode which is immediate. But using the event composition operators, the EA model is able to implement the coupling modes of the ECA model. Any coupling mode can be implemented by selecting an appropriate event specification, incorporating the required transaction events. Assume that E is a composite event, C a predicate to be evaluated when E occurs, and A the action to be executed if the condition evaluate to true. The following examples present different coupling possibilities in O++:

1. Immediate - Immediate

E && C ==> A

2. Immediate - Deferred

fa ( E && C, before tcomplete, after tbegin) ==> A

3. Immediate - Dependent

fa ( E && C, after tcommit, after tbeign) ==> A

4. Immediate - Independent

fa ( E && C, after tcommit | after tabort, after tbegin) ==> A

5. Deferred - Immediate or Deferred - Deferred

fa ( E, before tcomplete, after tbegin) && C ==> A

With such event specifications, the EA model is able achieve the ECA model coupling modes, and be equivalent to it. But this equivalence is not totally accurate. Consider the following coupling mode:

Immediate - Independent

fa ( E && C, after tcommit | after tabort, after tbegin) ==> A

Here in the ECA model, such a coupling will have the fired trigger running concurrently in a separate casually independent transaction. In the EA model, the fired trigger will be run in a separate transaction but only after the commit of the triggering transaction. There will be no concurrent processing of transactions.

A more recent approach to active rule processing is transaction transformation [MT95]. This approach proposes a formal transaction transformation method for rewriting user defined transactions. It is argued that this transformation can be performed at compile time, thus requiring no special run-time support. This approach will not be discussed further as it is beyond the scope of work presented in this thesis.

The purpose of this chapter was to introduce the concepts of event programming and active database systems. In the remainder of this thesis, we will present our start at modifying Relix ( Relational database on UNIX) from a passive to an active database system. In chapter two, we will introduce Relix and discuss in details some of the features which are relevant to our work. Chapter three is a user manual intended to introduce to the readers the features of event programming in Relix. Chapter four deals with implementation details of event programming in Relix. Finally we conclude this thesis by comparing our implementation of event programming to active database concepts presented in this chapter. In particular, we will show that our implementation is an EA model, and using the equivalence of EA and ECA presented above our model is equivalent to ECA. We will prove that, using our event specification model, we are able to model the event combinators presented in the EA model ( prior, sequence, fa, and faAbs).

Relix (Relational database on UNIX) is briefly described in this chapter. Relix is a language which represents data as relations and applies algebraic operations on these relations. In the relational model [COD70], a relation is represented in the form of a table. Tables have the following properties:

• rows are distinct
• columns are labelled
• values of a row under a column are simple
• ordering of rows and columns is insignificant

Rows are referred to as tuples and columns as attributes. The set of values that an attribute is defined on is referred to as domain.

In the algebraic approach, a query is the application of operations on a relation [MER77]. The result of a query is a relation. Relix expresses queries by applying relational algebra operations on relations. In addition, Relix allows queries on individual domains. This type of operations is referred to as domain algebra.

In this chapter, we will discuss some general features of Relix and we will concentrate on some features which are relevant to the work presented in this thesis. The chapter will be divided into two main sections. The first section introduces Relix via examples. In the second section we will discuss some implementation issues of Relix.

This section will introduce the basics of Relix. In addition, it will concentrate on two particular features of Relix, namely the update statement and procedures in Relix.

Relix provides both unary operators and binary operators. Relix relations are combined in relational expressions using those operators. Unary operators in Relix are selection and projection. Binary operators include natural join and relational division. Both operations will be explained by worked examples. We use the following relations in our examples:

Relix provides an assignment operator "<- " which can be used to assign a relation (or part of a relation) to another relation. Consider the following Relix statement :

This statement will create a new relation EMP_COPY and assign to it the relation EMPLOYEES.

In selection, a subset of the operand relation is created by keeping only those tuples which satisfy a boolean condition and filtering out all others. Consider the following example:

The operand is EMPLOYEE and the boolean condition is (SALARY <= 12000). The selection will create a new relation LOWPAY which includes all tuples in EMPLOYEES which satisfy the boolean condition. LOWPAY will be as follows:

Here we used selection on the EMPLOYEES relation and then assigned the result of that selection to the relation LOWPAY.

In projection, a vertical subset of the operand relation is created by including only those domains listed in the projection list and discarding the rest. Consider the following example:

The operand is EMPLOYEE and the projection list is NAME. Projection will create a new relation NAMES defined on the NAME domain. NAMES will be as follows:

Selection and projection can be combined in a single statement. This combination is referred to as a T_selector. For example:

Relix also provides an increment operator "<+". This operator can be used to append a relation to another relation. Consider the following Relix statement:

This statement will add the tuples in relation NEW_EMPLOYEES to relation EMPLOYEES. The result will be as follows:

The increment operator is in principle an update operation, a more detailed discussion will be presented later.

Binary operators are used for such operations as natural join and relational division [COD70]. Joins can be thought of as operations on sets. A set operation can result in either a logical value or a set value. Logical values can determine if a set A is a subset of B and so on. Set values can be the intersection or union of two sets ( A Ç B or A È B).

Merrett [MER84] introduced the m -joins, which are a generalization of set operations on relations, and the s -joins, which are a generalization of logical operations on relations. The results of both m -joins and s -joins are also relations.

The m -joins are divided as follows:

• ijoin : natural join (generalization of intersection)
• ujoin : union join (generalization of union)
• djoin : difference left join (generalization of difference)
• drjoin : difference right join
• rjoin : right join (generalization of symmetric difference)
• ljoin : left join
• sjoin : symmetric difference join

ijoin is the natural join [COD70] and is viewed as the generalization of set intersection:

The result of the ijoin is relation IJOIN which is as follows:

ijoin combined all tuples of relation EMPLOYEES with all tuples of relation MANAGERS which have matching values of the common attribute DEPT.

ujoin is the generalization of a set union:

The result of the ujoin is relation UJOIN which is as follows:

ujoin combined all tuples of relation EMPLOYEES with all tuples of relation MANAGERS. The tuples for which the values of DEPT ( the join attribute) did not match were also included with a DC (don’t care) value for the MANAGER attribute. Note that the tuples which do not have a DC value are exactly the same tuples which were produced by the ijoin.

Another join operation of relevance to the work presented in this thesis is the djoin (difference join). This operation can be viewed as a decrement operation. Using it we can delete certain tuples from a relation. Consider the following relations:

The Relix statement:

will produce the following result:

 

A(	X)
	a
	b

The dljoin in principle is an operation which can be used to update relations by removing some tuples from it.

s -joins

The s -joins are divided as follows:

• sup : superset (generalization of Ê )
• sub : subset (generalization of Í )
• eqjoin : equality (generalization of =)
• sep : separate (generalization of Ç i.e. intersection is empty)
• icomp : natural composition (generalization of Ç i.e. intersection is not empty)

Consider that we have two relations R(X,Y) and S(Y), sup is an operation which produces a relation such that the sets of Y of the same value y in R are a superset of Y in S. Consider the following example:

 

 

R (	X	Y)
	A	a
	A	b
	A	c
	B	d
	B	e

 

 

S(	Y)
	a
	b
	c

SUP <- R sup S;

the result of sup is a relation, SUP:

 

SUP (	X)
	A

icomp (natural composition) is binary operation which is similar to ijoin, but the difference is that the common attribute is not an attribute in the resulting relation:

ICOMP <- EMPLOYEES icomp MANAGERS;

the result of icomp is a relation, ICOMP:

 

 

ICOMP(	NAME	SALARY	MANAGER)
	CHRIS	17000	CHRIS
	JOE	10000	MARK
	JOHN	10000	PAUL
	MARK	12000	MARK
	PAUL	15000	PAUL

2.1.2 Domain algebra in Relix

Relix allows queries on individual domains. This is referred to as domain algebra [MER84]. Domain algebra operations are of two types: horizontal ( scalar ) operations and vertical operations. Examples of both will be provided below.

Horizontal operations

Using horizontal operations, we can perform a number of operations on individual domains. We can do arithmetic, renaming, or defining constants. Let us consider the following Relix commands:

let MONTHLY be SALARY / 12;

let ANNUAL be SALARY;

let TAX_PERCENT be 0.25;

let TAX be ANNUAL*TAX_PERCENT;

let NET be ANNUAL - TAX;

PAYROLL<- [NAME,MONTHLY,ANNUAL,TAX,NET] in EMPLOYEES;

In the first command, we defined a virtual attribute, MONTHLY, to be 1/12 of the SALARY; in the second, we renamed the attribute SALARY to be ANNUAL; in the third, we defined a constant, TAX_PERCENT, to be 0.25; and in the fourth and fifth, we defined TAX and NET to be the result of some arithmetic performed on the previously defined virtual attributes. A virtual attribute is an attribute which is defined in terms of other attributes, as above. It can be "actualized" via projection, as has been done in the last command. The last command will produce the relation PAYROLL whose attributes are those in the projection list. The PAYROLL relation will be as follows:

 

PAYROLL(	NAME	MONTHLY	ANNUAL	TAX	NET)
	CHRIS	1416	17000	4250	12750
	JOE	833	10000	2500	7500
	JOHN	833	10000	2500	7500
	MAGGIE	1000	12000	3000	9000
	MARK	1000	12000	3000	9000
	PAUL	1250	15000	3750	11250

Vertical operations

Vertical operations include reduction and functional mapping. Reduction produces a single result from the values of all tuples of a single attribute in a relation. Consider the following examples:

let TOT_TAX be red + of TAX;

let AVG_TAX be TOT_TAX / (red + of 1);

TAXES <- [TOT_TAX,AVG_TAX] in PAYROLL;

The first command indicate the reduction operation, "red" and the addition operator "+". This command will produce a sum for the TAX column. The second command will produce an average of this column by dividing the result obtained in the first command by the number of tuples (red + of 1). In the third command, we are actualizing these values by projecting them. Relix will produce a relation, TAXES, which is as follows :

 

TAXES(	TOT_TAX	AVG_TAX)
	19000	3166

Another form of reduction is equivalence reduction. It is similar to simple reduction but produces different results for different sets of tuples in the relation. Consider the following example:

let SAL_BY_DEPT be equiv + of SALARY by DEPT;

DEPT_SAL <- [DEPT,SAL_BY_DEPT] in EMPLOYEES;

the above command will produce a relation DEPT_SAL which is as follows:

 

 

DEPT_SAL(	DEPT	SAL_BY_DEPT)
	A	22000
	B	25000
	C	17000
	E	12000

Functional mapping involves an operand attribute and a ordering attribute. Functional mapping performs the accumulation of the operator specified by the ordering attribute.

2.1.3 Updates in Relix

Almost all query languages provide three types of updates: add, delete, and change. Every language uses its own update formalism which does not necessarily extend the capabilities of the relational and domain algebra but, rather, has its own notation which makes it easier to use. Updates might breach the integrity, consistency or reliability of a database system. Relix furnishes a relational operation which is used to modify tuple values, add new tuples and delete existing tuples[TSA87,KOM92]. The update statement carries out tuple modifications in place, in contrast to other update methods in Relix ( e.g., the assignment operation). The update statement is subdivided into four categories [KOM92]:

1. Addition of tuples

update S add T;

2. Deletion of tuples

update S delete T;

3. Global update, modifying values of some domains

update R change <domain_list>;

4. Updates using a join operation, modifying some tuples a relation

update R change <domain_list> <join_potion> S;

We will examine each of these categories by way of example. Now consider we have the following relations:

 

SALARY (	NAME	AMOUNT)
	BILL	10000
	JIM	12000
	MIKE	15000
	RAY	17000
	ROSS	9000

 

NEW_SALARY(	NAME	AMOUNT)
	ANN	11000
	KIM	12000
	SAM	14500
	MIKE	15000

Category 1:

The following Relix statement

update SALARY add NEW_SALARY;

will add all the tuples in relation NEW_SALARY to the relation SALARY. This statement is equivalent to:

SALARY <- SALARY ujoin NEW_SALARY;

and to

SALARY <+ NEW_SALARY;

After the update statement is executed, the relation SALARY will be as follows:

 

SALARY(	NAME	AMOUNT)
	ANN	11000
	BILL	10000
	JIM	12000
	MIKE	15000
	KIM	12000
	RAY	17000
	ROSS	9000
	SAM	14500

Category 2:

The following Relix statement

update SALARY delete NEW_SALARY;

will delete from SALARY all the tuples which are in NEW_SALARY. This statement is equivalent to:

SALARY <- SALARY djoin NEW_SALARY;

After the update statement is executed, the relation SALARY will be as follows:

 

 

SALARY(	NAME	AMOUNT)
	BILL	10000
	JIM	12000
	RAY	17000
	ROSS	9000

Category 3:

Consider the following Relix statement:

update SALARY change NAME <- "ZIAD", AMOUNT <- 10000;

This statement will modify all values of the domain NAME to "ZIAD" and all values of the domain AMOUNT to 10000. This modification will cause all tuples to have the values "ZIAD 10000" and thus the relation SALARY will end up with only one tuple since all duplicates are removed.

 

SALARY(	NAME	AMOUNT)
	ZIAD	10000

 

Category 4:

Considering the original SALARY relation , the Relix statement

update SALARY change AMOUNT <- 15500 using NEW_SALARY;

will change the value of domain AMOUNT to 15500 only for those tuples of relation SALARY which also appear in NEW_SALARY. The only such tuple is " MIKE 15000" and it will be modified to "MIKE 15500". After the update, the relation SALARY will be as follows:

 

 

SALARY(	NAME	AMOUNT)
	BILL	10000
	JIM	12000
	MIKE	15500
	RAY	17000
	ROSS	9000

2.1.4 Procedures in Relix

A new feature added to Relix is the concept of a procedure [SAH87, RSL95]. A procedure definition is a declaration which, in its simplest form, associates an identifier with a statement [ASU86]. The identifier is the procedure name, and the statement is the procedure body. In Relix, a set of Relix statements are associated with an identifier to form a procedure. In an ideal situation, any statement of the language can be in the procedure body. At this point in time, however, only some Relix statements can be included in the procedure body. Also, procedures in Relix can have zero or more parameters and a procedure can have blocks. In Relix a procedure having more than one block means that at declaration time the procedure may have more than one body, but at run time only one of these bodies is executed The number of blocks is determined by the number of parameters. Having n parameters implies that we can have up to 2ⁿ blocks. The following are some examples on how to define and manipulate procedures in Relix.

As mentioned above, a procedure is the association of an identifier with a statement. Consider the following Relix declaration:

proc P () is

{

domain D intg;

relation R (D) <- { (1), (2) };

};

Here, we have declared a procedure with no parameters called P. The body of the procedure starts after the "{" and has two statements. The first defines a domain D to be an integer, and the second creates a relation R defined on the attribute D and has two tuples. At this point in time, the procedure is only declared. To execute the procedure we have to call it. Calling a procedure is done simply by typing the following at the Relix prompt :

P();

Once the procedure is called, Relix will execute the procedure body and create the relation R.

 

 

R(	D)
	1
	2

Let us consider another example:

proc P() is

{

domain A intg;

domain B intg;

relation R (A,B) <- { (1, 1), (2,2), (3,3) };

update R delete where A=2 in R;

};

In the above example, a procedure called P is declared. The procedure body contains four Relix statements. The first two statements declare domains A and B to be integers. The third statement creates a relation R defined on the domains A and B and has 3 tuples. The last statement is an update statement which deletes from R all tuples which have the value of domain A equal to 2.

To run this procedure, we input the following at the Relix prompt:

P();

The first three statements will result in the following:

 

 

R(	A	B)
	1	1
	2	2
	3	3

The last statement will result in the deletion of the all the tuples which have a value of 2 for domain A. In relation R that is the tuple "2 2":

 

R(	A	B)
	1	1
	3	3

Now let us move a step further and give an example of a procedure which has parameters:

proc P (A, B, C, R) is

{

domain A intg;

domain B intg;

domain C string;

relation R (A, B, C) <- { (1, 11, "a"), (2, 22, "b"), (3, 33, "c") };

update R delete where A=2 in R;

};

Procedure P has four parameters A,B,C, and R. By default, these parameters are an output of procedure P (i.e. they are created in procedure P). The procedure body declares the three domains A, B, and C, then creates a relation R defined on these domains and assigns 3 tuples to it. Then the update statement deletes all tuples in R which have the value of domain A equal to 2. Calling the procedure :

P( X, Y, Z, S);

will define domains A and B to be integers and C to be a string. Let us examine in detail how the system relations are affected, the statements:

domain A intg;

domain B intg;

domain C string;

will result in defining domains X and Y as integers and Z as string. The statement:

relation R (A, B, C) <- { (1, 11, "a"), (2, 22, "b"), (3, 33, "c") };

will create a relation, S, defined on A, B and C (X, Y and Z):

S(	X	Y	Z)
	1	11	a
	2	22	c
	3	33	d

The statemen:

update R delete where A=2 in R;

will delete all tuples in relation S which have the value of domain X equal to 2

 

S(	X	Y	Z)
	1	11	a
	3	33	d

The final example on procedures will be an example which presents the concept of blocks:

proc P (A, B) is

{

domain B intg; block 0

}

alt

{

relation A (B) <- {(1), (2)}; block 1

};

A procedure P is defined to have two parameters and two blocks. A block, as mentioned earlier, means that a procedure has more than one body at declaration time, but only one of these bodies is executed at runtime. A detailed discussion on procedures with blocks will not be presented in this thesis. We will simply mention how the different blocks can be called. To call procedure P and execute it with block 0, we have to input the following at the Relix prompt:

P(out X, out Y);

The result of calling P with block 0 being executed is the declaration of a new domain, Y, as an integer.

To execute block 1, we input the following:

P(out X, in Y);

Here the result of calling P with block 1 being executed is the creation of a new relation X defined on domain Y.

Procedures can be displayed using the Relix print command:

pr!!P : displays procedure P on the screen.

The entry of a procedure in .rel can be displayed using the Relix command:

sr!!P

Procedures can be deleted using the Relix delete relation command:

dr!!P

2.2 Implementation of Relix

Relix is an interactive multi-user system which accepts one statement at a time. It consists of two main modules: a parser and an interpreter. The parser scans the input statement and, if syntactically correct, generates intermediate code. This intermediate code is then passed to the interpreter which executes it. Throughout these two phases, system tables are consulted and updated. Since Relix is a multi-user system, a special concurrency mechanism is introduced in order to allow many Relix processes to operate on shared databases. The current Relix implementation is based on an earlier main-memory version [LAL86].

2.2.1 Technical features

Relix is written in the C [KR78, PLA91] language and is implemented to run on the following machines:

Manufacture	Model	CPU	OS
Sun	4/280	Sparc	Sun Os 4.1
Sun	3/280	MC68030	Sun Os 3.5
Solbourne	5/260(2)	Sparc	Sun Os 4.0
NeXT	Cube	MC68040	Mach 2.0

It is portable to any version of the UNIX operating system [RT78, KP84]. In terms of implementation, Relix has the following features:

• All Relix relations are kept in secondary memory. This accommodates certain applications which cannot fit into RAM. Such applications include geographical databases [MK91] and image processing.

Relations are seen as UNIX files and databases as collections of UNIX files under UNIX directories. In each database ( UNIX directory), there exists a set of system tables.

• In order to maximize query efficiency, Relix uses a powerful set of algorithms such as Z-order and B-tree [MER84].

2.2.2 The parser and the interpreter

The Relix parser is generated by YACC [JOH78, MB90]. Parsing is a two phase step:

• Lexical analysis
• Syntax analysis and code generation

The lexical analyzer is generated by LEX [LES75, MB90]. LEX scans the parsed input and breaks it into tokens. Once a token is matched against a regular expression, the associated action gets executed. During the syntax analysis and code generation phase, YACC is used to detect syntax errors and grammar ambiguities. Once a grammar rule is reduced the associated action is performed. These actions produce the intermediate code. Once the intermediate code is generated the Relix interpreter executes it. The interpreter is a C function which interacts with the run time stack and calls other functions that perform various operations together with error checking and recovery. Some of these functions are:

• print_rel (), which prints a relation, procedure, or events,
• Relix_select(), which performs selection,
• assign(), which performs assignment between relations,

The following example demonstrates the operation of the parser and the interpreter. Consider the following Relix statement:

pr!!A

The Relix parser converts the valid statement into the following intermediate code:

push-name

A

print-rel

halt

The interpreter executes the above intermediate code and calls the function print_rel() in order to display the relation A.

2.2.3 Relix internals

While executing the intermediate code, the interpreter interacts with the system tables. Relix also provides a mechanism for internal representation of relations, which is very much based on the system tables.

The system tables

Relix has a number of system tables which are used as a data dictionary for storing information about the database. These tables are stored in the secondary memory and are loaded into RAM when Relix is invoked. The three most important system tables are:

• .rel which contains information about all the relations which appear in the database.
• .dom which contains information about all the domains which appear in the database.
• .rd which links relations with the domains which they are defined on.

The relation table has the following attributes:

.rel (rel_name sort_status rank ntuples )

• rel_name : the user defined identifier of the relation.
• sort_status : indicates the sort status of the relation (1 is sorted, 0 is unknown)
• rank : indicates the number of attributes in a relation. It is 0 for system relations.
• ntuples : the number of tuples in the relation.

The domain table has the following attributes:

.dom (domain_name type)

• domain_name : the user defined identifier of the domain.
• type : The data type of the domain. It can have one of the following values : integer, string, boolean, long, short, expression, name, statement, procedure, or comp.

The relation_domain link table has the following attributes:

.rd (rel_name domain_name domain_pos)

• rel_name : the relation name.
• domain_name : the domain name.
• domain_pos : specifies the position of the domain in the relation.

A number of functions are associated with each table to search, delete and insert. The interpreter uses these function to access and maintain the system tables.

Internal representation of relations

A relation in Relix is represented as a UNIX file, under a UNIX directory. This file contains tuples of the relation. In addition, each relation is represented by entries in the .rel, .dom ,and .rd tables. Consider the following example:

R(	X	Y)
	a	1
	b	2

The above relation, R, is defined on the domains X ( string) and Y( integer). For this relation, there will exist a UNIX file R in which each line is a tuple of the relation. The domain table, .dom, will have, among other entries, the following:

 

.dom(	domain_name	type)
	...	...
	X	2	(string)
	Y	4	(integer)
	...	...

The relation table .rel will have the following entry:

.rel ( rel_name sort_status rank ntuples )

R 1 2 2

(sort_status set to 1 indicates relation is sorted, rank set to 2 indicates number of attributes of R)

The relation_domain link table .rd will have the following entry:

 

.rel (	rel_name	sort_status	rank	ntuples)
	R	1	2	2

2.2.4 Implementation of Updates

In this section we will discuss the update algorithms for categories 1,2,3, and 4. Category 1 is just syntactic sugar for the increment operation while category 2 is syntactic sugar for dljoin. Category 3 is implemented by an algorithm called Update_global and category 4 is implemented by an algorithm called Update_partial [KOM92]. For syntax refer to Appendix A.

Update add : update S add T;

Addition of tuples is performed by a function called increment relation which adds the tuples in one relation (T) to the resultant relation (S), then removes duplicates from the resultant relation.

Update delete : update S delete T;

Update delete is another form of performing a dljoin. In update delete, first a join is performed between S and T. The result of the join is then removed from S.

Update_global :

Update_global modifies the values of the domains on the left hand side of the domain pairs with respect to the values on the right hand side of the pairs. This modification is global, i.e., all tuples of the relation are updated.

The function Update_global takes the following as parameters :

• relation_name : the name of the relation being updated.
• domain_list : the list of domains which appear on the left hand side of the domain pairs
• new_list : the list of domains which appear on the right hand side of the domain pairs.

The algorithm goes as follows:

• If domain_list or new_list is empty then give an error message
• If relation_name is an empty relation then no change to relation_name
• If any of the above does not occur then

• for each domain in domain_list and for each domain in new_list

loop

replace the value of the domain in domain_list with the value of the corresponding domain in new_list in all tuples of relation_name.

end loop

• project the updated relation on the domains it was originally defined on so that the relation obtained is sorted and free of duplicate tuples

If we consider the Relix statements:

update SALARY change NAME <- "ZIAD", AMOUNT<-10000;

relation_name is SALARY,

domain_list is NAME, AMOUNT,

new_list is "ZIAD",10000

The domain_list and the new_list are not empty, so we move to the next step; relation_name is not empty, so we move on to the next step; and for each tuple in the relation we change each domain in domain_list with the corresponding value in new_list. The SALARY relation will look as follows:

 

SALARY(	NAME	AMOUNT)
	ZIAD	10000
	ZIAD	10000
	ZIAD	10000
	ZIAD	10000
	ZIAD	10000

The last step in the algorithm will project the relation on the domains NAME and AMOUNT and will remove duplicates. The relation SALARY will be as follows:

 

SALARY(	NAME	AMOUNT)
	ZIAD	10000

Update_partial :

Update_partial modifies values of the domains on the left hand side of the domain pairs with respect to the values on the right hand side of the pairs. The update is called partial since the tuples which are modified are the result of the join operation between the base relation and the relational expression following the "using" keyword.

The function Update_partial takes as parameters the following:

• relation_name : the name of the relation being updated.
• domain_list : the list of domains which appear on the left hand side of the domain pairs
• new_list : the list of domains which appear on the right hand side of the domain pairs.

• join_relation : the relation produced by applying the join operation between the relation being updated and the relational expression following the "using" keyword. The default join operation is the natural join (ijoin).

The algorithm goes as follows:

• If domain_list or new_list is empty then give an error message
• If relation_name is an empty relation then no change to relation_name
• If join_relation is an empty relation then no change to relation_name
• If any of the above does not occur

• create a relation which contains all tuples of relation_name which do not belong to join_relation and thus will not be modified. Call this relation difference_relation.

• for each domain in domain_list and for each domain in new_list

loop

replace the value of the domain in domain_list with the value of the corresponding domain in new_list for all tuples of join_relation.

end loop

• merge the updated relation join_relation and the unmodified relation difference_relation into a new relation called target_relation.
• project target_relation on the domains which relation_name is defined on so as to obtain a relation with no duplicates.

If we consider the Relix statement:

update SALARY change AMOUNT <- 15500 using NEW_SALARY;

relation_name is SALARY

domain_list is AMOUNT

new_list is 15500

join_relation is the relation obtained from applying natural join between SALARY and NEW_SALARY, and it contains the following tuples:

 

join_relation(	NAME	AMOUNT)
	MIKE	15000

domain_list, new_list, relation_name, and join_relation are not empty, so we proceed to create difference_relation which will contain the following tuples:

 

difference_relation(	NAME	AMOUNT)
	BILL	10000
	JIM	12000
	RAY	17000
	ROSS	9000

P ALIGN="JUSTIFY">

Now we proceed and replace the value of the domain AMOUNT with the new value 15500 in every tuple of join_relation. join_relation will be as follows:

 

join_relation(	NAME	AMOUNT)
	MIKE	15500

Then we merge join_relation and difference_relation into target_relation

 

target_relation(	NAME	AMOUNT)
	BILL	10000
	JIM	12000
	MIKE	15500
	RAY	17000
	ROSS	9000

The last step is to project target_relation on the domains NAME and AMOUNT and eliminate duplicate tuples.

Now SALARY is equal to the projected relation target_relation and looks as follows:

 

SALARY(	NAME	AMOUNT)
	BILL	10000
	JIM	12000
	MIKE	15500
	RAY	17000
	ROSS	9000

2.2.5 Implementation of procedures

In this section we will present the syntax and algorithm for defining procedures in Relix. As mentioned before, a procedure is an identifier associated with a statements. The procedure syntax is as follows:

proc PROCEDURE_NAME ( PARAMETER_LIST) is

{

PROCEDURE_BODY

};

When this syntax is encountered by the Relix translator, a number of actions are performed, including syntax checking and updating some of the system tables:

• The translator checks the PROCEDURE_BODY for syntactic correctness; if an error is detected then the procedure declaration fails.
• If the PROCEDURE_NAME is already in use, then the procedure declaration fails.
• An entry for the procedure is created in .rel.
• If the PARAMETER_LIST is not empty, an entry for each parameter in the PARAMETER_LIST is created in the system table .comp.
• The PROCEDURE_BODY is compiled into i-code and a file called .PROCEDURE_NAME.proc is created.
• The PROCEDURE_BODY (source code) is written to a file called PROCEDURE_NAME.proc
• If the PROCEDURE_BODY contains a CONSTANT ASSIGN RELATION DECLARATION (i.e., relation R(..) <- {...}; ), a file called .PROCEDURE_NAME.XX is created to hold the constant values (XX is a unique string).

Note : the generated i-code (.PROCEDURE_NAME.proc) is not passed on to the Relix interpreter.

When a procedure call is encountered by the translator, the following actions are performed (procedure call syntax : PROCEDURE_NAME ( PARAMETER_LIST); ):

• If PROCEDURE_NAME is not a procedure, the operation fails.
• If the number of actual and formal parameters do not match, the operation fails.
• PROCEDURE_NAME is protected (i.e., cannot be deleted or called).
• The i-code is read from the file .PROCEDURE_NAME.proc
• Map the actual parameters to the formal parameters and create a new i-code file called .PROCEDURE_NAME.proc.XX (XX is a unique string).
• Call the interpreter to execute the new i-code.
• Delete the file .PROCEDURE_NAME.proc.XX.
• Return control.

Note : a procedure cannot have a command to delete itself or call itself.

When a delete procedure command (dr!!PROCEDURE_NAME) is encountered, the following actions are performed:

• Delete the entry in .rel corresponding to the procedure
• Delete the entries in .comp ( in case the procedure has parameters)
• Delete the source file PROCEDURE_NAME.proc
• Delete the i-code file .PROCEDURE_NAME.proc
• Delete any .PROCEDURE_NAME.* files

 

 

2.3 Summary

In this chapter, we have attempted to provide the reader with a basic understanding of Relix. We have introduced relational and domain algebra. In addition we have introduced the update statement. Since one of the aims of the work presented in this thesis is the modification of the update statement to support event handlers. Also, we introduced the concept of procedures in Relix, which is a new addition to the language, and has been developed in parallel with event handlers. As we will see in the following chapters, we have modified the original procedure declaration in Relix so that it can be used to support the definition of event handlers.

 

Chapter 3

 

 

 

User Manual

In our implementation, we have used the Relix procedure construct to define event handlers. An event handler can be viewed as an indirect procedure call, i.e., a procedure called by the system. In this chapter we will introduce the reader to the mechanisms by which he/she can define event handlers. In addition, we will present event handler properties and operations which can be performed on them. We will conclude this chapter by a worked out example which will amplify the user’s understanding of event handlers.

3.1 Procedures as event handlers

Event handlers are system generated procedure calls. Thus, if a user wishes to define a procedure as an event handler, he/she should specify that by giving it an event name. An event name is a special syntax by which the translator can distinguish between procedures and event handlers.

3.1.1 Naming event handlers

Suppose we have a relation R with attributes a, b, and c. If we wish to define an event handler which is to be executed after a change update is performed on R using attributes a and b, then we can write the following procedure to define the event handler:

 

proc post:change:R[a,b] () is

{

statements

};

Here, what we have defined is a procedure that is to be executed after a change update is performed on attributes a and b in relation R.

Using a special syntax we can declare a procedure as being an event handler. This special syntax is as follows: a prefix followed by the keyword update followed by the type of update then the relation being updated and, depending on the type, possibly followed by an attribute list. The syntax goes as follows:

<prefix:>type:relation<[attribute-list]>

each component of the name will be discussed next.

prefix:

Prefix is an optional part of the name. It can either be pre or post.

pre implies that the event handler is to be executed prior to the execution of the event which triggered it.

post implies that the event handler is to be executed after the triggering event has been executed.

If prefix is omitted then the event handler is defined as being a post-event handler.

type:

Type specifies on which type of update this event handler will be activated. It has three possible values: add, delete, change.

relation:

Is a relation name: a Relix identifier.

 

 

attribute-list:

Is a list of attributes of the preceding relation. When defining event handlers that have type add or delete, the attribute-list can be omitted. When defining event handlers with type change, an attribute list must be specified. Omitting the attribute-list will result in a syntax error and a failed definition. When specifying the attribute-list each attribute is separated from the preceding one by a comma (‘,’).

Suppose we have a relation R with attributes x, y, and z.

R(X, Y, Z)

All the following are valid event names:

pre: add:R[X,Y,Z]

post:add:R

add:R (equivalent to post:add:R)

delete:R[X,Y,Z]

change:R[X,Y] (equivalent to post:change:R[X,Y])

pre:change:R[X,Y]

post:change:R[X]

The following is not a valid event name:

pre:change:R

Event names are one-to-many. That is we can define multiple event handlers using the same event name. When stored, event handlers are assigned a system generated name.

3.1.2 Defining event handlers

As mentioned before, an event handler is a procedure with a special name. Thus defining event handers is just like defining procedures:

 

proc event-name () is

{

statements;

};

In addition, event handlers do not take parameters. This is due to the fact that they will be called by the system, not by the user.

3.1.3 Non determinism

Event handlers have the property of being non deterministic. What we mean is that they should not depend on each other. One event handler should not rely on the result of another event handler. Thus the order in which they are called is not of importance.

3.1.4 Nested event handlers

Since an event handler is just a procedure, and procedures can have a number of statements including update statements. Then, an event handler may contain a statement which in turn has its own event handlers. The user can nest event handlers as deep as he/she wants. But in practice, nesting beyond a second level is rare. We illustrate nesting in the following diagram

 

 

(Dotted lines originating from the top left corner of a box represent pre-event handlers calls, those originating from the bottom left corner represent a post-event handlers calls. Solid lines represent the sequence of execution of the event handlers.)

The order of execution of the event handlers will be:

PRE EVENT HANDLER 21

PRE EVENT HANDLER 11

POST EVENT HANDLER 21

PRE EVENT HANDLER 12

TRIGGERING EVENT

POST EVENT HANDLER 11

POST EVENT HANDLER 12

3.2 Event handler states

By default, when an event handler is defined it is set to active. Being set to active implies that when the triggering event occurs then the event handler will be executed. On the contrary, if the event is set to inactive, then when the triggering event occurs, the event handler is not executed. The user can use the commands eventoff and eventon to deactivate and activate event handlers.

3.2.1 Setting to inactive

The user can set one ore more event handlers to inactive by giving the following command:

>eventoff event-name;

If the user attempts to set an inactive event to inactive a message is displayed.

3.2.2 Setting to active

Similar to eventoff, to set event handlers to active the user can type the following command:

>eventon event-name;

If the user attempts to set an active event handler to active a message is displayed.

3.3 Selection of event handlers

Event handler selection is not an operation performed by the user, but rather by the system. But this operation is the most important operation when dealing with event handlers. It is used with setting events, printing events, and calling events. Selection is divided into two groups: Add/Delete selection and Change selection. Each will be discussed below.

3.3.1 Add / Delete selection

Consider the following relation

R(X, Y, Z) and the following active event handlers:

event-handler 1 : pre:add:R

event-handler 2 : pre:add:R

event-handler 3 : pre:delete:R

event-handler 4 : post:add:R

Now suppose we have the event update R add S, then we want to select all those event handlers which will be executed before the event itself. The selection process will return the following : event-handler 1 and event-handler 2. In other words, in the case of add / delete selection, the select process will return all those active event handlers which match in the prefix, type, and relation.

3.3.2 Change selection

Consider we have the relation

R(X, Y, Z) and the following active event handlers:

event-handler 1 : pre:change:R[X,Y,Z]

event-handler 2 : pre:change:R[X,Y]

event-handler 3 : pre:change:R:[X,Z]

event-handler 4 : pre:change:R[Y,Z]

event-handler 5 : pre:change:R[X]

event-handler 6 : pre:change:R[Y]

If we are about to execute the following statement:

update R change X<-value1, Y<-value2

The system will try to select the active event handlers which are to be executed before this statement. The system will perform selection and it will return the following:

event-handler 2, event-handler 5, and event-handler 6.

Why are only these event handlers selected?

The change selection will try to select all those active event handlers which have an attribute list which is a subset of the attribute list of the event (any combination of attributes in the attribute list).

X, Y, Z Ë X, Y thus event-handler 1 is excluded,

X, Z Ë X, Y thus event-handler 3 is excluded,

Y, Z Ë X, Y thus event-handler 4 is excluded,

On the other hand:

X, Y Ì X, Y thus event-handler 2 is included,

X Ì X, Y thus event-handler 5 is included,

Y Ì X, Y thus event-handler 6 is included.

3.4 Printing event handlers

Since event handlers are defined as procedures and they are stored as procedures with system generated names which the user is unable to know, we have expanded on the Relix pr!! command to be able to print event handlers.

When using the pr!! command, if the user supplies an event name, then all defined active event handlers which match the event name are displayed on the screen. The syntax for the print command is as follows:

>pr!!event-name;

3.5 Deleting event handlers

A user cannot delete an event handler, but rather set it to inactive. Event handlers are deleted by the system. They are deleted once the relation they are defined on is deleted.

3.6 Trigger relations

A trigger is defined as being the relation which has affected another relation through an update operation. For example, when using update R add S, we are adding S to R, and we consider S to be the trigger. A trigger relation is defined and can be used in the pre and post event handlers only. In the following subsections, we will define the trigger relation for each of the update mechanisms we have.

3.6.1 Add / Delete trigger relation

When using the update-add syntax to add tuples to a relation, the trigger relation is the relation containing the tuples being added. Consider the following Relix command:

>update R add S;

Here S is the trigger relation. Relix will provide a relation named "TRIGGER" which is identical to S. The user can reference "TRIGGER" in all the pre and post event handlers.

Similarly if we have the following Relix command:

>update R delete S;

The relation S is the trigger. Relix will provide a relation named "TRIGGER" which is identical to S. The user can reference "TRIGGER" in all the pre and post event handlers.

3.6.2 Change trigger relation

In the update-change category, we have two types of updates, update-global and update-partial. The definition of the trigger relation in each of them is not the same. The trigger relation for each type will be discussed below.

i- update-global

In update-global we are changing a value of one or more attributes of a relation for all tuples in the relation. In this case we have defined the trigger relation to be the relation being updated before any update has taken place. For example:

>update R change X <- value,...

the relation "TRIGGER" is defined to be R before update.

ii- update-partial

In update-partial we are changing the values of one or more attributes of some tuples in the relation. Before defining the trigger relation, let us consider the following Relix command:

> update R change X <- value,... using S;

The tuples being updated here are those which are the result of the join between R and S, in this case the ijoin. We have defined "TRIGGER" to be the relation obtained by performing the join: R ijoin S. If the user is not using the default join (ijoin), then "TRIGGER" will be the relation obtained by performing the join : R jointype S.

3.7 Worked example

In this section we will introduce an example demonstrating how event handlers are used. Our example is a stock exchange where the main operation is to buy and sell stocks. Buy and sell requests are stored in relations. Also, we have a relation to store the current price of stocks. Customers place buy and sell requests in the respective relation, and they specify at which price they want to buy or sell. Once the stock price relation is updated we must automatically do the following:

1. Store old price of stocks being changed in OLD_STOCK_PRICE relation.

2. Issue a buy request for those customers who want to buy stock.

3. Issue a sell request for those customers who want to sell.

4. Update sold transactions relation.

5. Update buy transaction relation.

The relations which we are going to use are the following:

STOCKS ( STOCK_NAME CURRENT_PRICE )

OLD_PRICES ( STOCK_NAME OLD_PRICE )

BUY_REQUEST ( CLIENT STOCK_NAME AMOUNT PRICE )

SELL_ REQUEST ( CLIENT STOCK_NAME AMOUNT PRICE )

TRAN_BOUGHT (CLIENT STOCK_NAME AMOUNT PRICE )

TRAN_SOLD (CLIENT STOCK_NAME AMOUNT PRICE )

NEW_PRICES ( STOCK_NAME NEW_CURRENT_PRICE

Where

STOCK_NAME is name of stock

CURRENT_PRICE is current price of stock

OLD_PRICE is old price of stock

CLIENT is the name of client buying or selling

AMOUNT is amount of stocks client wants to buy

PRICE is the price at which the client wants to sell or buy

NEW_CURRENT_PRICE is the new price of the stock

We will start by defining our domains :

domain STOCK_NAME string;

domain CURRENT_PRICE intg;

domain CLIENT string;

domain AMOUNT intg;

domain PRICE intg;

domain NEW_CURRENT_PRICE intg;

let OLD_PRICE be CURRENT_PRICE;

Our relations will be as follows when we first start :

STOCKS(	STOCK_NAME	CURRENT_PRICE )
	APPLES	1
	BALLS	2
	CARS	3
	DOORS	4
	EGGS	5
	FISH	6
	GUNS	7

 

 

OLD_PRICES (	STOCK_NAME	OLD_PRICE )
	APPLES	2
	BALLS	3
	CARS	4

 

BUY_REQUEST(	CLIENT	STOCK_NAME	AMOUNT	PRICE )
	ANNA	APPLES	10	3
	BILL	APPLES	15	4
	CHRIS	APPLES	10	1
	DAVE	CARS	15	3
	ELIE	FISH	10	6

 

 

SELL_ REQUEST(	CLIENT	STOCK_NAME	AMOUNT	PRICE )
	ANNA	BALLS	10	1
	BILL	CARS	15	5
	CHRIS	APPLES	10	4
	DAVE	GUNS	15	3
	ELIE	FISH	10	7

 

 

TRAN_BOUGHT(	CLIENT	STOCK_NAME	AMOUNT	PRICE )
	ARROUN	BALLS	10	1
	BRIAN	CARS	15	3
	CHRIS	APPLES	10	4
	DAVE	GUNS	15	3
	ELIE	FISH	10	7

 

 

TRAN_SOLD(	CLIENT	STOCK_NAME	AMOUNT	PRICE )
	ANNA	BALLS	10	1
	BILL	CARS	15	3
	CHRIS	APPLES	10	4
	DEMI	GUNS	15	3
	KAREN	FISH	10	7

 

 

 

 

 

 

 

 

 

 

 

 

Before defining the event handlers, we first have to identify the event for which we are going to run these event handlers. As mentioned above the event is an update to the

STOCKS relation:

> update STOCKS change CURRENT_PRICE <- NEW_CURRENT_PRICE

using NEW_PRICES;

Now let us start by defining the first event handler. We want to run an event handler which records the price of a stock before it is updated. Evidently it is a pre event handler. Now we define the event handler as follows:

> proc pre:change:STOCKS[CURRENT_PRICE] () is

{

OLD_PRICES <+ [STOCK, OLD_PRICE] in TRIGGER;

};

Where TRIGGER is the relation obtained by performing the following join :

STOCK ijoin NEW_PRICES

TRIGGER looks as follows:

 

TRIGGER(	STOCK_NAME	CURRENT_PRICE	NEW_CURRENT_PRICE)
	APPLES	1	3
	BALLS	2	4

The second event handler we want to define is the event handler which will update TRAN_BOUGHT and TRAN_SOLD. This event handler is to be executed after the event. Thus it is a post event handler. Now let us define this event handler:

> proc post:change:STOCKS[CURRENT_PRICE] () is

{

BUY <- [CLIENT,STOCK_NAME,AMOUNT,PRICE] in ( BUY_REQUEST [ STOCK_NAME,PRICE ijoin STOCK_NAME, NEW_CURRENT_PRICE ] in TRIGGER);

SELL <- [CLIENT,STOCK_NAME,AMOUNT,PRICE] in ( SELL_REQUEST [ STOCK_NAME,PRICE ijoin STOCK_NAME,NEW_CURRENT_PRICE] in TRIGGER);

update TRAN_BOUGHT add BUY;

update TRAN_SOLD add SELL;

};

TRIGGER is the same relation defined before.

Now after the BUY and SELL relations are added to TRAN_BOUGHT and TRAN_SOLD, we would like to delete BUY and SELL relations from BUY_REQUEST and SELL_REQUEST. We can do that by defining post event handlers which run after the update to TRAN_BOUGHT and TRAN_SOLD is done.

> proc post:add:TRAN_BOUGHT () is

{

update BUY_REQUEST delete BUY;

};

> proc post:add:TRAN_SOLD() is

{

update SELL_REQUEST delete SELL;

};

By defining these last two event handlers, we actually have defined nested event handlers. The event handler "post:change:STOCKS:CURRENT_PRICE" has in it two statements which can have their own events handlers:

update TRAN_BOUGHT add BUY;

update TRAN_SOLD add SELL;

and by defining the event handlers "post:add:TRAN_BOUGHT" and "post:add:TRAN_SOLD" we have accomplished nesting. In the figure below the number indicate the order in which the event handlers are executed.

 

 

 

 

By default, the event handlers are set to active. Suppose we want to set the event handler "pre:change:STOCKS[CURRENT_PRICE]" to inactive the user has to type the following command:

> eventoff pre:change:STOCKS[CURRENT_PRICE];

if he/she wishes to set it back to active the then the following command is typed

> eventon pre:change:STOCKS[CURRENT_PRICE];

If a user wishes to display event handlers on the screen the he/she can type the following command:

> pr!! pre:change:STOCKS[CURRENT_PRICE];

Typing this the user will get the following on his screen:

proc pre:change:STOCKS[CURRENT_PRICE] () is

{

OLD_PRICES <+ [STOCK, OLD_PRICE] in TRIGGER;

};

Now let us see what happens when the STOCKS relation is updated using the following command:

> update STOCKS change CURRENT_PRICE <- NEW_CURRENT_PRICE

using NEW_PRICES;

The command is first translated and the intermediate code generated. After that the intermediate code will pass to the interpreter where it is going to be executed. The interpreter will detect an update operation so following will be done:

* create the TRIGGER relation for this update statement

* check if pre event handlers exist

* if pre event handlers exist call them

* execute the update statement

* check if post event handlers exist

* if post event handlers exist call them

* delete TRIGGER relation

We will try to see what happens in our example:

* first we will create the TRIGGER relation. In this case it will be the relation obtained by performing the ijoin between STOCKS and NEW_PRICES

 

TRIGGER(	STOCK_NAME	CURRENT_PRICE	NEW_CURRENT_PRICE)
	APPLES	1	3
	BALLS	2	4

* the interpreter will detect that there is a pre event handler for the event and call it. In this case there is only one pre event handler:

pre:change:STOCKS[CURRENT_PRICE ]

this event handler will add tuples to the relation OLD_PRICES which give the price of the stocks before changing them.

 

OLD_PRICES(	STOCK_NAME	OLD_PRICE )
	APPLES	1
	APPLES	2
	BALLS	2
	BALLS	3
	CARS	4

there are no more pre event handlers so the interpreter will move to the next step.

* executing the event will result in having a new STOCKS relation

 

 

STOCKS(	STOCK_NAME	CURRENT_PRICE )
	APPLES	3
	BALLS	4
	CARS	3
	DOORS	4
	EGGS	5
	FISH	6
	GUNS	7

* the interpreter will detect that there is a post event handler and call it. In this case there is only one post event handler:

post:change:STOCKS:CURRENT_PRICE

This event handler will determine which clients want to buy a certain stock at the new update price and place these orders in the relation BUY; similarly, for those who want to sell, it will place the orders in the relation SELL.

 

BUY(	CLIENT	STOCK_NAME	AMOUNT	PRICE )
	ANNA	APPLES	10	3

SELL(	CLIENT	STOCK_NAME	AMOUNT	PRICE )
	{no tuples }

Next, the event handler has to update both TRAN_BOUGHT and TRAN_SOLD by executing the two update statements:

update TRAN_BOUGHT add BUY;

update TRAN_SOLD add SELL;

the interpreter will apply the same steps when executing the event which triggered the handlers:

* create TRIGGER relation (not of interest in this example)

* check for pre event handlers and run them ( none exist )

* execute the update statement

 

 

 

TRAN_BOUGHT(	CLIENT	STOCK_NAME	AMOUNT	PRICE )
	ANNA	APPLES	10	3
	ARROUN	BALLS	10	1
	BRIAN	CARS	15	3
	CHRIS	APPLES	10	4
	DAVE	GUNS	15	3
	ELIE	FISH	10	7

* check for post event handlers and run them , in this case one exists

post:add:TRAN_BOUGHT

It will delete those tuples added to TRAN_BOUGHT from BUY_REQUEST

 

BUY_REQUEST(	CLIENT	STOCK_NAME	AMOUNT	PRICE )
	BILL	APPLES	15	4
	CHRIS	APPLES	10	1
	DAVE	CARS	15	3
	ELIE	FISH	10	6

* delete TRIGGER relation

For the second update statement update TRAN_SOLD add SELL;

The same steps are performed:

* create TRIGGER relation (not of interest in this example)

* check for pre event handlers and run them ( none exists )

* execute the update statement

 

TRAN_SOLD(	CLIENT	STOCK_NAME	AMOUNT	PRICE )
	ANNA	BALLS	10	1
	BILL	CARS	15	3
	CHRIS	APPLES	10	4
	DEMI	GUNS	15	3
	KAREN	FISH	10	7

* check for post event handlers and run them , in this case one exists

post:add:TRAN_SOLD

It will delete those tuples added to TRAN_BOUGHT from BUY_REQUEST

 

SELL_ REQUEST(	CLIENT	STOCK_NAME	AMOUNT	PRICE )
	ANNA	BALLS	10	1
	BILL	CARS	15	5
	CHRIS	APPLES	10	4
	DAVE	GUNS	15	3
	ELIE	FISH	10	7

P ALIGN="JUSTIFY">

Note : The user must be aware that when executing event handlers the interpreter is being called recursively until all event handlers have been executed.

In the next chapter, we will discuss the implementation of event handlers in Relix. More details of the implementation and the way event handlers are executed will be presented.

 

 

 

 

 

 

 

 

Chapter 4

 

 

 

Implementation

In this chapter we will discuss the way we implemented event handlers and the changes we made to the grammar and interpreter to support event handlers. We will discuss the changes made to the procedure declaration. Then we will move to explain the new syntax introduced to manipulate event handlers. Also we will describe the way event handlers are stored in RAM and on disk and describe the algorithms used for selecting event handlers. Finally we will explain how all these pieces were assembled together in order to provide event programming capabilities in Relix.

4.1 Procedures as event handlers

In order to use procedures as a way to define event handlers we had to change the grammar used to define procedures so that it accepts an event name. The procedure declaration is as follows:

procedure_declaration :

P_DEC identifier '('

procedure_parameter_list ')'

IS procedure_body ;

We had to replace the non terminal symbol identifier with a non terminal symbol which can either be a an identifier or an event name:

 

 

procedure_declaration :

P_DEC procedure_name '('

procedure_parameter_list ')'

IS procedure_body ;

procedure_name :

event_name

|

event_name ‘[’ event_attribute_list’]’

|

IDENTIFIER ;

Now we have introduced a new non terminal symbol event_name which is the grammar we used to express the event_name syntax:

event_name :

prefix ‘:’ action

|

action ;

prefix :

POST

|

PRE ;

action :

ADD ‘:’ identifier

|

DELETE ‘:’ identifier

|

CHANGE ‘:’ identifier ;

event_attribute_list :

event_attribute

|

event_attribute_list ‘,’ event_attribute ;

event_attribute :

identifier ;

Using the above grammar to specify an event name, we can now use it to declare procedures as event handlers. Let us see, by way of example, what happens when a procedure is declared as an event handler:

Consider the relation R with the following attributes X, Y and Z

R( X, Y, Z)

We would like to define the following event handler:

>proc pre:change:R[X,Y] () is

{

statements;

};

Once the user enters this event handler the following takes place :

* the event attributes are set (prefix, type, relation and attribute list)

* a system name for the event handler is generated

* since event handlers are procedures they are stored as regular procedures (refer to chapter 2)

* the event attributes are stored in a system table

* event handler is set to active

Let us examine what happened when we declared the above event handler :

* prefix is set to "pre"

* event_type is set to "change"

* relation is set to "R"

* event_attribute list is set to a list containing X and Y

* since an event handler is a procedure and is stored as a procedure we have to generate a name for this procedure. We use system generated names for event handlers. A system generated name is a name generated by using a counter and a process id number and has the following form XX_YYYY, where XX is a counter and YYYY is a process id. The system generated name can be obtained by either creating a new name or by reusing an old name (refer to section 4.5 for more details).

* the system generated name is passed to the part of the translator which handles procedure storing and the event handler is stored on disk as XX_YYY.proc and the appropriate system tables are updated (refer to chapter 2).

* now we need a way to keep track of event handlers. We have introduced a new system table named ".events" which stores the event attributes. So we will add the attributes of the event handler to the table.

* the event handler is set to active.

4.1.1 The ".event" system table

The ".event" system table is the system table consulted when events are detected. Once an event is detected, the ".event" table is searched to find all pre and post event handlers which should be executed with the triggering event. The attributes of the table are the following:

* .urel_name : the name of the relation in the event name

* .attr_name : one of the attribute names in the attribute list

* .type_name : the type of action on which this event handler will be activated

* .prefix_name : the prefix of the event handler (pre or post)

* .proc_name : the procedure name under which this event handler was stored

* .active_stat : the state of the event handler (active or inactive)

* .delete_stat : indicates if the event handler is deleted or not

Now if we return to our example above and see how the event handler will be stored in the ".event" table:

.event (	.urel_name	.attr_name	.type_name	.prefix_name	.proc_name	.active_stat	.delete_stat )
	R	X	change	pre	10_1120	Y	N
	R	Y	change	pre	10_1120	Y	N

Why did we have two entries in the table for one event handler?

Since the number of attributes included in the event attribute list cannot be determined we have decided to include an entry for each attribute. We relate these entries by the procedure name which will be the same for all of them. Now let us define some more event handlers and see how will they be stored. Consider the following event handlers:

pre:change:R[X,Y,Z]

pre:change:R:[X,Z]

pre:change:R[X]

pre:add:R[X,Y,Z]

pre:delete:R[X]

post:add:R

post:delete:R

 

.event (	.urel_name	.attr_name	.type_name	.prefix_name	.proc_name	.active_stat	.delete_stat )
	R	X	change	pre	10_1120	Y	N
	R	Y	change	pre	10_1120	Y	N
	R	X	change	pre	11_1120	Y	N
	R	Y	change	pre	11_1120	Y	N
	R	Z	change	pre	11_1120	Y	N
	R	X	change	pre	12_1120	Y	N
	R	Z	change	pre	12_1120	Y	N
	R	X	change	pre	13_1120	Y	N
	R	DC	add	pre	14_1120	Y	N
	R	DC	delete	pre	15_1120	Y	N
	R	DC	add	post	16_1120	Y	N
	R	DC	delete	post	17_1120	Y	N

Now let us examine what happened when we defined the above event handlers. The first two are the same as the one discussed previously. The new ones are those with add and delete. The event handler "pre:add:R[X,Y,Z]" has an attribute list, but as mentioned in the previous chapter, when dealing with add or delete we do not pay any attention to the attribute list. The reason for that is that add / delete deals with tuples as a whole as opposed to change which deals with attributes. You can add or delete a whole tuple so that no matter what is specified in the event attribute list, it does not really has an effect. For this reason we decided to have the attribute name field in the ".event" table set to DC (DON’T CARE). And this DC value really conveys the message we want to have. In case of add / delete event handlers, we don’t care what the attribute is. This is the only difference between add/delete and change event handler storage in the system table ".event".

The above relation ".event" is how the table is stored on disk. But how is it stored in RAM?

4.1.2 The ".event" table in RAM

The ".event" table is stored as a hash table in RAM. The table is hashed on the system generated procedure name. As mentioned earlier, once an event handler is declared we first set the event attributes, next generate the system name for the procedure, and then store the event handler in the table.

 

figure 4.1 - the structure used to store an event in memory

figure 4.2 - .event table as it appears in memory

 

As can be noticed from the table, event handler entries are not stored in the order they are entered in. As explained in chapter 3, the order in which event handlers are entered does not imply that they will be called or stored in that order; this gives the non- determinism. On the contrary, they will be called in the order they are stored in the table. This will be explained more when the selection algorithm is discussed next.

4.2 Selection algorithms

Selection, as mentioned previously, is divided into parts: add / delete selection and change selection. We will discuss the algorithms for each next.

4.2.1 Add/delete selection

In the add/delete selection, we want to select all these event handlers which match the triggering event. Suppose we have the following Relix statement:

>update R add S;

where S is a relation with the same attributes as R. In this example we will assume that we have the event handlers defined above. The triggering event is an add update on relation R. Suppose we want to select all the pre event handlers which match the triggering event, we will apply the following algorithm:

procedure list = NULL

for all entries in .event table

if (PREFIX = "pre") and (RELATION = triggering event) and

(UPDATE TYPE = triggering event type) and (ACTIVE STATUS = "Y")

add PROCEDURE NAME to procedure list

return procedure list

After searching the table, the algorithm will return a list containing all those procedure names which matched our search attributes. Let us now see what will happen when we run this algorithm on the event above and the table we have. We will get the following list:

 

4.2.2 Change selection

The main difference between add/delete selection and change selection is that a change event handler will have a list of attributes. When selecting change event handlers we would like to select all those event handlers which are defined on the triggering event attribute list and any subset of those attributes.

Consider the relation .event defined in section 4.1.1:

 

.event (	.urel_name	.attr_name	.type_name	.prefix_name	.proc_name	.active_stat	.delete_stat )
	R	X	change	pre	10_1120	Y	N
	R	Y	change	pre	10_1120	Y	N
	R	X	change	pre	11_1120	Y	N
	R	Y	change	pre	11_1120	Y	N
	R	Z	change	pre	11_1120	Y	N
	R	X	change	pre	12_1120	Y	N
	R	Z	change	pre	12_1120	Y	N
	R	X	change	pre	13_1120	Y	N
	R	DC	add	pre	14_1120	Y	N
	R	DC	delete	pre	15_1120	Y	N
	R	DC	add	post	16_1120	Y	N
	R	DC	delete	post	17_1120	Y	N

If we are to do the selection using the relation .event as represented above as a flat relation, then we can perform selection using a s -join. As mentioned in chapter 2, s -joins are joins that are a generalization of logical operations on relation. In our case, the logical operation we want to perform is testing if a group of attributes is a subset of another. If that is the case, then we would like to return that group of attributes.

Consider that we have a relation attribute_list which is as follows:

attribute_list(	attribute_name)
	X
	Y

What we would like to do is find out all those procedures whose attribute list is a subset of the list in relation attribute_list, and who also match on the following attributes: pre, change, and R. In Relix we can perform this in the following way:

> procedure_names <- [.proc_name,.attr_name] where ( .urel_name = "R" and .type_name = "change" and .prefix_name = "pre") in .event;

this Relix statement will create a relation procedure_name which is as follows:

procedure_names(	.proc_name	.attr_name)
	10_1120	X
	10_1120	Y
	11_1120	X
	11_1120	Y
	11_1120	Z
	12_1120	X
	12_1120	Z
	13_1120	X

Now we can perform the following s -join to give us the result we desire:

> result <- attribute_list[.attr_name sup .attr_name]procedure_name;

relation result will be as follows:

result (	.proc_name)
	10_1120
	13_1120

The above method would have been perfect if the .event was represented as a flat relation in memory. Since it is not the case, we have developed the following algorithm to perform the change selection. The algorithm goes as follows:

procedure list = NULL

for all entries in the .event table

if (PREFIX = "pre") and (RELATION = triggering event) and

(UPDATE TYPE = triggering event type) and (ACTIVE STATUS = "Y")

and ( ATTRIBUE_LIST Ì triggering event attribute list )

add PROCEDURE NAME to procedure list

return procedure list

Let us see how the selection is done if we want to select pre event handlers for the following event:

>update R change X <- value1,Y <- value2;

tracing the algorithm with the input we have will give us the following:

The triggering event attribute list is: X and Y.

* Procedure 12_1120 has the following attribute list: X and Z.

is {X,Z} Ì {X,Y} ? No, then continue

* Procedure 11_1120 has the following attribute list: X,Y and Z.

is {X,Y,Z} Ì {X,Y} ? No, then continue

* Procedure 13_1120 has the following attribute list: X.

is {X} Ì {X,Y} ? Yes, then add 13_1120 to procedure list.

 

* Procedure 10_1120 has the following attribute list : X and Y.

is {X,Y} Ì {X,Y} ? Yes, then add 10_1120 to procedure list.

 

 

4.3 Setting events

Setting events to active or inactive is really quite simple. To implement this command, we have to introduce the following grammar:

set_event:

SET_EVENT_ON event_name

|

SET_EVENT_ON event_name ‘[’ event_attribute_list’]’

|

SET_EVENT_OFF event_name

|

SET_EVENT_OFF event_name ‘[’ event_attribute_list ‘]’;

Once one of these production rules is recognized, the following will be performed:

 

extract event attributes from event name

do a selection using these attributes ( returns procedure name list )

for each entry in the selected procedure name list

set the ACTIVE STATUS to requested state

So if we give the following command at the Relix prompt:

> eventoff post:delete:R

the above algorithm is applied and .event is changed as follows:

 

.event (	.urel_name	.attr_name	.type_name	.prefix_name	.proc_name	.active_stat	.delete_stat )
	R	X	change	pre	10_1120	Y	N
	R	Y	change	pre	10_1120	Y	N
	R	X	change	pre	11_1120	Y	N
	R	Y	change	pre	11_1120	Y	N
	R	Z	change	pre	11_1120	Y	N
	R	X	change	pre	12_1120	Y	N
	R	Z	change	pre	12_1120	Y	N
	R	X	change	pre	13_1120	Y	N
	R	DC	add	pre	14_1120	Y	N
	R	DC	delete	pre	15_1120	Y	N
	R	DC	add	post	16_1120	Y	N
	R	DC	delete	post	17_1120	N	N

4.4 Printing event handlers

Implementing the print event handlers command was also a straightforward problem. Since we already have a command which prints relations and procedures (pr!!), we only had to modify it to print event handlers. Event handlers are procedures and thus printing them should be the same as printing procedures. First we modified the pr!! command grammar from:

print_relation :

PRINT_REL ‘!!’ identifier

|

PRINT_REL ‘!’ identifier ;

to

print_relation:

PRINT_REL ‘!!’ event_name

|

PRINT_REL ‘!!’ event_name ‘[’ event_attribute_list’]’

|

PRINT_REL ‘!’ event_name

|

PRINT_REL ‘!’ event_name ‘[’ event_attribute_list’]’

|

PRINT_REL ‘!!’ identifier

|

PRINT_REL ‘!’ identifier ;

Now the pr!! command can accept a relation name, procedure name, or an event name. Once the translator detects that the pr command is followed by an event name, the following algorithm is executed:

extract event attributes from event name

do a selection using these attributes ( returns procedure name list )

for each entry in the selected procedure name list

execute print procedure function (already used with pr!!procedure_name)

4.5 Deleting event handlers

As mentioned before, event handlers are deleted by the system, not by the user. They are deleted if the relation they are defined on is deleted. But we perform this process in a batch mode rather than delete event handlers every time a relation is deleted. The way it is done is that once we exit Relix, we run our function which deletes event handlers. Deletion is not actual removal from the table but rather lazy deletion. That is, entries in the table are marked as deleted. The idea behind using lazy deletion is to reuse event handler names generated by the system. We reuse these names when a new event handler is inserted. Before generating a system name, we first check if there are any entries marked as deleted. If we find such an entry then we reuse the name.

The algorithm to perform deletion of event handlers goes as follows:

for each entry in .event table

if RELATION does not exist

delete procedure PROCEDURE NAME

mark entry as deleted

Now referring to the relation R which we have previously defined, suppose we issues a command to delete relation R:

>dr!!R

then we exit Relix

>q!!

then we will run the above algorithm and .event will change to be as follows:

 

 

.event (	.urel_name	.attr_name	.type_name	.prefix_name	.proc_name	.active_stat	.delete_stat )
	R	DC	change	pre	10_1120	Y	Y
	R	DC	change	pre	11_1120	Y	Y
	R	DC	change	pre	12_1120	Y	Y
	R	DC	change	pre	13_1120	Y	Y
	R	DC	add	pre	14_1120	Y	Y
	R	DC	delete	pre	15_1120	Y	Y
	R	DC	add	post	16_1120	Y	Y
	R	DC	delete	post	17_1120	Y	Y

4.6 Concurrency control

Since Relix is a multi-user relational database, we had to make sure that the .event system table is always up to date so that all users can have the same information presented to them. We have taken care of concurrency control by way of comparing the time stamp of the physical copy of the .event table. Once a user starts Relix, the time stamp of the .event table is recorded. If the user wishes to perform any operation on the table, then, before consulting the table, the system will compare the recorded time stamp with the current physical time stamp. If they do not match, then, before performing any operation on the table, it is reloaded from disk. By reloading, we ensure that the user is always consulting the updated copy of the table.

In addition to reloading the table, whenever a user is performing an operation on the table (inserting, writing, reloading, setting, selecting, or deleting) a system lock is activated. By activating the system lock, we can ensure that a user cannot insert new event handlers while another is selecting etc. . The system lock is released when the operation is completed.

4.7 Putting things together

In this section, we will explain the changes we made to the interpreter in order to support detection and handling of events. First, let us see how procedure calls are executed. As mentioned in chapter 2, the procedure is compiled to generate the intermediate code. Then the intermediate code is stored in a file. Once a procedure call is encountered, the interpreter will call a function called proc_call. proc_call does checking on the procedure parameters and then passes the procedure intermediate code to the interpreter, by calling the interpreter once again. Doing this is indirect recursion of the Relix interpreter. The key to our implementation is recursion.

 

 

 

 

Figure 4.3

procedure call execution (dotted line shows indirect recursive call to the interpreter) .

 

Having recursion in mind, we can proceed to explain the modifications made to the interpreter.

Event handlers were implemented for the update statement, so we had to modify only that part of the interpreter which deals with updates. In the interpreter, updates are divided into two groups, add/delete and change. Our implementation for both groups is almost the same. The only difference is in the selection process. For the add/delete group, we perform add/delete selection and for the change group we perform a change selection.

The first problem to solve is creating the TRIGGER relations. Since our implementation supports nested event handlers, this implies that a new TRIGGER relation can be created before we are done with the current one. So in this case we have to remember what the old TRIGGER relation was. This was accomplished by using a stack to store TRIGGER relation names. Once a relation is determined to be the TRIGGER relation, a copy of that relation is made and called "TRIGGER" and its name pushed on a stack. If we have nested event handlers, every time we move to a new level of nesting the current TRIGGER relation is pushed on the stack. Once that level is finished, the TRIGGER is popped off the stack and the previous level TRIGGER is restored.

Solving the trigger problem, we move to the second problem, selecting the proper event handlers. We have to determine which event handlers are to be executed pre and post executing the triggering event. First we determine the type of the triggering event (add, delete, change), then perform two event handler selection operations (pre and post). After obtaining the pre and post event handlers, the interpreter will call all pre event handlers, then execute the triggering event and finally call all post event handlers.

Since each call to execute an event handler is an indirect recursive call to the interpreter, and an event handler can have statements which in turn have their own event handlers, then we can achieve nesting easily.

In our implementation we only built a layer surrounding the existing update code. No modification was made to the update algorithms.

 

 

 

 

 

 

 

 

 

Figure 4.4 New layers added

The algorithm:

determine TRIGGER relation name

push TRIGGER relation name on trigger_stack

create TRIGGER relation

pre list = select pre event handlers

for each PROCEDURE NAME in pre list

call PROCEDURE NAME

execute triggering event {existing update algorithms}

post list = select post event handlers

for each PROCEDURE NAME in post list

call PROCEDURE NAME

delete TRIGGER relation

pop TRIGGER relation name from trigger_stack

if trigger_stack is not empty

restore previous TRIGGER relation {in case of nested event handlers and indirect recursive calls to the interpreter}

The algorithm is simple and straight forward. We just encapsulated the existing update code with the code needed to support detection and execution of event handlers. An example explaining how this algorithm works was presented in section 3.7.

 

 

Chapter 5

 

 

 

Conclusion

In this chapter we will first summarize the work presented in this thesis. Then we will compare our work with active database literature presented in chapter one. Finally we will present some ideas for future work on event-handlers in Relix.

5.1 Conclusions

We have used Relix procedures to perform event programming in Relix. By a simple modification to the procedure definition in Relix, we were able to use procedures to define event handlers. Also, we presented easy and straightforward syntax for event handler definition, activation, deactivation, and printing. We have demonstrated that, as in event-driven programming environments, event programming is also possible in database programming languages by using procedures, and that an event-handler is nothing more than a procedure invoked by a system generated call. Finally, we have showed that event programming in database systems can be accomplished in any procedural environment.

5.2 How does our model compare to the EA model

In this section, we will show how our model compare to the EA and ECA models. We will prove that by using our event specification mechanism we are able to implement the event operators specified in the EA model.

At the current stage of implementation, we only support basic event specification. We can define event handlers for the Relix update statements. But additional basic events can be incorporated in our implementation easily. Event handlers can be specified to be executed pre or post the occurrence of an event. This specification is similar to the before and after specification in the EA model.

Our current implementation of event handlers lacks a condition part when specifying an event handler. The reason for the absence of the condition is that the work done in this thesis was implemented on a version of Relix that does not support conditional statements. A more recent version of Relix which incorporates an "IF" statement has been introduced. Once both implementations of event handlers and conditional statements are incorporated, the condition part of the event handler can be incorporated easily in event handler definition. The "IF" statement in Relix has the following syntax:

IF relational-expression THEN

statements

ELSE

statements

ENDIF

Here the relational-expression is evaluated and if it returns a non empty result, then the condition is satisfied and the statements are executed. The ELSE part is optional.

The event handler definition will be modified to be as follows:

proc event-name () is

{

IF relational-expression THEN

statements

END IF

};

In such a definition, the condition part will be folded with the action part instead of the event part as in the EA model. This implies that in our model we do not have the various coupling modes suggested by the ECA model, and hence we do not provide for process and concurrency control in our implementation.

In our implementation, event handlers are executed in the following manner : once an event is detected, the appropriate event handlers are selected and fired immediately before the event is executed (pre-event handlers) or after the event is executed (post-event handlers). There exists one coupling mode in our implementation, namely immediate. The EA execution model described in chapter 1 is similar to our execution model provided we include transaction control. Relix does not support transaction control at its current stage of implementation. But if transaction control is implemented in Relix, event handlers are to be executed in the same transaction which detected the event. In case a transaction fails, then should we undo the effects of the event handlers fired by the transaction?

This question was addressed by the EA model and the answer depends on whether the implementation would present history of events as the "true" history (i.e. the history which records all operations including aborted ones) or as the "real" history (i.e. the history which records only actions that have been done successfully). In our implementation we suggest addressing this issue in the following manner : event handlers defined outside a transaction can be fired by events inside a transaction, but are not considered to be part of the transaction. Event handlers defined inside a transaction are considered as part of the transaction. If the transaction fails their effects should be undone.

By incorporating transaction control into Relix, we would be able to expand the set of basic events to include transaction events. Such events might be:

tran_begin : transaction begin

tran_end : transaction end

tran_commit : transaction commit

tran_abort : transaction fail

Having these basic events, we would be able to specify such events as:

pre:tran_begin : before transaction begin

post:tran_begin : after transaction begin

pre:tran_commit : before transaction commit

Using our implementation of event handlers, we are able to implement the following event composition operators specified by the EA model: sequence, prior, fa, and faAbs.

We will start by defining the "prior" operator. As defined in the EA model, prior( R, S) is the occurrence of event R prior to the occurrence of event S. Using our implementation, we can define prior in the following way: define an event handler for S inside event handler for R, containing the associated action, and deactivating the S event handler.

proc R_event_handler () is

{

. . .

proc S_event_handler ()

{

statements

eventoff S_event_handler;

};

};

Now the event operator fa ( R, S, Q) is defined to be the first occurrence of event S relative to an event R, with no intervening event Q relative to R taking place. We define

fa (R, S, Q ) = prior (R, S) and event handler for event Q which deactivates event S.

 

 

 

proc Q_event_handler () is

{

. . .

eventoff S_event_handler;

};

 

 

proc R_event_handler ()

{

. . .

proc S_event_handler ()

{

statements

};

};

faAbs (R, S, Q) which is similar to fa but where Q is relative the beginning of the event history, is defined as:

faAbs (R, S, Q) = prior (R, S) and event handler for event Q which deactivates event R

proc Q_event_handler ()

{

. . .

eventoff R_event_handler;

};

proc R_event_handler ()

{

. . .

proc S_event_handler ()

{

statements

};

};

sequence (R,S) which is defined as the occurrence of event S immediately after event R can be defined as:

sequence (R, S) = fa (R, S, Q) for all events Q

Being able to define the fa operator in our implementation, and having transaction events incorporated in Relix, we would be able to define the different coupling modes introduced by the ECA model and implemented in the EA model using the fa operator (section 1.6.1).

In our implementation of event handlers we are able to specify basic events. As mentioned above a version of Relix with an IF statement is being developed. Once the two versions of Relix are incorporated together, we would be able to specify logical events by adding a condition to the action specification. As far as composite logical events are concerned, the current implementation can not handle them. But if an event history file is constructed, then composite events can be detected by simply consulting the event history file. In addition, the event specification mechanism must be extended to enable the user to specify composite events. Time events (at, every, and after time) can also be added easily. Composite events, and time events, need a more flexible storage mechanism than the one currently used. The .event table must be modified in such a way so that it can store any type of event.

Other event specification operators : relative, choose, and every are not possible with the current implementation. But once an event history file is constructed, implementing these operators would be possible. As defined in the EA model relative(R,S), implies that the last logical event of R occur before the first logical event of S. Having an event history file would allow us to determine such a relationship between R and S. As for every and choose, their implementation is also possible if an event history file is present. For all these implementations to be possible a more elaborate event detector module has to be built. This event detector must be always running, and once an event occurs (basic, logical, or composite) it must determine and fire all the appropriate event handlers.

As discussed in chapter 1, the EA model is equivalent to the ECA model. As we have shown in this section, our implementation, with some proposed additions, is an EA model implementation. Thus our model is capable of performing as the EA model and, hence the ECA model.

 

 

5.3 Future work

In this section, we will present some ideas which we think are worth further investigation. First, we will discuss assigning priority to rules. Then we will move on to discuss transactions in Relix.

5.3.1 Rules and priorities

The rule system we have implemented is a non-deterministic rule system. One of the reasons our system is non-deterministic is that once an event is detected, rules are executed without allowing the user to specify the order of execution. It is argued that non-deterministic rule systems tend to be complex. One-way of eliminating this non-determinism is by assigning priorities to rules. The POSTGRES system used a 15 point priority system [SHP88]. In POSTGRES, rules have priority 0 by default. If a user assigns a higher priority to a rule, then at execution time the rule with highest priority is executed first. Also, in [ACL91], a formalism for a priority system is presented.

What we propose is a method of assigning priorities to Relix rules. We suggest that by default, all rules have a minimum priority set to 0. However, this priority can be over ridden by a user defined priority. One way of doing so is by modifying the event specification, i.e., by modifying the event name to include an optional priority. For example:

proc pre:add:R[X,Y]:9 () is

{

statements;

};

will mean that we will assign priority 9 to this event handler. The priority part of the event name would be optional. Skipping it would mean that the event handler is assigned the default priority 0.

In addition, we should allow a facility that would allow the user to modify the priority of a rule if the need arises. Here we might face a small problem. Our rule system is a one-to-many rule system (i.e., one event can be associated with more than one event handler). To overcome this problem, we should provide a mechanism by which the user can pinpoint an individual event handler and change its priority. In other words, the user must be able somehow to determine all event handlers associated with a single event and be able to select an individual event handler and modify its priority.

As far as execution is concerned, no change for the selection algorithms would be required. After selection is performed, the list of selected event handlers should be sorted in decreasing order. This sorting should allow the interpreter to fire the rules by order of priority. If more than one event handler have the same priority, then they will be executed in a non-deterministic way.

One benefit of assigning rules is that the user would be able to define an event handler which relies on the results of another event handler which is higher in priority. For example, assume we define the following event handlers:

proc event_name_1:10 ()

{

update R add TRIGGER;

E1_R <- R ijoin T;

};

proc event_name_2:5 ()

{

update E1_R delete TRIGGER;

};

In this example, event_name_2 can use a relation created in event_name_1. In case event_name_2 is executed before event_name_1, then the relation E1_R would not be available yet. With assigning a higher priority to event_name_1 we ensure that it would be executed and any relations it produces are available for use by lower priority rules.

 

5.3.2 Transaction control

The current implementation of Relix does not support the concept of a transaction. The lack of such a concept implies that when executing a set of statements which form an atom, then a failure in one of them would result is the failure of the operation being performed, and, in addition, all statements executed before the fail point would have become permanent and cannot be undone.

As mentioned in the previous section, event handlers defined inside a transaction are part of that transaction, while event handlers defined outside a transaction, can be called in the transaction, but their effects are not part of the transaction.

We suggest that a transaction be defined by using some mechanism which groups statements together. Statements can be grouped together using "begin_tran" and "end_tran" keywords as follows:

begin_tran

{

statements

} end_tran

Once the interpreter detects a "begin_tran" and "end_tran" it should determine all relations used in the block of statements and do the following:

impose write locks on all these relations, copy the relations and execute the grouped statements on the copies. If "end_tran" is reached and all operations are successful, copy the tables back, commit the changes, and release the write lock. Here commit of a transaction is implied by finishing successfully. The need also arises for a statement which will abort the transaction and ignores its effects. A "abort_tran" command can be used to accomplish this. An "abort_tran" would imply that once such a command is encountered, all statements defined after it (with in a block ended with an "end_tran") are skipped, changed relations are not copied back, and write locks are released.

 

The advantages of such method are the following:

• it will work on a multi-user system
• we have the ability to perform a roll back
• we use only copies of the needed relations

The disadvantages are:

• only one user can update a relation at a time until she/he commits and releases all locks

5.3.3 Fake updates

Fake updates is a feature of Relix not implemented yet. A fake update is one which triggers any demon watching over the relation indicated for update, without ever updating the relation. This feature can be implemented by using event handlers. In the Oracle DBMS [ORA94], triggers are of three types: pre, post, and on update. The "pre" and "post" triggers operate in a similar way to the pre and post triggers presented in this thesis. The "on" trigger works as follows: once the triggering event is detected then instead of executing the event, execute its event handler. We propose the implementation of an "instead" event handler which operates in a similar way to the Oracle "on" event handler. For example if we have the following update statement:

update R add S;

and we define the following event handler:

 

proc instead:update:add:R () is

{

statements;

};

Once the update to R is detected, instead of adding S to R, call the defined event handler.

It might be argued that using the instead event handler might cause the same code to be written twice. The user has to write the event handlers for update statement itself and, then she/he might write another set of event handlers for the instead event handler. Here the instead event handler is not the same event as the update statement, and thus its event handlers would be different.

Appendix A

Syntax

 

 

 

 

 

The syntax for the update statement is as follows:

update_statement :

update_first update_last_1

|

update_first '[' domain_option update_last_2

update_first :

UPDATE identifier

update_last_1 :

ADD relational_expression

|

DELETE relational_expression

|

CHANGE dom_pair_option using_option

update_last_2 :

ADD relational_expression_right

|

DELETE relational_expression_right

using_option :

/* empty */

|

USING join_option relational_expression

|

USING '[' domain_option join_non_empty relational_expression_right

 

 

join_option :

/* empty */

|

join_non_empty

join_non_empty :

join_mode

dom_pair_option :

dom_pair_list

|

/* empty */

dom_pair_list :

domain_pair ',' dom_pair_list

|

domain_pair

domain_pair :

identifier ASSIGN domain_expression

join_mode :

I_JOIN | U_JOIN | L_JOIN | R_JOIN | S_JOIN |

DL_JOIN | DR_JOIN | IE_JOIN | I_COMP | EQ_JOIN |

NEQ_JOIN | LT_JOIN | NLT_JOIN | LE_JOIN | NLE_JOIN |

GT_JOIN | NGT_JOIN | GE_JOIN | NGE_JOIN

relational_expression_right :

domain_option ']' relational_expression

domain_option :

/* empty */

|

domain_list

domain_list :

domain_list ',' domain_expression

|

domain_expression

relational_expression is not reduced any further and it can be any Relix relation combined with any of the unary or binary operators of the relational algebra.

The following are valid update statements :

update SALARY add NEW_SALARY;

update SALARY delete NEW_SALARY;

update SALARY change NAME <-"JOHN", AMOUNT<-11500;

update SALARY change AMOUNT<-15500 using NEW_SALARY;

update SALARY change AMOUNT<-9500 using djoin NEW_SALARY;

 

The syntax for procedure declarations and procedure related commands is as follows:

procedure_declaration :

P_DEC identifier '(' procedure_parameter_list ')' IS procedure_body

procedure_parameter_list:

/* empty */

|

procedure_parameters

procedure_parameters:

identifier ;

|

procedure_parameters ',' identifier

procedure_body:

procedure_block

|

procedure_body ALT procedure_block

|

/*empty*/

procedure_block:

'{' procedure_statements '}'

procedure_statements:

procedure_one_statement

|

procedure_statements procedure_one_statement

procedure_one_statement:

procedure_statement ';'

|

procedure_command

 

 

 

procedure_statement:

procedure_domain_declaration /* domain ... */

|

procedure_relation_declaration /* relation ... */

|

procedure_definition_statement /* let ... */

|

procedure_executable_statement

|

procedure_update_statement /* update ... */

|

procedure_call

procedure_domain_declaration:

DOMAIN_DEC identifier TYPE

procedure_relation_declaration:

RELATION_DEC identifier '(' attribute_list ')' rcp_ln_option

procedure_definition_statement:

LET identifier BE domain_expression

|

LET identifier INITIAL domain_expression BE domain_expression

procedure_executable_statement:

identifier

|

identifier ‘{ 'constant_list '}’ ASSIGN relational_expression

|

name_valued_expression ASSIGN relational_expression

|

name_valued_expression INCREMENT relational_expression

|

renaming_increment_left ASSIGN domain_option ']'

relational_expression

|

renaming_increment_left INCREMENT domain_option ']' relational_expression

|

name_valued_expression nest_operator identifier

|

renaming_increment_left domain_option nest_operator

domain_option ']' identifier

 

procedure_update_statement:

procedure_update_first update_last_1

|

procedure_update_first '[' domain_option update_last_2

procedure_update_first:

UPDATE identifier

procedure_command:

DEL_DOM

|

DEL_REL

procedure_call:

identifier procedure_actual_parameter_option

procedure_actual_parameter_option:

'(' procedure_actual_parameter_list ')'

|

LT procedure_actual_parameter_list GT

procedure_actual_parameter_list:

/* empty */

|

procedure_actual_parameters

procedure_actual_parameters:

procedure_actual_one_parameter

|

procedure_actual_parameters ',' procedure_actual_one_parameter

procedure_actual_one_parameter:

IN identifier

|

OUT identifier

|

IN

|

OUT

 

 

 

 

The following are example of procedure declarations :

proc p() is

{

domain X intg;

domain Y intg;

relation R (X, Y) <- { (1, 11), (2,22), (3,33) };

update R delete where X=2 in R;

};

 

proc p (A,B,C,R) is

{

domain A intg;

domain B intg;

domain C string;

relation R (A,B,C) <- { (1, 11, "a"), (2, 22, "b"), (3, 33, "c") };

update R delete where A=2 in R;

};

proc p (A, B, C) is

{

A <- B ijoin C;

}

alt

{

let C be A * 10;

let B be red+ of C;

R <- [B] in ([C] in S);

};

References

 

 

 

 

 

 

[ACL91] R. Agarwal, R. Cochrane, and B. Lindsay. On Maintaining Priorities in a Production Rule System. Proceedings of the 17th VLDB Conference, Barcelona , Spain 1991, 479-487.

[AG89] R. Agarwal and N. H. Gehani. Ode (Object Database and Environment) : The Language and the Data Model. Proceeding of ACM SIGMOD , Portland, Oregon 1989, 36-45.

[ASU86] A. Aho, R. Sethi and J. Ullman. Compilers : Principles, Techniques, and Tools . Addison-Wesley, 1986.

[BZ+95] A. Buchmann, J. Zimmermann, J. Blakeley, and D. Wells. Building an Integrated Active OODBMS : Requirements, Architecture, and Design Decisions. Proceedings of the Eleventh International Conference on Data Engineering, March 1995, Taipei, 117-128.

[CHA93] S. Chakravarthy. A Comparative Evaluation of Active Relational Database. Tech. Report UF-CIS-TR-93-002, 1993.

[COD70] E.F. Codd. A relational model for large shared data banks. CACM, 13(6):377-387, 1970.

[DAY88] U. Dayal. Active Database Management Systems. Conference on Data and Knowledge Bases, Jerusalem, 1988, 150-169.

[DB+88] U. Dayal, B. Blaustein, A. Buchmann, U. Chakravarthy, M, Hsu, R. Ledin, D. McCarthy, A Rosenthal, and S. Sarin. The HiPAC Project : Combining Active Databases and Timing Constraints. SIGMOD Record, Vol. 17, No. 1, March 1988, 51-70.

[DEL95] Borland Delphi for Windows, User’s Manual. Borland International, Inc., 1995.

 

[DHL90] U. Dayal, M. Hsu, and R. Ladin. Organizing Long-Running Activities with Triggers and Transactions. Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, N.J., 1990, 204-214

[DHL91] U. Dayal, M. Hsu, and R. Ladin. A Transactional Model for Long- Running Activities. Proceedings of the 17th VLDB Conference, Barcelona, Spain 1991, 113-122.

[DM94] B. Defude and H. Martin. From a Passive to an Active Database Supporting Exceptions. Proceedings of the 5th International Conference, DEXA ‘94, Athens, Greece, September 1994, 360-369.

[GGD91] S. Gatziu, A. Geppert, and K. Dittrich. Integrating Active Concepts into an Object-Oriented Database System. Database Programming Languages : Bulk Types & Persistent Data. The 3rd International Workshop, Nafplion, Greece 1991, 399-415.

[GJ91] N. H. Gehani and H.V. Jagadish. Ode as an Active Database : Constraints and Triggers. Proceedings of the 17th VLDB Conference, Barcelona, Spain, 199, 327-336.

[GJS92a] N. H. Gehani, H.V. Jagadish, and O, Shmueli. Composite Event Specification in Active Databases : Model & Implementation. Proceedings of the 18th VLDB Conference, Vancouver, British Columbia , Canada 1992, 327-338.

[GJS92b] N. Gehani, H. Jagadish, and O. Shmueli. Event Specification in an Active Object-Oriented Database. Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, San Diego, California, 1992, 81-90.

[GH+93] S. Ghandeharizadeh, R. Hull, D. Jacobs, J. Castillo, M. Escobar- Molano, S. Lu, J. Luo, C. Tsang, and G. Zhou. On Implementing a Language for Specifying Active Database Execution Models. Proceeding of the 19th VLDB Conference , Dublin, Ireland 1993, 441- 454.

[GR93] Jim Gray and Andreas Reuter. TRANSACTION PROCESSING : CONCEPTS AND TECHNIQUES. Morgan Kaufmann Publishers, Inc., San Mateo, CA, 1993.

[HJ91] Richard Hull and Dean Jacobs. Language Constructs for Programming Active Databases. Proceedings of the 17th VLDB Conference, Barcelona, Spain, 1991, 455-467.

[HLM88] M. Hsu, R. Ladin, and D. McCarthy. An Execution Model for Active Data Base Management Systems. Conference on Data and Knowledge Bases, Jerusalem, 1988, 171-179.

[IK93] H. Ishikawa and K. Kubota. An Active Object-Oriented Database : A Multi-Paradgim Approach to Constraint Management. Proceeding of the 19th VLDB Conference , Dublin, Ireland 1993, 467-479.

[JOH78] S. C. Johnson. YACC - Yet Another Compiler Compiler, Bell Laboratories CSTR 32, 1978.

[KOM92] Maria Komioti. Implementation of Process Synchronization in a Database Programming Language. Master’s thesis, McGill University, Montreal, Canada, 1992.

[KR78] Kernighan, B. W. and Ritchie D. M. . The C Programming Language. Prentice-Hall, 1978.

[KP84] Kernigham, B. W. and Pike, R. . The UNIX Programming Environment. Prentice-Hall, 1984.

[LES75] M. E. Lesk. LEX - A Lexical Analyzer Generator, Bell Laboratories CSTR 39, 1975.

[LAL86] Normand Laliberte. Design and Implementation of a Primary Memory Version of Aldat. Master’s thesis, McGill University, Montreal, Canada, 1986.

[MB90] Tony Mason, Doug Brown . Lex & Yacc . O’Reilly, Sebastopol, CA 1990.

[MD89] D. McCarthy and U. Dayal. The Architecture Of An Active Data Base Management System. Proceeding of ACM SIGMOD , Portland, Oregon 1989, 215-224.

[MER77] T.H. Merrett. Aldat - Augmenting the Relational Algebra for Programmers. Technical Report SOCS 78.1, Department of Computer Science, McGill University, November 1977.

[MER84] T.H. Merrett. Relational Information Systems. Reston Publishing, Reston, Virginia, 1984.

 

 

[MK91] Merrett, T.H. and Khalife, B. . Geographical information systems development using a general purpose database programming language. Technical Report TR-SOCS-91.2, Department of Computer Science, McGill University, February 1991.

[MOR83] M. Morgenstern. Active Databases as a Paradigm for Enhanced Computing Environments. International Conference on VLDB, New York, N.Y. ,1983, 34-42.

[MOS85] J. Eliot Moss. Nested Transactions : An Approach to Reliable Distributed Computing. The MIT Press, Massachusetts, 1985.

[MS88] M. Swaine. Dr. Dobb’s essential HyperTalk Handbook. M&T Publishing, Inc., Redwood City, California, 1988.

[MT95] D. Montesi and R. Torlone. A Transaction Transformation Approach to Active Rule Processing. Proceedings of the Eleventh International Conference on Data Engineering, March 1995, Taipei, 109-116.

[MUE94] Thomas A. Mueck. Active Databases : Concepts and Design Support. Advances in Computers, Vol. 39, Acadamic Press Inc., 1994, 107-189.

[NI94] W. Naqvi and M. Ibrahim. EECA : An Active Knowledge Model. Proceedings of the 5th International Conference, DEXA ‘94, Athens, Greece, September 1994, 380-389.

[ORA94] CDE2 : Forms Reference Manual, Oracle Corporation, Volume 1, 215- 231.

[PLA91] P. J. Plauger. The standard C library. Prentice-Hall PTR, 1991. ISBN

0-13-131509-9.

[RCB89] A. Rosenthal, S. Chakravarthy, and B. Blaustein. Situation Monitoring for Active Databases. Proceedings of the 15th International Conference on VLDB, Amsterdam, 1989, 455-464.

[RT78] Ritchie, D. M. and Thompson, K. L. . The Unix Programmer’s Manual, Bell Laboratories, 1978.

[RSL95] Rebecca S. Lui. Implementing Procedures in a Database Programming Language. Master’s thesis, McGill University, Montreal, Canada. 1996.

[SAH87] M. Stonebraker, J. Anton, and E. Hanson. Extending a Database System with Procedures. ACM Transactions on Database Systems, Vol. 12, No.3, September 1987, 350-376.

[SHP88] M. Stonebraker, E. Hanson, and S. Potamianos. The POSTGRES Rule Manager. IEEE Transactions on Software Engineering, Vol. 14, No. 7, July 1988, 897-907.

[SK+94] J. Sayles, S. Karlen, P. Molchan, and G. Bilodeau. GUI-BASED DESIGN AND DEVELOPMENT FOR CLIENT/SERVER APPLICATIONS. John Wiley and Sons, Inc., New York, 1994.

[SKM92] E. Simon, J. Kiernan, and C. de Mainderville. Implementing High Level Active Rules on top of a Relational DBMS. Proceedings of the 18th VLDB Conference, Vancouver, British Columbia, Canada 1992, 315-326.

[SPM91] U. Schrrier, H. Pirahesh, R. Agrawal, and C. Mohan. Alert : An Architecture for Transforming a Passive DBMS into an Active DBMS. Proceedings of the 17th VLDB Conference, Barcelona , Spain 1991, 469-478.

[SR86] Michael Stonebraker and Lawrence A. Rowe. The Design of POSTGRES. Proceedings of the ACM SIGMOD 1986 International Conference on Management of Data. Washington , D.C. , 1986, 340- 355.

[TSA87] Maria Tsakalis. Implementing QT-Selectors and Updates for a Primary Memory Version of ALDAT. Master’s thesis, McGill University, Montreal, Canada. 1987.