Incremental refresh of materialized views for many-to-many relationships

Abstract

A framework for the incrementally refreshing a materialized view is provided. The materialized view is based on a query that references a projected table and another set of base tables. The query projects the columns of the projected table. To refresh the materialized view, a set of tuples is computed that identify rows to delete, insert, or otherwise modify in the materialized view in order to refresh it. The set of tuples is computed by computing a set of intersections, (1) one for the intersection between the query and the change log of the projected table, and (2) at least one other between the equijoin of the change log for one of the other base tables and the projected table. The query may define an equijoin between the projected table and at least one base table based on equijoin conditions that define a many-to-many relationship or a one-to-many relationship.

Claims

What is claimed is:

1. A method for incrementally refreshing a materialized view, the method comprising the steps of:

computing a first set of tuples that identify a first set of changes to apply to a materialized view to incrementally refresh the materialized view;

wherein the materialized view is defined by a query that references a first base table and one or more other tables that include a second base table;

wherein the materialized view projects one or more columns of the first base table;

wherein the step of computing a first set of tuples includes computing a first union between

an intersection between the query and a first change log that indicates changes to said first base table, and

an intersection between the query and a first equijoin based on the first base table and a second change log that indicates changes to said second base table.

2. The method of claim 1, wherein the step of computing a first union includes computing a first union based on an intersection between the query and a second equijoin based on the first base table, the second base table, and a third change log that indicates changes to a third base table from said one or more other tables.

3. The method of claim 1,

wherein the first set of tuples identifies tuples to insert into said materialized view;

wherein the method further includes computing a second set of tuples that identifies tuples to delete from said materialized view;

wherein the step of computing a second set of tuples includes computing a second union between

a difference between the query and a third change log that indicates deletions to said first base table, and

a difference between the query and a third equijoin based on the first base table, and a fourth change log base table that indicates deletions to said second base table.

4. The method of claim 1, wherein the query specifies equijoin conditions that define a many-to-one relationship between the first base table and the second base table.

5. The method of claim 1, wherein the query specifies equijoin conditions that define a many-to-many relationship between the first base table and the second base table.

6. The method of claim 1, wherein the materialized view projects only columns from said first base table.

7. The method of claim 1, wherein the query returns only tuples with no duplicate tuples.

8. A method of incrementally refreshing a materialized query, the method comprising the steps of:

storing a materialized view, wherein said materialized view is defined by a query that:

references a first base table and a second base table,

defines an equijoin between said first base table and said second base table based on equijoin conditions that define either a one-to-many relationship or a many-to-many relationship between said first base table and said second base table, and

incrementally refreshing said materialized view based on a first change log and a second change log, wherein said first change log indicates changes to said first base table and said second change log indicates changes to said second base table.

9. The method of claim 8, wherein said query projects columns from only said first base table.

10. The method of claim 9, wherein said query returns only tuples with no duplicate tuples.

11. A method of incrementally refreshing a materialized query, the method comprising the steps of:

storing a materialized view, wherein said materialized view is defined by a query that defines a union between:

a first equijoin between a first base table and a second base table, and

a second equijoin between said first base table and another table;

wherein said materialized view projects one or more columns of said first base table; and

incrementally refreshing said materialized view based on a first change log, a second change log, and another change log, wherein said first change log indicates changes to said first base table, said second change log indicates changes to said second base table, and said other change log indicates changes to said other base table.

12. The method of claim 11, wherein said other table is said second base table and said other change log is said second change log.

13. A computer-readable medium carrying one or more sequences of instructions for incrementally refreshing a materialized query, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

computing a first set of tuples that identify a first set of changes to apply to a materialized view to incrementally refresh the materialized view;

wherein the materialized view is defined by a query that references a first base table and one or more other tables that include a second base table;

wherein the materialized view projects one or more columns of the first base table;

wherein the step of computing a first set of tuples includes computing a first union between

an intersection between the query and a first change log that indicates changes to said first base table, and

an intersection between the query and a first equijoin based on the first base table and a second change log that indicates changes to said second base table.

14. The computer-readable medium of claim 13, wherein the step of computing a first union includes computing a first union based on an intersection between the query and a second equijoin based on the first base table, the second base table, and a third change log that indicates changes to a third base table from said one or more other tables.

15. The computer-readable medium of claim 13,

wherein the first set of tuples identifies tuples to insert into said materialized view;

wherein the steps further include computing a second set of tuples that identifies tuples to delete from said materialized view;

wherein the step of computing a second set of tuples includes computing a second union between

a difference between the query and a third change log that indicates deletions to said first base table, and

a difference between the query and a third equijoin based on the first base table, and a fourth change log base table that indicates deletions to said second base table.

