Method and system for incremental database maintenance6484159Abstract The present invention is a method and system for incrementally maintaining a database having at least one materialized view based on at least one table. When changes to the table are received, a change table based on the received changes is generated. The generated change table is propagated upwards to form a higher-level change table and the materialized view is updated by applying the higher-level change table to the materialized view using a refresh operation. In one aspect, the change table includes a plurality of tuples representing the changes and the materialized view includes a plurality of tuples. The refresh operation has two parameters, a join condition and an update function specification. The materialized view is updated by finding all tuples in the materialized view that match the tuple in the change table, using the join condition, for each tuple in the change table and updating each found tuple in the materialized view by performing operations indicated by the update function specification. Claims What is claimed is: Description FIELD OF THE INVENTION
TABLE 1
Benefits of propagating change tables
(Materialized views are V.sub.2, V.sub.3, and V.sub.5.)
Changes Tuple Reads and Writes
Summary Number of (No. of Previous Present
Table Tuples Tuples) Work Invention
sales 1,000,000,000 10,000
stores 1,000 --
items 10,000 --
V.sub.1 = 1,000,000 600 610,000 10,000
SISales
V.sub.2 = 100 10 1,020 1,020
CitySales
V.sub.3 = 1,000 1,000 12,000 12,000
Category-
Sales
Total for V.sub.1, 623,020 23,020
V.sub.2, V.sub.3,
V.sub.4 = 1,000,000,010 10,000 2,000,000,010 11,000
SSInfo
V.sub.5 = 100,000 100 200 200
SSRecent-
Info
Total for V.sub.4 2,000,000,210 11,200
and V.sub.5
Rather than computing and propagating insertions and deletions beyond an aggregate node V.sub.1, as was done in the prior art, the present invention computes and propagates a change table for V.sub.1. A change table is a general form of the summary-delta tables introduced in an article by I. Mumick, D. Quass, and B. Mumick, entitled Maintenance of data cubes and summary tables in a warehouse, published in Proceedings of the AGM SIGMOD International Conference of Management of Data, Tucson, Ariz., June 1997. The symbol V is used to denote the change table of a view V. It is shown that propagation of change tables yields very efficient and simple maintenance expressions for general view expressions involving aggregate and outerjoin operators. The change table cannot be simply inserted or deleted from the materialized view. Rather, the change table must be applied to the materialized view using a special "refresh" operator. In Section 4, a refresh operator that is used to refresh views using the change tables is defined. The symbol {character pullout} is used to denote the refresh operator, where .theta. and U are parameters specifying join conditions and updated functions respectively. An example of the computation of change tables and refreshing of the CategorySales (V.sub.3) view 301 is shown in FIG. 3, when an exemplary sales table 302 is updated with insertions .DELTA.sales 304. As seen by its SQL definition, CategorySales is an aggregate view based on another aggregate view, SISales and on the items table 305. SISales is an aggregate view that is based on the sales table 304 and not on any other materialized views. Thus, SISales is termed a first-level materialized view, while CategorySales is a higher-level materialized view. A change table for SISales, change table V.sub.1 306 is generated based on the insertion table .DELTA.sales 304, as well as any deletion tables .gradient.sales (not shown). Since table V.sub.1 306 is associated with first-level materialized view, it is termed a first-level change table. In order to update CategorySales (V.sub.3) view 301, which is a higher-level view, a change table for CategorySales (V.sub.3) view 301 must be generated. This is done by propagating change table V.sub.1 306 upward to form a higher-level change table for the CategorySales (V.sub.3) view, V.sub.3 308. Change table V.sub.3 308 is applied to view V.sub.3 using the refresh operator {character pullout} to form refreshed view V.sub.3 312. The example starts with computing the change table V.sub.1 306 that summarizes the net changes to V.sub.1. For this first level of aggregates, the expression that computes V.sub.1 306 is similar to that derived in the article by Mumick, Quass and Mumick. V.sub.1 =.pi..sub.storeID,itemID,SumSISales=sum(price),NumSISales=sum(.sub..sub.-- .sub.count) (.PI..sub.storeID,itemID,price,.sub..sub.-- .sub.count=1 (.sigma..sub.p (.DELTA.sales)) {character pullout}.PI..sub.storeID,itemID,price=-price, _count=-1 (.sigma..sub.p (.gradient.sales))), where p is (date>Jan. 1, 1995). FIG. 3 presents an instance of the base relation sales 302 and the table .DELTA.sales 304, which is the set of insertions into sales. For the given tables, FIG. 3 also shows the computed change table V.sub.1 306. Next the change table V.sub.1 306 is propagated upwards to derive expressions for the change tables V.sub.2 (not shown) and V.sub.3 308 V.sub.3 =.pi..sub.category,SumCaSales=sum(SumSISales),NumCaSales=sum(NumSISales) (V.sub.1 {character pullout}items) FIG. 3 shows how the change table V.sub.3 308 is computed and the CategorySales (V.sub.3) view is refreshed. The change table V.sub.2 can be similarly computed. The new propagated change tables are then used to refresh their respective materialized views V.sub.2 and V.sub.3 using the refresh equations below (disregard .theta. and U for now). The details of the refresh equations are given in Example 3. Note that V.sub.1 does not need to be refreshed. V.sub.2 =V.sub.2 {character pullout}V.sub.2, and V.sub.3 =V.sub.3 {character pullout}V.sub.2. The refresh operation is illustrated by showing how the CategorySales view (V.sub.3) is refreshed. FIG. 3 shows the materialized table V.sub.3 =CategorySales for the given instance of base tables. Going back to computing the number of tuple accesses in Table 1, note that most of the computation is done in computing V.sub.1, which requires 10,000 tuple accesses to read .DELTA.sales. Given the small sizes of V.sub.1, items, and stores, the rest of the computation can be done in main memory and hence, the total number of tuples accesses is 10,000(to read .DELTA.sales)+11,000(to read items and sales)+2,020(to refresh V.sub.2 and V.sub.3)=23,020, showing that our technique is very efficient in comparison to previous approaches. A block diagram of a general process 500 for refreshing an aggregated materialized view is shown in FIG. 5. In step 502, change tables are computed for the first-level aggregates on which the higher-level materialized view being refreshed is based. In step 504, the first-level change tables are propagated upwards and the higher-level change table is computed. In step 506, the higher-level materialized view is refreshed by applying the higher-level change table to the higher-level materialized view with the refresh operation. A block diagram of a general refresh operation, as performed in step 506, is shown in FIG. 6. The refresh operation is represented by the notation V=V{character pullout}V Thus, an updated view V is generated by applying the change table V to the unupdated view V using the refresh operation. The refresh operation take two parameters. The parameter denoted .theta. specifies the join conditions, which are used to match the tuples in V, which are to be updated, to the tuples in V that contain the updates. The parameter denoted U is a list of update function specifications, that is, a list of which tuple attributes are to be updated and the operations that are to be performed in order to update each attribute. In step 602, for each tuple in the change table V, a tuple in the view V is found using the join conditions specified by parameter .theta.. In the example of FIG. 3, the join condition .theta..sub.3 specifies matching a non-aggregated attribute of tuples in the view and change table, and the update function U.sub.3 specifies updating of at least some of the aggregated attributes of the tuples in the view. Thus, for each tuple v.sub.3 in V.sub.3, a match in V.sub.3 using the join condition V.sub.3 category=V.sub.3 category (specified in .theta..sub.3) is sought. The tuple v.sub.3 =<C1, 170,3> in V.sub.3 matches with the tuple v.sub.3 =<C1,690,4> of V.sub.3. If a new tuple is inserted into the underlying table E, then no tuples will be found in the materialized view V that match a tuple in the change table V. The tuple in the change table will be inserted into the view. If there are a plurality of such tuples to be inserted, all such insertions will be converted to aggregated insertions or updates into by the refresh equation. The deletions from E need not necessarily result in any deletions from V. A tuple is deleted from V only if an aggregated attribute representing a count of a number of tuples in a group represented by a the tuple becomes zero, which is independent of the deletions of the deriving tuples from E. In step 604, the found tuples are updated by updating the specified attributes. The tuple <C1,170,3> in V.sub.3 means that three more sales totaling $170 have occurred for C1 category. The total sales for C1 are now 7 for a total amount of $860. To reflect the change, the tuple V is updated to <C1,860,7> by adding together the corresponding aggregated attributes (specified by the U.sub.3 parameter of the refresh operator). Outerjoins The change-table technique can also be used for maintenance of view expressions involving outerjoin operators. Outerjoin views are supported by SQL and are commonly used in practice, such as for data integration. The technique for maintaining outerjoin views by deriving maintenance expressions for outerjoin views V.sub.4 and V.sub.5 is illustrated. The net changes to V.sub.4, in response to insertions .DELTA.sales into sales, can be succinctly summarized in a change table V.sub.4. The change table V.sub.4 is computed and then propagated up as follows: V.sub.4 =.DELTA.sales{character pullout}.sub.sales,storeID=stores,storeID stores V.sub.5 =.sigma..sub.(date.gtoreq.1/1/95) (V.sub.4) V.sub.5 =V.sub.5 {character pullout}V.sub.5 FIG. 4 shows the materialized view V.sub.5 402,the change tables V.sub.4 and V.sub.5 404 for the database instance of FIG. 3, and the refreshed view V.sub.5 406. The process for refreshing an outerjoin view is similar to the process for refreshing an aggregate view. First-level change tables are computed, in the example of FIG. 4, using the equation V.sub.4 =.DELTA.sales{character pullout}.sub.sales,storeID=stores,storeID stores. The first-level change tables are propagated upwards and the higher-level change table is computed, in the example of FIG. 4, using the equation V.sub.5 =.sigma..sub.(date.gtoreq.1/1/95) (V.sub.4). The higher-level materialized view is refreshed by applying the higher-level change table to the higher-level materialized view with the refresh operation, in the example of FIG. 4, using the equation V.sub.5 =V.sub.5 {character pullout}V.sub.5. The major difference is in the specification of the refresh operation. For example, the refresh of V.sub.5 proceeds as follows. When an outerjoin is performed, two or more tables are merged to form a new table or view. The new table or view has a tuple corresponding to each value of a selected attribute or attributes present in any original table. Since it is not required that there be tuples corresponding to each value of the selected attribute in all original tables, the values of some attributes in the new table or view may be undefined. This is represented in FIG. 4 as NULL. Insertions into an original table may result in tuples being inserted into the new table or view, if no tuples in the view match the tuple in the change table, or they may result in undefined attributes being defined. Likewise, deletion from an original table may result in tuples being deleted from the new table or view, if the value of the selected attribute in that tuple is no longer present in any original table, or they may result in defined attributes becoming undefined. For example, each tuple in V.sub.5 is matched with tuples in V5 that have the same stores attributes, but have all NULL's in the attributes of sales. This join condition used for matching is specified in .theta..sub.5. In the example of FIG. 4, the only matching pair is (v5, v5), where v5=<NY3,13,1/1/92,100,NY3,Buffalo,NY>.di-elect cons.V.sub.5 and v.sub.5 =<NULL,NULL,NULL,NULL,NY3,Buffalo,NY>.di-elect cons.V.sub.5. The match results in an update of v5 to v5, according to the update specifications in U.sub.5. The remaining unmatched tuples in V.sub.5 are inserted into the view V.sub.5. The refreshed view V.sub.5 is also shown in FIG. 4. Given the small sizes of stores, .gradient.sales, and V.sub.4, the number of tuple accesses required to compute the change tables and refresh V.sub.5 is 10,000(to read .DELTA.sales)+1,000(to read stores)+200(to refresh V.sub.5). The present invention includes a novel technique to maintain general view expressions involving outerjoin operators. Previous work, for example, the article by A. Gupta, H. V. Jagadish, and I. S. Mumick, entitled Maintenance and self-maintenance of outerjoin views published in Proceedings of the NGITS, Tel Aviv, Israel, June 1997, only considers views that have outerjoin as the last operator. To apply the technique of that article to our example, it would be necessary to compute the intermediate view SSInfo, thereby incurring more than a billion tuple accesses. 3. The Change-Table Technique for View Maintenance This section explains the framework developed in the article by Xiaolei Qian and Gio Wiederhold entitled Incremental recomputation of active relational expressions. Published in IEEE Transactions on Knowledge and Data Engineering, pages 337-341, 1991, and the article by T. Griffin and L. Libkin entitled Incremental maintenance of views with duplicates published in Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 328-339, San Jose, Calif., May 1995, for deriving incremental view maintenance expressions and relate it to the change-table technique of the present invention. Let a database contain a set of relations R={R.sub.1, R.sub.2, . . . , R.sub.n }. A change transaction t is defined to contain for each relation R.sub.i the expression R.sub.i.rarw.(R.sub.i -.gradient.R.sub.i){character pullout}.DELTA.R.sub.i, where .gradient.R.sub.i is the set of tuples to be deleted from R.sub.i, and .DELTA.R.sub.i is the set of tuples to be inserted into R.sub.i. Let V be a bag-algebra expression defined on a subset of the relations in R. The refreshed-expression New(V, t) is used to compute the new value of R. In the article by Griffin and Libkin (which uses the notation pre(t, V) instead) the expression New(V, t) is defined to be: New(V, t)=(V-.gradient.(V, t)){character pullout}.DELTA.(V, t). So, the goal in deriving view maintenance expressions for a view V is to derive two functions .gradient.(V, t) and .DELTA.(V, t) such that for any transaction t, the view V can be maintained by evaluating (V-.gradient.(V, t)){character pullout}.DELTA.(V, t). In order to derive .gradient.(V, t) and .DELTA.(V, t), the article by Griffin and Libkin gives change propagation equations that show how deletions and insertions are propagated up through each of the relational operators. The work of Griffin and Libkin was extended to include aggregate operators by D. Quass, Materialized Views in Data Warehouses, Ph.D. thesis, Stanford University, Department of Computer Science, 1997, Chapter 4. The change-table technique of the present invention can be thought of as introducing a novel definition for New(V, t). The expression New(V, t) for view expressions involving aggregates and outerjoin is redefined as New(V, t)=(V{character pullout}(V, t)), where (V, t) is called the change table, {character pullout} is the refresh operator used to apply the net changes in a change table to its view, and (.theta., U) are the parameters of the refresh operator. The parameter .theta. specifies the join conditions on the basis of which the tuples from the change table and the view are matched. The parameter U specifies the functions that are used to update the matched tuples in V. The new definition of New(V, t) is motivated from the following observation. In the case of general view expressions involving aggregate operators, it is usually more efficient to propagate the change tables beyond an aggregate operator, instead of first computing and then propagating insertions and deletions. Propagation of the change table is particularly efficient when the change table depends only on the changes to the base relation, while the insertions and deletions depend on the old value of the view. As shown in the motivating example, if the aggregate node is not materialized, the computation of insertions and deletions could be very expensive. The new definition of New(V, t) means that it is necessary to define a general refresh operator, and derive change propagation equations for propagating change tables through various relational, aggregate and outerjoin operators, to obtain a complete technique for efficient incremental maintenance of general view expressions. In the following section, a formal definition of the refresh operator is presented. In later sections, change propagation equations for general view expressions involving aggregate and outerjoin operators is derived. 4. The refresh Operator In this section, a formal treatment of the refresh operator is given. Given a materialized table V and its change table V, the refresh is used to apply the changes represented in a change table. The binary refresh operator is a generalization of the refresh algorithm used in the article by Mumick, Quass and Mumick. The refresh operator is denoted by {character pullout}, where .theta. is a pair of two mutually exclusive join conditions and U is a list of update function specifications. The refresh operator takes two operands, a view V to be updated and a corresponding change table (denoted by V). Let V and V be views with the same attribute names A.sub.1, A.sub.2 . . . , A.sub.n. The subscript .theta. associated with the operator is a pair of join conditions .Fourier..sub.1 and .Fourier..sub.2. The superscript U is a list specifying the attributes that may be changed by the change operator, along with the update functions that specify the exact nature of the change to each attribute being changed. More precisely, U=<(A.sub.i.sub..sub.1 , .function..sub.1), (A.sub.i.sub..sub.2 , .function..sub.2), . . . , (A.sub.i.sub..sub.k , .function..sub.k)>, where A.sub.i.sub..sub.j , . . . , A.sub.i.sub..sub.k are attributes of V and .function..sub.1, . . . , .function..sub.k are functions. Unless otherwise specified, it is assumed that the functions in U are binary functions. In an expression V{character pullout}V, each tuple v of V is checked for possible matches (due to .Fourier..sub.1 or .Fourier..sub.2) with tuples in V. If a match is found due to the join condition .Fourier..sub.1, then the corresponding matching tuple v of V is updated as described in the next paragraph (using the specifications in the update list U). If the match is due to .Fourier..sub.2, the tuple v of V is deleted. The unmatched tuples in V are inserted into V. The matching done is one-to-one in the sense that a tuple v.di-elect cons.V matches with at most one tuple in V and vice-versa. If v finds more than one match in V, then an arbitrary matching tuple from V is picked. Update of a tuple v of V matching with the tuple v of V is done based on the update functions in U. For each pair (A.sub.i.sub..sub.j , .function..sub.j) in U, the A.sub.i.sub..sub.j attribute of v is changed to .function..sub.j (v(A.sub.i.sub..sub.j ), vA.sub.i.sub..sub.j )) where v(X) and v(X) denote the values of the X attribute of v and v respectively. Each pair in U is used to change the matching U is used to change the matching tuple V. EXAMPLE 2 Consider the view V.sub.3 =Categorysales defined in Example 1 earlier. The CategorySales table as defined in Example 1 computes the total sales for each category. In this example, the refresh operation is illustrated by applying the changes summarized in a change table CategorySales to its view CategorySales using the refresh operator. For this example, consider the instance of the base table shown in FIG. 3. FIG. 3 also shows the materialized table Categorysales for the given instance. In response to the insertion of the table .DELTA.sales into the base table sales, the change table CategorySales can be computed and is shown in the FIG. 3. The view CategorySales is refreshed using the expression CategorySales {character pullout}CategorySales, where the parameters, .theta..sub.3 =(.Fourier..sub.1, .Fourier..sub.2) and U.sub.3, of the refresh operator are defined as follows. .Fourier..sub.1 is (.ident..sub.category {character pullout}((CategorySales.NumCaSales+(CategorySales) .NumCaSales).noteq.0)) .oe butted..sub.2 is (.ident..sub.category {character pullout}((CategorySales.NumCaSales+(CategorySales) .NumCaSales)=0)) U.sub.3 =<(SumCaSales, .function.),(NumCaSales, .function.)>, where .function.(x, y)=x+y for any x, y. Note that .ident..sub.category represents the predicate (CategorySales.category=(CategorySales).category) here. Now, the refresh operation is attempted to be run on the change table CategorySales and the view CategorySales of FIG. 3. The first tuple v.sub.3 =<C1,170,3> of CategorySales matches with the tuple v.sub.3 =<C1,690,4> in CategorySales using the join condition .Fourier..sub.1. The match results in update of the tuple <C1,690,4> in CategorySales according to the specifications in the update list U.sub.3. The attribute SumCaSales of the tuple v.sub.3 is changed to v.sub.3.SumCaSales+v.sub.3.SumCaSales=170+690=860 and the attribute NumCaSales is changed to 4+3=7. Similarly, the tuple <C2,210,2>.di-elect cons.V.sub.3 matches with the tuple <C2,120,2>.di-elect cons.V.sub.3 and is updated to <C2,330,4>. The tuple <C3,480,2>.di-elect cons.V.sub.3 is also updated to <C3,530,3> accordingly. To illustrate deletion from the view Categorysales, let us assume that the change table Categorysales contains a tuple b=<C2,-210,-2> as a result of a deletion of a couple of tuples from the sales table. The tuple b will match with the tuple v=<C2,210,2>.di-elect cons.V.sub.3 using the join condition .Fourier..sub.2 and the match will result in deletion of the tuple v from V.sub.3. Implementation of the Refresh Operator One simple way to implement the refresh operator is using a nested loop algorithm, with the change table as the outer table, and the materialized view table as the inner table, as shown in Appendix A. The nested loop algorithm is just one possible way to implement the refresh operator. Quass and Mumick have developed a more efficient implementation of the refresh operation that uses existing outerjoin methods inside the DBMS. They defined a modify operator using a pair of join conditions and a series of condition-action lists. The modify operator can be easily implemented in a DBMS through slight modifications of existing physical query operators for outerjoins, such as hash outerjoin, sort-merge outerjoin, and nested-loop outerjoin. Cost-based optimization can be used to select the method most suitable for a given evaluation. Implementing the refresh operation of the present invention using the modify operator is significantly faster than iterative algorithms. 5. Propagating Change Tables Generated at Aggregates In this section, the derivation is given for the algebraic equations to (1) generate change tables at an aggregation node in a view expression, and (2) propagate these change tables through the relational, aggregate and outerjoin operators in a general view expression. DEFINITION 1 (Aggregate-change Table) A change table for a view expression involving aggregates is defined as an aggregate-change table if the change table either originated at an aggregate operator or is a result of propagation of a change table that originated at an aggregate node, using the propagation equations presented in Table 3. For example, the change tables, V.sub.1, V.sub.2, and V.sub.3, computed for the views V.sub.1, V.sub.2, and V.sub.3 respectively in Example 1 are aggregate-change tables. Note that the notions of aggregate-change table and outerjoin-change table have been defined only for simplifying the presentation of the material in this article. The present invention contemplates a general change table that encompasses aggregate-change tables, outerjoin-change tables and any other specific type of change table. DEFINITION 2 (Distributive Functions) An aggregate function is defined as distributive if it can be computed by partitioning the input parameters into disjoint sets of parameters, aggregating each set individually, then further aggregating the (partial) results from each set into the final result. DEFINITION 3 (Self-maintainable Aggregates) An aggregate function is defined to be self-maintamnable if the new value of the function can be computed solely from the old value of the function and the changes (insertions or deletions) to the base data. It will be shown that a special case of the general refresh operator is sufficient to apply the changes summarized in an aggregate-change table to its view. The special form yields very simple change propagation equations for propagation of aggregate-change tables through relational, aggregate and outerjoin operators. The notation Attrs(X) is used to represent the set of attributes referenced in X. Thus, Attrs(U) refers to the set of attributes specified in the update list U and Attrs(.theta.) represents Attrs(.Fourier..sub.1)U Attrs(.Fourier..sub.2), where .Fourier..sub.1 and .Fourier..sub.2 are the join conditions in .theta.=(.Fourier..sub.1, .Fourier..sub.2). 5.1 Generating the Aggregate-Change Table Consider a view V defined as an aggregation over a select-project-join (SPJ) expression. In this section, a brief description is given of how an aggregate-change table is generated at V in response to the insertions and deletions at the base tables. The method is similar to that of generating "summary-delta tables" for a "summary table" as described in the article by Mumick, Quass and Mumick. For the case when a view V is defined as an aggregation over an SPJ expression, the insertions and deletions to the base tables can be propagated to V as a single aggregate-change table, which is denoted by V. Without loss of generality, let us assume V to be .pi..sub.G,B=.function.(A) (R), where R is the SPJ subview, G is the set of group-by attributes, f is an aggregate function, and A is an attribute of R. In the case of distributive aggregate functions, the aggregate-change table V can be computed from the insertions and deletions into R by using the same generalized projection as the used for defining the view V. More precisely, V can be computed as V=.pi..sub.G,.function.(A),Count=sum(.sub..sub.-- .sub.count) (.PI..sub.G,A,.sub..sub.-- .sub.count=1 (.DELTA.R){character pullout}.PI..sub.G,A=N(A),.sub..sub.-- .sub.count=-1 (.gradient.R)), where the function N is suitably defined depending on the aggregate function .function. as shown in Table 2. For example, in the case of a sum aggregate the function N negates the attribute value passed. Once the aggregate-change table has been computed, the net changes, now in the aggregate-change table, are then applied to the view using the refresh operator. If the aggregate function .function. is a self-maintainable aggregate function, then the special form of refresh operator defined in the next subsection is sufficient to apply the change table V to the view V. For the case of aggregate functions that are not self-maintainable, more complex functions are needed in the update list U of the refresh operator. For example, to handle deletions from a subview of a simple MIN/MAX aggregate view, the update function needs to compute the new MIN/MAX value, if needed, by accessing the base relations (see the article by Mumick, Quass and Mumick for details). The change propagation equations and other formalism presented in this article are independent of the complexity and input parameters of update functions used in the update list U of refresh.
TABLE 2
Table used to change the aggregate attributes in deletions
Aggregate Change due to N
COUNT(*) -1
SUM(expr) -expr
MIN(expr) expr
MAX(expr) expr
5.2 Refresh Operator for Applying Aggregate-Change Tables For the case of applying net changes computed in an aggregate-change table to its view, the refresh operator required is a special case of the generic operator defined earlier in Section 4. The special characteristics of the refresh operator are used to derive simpler change propagation equations. Recall that the expression used to refresh a view V using its change table V is V=V{character pullout}V, where .theta.=(.Fourier..sub.1, .Fourier..sub.2) and U is the update list. In the case of the refresh operator used to apply aggregate-change tables, .Fourier..sub.1 is (.ident..sub.G {character pullout}{character pullout}p) and .Fourier..sub.2 is (.ident..sub.G {character pullout}p), for some predicate p and a set of attributes G common to both V and V. As defined before, the notation .ident..sub.G here represents the predicate {character pullout}.sub.g.di-elect cons.G (V..sub.g =V..sub.g), as V and V are the left and right operands of the join operator. Also, the set of attributes G is disjoint from the set of attributes, Attrs(U), that are being updated. The predicate p specifies when the matching tuple in V is to be deleted, i.e., when the value of the attribute that stores the number of deriving base tuples becomes zero. An aggregate-refresh operator is derived that is a special form of the refresh operator (as described above) used to apply an aggregate-change table to its view. The characteristics of the aggregate-refresh operator are used to derive simple change propagation equations for propagating aggregate-change tables. DEFINITION 4 (Aggregate-refresh Operator) A refresh operator {character pullout} is said to be an aggregate-refresh operator if: .theta.=(.Fourier..sub.1, .Fourier..sub.2) and the join condition .Fourier..sub.1 is (.ident..sub.G {character pullout}p.sub.1), and the join condition .Fourier..sub.2 is (.ident..sub.G {character pullout}p.sub.2), for some predicates p.sub.1, p.sub.2 and a set of attributes G common to both the view and its aggregate-change table. p.sub.1 ={character pullout}p.sub.2. G.andgate.Attrs(U)=.phi.. 5.3 Change Propagation Equations Table 3 gives the change propagation equations for propagating aggregate-change tables through relational, aggregate and outerjoin operators. Below, is a brief explanation of each row of Table 3. In this table, it is assumed that an aggregate-change table has been generated at the first aggregate operator in a view expression, in response to insertions and/or deletions from the view's subview. The above base case has not been shown in the table. In Theorem 1, the correctness of the refresh equations of Table 3 is proven.
TABLE 3
Change propagation equations for propagating aggregate-change and
outerjoin-change
tables
No. V New V Refresh Equation V
Conditions
.theta. = .Fourier..sub.1, .Fourier..sub.2)
.Fourier..sub.1 is .ident..sub.G {character
pullout}{character pullout}p.sub.1
.Fourier..sub.2 is .ident..sub.G {character
pullout}p.sub.1
1 .sigma..sub.p (E.sub.1) .sigma..sub.p (E.sub.1 {character
pullout}E.sub.1) V{character pullout}.sigma..sub.p (E.sub.1) .sigma..sub.p
(E.sub.1) Attrs(p) .OR right. G
2 .PI..sub.A (E.sub.1) .PI..sub.A (E.sub.1 {character pullout}E.sub.1)
V{character pullout}.PI..sub.A (E.sub.1) .PI..sub.A (E.sub.1)
Attrs(.theta.) .OR right. A
3 E.sub.1 .times. E.sub.2 (E.sub.1 {character pullout}E.sub.1) .times.
E.sub.2 V{character pullout} (E.sub.1 .times. E.sub.2) E.sub.1 .times.
E.sub.2
.theta..sub.1 = (.Fourier..sub.1
{character pullout}.ident..sub.r, .Fourier..sub.2 {character
pullout}.ident..sub.r)
.tau. = Attrs(E.sub.2)
4 E.sub.1 {character pullout} E.sub.2 (E.sub.1 {character pullout}
E.sub.1) {character pullout}E.sub.2 V{character pullout}(E.sub.1
{character pullout} E.sub.2) E.sub.1 {character pullout} E.sub.2 Attrs(J)
.OR right. G
.theta..sub.1 = (.Fourier..sub.1
{character pullout}.ident..sub.r, .Fourier..sub.2 {character
pullout}.ident..sub.r)
.tau. = Attrs(E.sub.2)
5 E.sub.1 {character pullout} E.sub.2 (E.sub.1 {character pullout}
E.sub.1) {character pullout}E.sub.2 ((V-E.sub.2 {character pullout}
E.sub.1) {character pullout}E.sub.2 E.sub.1
6 .pi..sub.G',F (E) .pi..sub.G',F (E{character pullout} E) V{character
pullout}.pi..sub.G',f(A) (E) .pi..sub.G',F (E) A.sub.i .di-elect cons.
Attrs(U), G'
F = f.sub.1 (A.sub.1), .theta..sub.3 =
(.ident..sub.G' {character pullout}{character pullout}p.sub.3,
.ident..sub.G' {character pullout}p.sub.3) .OR right. G,
f.sub.i 's are
. . . , f.sub.k (A.sub.k). p.sub.3 is (V.Cnt +
V.Cnt) .noteq. distributive, and
0
the function in U
U.sub.3 = <(A.sub.1, f.sub.1), .
. . , (A.sub.k, f.sub.k)> for A.sub.i is f.sub.i.
7 E.sub.1 {character pullout} E.sub.2 (E.sub.1 {character pullout}
E.sub.1) {character pullout}E.sub.2 V{character pullout}(E.sub.1
{character pullout} E.sub.2) (E.sub.1 {character pullout} Attrs(J) .OR
right. G
.theta..sub.1 = (.Fourier..sub.1
{character pullout}.ident..sub.r, .Fourier..sub.2 {character
pullout}.ident..sub.r) E.sub.2)
.tau. = Attrs(E.sub.1)
Each row in the table considers propagation of an aggregate-change table through a relational, aggregate or outerjoin operator. The first column gives the equation number used for later reference in examples. The second column in the table gives the definition of V. The third column expresses the new expression for V due to a change occurring at one of the subexpressions E.sub.1 of V. In each row, possibly due to changes at base table, the subexpression E.sub.1 changes to E.sub.1 {character pullout}E.sub.1 where E.sub.1 is an aggregate-change table and {character pullout} is an aggregate-change operator. It is assumed that .theta. is (.Fourier..sub.1, .Fourier..sub.2), where .Fourier..sub.1 is .ident..sub.G {character pullout}{character pullout}p1 and .Fourier..sub.2 is .ident..sub.G {character pullout}p.sub.1, for some predicate p.sub.1 and a set of attributes G in E.sub.1. The fourth column gives the refresh equation which is used to refresh the view V and also yields the value of the propagated aggregate-change table. In Theorem 1 it is proven that the refresh equation given in the fourth column is equivalent to the expression in the third column for each row of Table 3. Theorem 1 also proves that the refresh operator used in the refresh equations of fourth column is an aggregate-refresh operator. The fifth column gives the expression for the propagated aggregate-change table V. Finally, the last column of the table mentions the conditions under which the equivalence of the fourth column and third column expressions hold, i.e., conditions under which the change propagation can be done. If the condition is not satisfied, then the refresh equation cannot be used to propagate the aggregate-change table. Later, it will be shown how to handle changes at such an operator node, when the condition of Table 3 is not satisfied. The first row of the table depicts the case of a selection view V=.sigma..sub.p (E), where E is a subexpression. In this case, as depicted in the third column, the subexpression E changes to E{character pullout}E, where E is an aggregate-change table and {character pullout} is an aggregate-change operator. The expression for the propagated aggregate-change table V=.sigma..sub.p (E) is given in the fifth column. For the case of the selection view, the condition required for the change propagation is Attrs(p).OR right.G. In other words, an aggregate-change table can be propagated through a selection operator if the selection operator if the selection condition is defined over the G attributes, which are the attributes that are not being updated. The second row depicts the case of projection on a set of attributes A. The condition implies that an aggregate change table can be propagated through a duplicate-preserving projection only if all the attributes used in the join conditions of .theta. are included in the projection list A. The third row considers the case of a cross product operation. In this case, the parameter .theta. of the refresh operator is changed to also include the condition .ident..sub.Attrs(E.sub..sub.2 .sub.) in the join conditions .Fourier..sub.1, and .Fourier..sub.2. No conditions are specified in the fifth column meaning that any aggregate-change table can be propagated through a cross product operator. The fourth row depicting the case of a join operation follows from the combination of previous cases of selection and cross product. The fifth row considers propagation of an aggregate-change table through the bag union operator. The expression for V in the fifth column gives only the change table (V=E.sub.1). As the refresh equation in the fourth column shows, the refresh in this case is more complex than simply applying the change table. It is necessary to apply a set of deletions (.gradient.V=E.sub.2) into the view V. One can derive a very efficient refresh equation for the case of bag union operator, if the tuples in V are "tagged" L/R depending on whether they come from the left operand E.sub.1 or the right, operand E.sub.2. The sixth row depicts the case of propagation through a generalized projection (aggregate) operator. For the purposes of aggregate-change tables, it is assumed that any subexpression involving an aggregate operator stores with each tuple a count of the number of deriving base tuples. This count is stored in a general attribute which is called the count attribute. For example, NumCiSales and NumCaSales are count attributes in the views V.sub.2 and V.sub.3 of Example 1. After propagation through the aggregate operator, the join conditions and the update specifications of the refresh operator change as shown in the fourth column. The attribute named Cnt used in p.sub.3 is the count attribute of V. The condition in the fifth column says that each aggregate function .function..sub.i is distributive, the set of group-by attributes G' is a subset of G, and the update list U used to change E contains (A.sub.i, .function..sub.i) for all 1.ltoreq.i.ltoreq.k. Note that the duplicate-elimination operation is a special case of generalized projection, and is covered by the sixth row. The seventh row gives the refresh equation for the case of propagating an aggregate-change table through a full outerjoin operation. In this case, the refresh operator specifications change as in the case of cross product. The outerjoin propagation equation in the seventh row is simplified a little (as discussed in Appendix C). Note that no change propagation equation is given for the case of monus because an aggregate-change table cannot be propagated through the minus operator (See the paragraph on singularity points below). Also, the refresh operator used in each of the derived refresh equations of column 4 is an aggregate-refresh operator. Singularity Points The operator nodes in a view expression tree, where none of the refresh equations in Table 3 apply, are called singularity points. Consider a view V and a singularity point V.sub.1, which is a subexpression of V, in the expression tree of V. As propagation of the change table V.sub.1 is not possible, it is necessary to compute insertions (.DELTA.V.sub.1) and deletions (.gradient.V.sub.1) into V.sub.1 and propagate the insertions and deletions upwards. The tables .DELTA.V.sub.1 and .gradient.V.sub.1 can be computed from V.sub.1 by applying the refresh algorithm (Algorithm 1). If V.sub.1 is not materialized, the base relations are used to compute (relevant parts of) V.sub.1 whenever required by the refresh algorithm. The insertions (.DELTA.V.sub.1) and deletions (.gradient.V.sub.1) to V.sub.1 are then propagated through the singularity point using the change propagation equations described in the article by Griffin and Libkin, and in the article by Quass. The propagation insertions and deletions at a singularity point can now be propagated upwards using techniques presented in this article (as they may result in change tables further on) or the techniques of Griffin and Libkin for propagating insertions and deletions through relational operators. THEOREM 1 Assume that the refresh operator used in the expression of the third column in Table 3 is an aggregate-refresh operator. Then, the change propagation equations given in Table 3 for propagation of aggregate-change tables are correct, i.e., for each row, the expression in the third column is equivalent to the refresh equation in the fourth column. Also, the refresh operator derived in the refresh equation (column 4) is an aggregate-refresh operator as well. EXAMPLE 3 In this example, the techniques developed in this section are illustrated as applied to the views of the motivating Example 1. Recall from Example 1 the definitions of V.sub.1 (SISales), V.sub.2 (CitySales), and V.sub.3 (CategorySales). Thus: V.sub.1 '=.pi..sub.storeID,itemID,SumSISales=sum(price), NumSISales=count(*) (sales) V.sub.1 =.sigma..sub.date>1/1/95 (V.sub.1 ') V.sub.2 '=V.sub.1 {character pullout}stores V.sub.2 =.pi..sub.city,itemID,SumSISales=sum(price),NumSISales=count(*) (V.sub.2 ') V.sub.3 '=V.sub.1 {character pullout}items V.sub.3 =.pi..sub.category,SumCaSales=sum(SumSISales),NumCaSales=sum(NumSISales) (V.sub.3 ') where the (virtual) views V.sub.1 ', V.sub.2 ' V.sub.3 ' have been added for better illustration of how the aggregate-change tables propagation. The change propagation equations of Table 3 are used to derive the maintenance expressions for V.sub.2 and V.sub.3 in response to changes in sales, as follows. V.sub.1 '=.pi..sub.storeID,itemID,SumSISales=sum(price),NumSISales=sum(.sub..sub. -- .sub.count) (.PI..sub.storeID,price,.sub..sub.-- .sub.count=1 (.DELTA.sales) {character pullout}.PI..sub.storeID,price=-price,.sub..sub.-- .sub.count=-1 (.gradient.Sales)) [From Section 5.1] V.sub.1 =.sigma..sub.date>1/1/95 (V.sub.1 ') [From (1) in Table 3] V.sub.1 =V.sub.1 {character pullout}(V.sub.1), where .theta..sub.1 =(.ident..sub.{storeID,itemID} {character pullout}{character pullout}p, .ident..sub.{storeID,itemID} {character pullout}p) V.sub.2 '=V.sub.1 {character pullout}stores V.sub.2 '=V.sub.2 {character pullout}V.sub.2 ', [From (4) in Table 3] where .theta..sub.12 is (.ident..sub.{storeID,itemID}.orgate.Attrs(stores) {character pullout}{character pullout}p, .ident..sub.{storeID,itemID}.orgate.Attrs(stores) {character pullout}p) V.sub.2 =.pi..sub.city,SumSISales=sum(SumSISales),NumCiSales=sum(NumSISales) (V.sub.2 ') [From (6) in Table 3] V.sub.3 '=V.sub.1 {character pullout}items V.sub.3 '=V.sub.3 '{character pullout}V.sub.3 ', [From (4) in Table 3] where .theta..sub.13 is (.ident..sub.{storeID,itemID}.orgate.Attrs(items) {character pullout}{character pullout}p, .ident..sub.{storeID,itemID}.orgate.Attrs(items) {character pullout}p) V.sub.3 =.pi..sub.category,SumCaSales=sum(SumSISales),NumCaSales=sum(NumSISales) (V.sub.3 ') V.sub.3 =V.sub.3 {character pullout}V.sub.3, where .theta..sub.3 is (.ident..sub.category {character pullout}{character pullout}p, .ident..sub.category {character pullout}p) [From (6) in Table 3] In all the above equations, U is of the form <(SUM, .function.)(COUNT, .function.)> and p is of the form (LHS.COUNT+RHS.COUNT)=0), where SUM is the aggregated attribute (SumSISales, SumCiSales, or SumCaSales) in the corresponding view, COUNT is the count attribute (NumSISales, NumCiSales, or NumCaSales) depending on the view, and .function.(x, y)=x+y for all x, y. (Recall that LHS and RHS refer to the left and right operands of the join operation where p occurs.) As described in Example 1, the above derived maintenance expressions for V.sub.2 and V.sub.3 are very efficient compared to the expressions derived by previous approaches. 6. Maintaining Outerjoin Views Efficiently In this section, it is shown how our change-table techniques can be used to derive efficient and simple algebraic expressions for maintenance of view expressions involving outerjoin operators. Outerjoin is supported in SQL. Further, outerjoins have recently gained importance because data from multiple distributed databases can be integrated by means of outerjoin views. Outerjoins are also extensively used in object-related relational systems. DEFINITION 5 (Outerjoin-change Table) A change table for a view involving outerjoin operations is defined as an outerjoin-change table if the change table was either generated at an outerjoin operator or is a result of propagation of an outerjoin-change table, using the propagation equations that will be derived for propagating outerjoin-change tables. For example, the change tables, V.sub.4 and V.sub.5, computed for the views V.sub.4 and V.sub.5 in Example 1 are outerjoin-change tables. First, it is shown how the insertions and deletions into an outerjoin view (R{character pullout}S), in response to insertions into the base table R, can be summarized into an outerjoin-change table. The next changes represented by the outerjoin-change table are then applied to the outerjoin view using the refresh operator. Computation of an outerjoin-change table at an outerjoin view in response to deletions from a base table requires a more general refresh operator, as discussed in Appendix C. 6.1 Generating Outerjoin-Change Table At An Outerjoin Node Given tables R(A.sub.1, A.sub.2, . . . , A.sub.n) and S(B.sub.1, B.sub.2, . . . , B.sub.m), consider an outerjoin view V(A.sub.1, . . . A.sub.n, B.sub.1, . . . , B.sub.m)=R{character pullout}S, where J is an equi-join condition. Insertions into R, .DELTA.R, result in some insertions and deletions into V. These set of insertions and deletions to V can be summarized into an outerjoin-change table V defined as V=.DELTA.R{character pullout}S. Note that the tables V and V have the same schema and attribute names. It is shown that with the following specification of the refresh operator, the net changes in the outerjoin-change table V can be applied to the view V to obtain the correctly refreshed V. The specifications .theta.=(.Fourier..sub.1, .Fourier..sub.2) and U, of the refresh operator used to apply V to V are defined as follows. .Fourier..sub.1 is (.ident..sub.G {character pullout}p) where G=Attrs(S) and p=(E.sub.1.ltoreq.j.ltoreq.n (V.A.sub.j =NULL)). .Fourier..sub.2 is FALSE. The update list U of update function is <(A.sub.1, .function.), (A.sub.2, .function.), . . . , (A.sub.n, .function.)>, where .function.(x, y)=y for all x, y. THEOREM 2 Consider the view V=R{character pullout}S defined as above. For the above definition of V and the refresh operator specifications of .theta.=(.Fourier..sub.1, .Fourier..sub.2) and U, the following holds: (R{character pullout}.DELTA.R){character pullout}S=(R{character pullout}S){character pullout}(V) 6.2 Propagating Outerjoin-Change Tables Only a special form of the generic refresh operator, which is called an outerjoin-refresh operator, is required to refresh a view using its outerjoin-change table. DEFINITION 6 (Outerjoin-refresh Operator) Let {A.sub.1, A.sub.2, . . . , A.sub.n, B.sub.1, B.sub.2, . . . , B.sub.m } be the set of attributes in V and its outerjoin-change table V. A refresh operator {character pullout} used to apply the outerjoin-change table V to its view V is said to be an outerjoin-refresh operator if: The join condition .Fourier..sub.1 is (.ident..sub.G {character pullout}p), where G={B.sub.1, B.sub.2, . . . , B.sub.m } and p is a predicate on the attributes (LHS.A.sub.1, LHS.A.sub.2, . . . , LHS.A.sub.n). The join condition .Fourier..sub.2 is FALSE. U is <(A.sub.1, .function.), (A.sub.2, .function.), . . . , (A.sub.n, .function.)>, where .function.(x, y)=y for all x, y. Note that Attrs(U).andgate.G=.phi. and Attrs(U).andgate.G=Attrs(V). The refresh equations given in Table 3 correctly propagate an outerjoin-change table as well, except for the case of propagation through the outerjoin operator, for which a different equation is derived, as follows: Consider a view V=E.sub.1 {character pullout}E.sub.2 where E.sub.1 and E.sub.2 are general view expressions. Suppose that the expression E.sub.1 is refreshed to E.sub.1 {character pullout}E.sub.1 using its outerjoin-change table E.sub.1 where the refresh operator {character pullout} is an outerjoin-refresh operator. Let .theta.=(.ident..sub.G {character pullout}p, FALSE), for some predicate p and a set of attributes G common to E.sub.1 and E.sub.1. The following equation shows how to propagate the outerjoin-change table E.sub.1 to V under the condition Attrs(J).OR right.G. V=(E.sub.1 {character pullout}E.sub.2) V=((E.sub.1 {character pullout}E.sub.1){character pullout}E.sub.2)=E.sub.1 {character pullout}E.sub.2){character pullout}(V) where .theta..sub.1 =(.ident..sub.Attrs(E.sub..sub.2 .sub.) {character pullout}((p{character pullout}.ident..sub.G){character pullout}(E.sub.e.sub..sub.1 .sub..di-elect cons.Attrs(E.sub..sub.1 .sub.) LHS.e.sub.1 =NULL)),FALSE), U.sub.1 =<(A.sub.1, .function.),(A.sub.2, .function.), . . . ,(A.sub.k, .function.)>, and {A.sub.1, A.sub.2, . . . , A.sub.k }=Attrs(E.sub.1). The function .function. is such that .function.(x, y)=y for all x, y. Note that the refresh operator used in the equation (7b) to refresh V using V is an outerjoin-refresh as well. THEOREM 3 Assume that the refresh operator used in the expression of the third column in Table 3 is an outerjoin-refresh operator. Then, the change propagation equations given in Table 3, with the following two changes, correctly propagate outerjoin-change tables. The refresh equation for selection view is correct even without the condition given in column 6. The above equation (7b) is used for propagation through an outerjoin operator. Also, the refresh operator derived in each of the refresh equations (column 4) is also an outerjoin-refresh operator. EXAMPLE 4 Consider a view V=.pi..sub.A,B,F=sum(D),H=sum(E),Num=Count(*) ((.sigma..sub.A<5 ((R{character pullout}.sub.C=D S){character pullout}T)), where R(A, B, C), S(D, E), and T(A, B, L) are base relations, and {character pullout} is the natural join operation, i.e., a join with the join condition (.ident..sub.{A,B}). Recall that for the purposes of calculating the SUM aggregates, the attribute value of NULL is taken as 0, provided at least one tuple has a non-NULL value. For clarity of presentation, let us assume V.sub.1 =R{character pullout}.sub.C=D S, V.sub.2 =V.sub.1 {character pullout}T, V.sub.3 =.sigma..sub.A>5 (V.sub.2). Let us define a predicate p as ((LHS.D=NULL){character pullout} (LHS.E=NULL)), a predicate q as ((LHS.Num+RHS.Num)=0), an update list U.sub.1 as <(F, .function.),(H, .function.)>, and U as <(D, g),(E, g),(Num, g)>. Here, .function.(x, y)=y for all x, y and g(x, y)=x+y for all x, y.noteq.NULL and g(NULL, y)=y. The techniques of maintaining views involving outerjoin operators by deriving maintenance expressions for V in response to insertions, .gradient.S, into S, are illustrated. V.sub.1 =(R{character pullout}.gradient.S) V.sub.1 =V.sub.1 {character pullout}V.sub.1, where .theta..sub.1 is (.ident..sub.Attrs(R) {character pullout}p FALSE) [From Theorem 2] V.sub.2 =V.sub.1 {character pullout}T V.sub.2 =V.sub.2 {character pullout}V.sub.2, where .theta..sub.2 is (.ident..sub.Attrs(R).orgate..sub.Attrs(T) {character pullout}p, FALSE) [From (4) in Table 3] V.sub.3.sigma..sub.A>5 (V.sub.2) V.sub.3 =V.sub.3 {character pullout}V.sub.3 [From (1) in Table 3] V=.pi..sub.A,B,F=Sum(D),H=Sum(E),Num=Count(*) (V.sub.3) V=V{character pullout}V, where .theta. is (.ident..sub.{A,B} {character pullout}{character pullout}q, .ident..sub.{A,B} {character pullout}q) [From (4) in Table 3] APPENDIX A: REFRESH ALGORITHM Algorithm 1: Refresh Algorithm Input Table V(A.sub.1, A.sub.2, . . . , A.sub.n). Change Table V(A.sub.1, A.sub.2, . . . , A.sub.n). .theta.=(.Fourier..sub.1, .Fourier..sub.2), U=<(A.sub.i.sub..sub.1 , .function..sub.1), (A.sub.i.sub..sub.2 , .function..sub.2), . . . , (A.sub.i.sub..sub.k , .function..sub.k)> Output Refreshed table V, i.e., V{character pullout}V. Method DECLARE cursor box_CURSOR FOR SELECT A.sub.1, A.sub.2, . . . , A.sub.n FROM V; OPEN cursor_box; LOOP FETCH cursor_box INTO :a.sub.1, :a.sub.2, . . . , :a.sub.n,; UNTIL not-found DECLARE cursor_view CURSOR FOR SELECT A.sub.1, A.sub.2, . . . , A.sub.n FROM V WHERE (.Fourier..sub.1 (A.sub.1, A.sub.2, . . . , A.sub.n, : a.sub.1, : a.sub.2, . . . , : a.sub.n) OR .Fourier..sub.2 (A.sub.1, . . . , A.sub.n, :a.sub.1, . . . , : a.sub.n)) AND (NOT changed); OPEN cursor_view; LOOP FETCH cursor_view INTO :a.sub.1 :a.sub.2, . . . , : a.sub.n ; UNTIL not-found IF not-found INSERT INTO VVALUES (:a.sub.1, :a.sub.2, . . . , :a.sub.n); ELSE-IF .Fourier..sub.2 (:a.sub.1, :a.sub.2, . . . , :a.sub.n,:a.sub.1, :a.sub.2, . . . , :a.sub.n) DELETE FROM V WHERE CURRENT OF cursor_view; break; ELSE UPDATE V SET update attributes=function of update attributes from cursor_view as changed. break; ENDIF ENDLOOP CLOSE cursor_view; ENDLOOP CLOSE cursor_box; APPENDIX B: PROOF OF THEOREMS C.1 Proof of Theorem 1 Proof: Selection: V=.sigma..sub.p (E). First, it is shown that if e.di-elect cons.E affects a tuple v.di-elect cons..sigma..sub.p (E).OR right.E by updating or deleting v from R, then e.di-elect cons..sigma..sub.p (E). As e results in an update or deletion of v, the pair (es, e) satisfies the join condition (.ident..sub.G). Now, as Attrs(p).OR right.G. if es satisfies p then e satisfies p too. Thus, all tuples in E that can update or delete a tuple in V=.sigma..sub.p (E) are in .sigma..sub.p (E)=V. Therefore, all the required updates or deletions to V are captured by the refresh equation. Let I be the set of tuples in E that do not find a match in E.I is the set of tuples inserted into E and thus, .sigma..sub.p (I) should be inserted into V. As .sigma..sub.p (I).OR right..sigma..sub.p (E)=V, and as no tuple in .sigma..sub.p (I) will find a match in V.OR right.E, .sigma..sub.p (I) will be inserted into V using the refresh equation of V. Therefore, refresh equation doesn't miss any legitimate insertions into V. Also, a tuple v.di-elect cons..sigma..sub.p (E) cannot find a mach in .sigma..sub.p E.sub.1 because Attrs(p).OR right.G. Therefore, if v doesn't find a match in V=.sigma..sub.p (E), then v does not find a match in E. Hence, all insertions into V due to the refresh equation are legitimate. Projection: V=II.sub.A (E). If Attrs(.theta.).OR right.A, then the information needed to decide the effect of a tuple e.di-elect cons.E on a tuple e.di-elect cons.E, if any, is available in II.sub.A (s). Hence, E can be directly applied to V=II.sub.A (E) after the same projection step. Note that the resulting refresh operator is also an aggregate-refresh operator. Cross Product: V=E.sub.1.times.E.sub.2. Suppose a tuple e.sub.1.di-elect cons.E.sub.1 matches with a tuple e.sub.1.di-elect cons.E.sub.1. Consider the set E.sub.1.sup.[]e.sup..sub.1 =(e.sub.1.times.E.sub.2).OR right.V. It is easy to see that each tuple (e.sub.1, e.sub.2).di-elect cons.E.sub.2.sup.[]e.sup..sub.1 will result in a match with a tuple (e.sub.1, e.sub.2).di-elect cons.(e.sub.1.times.E.sub.2) due to the join conditions in .theta..sub.1. The matches will result in appropriate updates and deletions. Also any unmatched tuple e.sub.1.di-elect cons.E.sub.1 will also result in the unmatched tuples in (e.sub.1.times.E.sub.2).OR right.V. Join: V=E.sub.1 {character pullout}E.sub.2. Follows from the previous cases, but stated in the table for convenience. Union: V=E.sub.1 {character pullout}E.sub.2. As ((E.sub.1 {character pullout}E.sub.2)-E.sub.2)=E.sub.1, the equivalence of the expression is obvious. Aggregation: V=.pi..sub.G',.function.(A) (E). Without loss of generality, this case is proven when k=1. Let .function..sub.1 =.function. and A.sub.1 =A. It is assumed that (G'.OR right.G){character pullout}A.OR right.Attrs(U), U=<(A.sub.1, .function.), (A.sub.2, .function.), . . . , (A.sub.k, .function.)> and .function. is a distributive function. Let us assume that the tuples e.sub.1, e.sub.2, . . . e.sub.k.di-elect cons.E have the same G' values and their aggregated attribute A values are a.sub.1, a.sub.2, . . . , a.sub.k. Also, assume that the tuple e.sub.i matches with a tuple e.sub.i.di-elect cons.E due to .Fourier..sub.1 and that the aggregated attribute A value of e.sub.i is a.sub.1. Note that e.sub.i 's have the same G' values too. The attribute value a.sub.i of e.sub.i is updated to .function.(a.sub.i, a.sub.i) due to U. Thus the aggregated value in V derived from e.sub.i, . . . , e.sub.k should change from .function.(a.sub.1, a.sub.2, . . . , a.sub.n) to .function.(.function.(a.sub.1, a.sub.1), .function.(a.sub.2, a.sub.2), . . . , .function.(a.sub.n, a.sub.n)). Now, by the definition of V, the tuples e.sub.1, . . . , e.sub.k.di-elect cons.E will be grouped to yield the aggregate attribute value .function.(a.sub.1, . . . , a.sub.n). The refresh equation of V correctly changes the aggregated value of the grouped value of e.sub.i s from .function.(a.sub.1, a.sub.2, . . . a.sub.n) to .function.(.function.(a.sub.1, a.sub.2, . . . a.sub.n), .function.(a.sub.1, . . . , a.sub.n). As .function. is a distributive function, .function.(.function.(a.sub.1, a.sub.1), .function.(a.sub.2, a.sub.2), . . . .function.(a.sub.n, a.sub.n))=.function.(.function.(a.sub.1, a.sub.2, . . . , a.sub.n), .function.(a.sub.1, . . . , a.sub.n)), hence the refresh equation of V correctly updates the aggregated attribute values in V. All insertions into E due to E will be converted to aggregated insertions or updates into V by the refresh equation. The deletions from E need not necessarily result in any deletions from V. A tuple is deleted from V only if its aggregated attributes become zero, which is independent of the deletions of the deriving tuples from E. Outerjoin: V=E{character pullout}E.sub.2. Suppose E.sub.1 induces a set of insertions I into the relation E.sub.1. Each tuple i.di-elect cons.I results in a set of tuples E.sub.2.sup.i =i{character pullout}E.sub.2 in V. No tuple e.sub.2.sup.i.di-elect cons.E.sub.2.sup.i finds a match in V due to the predicate (.ident..sub.G {character pullout}.ident..sub..tau.), because if it did, i would have found a match in E.sub.1 due to .ident..sub.G. Therefore, the refresh equation results in E.sub.2.sup.i being inserted into V for each i.di-elect cons.I. Let us assume that M(.OR right.E.sub.1) is a set of tuples that find a match in E.sub.1 due to .ident..sub.G and hence, result in either deletion or update of a tuple in E.sub.1. Each tuple m.di-elect cons.M results in a set of tuples E.sub.2.sup.m =m{character pullout}E.sub.2 in V. If m matched with a tuple e.sub.2.di-elect cons.E.sub.2 due to both having the same G attributes, then each tuple (r,m).di-elect cons.E.sub.1.sup.m would match the corresponding tuple (r,s).di-elect cons.E.sub.1.sup.s =E.sub.1 {character pullout}S. The tuple (r,s) exists in E.sub.1 {character pullout}s because (r,m).di-elect cons.E.sub.1.sup.m and Attrs(J).OR right.G. Also, note that E.sub.2.sup.s.OR right.V. Thus the refresh equation of V affects the updates and deletions correctly. This completes the proof. C.2 Proof of Theorem 2 Proof: Due to insertion of .DELTA.R into R, the view V should change as follows. The set of tuples .DELTA.R{character pullout}S should be inserted into V but the tuples of the kind (NULL, . . . , NULL, s.sub.1, s.sub.2, . . . , s.sub.m).di-elect cons.V should be deleted from V if a corresponding tuple (r.sub.1, r.sub.2, . . . r.sub.n, s.sub.1, s.sub.2, . . . , s.sub.m) is being inserted into V from V. The above effect an be achieved by changing a tuple v=(NULL, . . . , NULL, s.sub.1, s.sub.2, s.sub.m) in V to v=(r.sub.1, r.sub.2, . . . , r.sub.n, s.sub.1, s.sub.2, . . . , s.sub.m) if such a tuple v exists in V. The refresh of V would be complete if the tuples v in V for which no such match occurs are inserted into V. By the definition of the refresh operator and its specification, one can see that is exactly what is achieved by the expression V{character pullout}V. C.3 Proof of Theorem 3 Proof. The proof is the same as in Theorem 1 except for the cases of selection and outerjoin, which uses a different equation. V=.sigma..sub.p (E). The second characteristic of the outerjoin-refresh operator is used to show that .sigma..sub.p (E{character pullout}E=.sigma..sub.p (E). Using the same arguments as in Theorem 1, the refresh equation of V doesn't miss any legitimate insertions into V affected by the refresh operation E{character pullout}E. Now it is shown that all insertions into V using the refresh equation are legitimate. The refresh equation may induce an insertion of the tuple v.di-elect cons.V into V if v doesn't find a match in V. If v.di-elect cons.I, where I is the set of tuples in E that don't find a match in E, then the insertion is obviously legitimate. Suppose, v.epsilon slash.I. That implies that v.di-elect cons.E found a match with a tuple e.di-elect cons.E. Because of the second characteristic of an outerjoin-refresh operator and its specification, any match results in the tuple in E being updated to the matching tuple in E. Thus, the effect of the refresh operation E{character pullout}E is that the tuple e is updated to v. As v.di-elect cons.V, it satisfies the selection condition p and hence, v is included in V. Thus, the insertion of v into V by the refresh equation is correct. In the refresh equation, if a tuple v.di-elect cons.V is updated due to a tuple v.di-elect cons.V=.sigma..sub.p (E), then v.di-elect cons.E would have been updated by v too in the refresh operation of E. As v is updated to v which satisfied the predicate p, the updated tuple v is correctly retained in V by the refresh equation. This shows that the updates to V in the refresh equation are legitimate. The only updates the refresh equation might miss are of the kind where a tuple e.di-elect cons.E matches with a tuple e'.di-elect cons..tau..sub.p (E). In such a case, the tuple e' is updated to e. If e.di-elect cons..sigma..sub.p (E), then the updated tuple e should be included in V. This happens in the refresh equation too, as e doesn't find a match in V and hence is inserted into V. Outerjoin: V=E.sub.1 {character pullout}E.sub.2. The correctness of the refresh equation is proven. Let M(.OR right.E.sub.1) be the set of tuples in E.sub.1 that find a match in E.sub.1 due to .Fourier..sub.1 =.ident..sub.G {character pullout}p. Note that G is a set of attributes in E.sub.1 and p is a predicate over the rest of the attributes in E.sub.1. Consider m.di-elect cons.M and that m finds a match e.sub.1.di-elect cons.E.sub.1 due to .Fourier..sub.1. Each m results in the set of tuples E.sub.2.sup.m =m{character pullout}E.sub.2 in V=E{character pullout}E.sub.2. Each tuple e.sub.2.sup.m =<m, e.sub.2 >.di-elect cons.E.sub.2.sup.m will find a corresponding match in v=<e.sub.1, e.sub.2 >.di-elect cons.V due to the join condition .ident..sub.Attrs(E2).orgate.G {character pullout}p. Note that as Attrs(J).OR right.G. the existence of tuple <m, e.sub.2 > in E.sub.2.sup.m implies the existence of v in V. The tuple <e.sub.1, e.sub.2 > gets updated to <m, e.sub.2 > due to the list U.sub.1 in the refresh equation of V. This update affected by the refresh equation is correct because m changes e.sub.1 to m too, as Attrs(G).orgate.Attrs(U)=Attrs(E.sub.1) and m and e.sub.1 have the same G attributes. Thus, all the updates into E.sub.1 are correctly propagated to V. The refresh equation of V results in more updates in V. Let I.OR right.E.sub.1 be the set of tuples in E.sub.1 that are inserted into E.sub.1 (because they didn't find a .Fourier..sub.1 in E.sub.1). Consider i.di-elect cons.I. Each i results in the set of tuples E.sub.2.sup.i =i{character pullout}E.sub.2 in V. Tuple <i, e.sub.2 >.di-elect cons.E.sub.2.sup.i could only find a match v.di-elect cons.V due to the join condition .ident..sub.Attrs(E.sub..sub.2 .sub.) {character pullout}(E.sub.e.di-elect cons.Attrs(E.sub..sub.1 .sub.) LHS.e=NULL), in which case the tuple v is correctly updated to <i, e.sub.2 >. All the unmatched tuples in V are correctly inserted into V. APPENDIX C: PROPAGATION OF DELETIONS THROUGH OUTERJOIN OPERATORS The changes in V=R{character pullout}S due to deletions from a base relation R cannot be summarized in an outerjoin-change table within our restricted definition of refresh operator. In this section, it is shown that deletions can be propagated from a base table through a outerjoin operator by keeping a count of duplicate tuples in one of the base relations and using an extended version of the refresh operator. Let S.sup.set denote the expression .pi..sub.Attrs(S),Num=Count(*) (S). In response to deletions .gradient.R from R, V, called an OJdeletion-change table, is defined as .gradient.R{character pullout}S.sup.set. The view V is refreshed using the same refresh equation V{character pullout}V, where .theta.=(.ident..sub.Attrs(V), .ident..sub.Attrs(S)) and U=<(A.sub.1, .function.), . . . , (A.sub.n, .function.)>, where .function.(x, y)=NULL for all x, y and {A.sub.1, . . . , A.sub.k }=Attrs(R). The refresh algorithm used to refresh the view Vusing its OJdeletion-change table is shown in Algorithm 2. The propagation equations of Table 3 for propagating aggregate-change tables through an outerjoin operator can be extended by introducing counts, in the manner described above. Algorithm 2: Refresh Algorithm to Apply an OJdeletion-Change Table to its View Input View V(A.sub.1, . . . , A.sub.n, B.sub.1, . . . , B.sub.m) Change Table V(A.sub.1, . . . , A.sub.n, B.sub.1, . . . , B.sub.m, Num) .theta.=(.Fourier..sub.1, .Fourier..sub.2), U=<(A.sub.1, .function..sub.1), (A.sub.2, .function..sub.2), . . . , (A.sub.k, .function..sub.n)> Output Refresh table V, i.e., V{character pullout}V. Procedure BEGIN for each tuple v=(r, s, l) in V Let {v.sub.1, . . . , V.sub.t } be the tuples in V that match v due to the join condition .Fourier..sub.1. if there is a tuple v'.di-elect cons.V such that v'.epsilon slash.{v.sub.1, . . . , v.sub.1 } and v' matches with v due to the join condition .Fourier..sub.2 then Delete tuples v.sub.1, v.sub.2, . . . , v.sub.1 from V; else Update each tuple v.sub.1, v.sub.2, . . . , v.sub.I in V using the specifications in U; endif endfor RETURN V END Note that the refresh operator doesn't need to query the sources and hence, can be executed very efficiently. Change propagation equations required for propagating an OJdeletion-change table through rational and aggregate operations can be appropriately defined. Although specific embodiments of the present invention have been described, it will be understood by those of skill in the art that there are other embodiments that are equivalent to the described embodiments. Accordingly, it is to be understood that the invention is not to be limited by the specific illustrated embodiments, but only by the scope of the appended claims.
|
Same subclass Same class Consider this |
||||||||||