US 5,535,385 AGrant
Dealing With Side Effects of Transactions in Data Base Systems Using a Multi-Set Algebra
Issue Date:1996-07-09
•37 Claims
•6 Drawing Sheets
Abstract
Apparatus and methods for reducing the amount of computation required to determine the consequences of a side effect resulting from a transaction on a relation in a data base system. The apparatus and methods use equational reasoning based on a bag algebra representation of a class of transaction and the relation to produce a pre-expression which describes the side effect. The pre-expression is included in the data base system's data dictionary, and when a transaction of the class is received in the data base system, the pre-expression is used to determine the side effect. The pre-expression is formed with a strongly-minimal pair of delete and insert bags. The apparatus and methods may be used to maintain materialized views, to check for violation of constraints on the data base, and to activate triggers, monitors, and active queries.
Metadata
Assignee
- AT&T Corp.
Inventors
- Timothy G. Griffin
- Leonid Libkin
Application Information
Application Number:US 4444671
Filing Date:1995-05-19
Priority Date:1995-05-19
Art Unit:237
Classifications
IPC:
G06F 1730
Field of Search:
395600
Patent Drawings (6 sheets)
Description
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention concerns data base system generally and more specifically concerns side effects of transactions in data base systems.
2. Description of the Prior Art
A popular type of data base system is the relational data base system, in which the data in the data base is logically organized into relations, that is, tables with rows and columns. When a user of a data base system wishes to obtain information from it, the user makes a query, which describes the information to be obtained in terms of relations, columns, and limitations on the values of the columns in individual rows. The result of the query is another relation, which is termed a view. The relations from which the view is computed are termed the base relations of the view. If the view is in turn used as a base relation in the computation of a second view, the computation of the second view may be speeded up by materializing the view, that is, storing it in the data base system, rather than recomputing it each time it is used as a base relation.
In addition to querying data bases, users often add information to the data base and delete information from the data base. Adding or deleting information is termed a transaction. Of course, when a transaction changes a relation which is a base relation for a materialized view, the materialized view may need to be changed as well. One way of changing the materialized view is to recompute it from the base relations, but the whole point of the materialized view is to avoid recomputation. The problem of finding ways of updating materialized views without completely recomputing them is termed in the art the view maintenance problem.
Materialized views are however not the only components of data base systems which are affected by changes in base relations. Many data base systems have components which monitor changes in the data base and take actions if certain changes occur. Included among these components are integrity constraints, that is, rules for preventing transactions which are inconsistent with some property of the data base, monitors, which notify the user when certain changes occur, triggers, which take action when the changes occur, and active queries, which are computed in response to triggers. The same techniques which are used to avoid complete recomputation of views when a base relation changes can also be used generally to reduce the amount of computation needed to determine whether an action is to take place in response to a change in a base relation.
For the most part, prior art solutions to the view maintenance problem have been algorithmic, that is, for each kind of change to the base relations, an algorithm is provided which computes the changes to the view base relations, an algorithm is produced that computes the changes to the view. A typical example of the algorithmic approach is S. Ghandeharizadeh, R. Hull, D. Jacobs et al., On implementing a language for specifying active database execution models, In: Proc. VLDB-93. Qian and Widerhold have employed equational reasoning, that is, the change required in the view which is required by the change in the base relations is determined by means of a series of algebraic translations of the change in the base relations. See X. Qian and G. Wiederhold, Incremental Recomputation of Active Relational Expressions, IEEE Transactions on Knowledge and Data Engineering, 3(3):337"341,1991.
Equational reasoning offers a number of advantages over the algorithmic approach:
Unlike the algorithmic approach, it provides us with precise semantics of changes to the views. Consequently, using the equational approach makes it easier to prove correctness of the change propagation algorithm.
This approach is robust: if language changes (e.g. new primitives are added), one only has to derive new rules for the added primitives, leaving all other rules intact. As long as the new rules are correct, the correctness of the change propagation algorithm is not affected.
The resulting changes to the view are obtained in form of expressions in the same language used to define the view. This makes additional optimizations possible. For example, the expressions for changes that are to be made (e.g. for sets/bags of tuples to be deleted/added) can be given as an input to any query optimizer that might find an efficient way of calculating them.
Qian and Wiederhold's work and most of the algorithmic approaches have assumed that relations are set-valued, that is, duplicate rows are eliminated from the view. However, most practical database systems do not eliminate duplicates from views, and consequently cannot be modelled by sets. Instead, they must be modelled by bags, that is, multisets, or collections in which duplicates are permitted. The ability to handle duplicates is particularly important in dealing with aggregate functions in data base systems. Such functions obtain a value by aggregating other values. For instance, if the average salary of employees is to be computed, then one applies the aggregate function AVG to II.sub.Salary (Employees). Duplicates cannot be removed from the view since the result would be wrong when at least two employees had the same salary. Not eliminating duplicates also speeds up query evaluation, as duplicate elimination is generally a rather expensive operation.
Unfortunately, the theoretical work done on relations that are assumed to have no duplicates does not carry over to relations that do have them. Further, the little work which has been done on view maintenance when duplicates are present is algorithmic, see A. Gupta, I. S. Mumick, and V. S. Subrahmanian, Maintaining views incrementially, in: SIGMOD-93, pp. 157-166. Finally, Qian and Wiederhold's work contains an error which renders it unable to guarantee a minimality condition, namely that no rows are changed unnecessarily in the view being updated in response to a change in its base relations.
It is thus an object of the present invention to provide solutions for the view update problem which take the existence of duplicate rows in the view into account, which employ equational reasoning, and which are in fact able to guarantee a strong minimality condition.
SUMMARY OF THE INVENTION
The above object is achieved by making a definition of the side effect resulting from the transaction in terms of the relation or relations whose alteration by the transaction causes the side effect. The definition is then transformed using equational reasoning into a pre-expression which defines the effects of the side effect and can deal correctly with duplicates. In a preferred embodiment, the method deals correctly with duplicates because the definition, the equational reasoning, and the pre-expression are all done in terms of a bag algebra. One important application of the invention is making updates of materialized views.
Other objects and advantages of the apparatus and methods disclosed herein will be apparent to those of ordinary skill in the art upon perusal of the following Drawing and Detailed Description, wherein:
BRIEF DESCRIPTION OF THE DRAWING
FIG. 1 is a block diagram of a prior-art data base system;
FIG. 2 is a diagram of a data dictionary;
FIG. 3 is a diagram of an equational materialized view description generator;
FIG. 4 is a diagram showing how a materialized view maintenance description is used to update a materialized view;
FIG. 5 shows example base relations and an example view relation;
FIG. 6 shows change propagation equations used in a preferred environment; and
FIG. 7 shows recursive functions used in a preferred embodiment to compute a pre-expression.
Reference numbers in the Drawing have two parts: the two least-significant digits are the number of an item in a figure; the remaining digits are the number of the figure in which the item first appears. Thus, an item with the reference number 201 first appears in FIG. 2.
DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT
The following Detailed Description will begin with an overview of a data base system, will then present a general view of the problem of materialized view maintenance and the details of how equational reasoning may be employed in materialized view maintenance, and will finally present details of an implementation of materialized view maintenance in a data base system.
Overview of a Data Base System: FIGS. 1 and 2
FIG. 1 is a block diagram of a data base system 101 implemented in a digital computer system. The digital computer system has the usual components: a processor unit 109 with a processor 119 and a memory 111, an input device 107, for example a keyboard or a pointing device such as a mouse, connected to processor unit 109 for receiving inputs from a user, an output device 101 such as a CRT or flat panel display for displaying output from processing unit 109 to the user, and mass storage device 121, for example, a hard disk drive, which stores persistent data. The digital computer system may be of any size, from a personal computer to a mainframe or supercomputer.
When the digital computer system is being used to implement a data base system 101, processor 119 is executing a data base program 113 from memory 111 using program data 115. As the digital computer system executes the program, it responds to inputs from input device 107 and displays outputs on display 101. Data base user interface 102, which controls operation of data base system 101, is displayed in a window of display 101. For present purposes, data base user interface 102 has two components: command area 103 and view display 105 Command area 103 displays input from input device 107. The input may be a query, in which case, a view 117 which satisfies the query is constructed in memory 111 and is displayed in view display 105, or it may be a transaction, in which case data base system 101 changes the data it contains as specified in the transaction.
The actual information in the data base is generally contained in mass storage 121, although it may be maintained in memory 111 in systems where extremely rapid access is required. The information itself is contained in relations 124. There are two kinds of relations: base relations 125, in which the data in the data base is originally stored, and which are therefore the relations that are directly changed in a transaction, and materialized views, which are views, i.e., relations derived from other relations by a query, which have been written to mass storage 121. Data dictionary 123, finally, is what makes the data in relations 124 into relations. For each relation in relations 124, data dictionary 123 specifies the relation's name, the names and data types of the relations's column, and the actual location of the data for the relation in mass storage 121.
To operate data base system 101, a user uses input device 107 to input a command to command display 103. The command may specify either a transaction or a query. In either case, relations and fields in relations are specified in the command by name and the command may also specify conditions on field values. The command is typically written in a query language such as SQL, but graphical command interfaces may also be employed. If the command is a query, processor 119 under control of data base program 113 responds to the query by using data dictionary 123 to interpret the relation names and field names in the query, retrieves the rows and fields specified in the query into program data 115 in memory 111, uses the conditions to determine which of the retrieved rows and fields are to be used in view 117 specified by the query, sets up view 117 in memory 111, and then displays it in view display 105.
If the command is a transaction, it specifies relations, fields, and perhaps even conditions as in a query, but it additionally specifies changes in the relations or fields, for example, deletions or additions of rows in relations or changes in the values of fields. Processor 119 under control of data base program 113 again uses data dictionary 123 to interpret the transaction and locate the row which needs to be deleted or changed or to determine where a new row should be stored in mass storage 121. In the case of a deletion, data base program deletes the indicated row; in the case of an addition or change, program 113 constructs the new record in program data 115 and then writes it to the proper location in mass storage 121.
As is apparent from the foregoing description of data base system 101, data dictionary 123 contains the descriptions which permit data base program 113 to properly interpret queries and transactions. FIG. 2 presents a block diagram of a data dictionary 123 of the type employed in systems which require view maintenance. For present purposes, two parts of data dictionary 123 are of interest: relation descriptions 201 and transaction response descriptions 207. Relation descriptions 201 contain a description of each of the relations 124 in mass storage 121. In a system which materializes views, there are two kinds of relation descriptions: base relation descriptions 203, which describe base relations 125, and materialized view descriptions 205, which describe materialized views. A materialized view description 205 is locatable in data dictionary 123 from the base relation descriptions 203 for the base relations used to make the view.
Transaction response descriptions 207 describe data base system 101's responses to a change in a relation in relations 124. As indicated above, depending on the data base system, the responses may include maintaining materialized views (209), performing consistency checks (211), executing trigger code (211), executing monitor code (215), and performing active queries (217). Transaction response descriptions which involve a particular base relation are accessible from the base relation description 203 for the base relation. When data base system 101 executes a transaction, the transaction response descriptions 207 for the base relations involved in the transaction are checked and if any of them describes the transaction being performed, the responses specified in the transaction response descriptions are carried out as part of the transaction.
Producing Improved Response Descriptions
As pointed out in the Description of the Prior Art, supra, the prior art has not provided techniques for producing transaction response descriptions which were both based on equational reasoning and were able to deal with duplicates. The following discussion of novel techniques for producing such transaction response descriptions begins with an example which illustrates the inadequacies of prior-art techniques based on equational reasoning for producing transaction response descriptions, then explains the bag algebra upon which the novel techniques are based, next specifies the equations underlying the novel techniques, and finally presents the algorithm which implements the equations.
An Example: FIG. 5
FIG. 5 shows a data base 501 which will be used as an example in the following discussion. Data base 501 has three base relations, indicated by the reference numbers 502, 507, and 511, and a view 513. Each relation is a table which is made up of one or more rows 503 and columns 505. Relations S1(Pid, Cost, Date) 502 S2(Pid, Cost, Date) 507 are relations for recording shipments of parts received from two different suppliers. In the notation used to describe the relations, S1 is the name of the relation and the names in parentheses following the name of the relation are the names of the columns. Thus, each row in relations S1 and S2 has three attributes (or fields). The attribute Pid is a unique identifier for the part with which the row is concerned. Cost is the cost of the part identified by Pid, and Date is the day the shipment which included the part arrived. In addition we have the relation Paid(Pid, Cost, S), which is a table of parts that have already been paid for. Since there are only two suppliers, S1 and S2, The attribute S in this relationship must have either the value 1 or the value 2, indicating which supplier was paid.
We would like to compute the total amount of money we owe--the cost of all parts received by not yet paid for. One way of doing this is to define a view Unpaid 513 which contains a row for each part which has been received but not yet paid for. The attributes of the row are Pid and Cost. Once the view has been computed, the total amount owed can be found by adding the values in Cost. One way of defining Unpaid 513 is to produce a first view V.sub.1 which contains rows made up of the Pid and Cost fields from both S1 and S2 and a second view V.sub.2 which contains rows made up of the Pid and Cost fields from Paid, and then produce Unpaid by finding all the rows in V.sub.1 which are not in V.sub.2.
A definition of these operations in bag algebra uses the projection operator II, the additive union operator , and the monus operator -. II makes a relation which has a row for each row of the relation from which the projection is made, but has only the attributes specified in the operation. is a union operator that includes duplicates when it makes a union of two bags. - subtracts multiplicities. If a record r occurs n times in S and m times in T, then the number of occurrences of r in S-T is n-m if n.gtoreq.m and 0 if n<m. The bag algebra definition looks like this: ##EQU1## Here, because is used, V.sub.1 contains two copies of the record [Pid P1, Cost 1,200]. Because- is used, Unpaid contains 1 row for P1 and two rows for P4.
Once we have Unpaid, the TOTAL() aggregation operator can be used to obtain the amount still owed:
Note that multiset semantics gives the correct answer here, while set-theoretic semantics, which do not permit duplicate rows, do not. For example, for the relations shown in FIG. 5, the amount Owe is $7,400. However, if we switch to set semantics and calculate Unpaid as (II.sub.Pid,Cost (S1).orgate. II.sub.Pid,Cost (S2))-II.sub.Pid,Cost (Paid), then Owe calculated by the same formula equals $4,800.
The materialized view maintenance problem arises if we materialize Unpaid 513. Then, if we find that Paid contains a mistake, for instance, a payment was made to supplier S1 for part P3 instead of to supplier S2 for part P5 and we correct the mistake in Paid, we must also update Unpaid. In the bag algebra, this correction is represented by using the delete bag .gradient.Paid to represent the rows that the correction will delete from Paid and the insert bag .DELTA.Paid to represent the rows that the correction will insert in Paid. The transaction which corrects Paid may thus be described in the bag algebra as follows:
Rather than recomputing the entire view Unpaid from scratch, we would like to find expressions .gradient.Unpaid and .DELTA.Unpaid such that
This has the potential of greatly reducing the amount of computational resources needed to recompute this new value.
As required for our correction, let .gradient.Paid contain the single record [Pid P5 Cost 4,000, S 2] and .DELTA.Paid contain the single record [Pid P3, Cost 1,300, S 1]. (That is, we discovered that a payment was made to the first supplier for P3 rather than the second for PS.) Then it is fairly easy to see that .gradient.Unpaid should evaluate to [Pid P3, Cost 1,300] and that .DELTA.Unpaid should evaluate to [Pid P5, Cost 4,000].
Since our algorithm works with delete bags and insert bags, it need not know anything about what kind of changes occurred in the rows being inserted and deleted. Thus, in the example, it simply produces the delete bag, .gradient.Unpaid, as follows:
and the insert bag, .DELTA.Unpaid, like this:
The min operator used to produce .gradient.Unpaid is defined as follows: S min T is a multiset such that the number of occurrences of a record r in it is min(n,m), where n and m are numbers of occurrences in S and T respectively.
An advantage of the way that the delete and insert bags are defined is that evaluation of the expressions for .gradient.Unpaid and .DELTA.Unpaid can be made very efficient. First we assume that all relations S1,S2 and Unpaid have an index built on the them that uses Pid as a key. Then, in order to evaluate the expressions for .gradient.Unpaid and .DELTA.Unpaid we only have to find the numbers of occurrences of elements of II.sub.Pid,Cost (.gradient.Paid) and II.sub.Pid,Cost (.DELTA.Paid) in V.sub.1, V.sub.2 and II.sub.Pid,Cost (Paid). For example, to find .gradient.Unpaid, for each r .DELTA.Paid we find x,y,z, .upsilon. as the numbers of occurrences of r in .DELTA.Paid, .gradient.Paid, V.sub.1 and V.sub.2. Then R occurs min {(x-y),(z-.upsilon.)} times in .gradient.Unpaid. Thus, the complexity of such evaluation depends on how fast we can access elements of the base relations, not on how fast we can access the views. Typically, access to base relations is much faster than access to views. Even if no index exists, the time complexity is still linear in the sizes of the base relations.
Another big benefit of the above approach is reduced memory requirements. Whereas recomputing the whole view Unpaid would require memory space linear in the size of base relations, the propagation algorithm only requires that we find the number of occurrences of certain records in base relations and then evaluate an arithmetic expression. Therefore, space needed for updating the view Unpaid is linear in the size of changes to the base relations. Typically, the number of rows which change is relatively small compared to the number of rows in the relations. Thus, calculating changes to the view as opposed to recomputing the view leads to substantial improvement in space usage.
Once changes to Unpaid are calculated, the new value of Owe is found as
The correctness of this is guaranteed for our solution. Indeed, Owe.sup.new calculated above is $10,100, and one can see that it is the correct amount still owed once changes to Paid have been made.
The Bag Algebra
Several equivalent approaches to bag-based database languages have been proposed. See S. Grumbach, T. Milo, Towards tractable algebras for bags, In PODS-93, pp.49-58; L. Libkin, L. Wong, Aggregate functions, conservative extension, and linear order, in Proc. Database Programming Languages, Springer Verlag, 1994, pp. 97-114; and L. Libkin, L. Wong, New techniques for studying set languages, bag languages, and aggregate functions, in PODS-94, pp. 155-166. The bag-based database language that we use to formulate the change propagation algorithm differs from the proposed languages in that it is restricted to to flat bags (that is, bag-valued attributes are not allowed).
Definitions of Bag Algebra Operations
In what follows, base relation names are denoted by the symbols R, R.sub.1, R.sub.2, . . .. Let p range over quantifier-free predicates, and A range over sets of attribute names. expressions are generated by the following grammar. ##EQU2##
To define the semantics of these operations, let count(x, S) be the number of occurrences of x in a bag S. Then, for any operation e in the language, we define count(x, e(S,T))or count(x,e(S))as a function of count(x, S) and count(x, T) as follows: ##EQU3## This language is not intended to be minimal. For example, min can be defined as S min T def S- (S-T). For the full characterization of interdefinability of the operations of , consult Libkin and Wong, Some Properties . . ., supra.
We use the symbols S, T, W, and Z to denote arbitrary expressions, and s to denote a database state, that is, a partial map from relation names to multisets. If s is a database state and T is a expression such that s is defined on all relation names mentioned in T, then s(T) denotes the multiset resulting from evaluating T in the state s. (Note that s is a function, so we consider evaluating T in s as the result of applying s to T.) The notation T=.sub.b S means that for all database states s, if s is defined on all relation names mentioned in S and T, then s(T)=s(S).
Specification of Transactions
A transaction is a program that changes the state of a database in one atomic step. There are many approaches to languages for specifying transactions. Here, we adopt an abstract view of transactions, in order to make the results independent of a particular language used, but at the same time readily applicable to any such language.
The abstract transactions to be considered are of the form ##EQU4## As before, the expression .gradient.R.sub.i represents a bag deleted from relation R.sub.i and .DELTA.R.sub.i represents a bag inserted into base relation R.sub.i. More formally, when transaction t is executed in state s of the data base, then value of R.sub.i in state t(s) becomes s((R.sub.i -.gradient.R.sub.i) .DELTA.R.sub.i).
A pre-expression for a transaction is an expression which can be evaluated before the transaction to determine the result of the transaction. In the case of an update of a materialized view, the pre-expression indicates how the materialized view is to be updated; in the case of consistency checking, the value of the pre-expression indicates whether the results of the transaction are consistent with the data base's consistency constraints; in the cases of monitors, triggers, and active queries, the value of the pre-expression indicates which monitor, trigger, or active query will be activated.
More formally, The expression T is a pre-expression of S w.r.t. t if for every database state s we have s(T)=.sub.b t(s)(S). It is easy to check that ##EQU5## is a pre-expression of S w.r.t.t.
Goals to be Achieved by the Technique
The aim of the technique is to provide an algorithm for generating strongly minimal pre-expressions for view maintenance at compile time which are computationally more efficient than recomputation of the materialized view. More particularly, suppose S(R.sub.1, . . . R.sub.n) is a expression and t is a transaction. We would like to determine how t's changes to the base relations propagate to changes in the value of S. In particular, we seek to construct expressions .DELTA.S and .gradient.S, called a solution for pre(t,S), which may be used in pre-expressions of the form
Clearly, not all pre-expressions having the above form are equally acceptable. For example, .gradient.S=S and .DELTA.S=pre(t,S) is always a solution. What are "good" solutions? First, if S is a materialized view, then it will be generally cheaper to evaluate (S-.gradient.S) .DELTA.S than to evaluate pre(t,S) in the current state (or to evaluate S after t has been executed). Second, we will impose some "minimality" conditions on .gradient.S and .DELTA.S to make sure that no unnecessary tuples are produced. In particular,
1. .gradient.S-S=.sub.b .phi.: We only delete tuples that are in S.
2. .DELTA.S min .gradient.S=.sub.b .phi.: We do not delete a tuple and then reinsert it.
A solution meeting condition (1) will be called weakly minimal, while a solution meeting both conditions (1) and (2) will be called strongly minimal. Note that, in contrast to the relational case, it does not make sense to insist that S be disjoint from .DELTA.S since a transaction may increase the multiplicities of elements in S.
Minimality (weak or strong) is especially desirable due to the way in which changes interact with aggregate functions. For example, we have
assuming a (weakly or strongly) minimal solution.
Again, not all strongly minimal solutions are equally acceptable. For example, the pair
and
is a strongly minimal solution. However, there is no advantage in using it to maintain the view given by Q.
The Algorithm for Finding Strongly Minimal Pre-Conditions
The following discussion will first present the collection of change propagation equations employed in the preferred embodiment and will then describe the recursive algorithm used in the preferred embodiment to apply the change propagation equations.
The Change Propagation Equations: FIG. 6
As already pointed out, techniques for doing equational reasoning using equations written in a relational algebra have been described in the Qian-Wiederhold reference supra. That reference discloses a change propagation algorithm which is based on a collection of equations that are used to "bubble up" change sets to the top of an expression. For example, the Qian-Wiederhold reference uses the equation
to take the insertion .DELTA.S into S and propagate it upward to the insertion .DELTA.S-T into S-T.
Our algorithm is based on a collection of such propagation rules for expressions in the bag algebra . Finding such a collection is complicated by the fact that expressions, unlike set-valued relational expressions, do not obey the familiar Boolean algebra used with set-valued relational expressions. When (S.orgate..DELTA.S)-T is replaced with the bag expression (S .DELTA.S)-T, the above example becomes
which is not immediately obvious. FIG. 6 shows the collection 601 of equations for change propagation in bag expressions which are used in the preferred embodiment of the algorithm. Some subexpressions are annotated with a .gradient. (for a deletion bag) or a .DELTA. (for an insertion bag). This annotation simply emphasizes the intended application of these equations: when read as left-to-right rewrite rules, they tell us how to propagate changes upward in an expression. Note that the correctness of these equations involves no assumptions concerning minimality of the change bags.
By repeated applications of the equations in FIG. 6, we can propagate any number of changes upward. For example, consider the expression U=S T. Suppose that
The changes to S and T can be propagated upward and expressed as changes to U as follows: ##EQU6## where .gradient..sub.1 U=(.gradient.S min S) (.gradient.T min T) and .DELTA..sub.1 U=.DELTA.S .DELTA.T. The last step is simply an application of the general rules
G1. (S T) W=.sub.b S (T W)
G2. (S-T)-W=.sub.b S-(T W)
which are applied in order to collect all deletions into one delete bag and all insertions into one insert bag.
Repeated application of the equations of FIG. 6 guarantees a solution, but not necessarily a strongly minimal one. However, the following theorem shows that any solution can be transformed into a strongly minimal one:
Theorem 1 Suppose that W=.sub.b (Q-.gradient..sub.1 Q) .DELTA..sub.1 Q. Let .gradient..sub.2 Q=(Q min .gradient..sub.1 Q)-.DELTA..sub.1 Q and .DELTA..sub.2 Q=.DELTA..sub.1 Q-(Q min .gradient..sub.1 Q). Then
a) W=.sub.b (Q-.gradient..sub.2 Q) .DELTA..sub.2 Q
b) .gradient..sub.2 Q-Q=.sub.b .phi.
c) .gradient..sub.2 Q min .DELTA..sub.2 Q=.sub.b .phi..
Returning to the example from above, .gradient..sub.1 U and .DELTA..sub.1 U can be transformed to a strongly minimal solution by taking .gradient..sub.2 U to be
and .DELTA..sub.2 U to be
Although these expressions are rather complex, they can be greatly simplified to ##EQU7## under the assumption that the solutions (.gradient.S, .DELTA.S) and (.gradient.T, .DELTA.T) are strongly minimal.
The foregoing example provides a simple illustration of the steps employed generally in the preferred embodiment to obtain the algorithm used to compute the strongly-minimal pre-condition.
1. A general solution is derived by repeated application of the propagation rules of FIG. 6.
2. A strongly minimal solution is obtained by application of theorem 1.
3. The results are simplified under the assumption that all solutions for subexpressions are strongly minimal.
In the preferred embodiment, these steps are employed to obtain a recursive algorithm.
Note that if we are only concerned with correctness, then there is considerable freedom in the design of the propagation equations presented in FIG. 6. For example, we could replace equation P8 with
However, in designing set of equations 601, we have set out to reduce the amount of computation required to determine the changes to a view. Note that all of the equations in FIG. 6 follow the same pattern. For any operation e and its value V=e(R.sub.1, . . .,R.sub.n), n=1 or n=2, if one of its arguments changes, then its value V' on changed arguments is obtained as either V-.gradient. or V .DELTA.. The expressions for .gradient. and .DELTA. are always of special form. They are "controlled" by .gradient.R.sub.i s and .DELTA.R.sub.i s, that is, they can be computing by iterating over those bags and fetching corresponding elements from the base relations, rather than by iterating over the base relations themselves. Furthermore, this special form is preserved in the transformations defined in the above theorem for minimalizing a solution.
For example, to compute Z=((.gradient.T min T)-(T-S)) (rule P8 in FIG. 6), for each element x .gradient.T, let n, m and k be numbers of occurrences of x in .gradient.T, T and S respectively. Then x occurs min(n, m)-(m-k) times in Z. Thus, to compute Z, we only fetch elements in .gradient.T from T and S. Since .gradient.R.sub.i s and .DELTA.R.sub.i s are generally small compared to the size of base relations R.sub.i s, this special form of expressions for .gradient. and .DELTA. will make the change propagation algorithm suitable for maintaining large views.
The Algorithm for Deriving Pre-expressions: FIG. 7
This section presents algorithm 701 shown in FIG. 7 for computing a strongly minimal pre-expression for a given view maintenance problem which we employ in the preferred embodiment. That is, given a transaction t and a expression Q, we will compute expressions .gradient.Q and .DELTA.Q such that pre(t,Q)=.sub.b (Q-.gradient.Q) Q.
We first define two mutually recursive functions .gradient.(t,Q) 703 and .DELTA.(t,Q) 705 such that for any transaction t pre(t,Q)=.sub.b (Q-.gradient.(t,Q)) .DELTA.(t,Q). For readability, we use the abbreviations add(t, S) for S .DELTA.(t,S) and del(t,S) for S-.gradient.(t,S).
We derived the clauses of functions 703 and 705 using the three steps just described. The last step, namely simplification of the results under the assumption that all recursively derived solutions are strongly minimal, is quite important since the assumption of strong minimality is no longer available when query optimization is done at a later stage. That is also the reason why the minimalization theorem is applied at every stage of the algorithm rather than just once at the end.
The algorithm is simply this: given inputs t and Q, use the functions .gradient.(t,Q) and .DELTA.(t,Q) to compute a solution for pre(t,Q). Note that in other embodiments, .gradient.(t,Q) and .DELTA.(t,Q) could be combined into one recursive function. Thus the algorithm requires only one pass over the expression Q.
The following theorem shows that the functions .gradient. and .DELTA. correctly compute a solution to the view maintenance problem and that they preserve strong minimality.
Theorem 2 Let t be a strongly minimal transaction. That is, R-.gradient.R=.sub.b .phi. and .gradient.R min .DELTA.R=.sub.b .phi. for any R.rarw.(R-.gradient.R) .DELTA.R in t. Let Q be a expression. Then
1. pre(t,Q)=.sub.b (Q-.gradient.(t,Q)) .DELTA.(t,Q)
2. .gradient.(t,Q)-Q=.sub.b .phi.
3. .DELTA.(t,Q) min .gradient.(t,Q)=.sub.b .phi.
Although some of the clauses in the definition of functions .gradient. and .DELTA. are rather complex, many of the subexpressions either turn out to be .phi. or can be easily simplified to .phi..
We can illustrate this with example data base 501 of FIG. 5: ##EQU8## where the t is a transaction that changes Paid to (Paid-.gradient.Paid) .DELTA.Paid. Using our change propagation functions, the delete bag can be calculated as follows. ##EQU9## In a similar way we can compute the change bag for insertions, .DELTA.(t,Unpaid), to be
One advantage of our approach is that it produces queries that can be further optimized by a query optimizer. Consider the following example. Suppose that we have a view WellPaid defined as
Now if a deletion has been made to Employees, then we compute
We have treated deletions and insertions as black boxes, but often they are specified in some transaction language or as queries. For example, if .gradient.Employees=.sigma..sub.Salary<5,000 (Employees), then we can substitute this value for .gradient.Employees in the equation for .gradient.WellPaid, obtaining
for .gradient.WellPaid. Any query optimizer that "knows" that .sigma..sub.p1 (.sigma..sub.p2 (S))=.sigma..sub.p1&p2 (S) and that 5<50 will figure out that .gradient.WellPaid=.0. and no computation needs to be done.
0.1 Using Strongly Minimal Solutions with Aggregate Functions
Most database query languages provide a number of aggregate functions such as COUNT, TOTAL, AVG, STDEV, MIN, MAX. It has been observed that all of the above aggregate except MIN and MAX) can be expressed in a query language if the query language is endowed with arithmetic operations and the following summation operator:
For example, COUNT is .SIGMA..sub.1 where the function 1 always returns 1; TOTAL is .SIGMA..sub.id, AVG is TOTAL/COUNT. See in this regard L. Libkin, L. Wong, Aggregate functions, conservative extension, and linear order, In: Proc. Database Programming Languages, Springer, 1994, pp. 97-114 and L. Libkin, L. Wong, Conservativity of nested relational calculi with internal generic functions, Information Processing Letters 49 (1994), pp. 273-280.
Any strongly minimal solution for the view maintenance problem allows us to handle duplicates correctly because the following will hold:
Now if an aggregate function is defined as AGR(S)=.rho.(.SIGMA..sub.f1 (S), . . .,.SIGMA..sub.fk (S)) where .rho. is an arithmetic expression in k arguments, to be able to maintain the value of AGR when the view S changes, one has to keep k numbers, .SIGMA..sub.fi (S), i=1, . . ., k. Once changes to the view (.gradient.S and .DELTA.S) become known, the values of .SIGMA..sub.fi are recomputed by the formula above and then .rho. is applied to obtain the value of AGR. For example, AVG(S)=TOTAL(S)/COUNT(S)=.SIGMA..sub.id (S)/.SIGMA..sub.1 (S). Assume that n=TOTAL(S) and M=COUNT(S). If S changes and a strongly minimal solution S.sup.n =(S-.gradient.S) .DELTA.S is computed, let n.sub.1 =.SIGMA..sub.id (.gradient.S), n.sub.2 =.SIGMA..sub.id (.DELTA.S), m.sub.1 =.SIGMA..sub.1 (.gradient.S), m.sub.2 =.SIGMA..sub.1 (.DELTA.S). Then AVG(S.sup.n) can be computed as (n-n.sub.1 +n.sub.2)/(m-m.sub.1 +m.sub.2). Notice that all additional computation of aggregates is performed on changes to the views, so one may expect it to be fast.
Two aggregates that require special treatment are MIN and MAX. Assume that MIN(S)=n, and we want to compute MIN(S.sup.n) where S.sup.n =(S-.gradient.S) .DELTA.S strongly minimal. If we compute m=MIN(.gradient.S) and k=MIN(.DELTA.S), then k.ltoreq.n implies MIN(S.sup.n)=k and m>n implies MIN(S.sup.n)=min(n,k). However, if n=m and k.gtoreq.n, then there is no way to say what the value of MIN(S.sup.n) is for the minimal value n can be reached at several elements of S and we do not know if all of them were deleted in .gradient.S. Thus, in only this case one has to recompute S.sup.n in order to evaluate MIN correctly.
Computing Minimal Pre-Conditions in a Data Base System
The foregoing has provided an exposition in a bag algebra of how a to compute a minimal pre-condition for updating a materialized view when the view's base relations have been altered. In the following, we will discuss how the results of the foregoing section can be applied in practical data base systems. We will begin with a discussion of the relationship between the bag algebra and query languages and will then show how minimal pre-conditions are computed and used in a data base system.
Query Languages and Bag Algebras
As pointed out in the Description of the Prior Art, bag algebras describe the same operations that query languages do. The bag algebra can thus be itself used as a query language; all that is required is a data base system 101 whose data base program 113 is able to interpret bag algebra expressions.
More important, because the bag algebra and the query language describe the same operations, expressions in the bag language are equivalent to at least a subset of the expressions in the query language and translations may be made between the bag language expressions and the query language expressions in the subset language expressions and query language expressions may be made. For example, many SQL expressions can be translated into the bag algebra used in the preferred embodiment and any bag algebra expression used in the preferred embodiment may be translated into an SQL expression. One way to take advantage of the mutual translatability between the bag language and the subset of the query language is to receive the query language descriptions of the information needed to obtain the pre-expression, translate them into equivalent bag algebra expressions, use the algorithm to produce the pre-expression in the bag algebra, and then translate the pre-expression back into the query language. Another way is to make query language equivalents of functions 703 and 305 and use them to obtain the query language pre-expression directly from the query language transaction specification.
Making a Pre-Condition in a Data Base System: FIG. 3
FIG. 3 shows a pre-condition compiler 301 which may be used to generate preconditions made with equational reasoning of the kind just described. Precondition compiler 301 is implemented in computer system 101. Compiler 301 takes as its input a transaction description 303 which a user of compiler 301 provides at user interface 102. The transaction description describes the transaction as a change to one or more base relations. The output of compiler 301 is a minimal pre-condition. For purposes of the present discussion, the minimal pre-condition describes how a materialized view is to be maintained and is thus a materialized view maintenance description 317.
Compiler 301 has the usual components, which are implemented in programs which execute on processor 119. The first component is lexer 304, which takes the text string transaction description 303 which was input by the user and divides it into meaningful parts called tokens. The next component is parser 305, which takes the tokens and makes a tree in which each node is one of the tokens. Then semantic analyzer 307 determines the semantics of the tokens. In this case, the information needed to do that is contained in data dictionary 123. Data dictionary 123 contains descriptions 313 of the base relations involved in the transaction and also contains descriptions 315 of materialized views built from the base relations involved in the transaction.
Once semantic analyzer 307 has determined the relationships between the base relations involved in the transaction and the views which must be updated as a consequence of the transaction, equational pre-condition generator 311 can employ algorithm 701 to obtain the minimal pre-conditions for maintaining the affected views. These are then stored as individual materialized view maintenance descriptions 317 in section 209 of data dictionary 123. The descriptions 317 are locatable from the base relation descriptions for the base relations upon which the transactions which require view updates are performed. Details of compiler design and construction may be found in standard works such as Aho, Sethi, Ullman, Compilers, Principles, Techniques, and Tools, Addison-Wesley, 1986.
It should be pointed out at this point that transaction description 303 does not describe a specific transaction, but rather a class thereof (for example, any change to a specified column in a base relation) and that each minimal pre-condition also describes a class of actions to be taken, for example those taken when the specified column is changed.
Using a Minimal Pre-Condition in a Data Base System: FIG. 4
FIG. 4 shows a system 401 for using a minimal pre-condition in a data base system. The input to the system is a transaction instance 403 provided by the user at user interface 102. Transaction instance 403 is an instance (particular one) of a class of transaction described in a transaction description 303. Transaction instance 403 is received in data base program 113. Transaction code 405 in data base program 113 responds to transaction instance 403 by obtaining information 413 from base relation descriptions 203 for the base relations 125 changed by the transaction. The information indicates the locations in base relations 125 of the data to be changed in the transaction and also specifies the locations of any materialized view descriptions 205 and transaction response descriptions 207 associated with the base relations being changed. Transaction code 405 changes the base relations 125 as required by the transaction (arrow 409), and if there are transaction response descriptions and materialized view descriptions associated with the base relation descriptions, transaction code 405 invokes maintenance code 407 with the locations of those descriptions.
Maintenance code 407 then uses the associated materialized view descriptions (arrow 415) and the associated transaction response descriptions (arrow 417) to determine haw the materialized views are to be updated and performs the update using the values specified in transaction instance 403, as shown by arrow 411.
Advantages of Using Bag Algebra to Produce Pre-Expressions
Among the advantages of the techniques disclosed herein are the following:
The techniques disclosed herein are linguistically closed. That is, we give explicit algebraic representations to all expressions generated in change propagation, and these are represented in the language . There is thus never any need to extend the algebraic representations and computation involving the algebraic representations can be optimized as much as possible. Optimization is not restricted to generating change expressions, but can be done at later stages as well.
Next, because our approach is algebraic, it gives a declarative semantics to change propagation that is not tightly bound to one computational model. The language-independent declarative semantics make correctness proofs much easier, simplify the process of extending the algorithm to new constructs, and allow us to apply our results to the production of preconditions generally. For example, suppose that we are given the integrity constraint ##EQU10## and a strongly minimal transaction t={R.sub.2 .rarw.(R.sub.2 -.gradient.R.sub.2) .DELTA.R.sub.2 }. Furthermore, suppose that we would like to transform t to a safe transaction,
that can never leave the database in a state violating .sigma.. If we assume that .sigma. will always hold before t' is executed, then we can use our algorithm, together with some logical manipulations, to produce ##EQU11## as the formula .alpha..
Finally, we are able to use the inductive assumptions of strong minimality to further simplify our solutions. Since the information required for these simplifications is not available to a general purpose query optimizer, the general purpose optimizer may produce a solution which is less efficient than ones which can be found using our techniques.
Further directions in which our techniques can be developed include providing a specialized query optimizer to take advantage of strong minimality. Such an optimizer would be based on a collection of inference rules for deriving disjointness (for example, if S is disjoint form T, then S-W is disjoint from T-Z) and simplification rules that exploit disjointness (for example, if S is disjoint from T, then S-T simplifies to S). The optimization process is initiated by recognizing that all pairs produced by our algorithm, (.gradient.S,.DELTA.S), are disjoint.
One current drawback to our approach is that, as with the relational algebra, bag languages such as cannot express recursive queries. However, it is possible to extend with loops or a fixed-point operator. Another extension of our approach would permit our bag algebra to deal with complex objects.
Conclusion
The foregoing Detailed Description has disclosed to those skilled in the data base arts how to use equational reasoning based on a bag algebra to produce minimal preconditions which specify side effects of transactions made on base relations in the data base. The disclosure has shown how the minimal preconditions correctly take duplicate rows into account and how the minimal preconditions may be used in maintaining materialized views, enforcing consistency constraints, determining whether a trigger or monitor action is to be executed, and determining whether an active query should be activated.
Applicants have disclosed the best manner presently known to them of practicing their equational reasoning techniques, but other embodiments are of course possible. In particular, different bag algebras, different propagation equations, and a different algorithm for computing the minimal preconditions may be employed. Further, expressions in the bag algebra may be directly used to specify queries, transactions, and pre-expressions to the data base system or query language instructions equivalent to the bag algebra expressions may be used, with translations being made by the data base system where convenient. In the preferred embodiment, the pre-expressions are produced by compilation and stored in the data dictionary for use at runtime; however, in other embodiments, the pre-expressions may be produced at runtime. Additionally, while the techniques have been disclosed in the context of a relational data base system, they can be employed in any data base system for which bag algebra equivalents of query language expressions exist.
In the preferred embodiment described herein, the transaction response descriptions are part of data dictionary 123 and are executed by code in data base program 113. In other embodiments, the data base management system may include an application program which maintains the response descriptions and uses them to determine what commands are actually given to data base program 113. For example, if the response descriptions are being used to maintain consistency, the application program could use them to check the consequences of a transaction before actually issuing the command for the transaction to the data base system. If the application program determines that the command would violate an integrity constraint, it can then not issue the command.
All of the above being the case, the foregoing Detailed Description is to be understood as being in every respect illustrative and exemplary, but not restrictive, and the scope of the invention disclosed herein is not to be determined from the Detailed Description, but rather from the claims as interpreted according to the full breadth permitted by the law.
Claims
What is claimed is:
1. A method employed in a data base system of determining a side effect on the data base system of a transaction on a relation in the data base system, the method comprising the steps of: receiving a description of the transaction in terms of the relation; transforming the description in accordance with a set of change propagation equations which correctly deal with duplicates to produce a pre-expression which specifies the side effect; and responding to the transaction by producing the side effect specified in the pre-expression.
2. The method set forth in claim 1 wherein: the description, the change propagation equations, and the pre-expression are all modellable in a bag algebra.
3. The method set forth in claim 2 wherein: the data base system employs a query language to describe relations and transactions; and the description, the change propagation equations, and the pre-expression are in the query language.
4. The method set forth in claim 1 wherein: the step of transforming includes the step of computing a delete bag and an insert bag in the pre-expression.
5. The method set forth in claim 4 wherein: the step of computing a delete bag and an insert bag computes the delete bag and the insert bag such that they are strongly minimal.
6. The method set forth in claim 1 wherein: the transaction description in the step of receiving a transaction description describes a class of transactions; and the transaction in the step of responding to the transaction description is an instance of the class.
7. The method set forth in claim 6 wherein: the steps of making the description and transforming the description are performed prior to the receipt of the instance in the data base system.
8. The method set forth in claim 1 wherein: the step of transforming is applied recursively to the description.
9. The method set forth in any of claim 1, 2, 3, 4, 5, 6, 7, or 8 wherein: the side effect is an update of a materialized view.
10. The method set forth in claim 9 wherein: the step of transforming the definition produces a pre-expression which defines how the transaction updates the materialized view in terms of elements of the base relation.
11. The method set forth in any of claim 1, 2, 3, 4, 5, 6, 7, or 8 wherein: the side effect determines whether the transaction violates a consistency constraint of the data base system.
12. The method set forth in claim 11 wherein: the side effect is produced prior to performing the transaction.
13. The method set forth in any of claim 1, 2, 3, 4, 5, 6, 7, or 8 wherein: the side effect activates a trigger in the data base system.
14. The method set forth in any of claim 1, 2, 3, 4, 5, 6, 7, or 8 wherein: the side effect activates a monitor in the data base system.
15. The method set forth in any of claim 1, 2, 3, 4, 5, 6, 7, or 8 wherein: the side effect activates an active query in the data base system.
16. A method employed in a data base system of determining a side effect on the data base system of a transaction on a relation in the data base system, the method comprising the steps of: receiving a description of the transaction in terms of the relation; transforming the definition in accordance with a set of change propagation equations which deal correctly with sets to produce a pre-expression which specifies the side effect in terms of a strongly minimal delete bag and insert bag; and responding to the transaction by producing the side effect specified in the pre-expression.
17. The method set forth in claim 16 wherein: the side effect is an update of a materialized view.
18. The method set forth in claim 17 wherein: the step of transforming the definition produces a pre-expression which defines how the transaction updates the materialized view in terms of elements of the base relation.
19. The method set forth in claim 16 wherein: the side effect determines whether the transaction violates a consistency constraint of the data base system.
20. The method set forth in claim 28 wherein: the side effect is produced prior to performing the transaction.
21. The method set forth in claim 16 wherein: the side effect activates a trigger in the data base system.
22. The method set forth in claim 16 wherein: the side effect activates a monitor in the data base system.
23. The method set forth in claim 16 wherein: the side effect activates an active query in the data base system.
24. An improved data base system, the data base system being of the type which includes at least one relation and a definition of the relation and which performs a transaction on the relation and the improvement comprising: a pre-expression in the data base which specifies a side effect of the transaction on the data base, the pre-expression having been produced by steps including receiving a description of a class of transactions to which the transaction belongs in terms of the relation and transforming the description in accordance with a set of change propagation equations which correctly deal with duplicates to produce a pre-expression which specifies the side effect for transactions belonging to the class; and means responsive to the transaction and the pre-expression for responding to the transaction by producing the side effect specified in the pre-expression.
25. The data base system set forth in claim 24 wherein: the step of transforming includes the step of computing a delete bag an an insert bag in the pre-expression.
26. The data base system set forth in claim 25 wherein: the step of computing a delete bag and an insert bag computes the delete bag and the insert bag such that they are strongly minimal.
27. The data base system set forth in any of claim 24, 25 or 26 wherein: the side effect is an update of a materialized view.
28. The data base system set forth in any of claim 24, 25 or 26 wherein: the side effect determines whether the transaction violates a consistency constraint of the data base system.
29. The data base system set forth in any of claim 24, 25 or 26 wherein: the side effect activates a trigger in the data base system.
30. The data base system set forth in any of claim 24, 25 or 26 wherein: the side effect activates a monitor in the data base system.
31. The data base system set forth in any of claim 18, 19, 24, 25 or 26 wherein: the side effect activates an active query in the data base system.
32. An improved data base system, the data base system being of the type which includes at least one relation and a definition of the relation and which performs a transaction on the relation and the improvement comprising: a pre-expression in the data base which specifies a side effect of the transaction on the data base, the pre-expression having been produced by steps including receiving a description of a class of transactions to which the transaction belongs in terms of the relation and transforming the definition in accordance with a set of change propagation equations which deal correctly with sets to produce a pre-expression which specifies the side effect in terms of a strongly minimal delete bag and insert bag; means responsive to the transaction and the pre-expression for responding to the transaction by producing the side effect specified in the pre-expression.
33. The data base system set forth in claim 325 wherein: the side effect is an update of a materialized view.
34. The data base system set forth in claim 32 wherein: the side effect determines whether the transaction violates a consistency constraint of the data base system.
35. The data base system set forth in claim 32 wherein: the side effect activates a trigger in the data base system.
36. The data base system set forth in claim 32 wherein: the side effect activates a monitor in the data base system.
37. The data base system set forth in claim 32 wherein: the side effect activates an active query in the data base system.
Non-Patent Literature (10)
- S. Grumbach, T. Milo, "Towards Tractable Algebras for Bags", Proceedings of Principles of Database Systems, PODS '93.
- L. Libkin, L. Wong, "New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions", Proceedings of Principles of Database Systems, PODS '94.
- L. Libkin, L. Wong, "Some Properties of Query Languages for Bags", Proceedings of Database Programming Languages, 1993.
- S. Ceri, J. Widom, "Deriving Production Rules for Incremental View Maintenance", Proceedings of 1991 VLDB Conference, pp. 577-589.
- X. Qian, G. Wiederhold, "Incremental Recomputation of Active Relational Expressions", IEEE Transactions on Knowledge and Date Engineering, vol. 3, No. 3, Sep. 1991.
- A. Gupta, I. S. Mumick, V. S. Subrahmanian, "Maintaining Views Incrementally", SIGMOD '93.
- J. Srivastava, D. Rotem, "Analytical Modeling of Materialized View Maintenance", PODS '88.
- J. A. Blakeley, P. Larson, F. W. Tompa, "Efficiently Updating Materialized Views", Proceedings of Sigmod '86, Washington, D.C. May 28-30, 1986.
- E. N. Hanson, "A Performance Analysis of View Materialization Strategies", Proceedings of SIGMOD, May 27-29, 1987.
- A. Gupta, I. S. Mumick, "Maintenance of Materialized Views: Problems, Techniques, and Applications", Bulletin of the Technical Committee on Data Engineering, vol. 18, No. 2, Jun. 1995.