16. The computer-readable medium of claim 13, wherein the query specifies equijoin conditions that define a many-to-one relationship between the first base table and the second base table.

17. The computer-readable medium of claim 13, wherein the query specifies equijoin conditions that define a many-to-many relationship between the first base table and the second base table.

18. The computer-readable medium of claim 13, wherein the materialized view projects only columns from said first base table.

19. The computer-readable medium of claim 13, wherein the query returns only tuples with no duplicate tuples.

20. A computer-readable medium carrying one or more sequences of instructions for incrementally refreshing a materialized query, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

storing a materialized view, wherein said materialized view is defined by a query that:

references a first base table and a second base table,

defines an equijoin between said first base table and said second base table based on equijoin conditions that define either a one-to-many relationship or a many-to-many relationship between said first base table and said second base table, and

incrementally refreshing said materialized view based on a first change log and a second change log, wherein said first change log indicates changes to said first base table and said second change log indicates changes to said second base table.

21. The computer-readable medium of claim 20, wherein said query projects columns from only said first base table.

22. The computer-readable medium of claim 21, wherein said query returns only tuples with no duplicate tuples.

23. A computer-readable medium carrying one or more sequences of instructions for incrementally refreshing a materialized query, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

storing a materialized view, wherein said materialized view is defined by a query that defines a union between:

a first equijoin between a first base table and a second base table, and

a second equijoin between said first base table and another table;

wherein said materialized view projects one or more columns of said first base table; and

incrementally refreshing said materialized view based on a first change log, a second change log, and another change log, wherein said first change log indicates changes to said first base table, said second change log indicates changes to said second base table, and said other change log indicates changes to said other base table.

24. The computer-readable media of claim 23, wherein said other table is said second base table and said other change log is said second change log.

Description

FIELD OF THE INVENTION

The present invention relates to DBMSs, and in particular, to maintaining materialized views.

BACKGROUND OF THE INVENTION

In a database management system (DBMS), data is stored in one or more data containers, each container contains records, and the data within each record is organized into one or more fields. In relational DBMSs, the data containers are referred to as tables, the records are referred to as rows, and the fields are referred to as columns. In object oriented databases, the data containers are referred to as object classes, the records are referred to as objects, and the fields are referred to as attributes. Other database architectures may use other terminology.

The present invention is not limited to any particular type of data container or database architecture. However, for the purpose of explanation, the examples and the terminology used herein shall be that typically associated with relational databases. Thus, the terms "table", "row" and "column" shall be used herein to refer respectively to the data container, record, and field.

In a DBMS used for "data warehousing" or "decision support", it is common for identical or closely related queries to be issued frequently. For example, a business may periodically generate reports that summarize the business facts stored in the database, such as: "What have been the best selling brands of soft drinks in each of our sales regions, during the past six months?".

To respond to such queries, the database server typically has to perform numerous join operations because the database records contain the information that is required to respond to the queries. When a DBMS contains very large amounts of data, certain queries against the database can take an unacceptably long time to execute. The cost of executing a query may be particularly significant when the query (which takes the form of a "SELECT" statement in the SQL database language) requires join operations among a large number of database tables.

MATERIALIZED VIEWS

Among commercial users of DBMSs, it has become a common practice to store the results of often-repeated queries in database tables or some other persistent database object. By storing the results of queries, the costly join operations required to generate the results do not have to be performed every time the queries are issued. Rather, the database server responds to the queries by simply retrieving the pre-computed data.

These stored results are commonly referred to as materialized views. The contents of a materialized view is defined by metadata referred to as a view definition. The view definition contains mappings to one or more columns in the one or more tables containing the data. Columns and tables that are mapped to a materialized view are referred to herein as base columns and base tables of the materialized view, respectively. The column and the base column mapped to the column are referred to as being the same field. The data maintained in the base columns is referred to herein as base data. The data contained in a materialized view is referred to herein as materialized data.

Typically, the view definition is in the form of a database query, herein referred to as a materialized view query. The materialized view query is computed and the results are stored as the materialized view. The results can be in the form of rows, which may be rows from a single base table or a rows created by joining rows in the base table. When a "base" row (or a subset of its columns) from a base table is included in the computed results of a materialized view query that are stored, the row is referred to as being included in the materialized view. The base table whose rows are included in the materialized view are referred to as the "projected" table. Likewise, when a "base" row (or a subset of its columns) from a base table is included in the computed results of a query, the row is said to be returned by the query. Furthermore, the columns that are included in the materialized view or the computed results in the query are referred to as being projected by the materialized view or query.

Materialized views eliminate the overhead associated with gathering and deriving the data every time a query is executed. Through a process known as query rewrite, a query can be optimized to recognize and use existing materialized views that could answer the query. Typically, the query rewrite optimization is transparent to the application submitting the query. That is, the rewrite operation happens automatically and does not require the application to know about the existence of materialized views, nor that a particular materialized view has been substituted for the original query.

