Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-03-29
2004-04-13
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06721725
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to executing triggers in active relational databases and more specifically to the concurrent execution of after-triggers in a relational data base management system.
DESCRIPTION OF THE RELATED ART
Database management systems (DBMS)
11
, such as the system shown in
FIG. 1
, have become the dominant means of keeping track of data, especially for servers connected to the Internet. These systems take an organized approach to the storage of data by imposing a data model, typically a relational data model, on the data
17
that is stored in the database
15
. Included in the typical DBMS are a Query Processing Engine
13
, a File Access and Storage Management subsystem
21
for accessing the database
15
, a Concurrency Control subsystem
19
for managing locks needed for concurrency on database items (tables and rows) and a Recovery Control Subsystem
23
for restoring the DBMS
23
to a consistent state after a fatal error. The latter two subsystems
19
,
23
, are interconnected with the File Access and Storage Management subsystem
21
.
In the relational data model, data is stored as a relation, which has two aspects, the relation schema and the relation instance. The relation schema specifies the relation's name, and the name and domain of each column in the relation. The relation instance is a set of records (also called rows or tuples) that conform to the relation schema. A relation instance is therefore a table of records, each of which has a column that meets the domain constraints imposed by the schema.
Not only does the DBMS impose a constraint on storage of data, a DBMS usually formalizes the means by which information may be requested from the database. In particular, a query language is specified by which questions may be put to the database. The language is usually based on a formal logic structure such as relational algebra or calculus. Queries are usually carried out in the DBMS
11
by a Query Processing Engine
13
, which has a number of components for parsing a query, creating a query plan, and evaluating the query plan. In particular, a component of the Query Processing Engine
13
, a Query Optimizer, creates one or more query plans, each in the form of a tree of relational operators, that are evaluated for execution of the query based on some efficiency metric.
Relational operators take one or more tables as inputs and generate a new table as the output. For example, a selection operator selects one or more rows of an input table meeting the selection criteria to produce an output table having only those rows. Operators can be composed since an operator may take as input a table generated as the output of another operator. A tree of operators is the representation of a composition of the relational operators appearing as the nodes of the tree.
A tree of such operators for a particular query plan is shown in FIG.
3
. As can be observed from the tree of
FIG. 3
, relational operators are connected to each other and to base tables T
1
and T
2
by means of queues Q
1
-Q
4
. These queues supply input rows to a particular operator and store output rows from the operator. The queues allow an operator to start processing rows as soon as the operator that supplies the rows begins to produce them and before all rows are produced. Such pipelining improves the efficiency of the system because intermediate results need not be stored in a temporary table and then read again for input.
The standard language for implementing a DBMS is the Structured Query Language (SQL). This language includes Triggers, which are actions executed by the DMBS under certain conditions.
A database having a set of triggers is called an active database and each trigger in the database has three parts, an event, a condition and an action. The event part is a change to the database, such as an insertion, deletion, or modification of a table, that activates the trigger. The SQL statement which is the activating event, is termed the activating statement. A condition is a test by the activated trigger to determine whether the trigger action should occur and an action is an SQL statement that is executed if the trigger event and trigger condition are both satisfied. The set of rows affected (i.e., inserted, updated, or deleted) by the activating statement is termed the affected set of rows for the relevant trigger.
The action part of the trigger can occur either before or after the activating statement. If before, it is called a before-trigger and if after, it is called an after-trigger. In addition, triggers can operate at the row level or the statement level. A statement trigger executes its action once per activating statement and a row trigger executes its action for each row in the affected set. The combination of “before” and “after” with “row” and “statement” creates four different types of triggers. Chain reactions of trigger actions and recursive trigger actions are also possible.
The execution of triggers in a relational database is governed by the proposed ANSI standard for SQL (SQL:1999) which places certain restrictions on trigger execution. A chief restriction is that the triggers be executed serially in their creation time order or at least that the serial execution of triggers be equivalent in outcome and effect on the database to the execution of triggers in their creation time order. However, the serial execution of triggers, in accordance with the proposed ANSI:99 standard, would seriously affect the performance of the DMBS, especially if many trigger actions are involved. Thus, there is a need for the improved execution of multiple trigger actions which leads to improved performance of trigger actions over a purely sequential execution, but still conforms to the ANSI standard.
BRIEF SUMMARY OF THE INVENTION
The present invention is directed towards the above need. A method of forming an execution plan in accordance with the present invention includes the following steps. First, any triggers that may be activated by an activating statement and any rows in database tables that are affected by the activating statement are determined. An operator tree for the activating statement is then formed and a tree for the trigger that is activated by the activating statement is formed. The activated trigger is either a row-after trigger or a statement-after trigger. If the activated trigger is a row-after trigger, the tree for the row-after trigger is joined to the operator tree for pipelined execution with the operator tree and any rows affected by the activating statement are pipelined to the row-after trigger for input. If the activated trigger is a statement-after trigger, the tree for the statement-after trigger is joined to the operator tree for execution subsequent to the operator tree. The statement-after trigger obtains input during execution from a temporary table that accumulates affected rows from the execution of the activating statement.
If a plurality of row-after triggers is activated by the activating statement, each of the trees for the row-after triggers is joined to the operator tree for pipelined execution with the operator tree. In one embodiment, the plurality of trees for activated row-after triggers is connected to a parallel union operator to form a group and a flow operator is interconnected between the parallel union operator and the operator tree.
If a plurality of statement after triggers is activated by the activating statement, each of the statement-after trigger trees is joined to the operator tree for execution subsequent to the execution of the operator tree. In one embodiment, the activated statement-after actions are connected to a parallel union operator to form a group, a flow operator is interconnected between the operator tree and a temporary table that accumulates affected rows from the operator tree and an ordered union operator is interconnected between the parallel union operator and the flow operator.
Joining both a plurality of activated row-after triggers and a plurality of stat
Ben-Zvi Boaz
Levy Eliezer
Peleg Nitzan
Sherman Yuval
Hewlett--Packard Development Company, L.P.
Mizrahi Diane D.
Wu Yicun
LandOfFree
Method of parallel trigger execution in an active database does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of parallel trigger execution in an active database, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of parallel trigger execution in an active database will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3213302