REFRESHING MATERIALIZED VIEWS

As new data is periodically added to the base tables of a materialized view, the materialized view needs to be updated to reflect the new base data. When a materialized view accurately reflects all of the data currently in its base tables, the materialized view is considered to be "fresh". Otherwise, the materialized view is considered to be "stale". A stale materialized view may be recomputed by various techniques that are collectively referred to as a "refresh". A refresh may performed for a materialized view while modifications are concurrently being made to its base tables.

One approach to refreshing materialized views is referred to as the "total refresh" or "full refresh" approach. According to the total refresh approach, the values in materialized views are recalculated based on all of the base data every time new base data is supplied. Systems that employ the full refresh approach have the disadvantage that the re-creation process is a relatively lengthy operation due to the size and number of tables from which the materialized data is derived. For example, when ten new rows are added to a particular base table that contains a million rows, a total refresh operation would have to process all one million and ten rows of the base table to regenerate the materialized views derived using the base table.

The process of updating materialized data may be improved by performing incremental refresh, where rather than generating a new set of materialized data based on calculations that use all of the base data, the materialized data is updated based on modifications to the base data.

One type of conventional approach for incremental refresh, the concurrent refresh approach, refreshes the materialized view whenever the base tables of the materialized views are modified. A disadvantage for this approach is that it adds overhead to operations that modify the base tables. Furthermore, the overhead is incurred during periods of greatest activity for the base tables.

There are several reasons the concurrent refresh approach requires that the materialized view be refreshed whenever the base tables are changed. First, the concurrent refresh approach uses an algorithm that requires that the old values of the base table be available. Generally, these values are available if the materialized view is refreshed whenever the base table is modified. Second, the algorithm used may also require that the materialized view be refreshed based on the chronological order of changes. Refreshing the materialized view as changes are made to the base tables ensures that the materialized view is refreshed according to the chronological order of changes.

Other conventional incremental refresh approaches that can defer refresh of a materialized view may also depend on the availability of the old values of the base table and knowledge of the chronological order in which changes are made to a base table. Retaining this information can be very costly for a DBMS, or such information may simply not be available when the refresh is performed.

Furthermore, many types of materialized views cannot be incrementally refreshed by the conventional incremental refresh approaches. For example, there is no mechanism that incrementally refreshes a materialized view that defines a join operation that is based on a many-to-many relationship between the tables being joined, or that is based on a union of queries. To illustrate a materialized view that cannot be incrementally refreshed using conventional incremental refresh approaches, the following table definitions and materialized view superstore are provided.

create table bookstore (

storenum number primary key,

name varchar2(1000),

location varchar2(1000));

create table school (

schoolnum number primary key,

population number);

create table supplies (

storenum number,

schoolnum number,

primary key (storenum, schoolnum));

create table sale (

saleid number primary key,

storenum number,

amount number,

itemid number,

saledate date);

The base tables are used by an application to model the sales between bookstores and schools. The application maintains the table supplies so that two of its columns hold primary key values for tables school and bookstore. Supplies.storenum contains primary key values from bookstore.storenum; supplies.schoolnum contains primary key values from school.schoolnum.

The columns of tables and the values in the column may be used to establish a relationship between tables and between the rows in the tables. A row in one table and a row in another table are related if one or more of their columns satisfy a "relational" condition, typically based on equality. For example, a row in bookstore is related to a row in supplies if, for these rows, the columns bookstore.storenum and supplies.storenum are both equal to one.

A table has a one-to-one relationship with another table when one row in the table can only be related to one row in the other table. A table has a one-to-many relationship with another table when a row in the table can be related to multiple rows in the other table. A table has a many-to-many relationship with another table when multiple rows in the table may be related to multiple rows in the other table.

A third table may be used to establish a many-to-many relationship between tables. The relational conditions defining the relationship are based on columns in the three tables. Column values in a row of the third table establish relationships between rows of one table and rows of another table. To illustrate a many-to-many relationship, FIG. 1 is provided. FIG. 1 shows table-of-values 101, which depict illustrative values for tables bookstore, supplies, and school. Values for all columns are not shown.

Row 121 is related to multiple rows in school, i.e. row 141 and 142, for the following reason. Row 121 of bookstore is related to row 131 and 132 in supplies because for rows 131 and 132, the value in supplies.storenum is equal to `1`, which is the value of bookstore.storenum of row 121. Row 131 is related to row 141 of school.schoolnum because for row 131 the value in supplies.schoolnum is equal to `1`, which is equal to the value in school.schoolnum of row 141. Row 132 is related to row 142 of school.schoolnum because for row 132 the value in supplies.schoolnum is equal to `2`, which is equal to the value in school.schoolnum of row 142. Because rows 131 and 132 are related to row 121 in bookstore and rows 141 and 142, rows 131 and 132 establish a relationship between a row in bookstore and multiple rows in school.

Likewise, row 141 in school is related to rows 131 and 133 in supplies. Row 131 is related to row 121 in bookstore and row 133 is related to row 122 in bookstore. Because rows 131 and 133 are related to row 141 in school and to rows 121 and 122 in bookstore, rows 131 and 133 establish a relationship between a row in school and multiple rows in bookstore. Thus a many-to-many relationship exists between bookstore and school because multiple rows in bookstore may be related to multiple rows in school and vice versa. Thus supplies establishes a many-to-many relationship between bookstore and school.

ILLUSTRATIVE MATERIALIZED VIEW DEFINITION

Materialized view superstore is defined by database command QCM as follows.

    create materialized view superstore refresh fast as
        select * from bookstore where exists
          (select 1 from supplies where supplies.storenum =
          bookstore.storenum and exists
          (select 1 from school where school.population > 1000 and
          school.schoolnum = supplies.schoolnum))
        union
        select * from bookstore where exists
          (select 1 from sale where sale.storenum = bookstore.storenum and
          sale.amount > 10000)

    TABLE A
    i = 1       l.sub.1 = 3 (i.e. bookstore, supplies, school)
    (i.e. QCM1) R.sub.11 corresponds to bookstore
                R.sub.12 corresponds to .sigma.(school).sub.{school.population
     > 1000}
                R.sub.13 corresponds to supplies
                C.sub.0 corresponds to storenum, name, & location in bookstore
    i = 2       l.sub.2 = 2
    (i.e. QCM2) R.sub.21 corresponds to bookstore
                R.sub.22 corresponds .sigma.(sales).sub.{sales.amount >
     10000}
                C.sub.0 corresponds to storenum, name, & location in bookstore

    I.  .DELTA..sup.+.OR left. Q - Q' .DELTA..sup.+ is a superset of tuples
     that includes at least the
                        difference between Q and Q'. Q' is the value of
                        Q.sub.mv at time t. Thus, .DELTA..sup.+ contains a
     superset of the
                        tuples added to the materialized view since time t.
    II. .DELTA..sup.+.OR right. Q .DELTA..sup.+ is a subset of the tuples in Q.
     Thus, every
                        tuple in .DELTA..sup.+ is in Q, the current value of
     the
                        materialized view.
    III. .DELTA..sup.-.OR left. Q' - Q .DELTA..sup.- is a superset of the
     difference between Q' - Q.
                        Thus .DELTA..sup.- is a superset of the tuples deleted
     from
                        the materialized view since time t.
    IV. .DELTA..sup.- .andgate. Q = NILL There is no tuple in .DELTA..sup.-
     that is in the current value
                        of the materialized view at time t.

    1.  R.sub.ij      The current value of a relation. R'ij is the value at a
                      previous time t.
    2.  .DELTA..sup.+.sub.ij, where: .DELTA..sup.+.sub.ij is a superset of the
     tuples that have been
        .DELTA..sup.+.sub.ij .OR left. Rij - R'ij inserted into R.sub.ij after
     time t. .DELTA..sup.+.sub.ij may be computed
                      from change logs. .DELTA..sup.+.sub.ij may include more
     inserted
                      rows than were actually inserted since time t. Note
                      the definition of .DELTA..sup.+.sub.ij does not require
     the
                      chronological order of the inserts.
    3.  .DELTA..sup.-.sub.ij, where: .DELTA..sup.-.sub.ij is a superset of the
     tuples deleted from R'ij from
        .DELTA..sup.-.sub.ij .OR left. R'ij - Rij time t. .DELTA..sup.-.sub.ij
     may be may be computed from the
                      materialized view logs. .DELTA..sup.-.sub.ij may include
     more
                      deleted rows than were actually deleted since time t.
                      Note the definition of .DELTA..sup.-.sub.ij does not
     require the
                      chronological order of the deletes.

    select * from bookstore where exists
        (select 1 from supplies where supplies.storenum =
          bookstore.storenum)

• Inventors
  Arora, Nimar;
• Assignee
  Oracle International Corporation (Redwood Shores, CA)
• Published
  Mar-16-2004
• Current US Classes:
  707/102
  707/3
• Application #
  969938
• International Classes
  G06F 017/30
• Field of Search
  707/2 707/3 707/10 707/102 707/103
• Examiner
  Mizrahi; Diane D.
• Agent
  Bingham; Marcel K. Hickman Palermo Truong & Becker LLP
• US Patent References:
  6272502
  6339769
  6513034
  6532470
  6546402
  6591266