United States Patent
`Witkowski et al.
`
`19
`
`54) INCREMENTAL MAINTENANCE OF
`MATERALIZED VIEWS CONTAINING
`ONE-TO-N LOSSLESS JOINS
`
`75 Inventors: Andrew Witkowski, Foster City; Karl
`Dias, San Mateo, both of Calif.
`73 Assignee: Oracle Corporation, Redwood Shores,
`Calif.
`
`21 Appl. No.: 09/109,115
`22 Filed:
`Jul. 2, 1998
`(51) Int. Cl." ...................................................... G06F 17/30
`52 U.S. Cl. .......................... 707/2; 707/2; 707/4; 707/6;
`707/102; 707/103
`58 Field of Search ..................................... 707/2–4, 6–7,
`707/10, 102, 103; 705/26–27, 34; 706/16;
`709/204; 717/2
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,584,024 12/1996 Shwartz ...................................... 707/4
`5,812,840 9/1998 Shwartz ...
`... 707/4
`5,970,482 10/1999 Pham et al.
`... 706/16
`5,974,407 10/1999 Sacks ............
`... 707/2
`5,991,754 11/1999 Raitto et al. ................................ 707/2
`OTHER PUBLICATIONS
`Bhargava, Gautam et al., “Hypergraph based recordings of
`outer join queries with complex predicates', Proceedings of
`the 1995 ACM SIGMOND International Conference on
`Management of Data and Symposium on Principles of
`Database Systems, May 22-25, 1995, AC.
`Bhagrava, Gautam et al., “Efficient proceedings of outer
`joins and aggregate junctions, Proceedings of the Twelfth
`International Conference on Data Engineering, 1996., Feb.
`26-Mar. 1, 1996, pp. 441–449.
`Biggs, Maggie, “Oracle8 still in pole position”, InfoWorld,
`Framingham; Dec. 15, 1997, vol. 19, Issue 50, p. 1, 97,
`ISSN: 01996649, Dec. 1997.
`
`USOO6125360A
`Patent Number:
`11
`(45) Date of Patent:
`
`6,125,360
`Sep. 26, 2000
`
`Chen, Arbee, “Outerjoin Optimization in Multidatabase Sys
`tems”, Proceedings of the Second International Symposium
`on Database in Parallel and Distributed Systems, 1990, Jul.
`2–4, 1990, pp. 211-218.
`Lee, Byung Suk et al., “Outer joins and filters for instanti
`ating objects from relational databases through Views”,
`IEEE Transactions on Knowledge and Data Engineering,
`Feb. 1994, vol. 6, Issue 1, pp 108-119.
`(List continued on next page.)
`Primary Examiner-Hosain T. Alam
`ASSistant Examiner Shahid Alam
`Attorney, Agent, or Firm-Hickman Palermo; Truong &
`Becker, LLP, Brian D. Hickman
`57
`ABSTRACT
`A method and apparatus are provided for performing incre
`mental refreshes to materialized views defined by one-to-N
`lossleSS joins. Each base table of the materialized view is
`selected to be processed as the current “selected table”. The
`processing of the current Selected table varies depending on
`whether the selected table is the right side table of an outer
`join. If the selected table is not the right table of an outer
`join, then the Selected table is processed by (1) deleting rows
`from the materialized view based on rows of the selected
`table that have been updated or deleted in the selected table
`during the batch window, and (2) inserting rows into the
`materialized view based on updates and inserts into the
`selected table that occurred during the batch window. If the
`Selected table is the right table of an outer join, then changes
`made to the Selected table are processed in a way that
`reduces the number of changes that have to be made to the
`materialized view. According to one embodiment of the
`invention, operations performed during the incremental
`refresh are performed by issuing database Statements (e.g.
`SQL queries) to a database server. The incremental refresh
`techniques described herein are “memoryless” in that they
`do not require a record of the Sequence of changes that were
`made during a batch window. Techniques are described for
`performing the incremental refresh Steps through the use of
`database commands and queries.
`32 Claims, 7 Drawing Sheets
`
`—
`500
`SELECT THELEFMOSTUNPROCESSEDTABLET)
`
`501
`DNTYROA'S HATHAWEBEEN CHANGED INTDT)
`
`52
`IDENTIFY CHANGEDROWS THATSTILLEXISTNTi(WT)
`
`
`
`504
`SSELECTEDTABLETHERIGHT
`SIE OF ANOUTER JOIN
`
`506
`PROCESS THERGHT
`SIDE OF ANOUTER
`JON
`
`
`
`so
`DELEEROWSFRQMMW
`BASED ONUPDATED AND
`DELETEDROWS OF Ti
`
`52
`NSERTROWSINTOMW
`BASED ONUPDATES AND
`NSERTSMADE TOT
`
`
`
`
`
`
`
`54
`ANY UNPROCESSED
`TABLES
`
`Booking, Exh. 1013, Page 1
`
`

`

`6,125,360
`Page 2
`
`OTHER PUBLICATIONS
`Lo, Ming-Ling et al., “Spatial Hash-Joins”, Proceedings of
`the 1996 ACM SIGMOND International Conference on
`Management of Data, Jun. 1996, pp 247–258.
`Marek, Robert et al., “TID Hash Joins, Proceedings of the
`third international conference in Information and knowledge
`management, 1994, Nov. 2-, Dec. 2, 1994, pp. 42-49.
`Mishra, Priti et al., “Join Processing in Relational Data
`bases”, ACM Computing Surveys, vol. 24, No. 1, Mar. 1992,
`pp 63-113.
`Pang, HweeHwa et al., “Partially Preemptible Hash Joins”,
`Proceedings of the 1993 ACM SIGMOND international
`conference on Management of data, May 1993, pp 59-68.
`
`ROSS, Kenneth et al., “Materialized view maintenance and
`integrity constraint checking: trading Space for time', Pro
`ceedings of the 1996 ACM SIGMOND international con
`ference on Management of data, Jun. 3-6, 1996, pp
`447-458.
`O'Neil et al., “Multi-Table Joins Through Bitmapped Join
`Indices”, SIGMOND Record, vol. 24, No. 3, Sep. 1995, pp
`8-11.
`Yan, Weipeng et al., “Performing Group-By before Join',
`Proceedings of the 10th International Conference on Data
`Engineering, 1994, Feb. 14-18, 1994, pp 89-100.
`
`Booking, Exh. 1013, Page 2
`
`

`

`U.S. Patent
`
`Sep. 26, 2000
`
`Sheet 1 of 7
`
`6,125,360
`
`22. 7
`
`
`
`TABLE 110 (R)
`
`TABLE 112 (S)
`
`Booking, Exh. 1013, Page 3
`
`

`

`U.S. Patent
`
`Sep. 26, 2000
`
`Sheet 2 of 7
`
`6,125,360
`
`8
`Z
`
`X{}JONALEN
`TWOOT
`
`
`
`
`
`
`
`
`
`
`
`555
`
`
`
`(JOSSE OO}}d
`
`TOHINOO
`HOS}}{\O
`
`Booking, Exh. 1013, Page 4
`
`

`

`U.S. Patent
`
`Sep. 26, 2000
`
`Sheet 3 of 7
`
`6,125,360
`
`TABLEX
`X.rOW id X.a
`
`X.b
`
`922, 7-6
`asy
`BASE TABLES AT TIMET1
`Y.OW id Ya Yb
`
`
`
`
`
`22, 798
`
`X rid
`
`X.a
`
`MATERALIZED VIEWAT TIME T1
`(MV 400)
`X.b Y rid
`
`Y.a
`
`Y.b
`
`
`
`
`
`a nununu
`Rex
`.
`a
`rx .
`Rouvilu.
`Rex 2 ava 2
`a
`
`Booking, Exh. 1013, Page 5
`
`

`

`U.S. Patent
`
`Sep. 26, 2000
`
`Sheet 4 of 7
`
`CHANGESTOY
`
`OPERATION
`RowID
`
`RowID
`
`6,125,360
`
`Hig.46
`
`
`
`CHANGESMADEDURINGBATCHPERIOD
`
`
`
`
`
`X.a
`
`CHANGESTOX OPERATION
`
`Booking, Exh. 1013, Page 6
`
`Booking, Exh. 1013, Page 6
`
`

`

`U.S. Patent
`
`Sep. 26, 2000
`
`Sheet S of 7
`
`6,125,360
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`500
`SELECT THE LEFT MOSTUNPROCESSEDTABLE(T)
`
`501
`IDENTIFYROWS THAT HAVE BEEN CHANGED INTi(DIt T)
`
`502
`IDENTIFY CHANGEDROWS THAT STILLEXIST IN Ti(VT)
`
`504
`ISSELECTED TABLE THE RIGHT
`SIDE OF ANOUTER JOIN
`?
`
`506
`PSSESASE"
`JOIN
`
`
`
`510
`DELETE ROWS FROMMV
`BASED ON UPDATED AND
`DELETED ROWS OF Ti
`
`512
`INSERT ROWS INTO MV
`BASED ON UPDATES AND
`INSERTS MADE TO Ti
`
`
`
`514
`ANY UNPROCESSED
`TABLES
`
`
`
`
`
`
`
`NO
`
`DONE
`
`Booking, Exh. 1013, Page 7
`
`

`

`U.S. Patent
`
`Sep. 26, 2000
`
`Sheet 6 of 7
`
`6,125,360
`
`27. 6.6
`
`BASE TABLES AT TIME T2
`
`TABLE X
`X.OWid
`X.a
`
`X.b
`
`TABLE Y
`Y.OWid
`Y.a
`
`Y.b
`
`MV 400 AFTER INCREMENTALUPDATE
`
`rowid X rid
`
`
`
`X.a X.b Y rid
`
`Y.a
`
`Y.b
`
`Booking, Exh. 1013, Page 8
`
`

`

`U.S. Patent
`
`Sep. 26, 2000
`
`Sheet 7 of 7
`
`6,125,360
`
`506
`PROCESSRIGHT SIDE
`OF OUTER JOIN
`
`922. 7
`
`
`
`700
`INITIALIZE TEMPORARY TABLES
`(TMP MV, TMP MVCNT RIDS, TMP CNT)
`
`702
`SET TO NULL SELECTED COLUMNS OF MV ROWS THAT
`JOIN WITH EXACTLY ONE CHANGEDROW OFT
`
`704
`DELETE ROWS FROM MV THAT JOIN
`WITH MORE THAN ONE ROW OF Ti
`
`
`
`706
`INSERTAROW WITHNULL COLUMNS FOR OJGraph(T)FOR THE ROWS
`NMV THAT JOIN WITH MORE THAN 1 ROW OF Ti AND ALL OF WHICH
`HAVE BEEN DELETED FROMMV
`
`708
`NITIALIZE NEW TEMPRORARY TABLES
`(NEWMV, TMP MV RIDS, TMP NEWCNT)
`
`710
`UPDATE THOSE ROWS IN MV THAT JOIN
`TOEXACTLY ONE ROW INT
`
`712
`DELETE MVROWSFOR WHICHATROW WILL
`JOIN WITH MORE THAN ONE TROW
`
`714.
`INSERT INTOMV THE NEW ROWSFROMNEW MV WHICH
`HAVE NOTALREADY BEENUPDATED INSTEP 710
`
`Booking, Exh. 1013, Page 9
`
`

`

`1
`INCREMENTAL MANTENANCE OF
`MATERALIZED VIEWS CONTAINING ONE
`TO-N LOSSLESS JOINS
`
`RELATED APPLICATIONS
`This application is related to U.S. patent application Ser.
`No. 09/109,782, entitled “INCREMENTAL MAINTE
`NANCE OF MATERIALIZED VIEWS CONTAINING
`ONE-TO-ONE LOSSLESS JOINS” filed by Andrew Wit
`kowski and Karl Dias on Same day here with, the contents of
`which are incorporated herein by reference.
`
`FIELD OF THE INVENTION
`The present invention relates to database Systems, and
`more Specifically, to the maintenance of materialized views
`that contain one-to-n lossleSS joins.
`
`15
`
`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 database Systems, 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 architec
`tures 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.
`Referring to FIG. 1, it illustrates two exemplary tables:
`table R (110) and table S (112). Table R has two columns,
`labeled “r.a' and “r.b', and table S has two columns labeled
`“S.a' and “S.c'. To extract data from a table, users can issue
`queries that Select columns from the table and, optionally,
`Specify a criteria that determines which rows are to be
`retrieved. For example the SQL query "SELECTS.a from S
`WHERE S.b=2' requests the values from columns...a of table
`S for the rows in which the value in columns.b equals 2. In
`table S of FIG. 1, the only row that has the value 2 in the S.b
`column is row 124. Consequently, the query would cause the
`DBMS to return the value from the s.a column of row 124,
`which is 4.
`For various reasons, it is not desirable for certain users to
`have access to all of the columns of a table. For example, one
`column of an employee table may hold the Salaries for the
`employees. Under these circumstances, it may be desirable
`to limit access to the Salary column to management, and
`allow all employees to have access to the other columns. To
`address this situation, the employees may be restricted from
`directly accessing the table. Instead, they may be allowed to
`indirectly access the appropriate columns in the table
`through a “view”.
`A view is a logical table. AS logical tables, ViewS may be
`queried by users as if they were a table. However, views
`actually present data that is extracted or derived from
`existing tables. Thus, problem described above may be
`Solved by (1) creating a view that extracts data from all
`columns of the employee table except the Salary column, and
`(2) allowing all employees to access the view.
`A view is defined by metadata referred to as a view
`definition. The View definition contains mappings to one or
`
`25
`
`35
`
`40
`
`50
`
`55
`
`60
`
`65
`
`6,125,360
`
`2
`more columns in the one or more tables containing the data.
`Typically, the view definition is in the form of a database
`query. Columns and tables that are mapped to a view are
`referred to herein as base columns and base tables of the
`View, respectively.
`The data presented by conventional views is gathered and
`derived on-the-fly from the base tables in response to queries
`that access the views. That data gathered for the View is not
`persistently Stored after the query accessing the view has
`been processed. Because the data provided by conventional
`views is gathered from the base tables at the time the views
`are accessed, the data from the views will reflect the current
`state of the base tables. However, the overhead associated
`with gathering the data from the base tables for a view every
`time the View is accessed may be prohibitive.
`A materialized view, on the other hand, is a view for
`which a copy of the View data is Stored Separate form the
`base tables from which the data was originally gathered and
`derived. The data contained in a materialized view is
`referred to herein as (“materialized data”). Materialized
`ViewS eliminate the overhead associated with gathering and
`deriving the View data every time a query accesses the view.
`However, to provide the proper data, materialized views
`must be maintained to reflect the current State of the base
`tables. When the base tables of a materialized view are
`modified, computer resources must be expended to both
`determine whether the modifications require corresponding
`changes to the materialized data, and to make the required
`corresponding changes. Despite the high cost associated
`with maintaining materialized views, using a materialized
`View can lead to a significant overall cost Savings relative to
`a conventional view when the materialized view represents
`a Set of data that is infrequently changed but frequently
`accessed.
`Views are often based on joins of two or more row
`Sources. A join is a query that combines rows from two or
`more tables or ViewS. Ajoin is performed whenever multiple
`tables appear in a query's FROM clause. The query's select
`list can Select any columns from any of the base tables listed
`in the FROM clause.
`Most join queries contain WHERE clause conditions that
`compare two columns, each from a different table. Such a
`condition is called a join condition. To execute a join, the
`DBMS combines pairs of rows for which the join condition
`evaluates to TRUE, where each pair contains one row from
`each table.
`To execute a join of three or more tables, the DBMS first
`joins two of the tables based on the join conditions com
`paring their columns and then joins the result to another
`table based on join conditions containing columns of the
`joined tables and the new table. The DBMS continues this
`process until all tables are joined into the result.
`In addition to join conditions, the WHERE clause of a join
`query can also contain other conditions that refer to columns
`of only one table. These conditions can further restrict the
`rows returned by the join query.
`An equijoin is a join with a join condition containing an
`equality operator. An equijoin combines rows that have
`equivalent values for the Specified columns. Query 1 is an
`equijoin that combines the rows of tables R and S where the
`value in column ra is the same as the value in column S.a.
`
`QUERY1
`
`SELECT *
`FROM R, S
`WHERE ra=s.a;
`FIG. 2a is a block diagram of a materialized view (MV
`202) whose view definition is Query 1. MV 202 has two rows
`
`Booking, Exh. 1013, Page 10
`
`

`

`3
`204 and 206. Row 204 results from combining row 114 of
`table R with row 120 of table S. Row 206 results from
`combining row 116 of table R with row 122 of table S. Row
`118 of table R does not combine with any row in table S
`because no row in table S has the value 3 in column S.a.
`The join illustrated by Query 1 is a “simple” or “inner”
`join. With an inner join, rows that do not satisfy the join
`condition are not reflected in the join result. For example,
`row 118 did not satisfy the join condition relative to any
`rows in table S, so row 118 is not reflected in the resulting
`materialized view 202. In contrast, an outer join returns all
`rows that Satisfy the join condition and those rows from one
`table for which no rows from the other satisfy the join
`condition.
`FIG.2b is a block diagram illustrating a materialized view
`250 that results from an outer join between tables R and S.
`Materialized views that are formed by joins, Such as mate
`rialized views 202 and 250, are referred to herein as mate
`rialized join ViewS. Query2 illustrates the outer join query
`that defines materialized view 250.
`QUERY2
`
`5
`
`15
`
`66
`
`SELECT *
`FROM R, S
`WHERE ra(+)=s.a;
`Query2 differs from Query 1 in that the inner join operator
`=” has been replaced with the outer join operator “(+)=”.
`The table listed on the (+) side of the outer join operator is
`referred to as the outer join table. In query2, table R is the
`outer join table. All of the rows in the outer join table are
`reflected in the results of an outer join, whether or not they
`Satisfy the join criteria with any rows in the other join tables.
`As illustrated in FIG. 2b, the materialized view 250 that
`results from the outer join includes rows 252 and 254 that
`are identical to rows 204 and 206 of materialized view 202,
`respectively. However, materialized view 250 further
`includes row 256 which was produced when row 118 of
`table R failed to satisfy the join conditions any row in table
`S.
`AS with all types of materialized views, the materialized
`join ViewS must be maintained So that the data contained
`therein reflects the current State of the base tables. Changes
`made to any of the base tables may necessitate changes in
`the materialized join View. Changes made to the base tables
`may include, for example, the insertion of new rows, the
`deletion of existing rows, and the update of existing rows.
`In general, there are two approaches to causing a mate
`rialized view to reflect changes made to its base tables. One
`approach, referred to as a total refresh, involves discarding
`the current materialized view data and recomputing the
`entire materialized view based on the current State of the
`base tables. The clear disadvantage of performing a total
`refresh is that the performance penalty associated with
`recomputing the join View every time a base table is updated
`may outweigh the performance benefit achieved for not
`having to recompute the view every time it is accessed.
`The Second approach for maintaining a materialized view
`is referred to herein as incremental maintenance. With
`incremental maintenance, the materialized view is not
`recomputed every time a base table is changed. Instead, the
`DBMS determines what changes, if any, have to be made to
`the materialized view data in order for the materialized view
`data to reflect the changes to the base tables. Incremental
`maintenance Significantly reduces the Overhead associated
`with maintaining a materialized view when, for example,
`changes to the base table only require the insertion or
`deletion of a Single row within the materialized view.
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,125,360
`
`4
`Incremental maintenance can be either immediate or
`deferred. Immediate incremental maintenance requires the
`materialized join View to be updated to reflect a change to a
`base table immediately in response to the change is made to
`the base table. Deferred incremental maintenance allows
`changes to the base tables to be made over a period of time
`(a “batch window”) without updating the materialized view.
`After the end of the batch window, the materialized view is
`updated to reflect all of the changes that were made during
`the batch window.
`Deferred incremental maintenance of a materialized join
`View is difficult for a variety of reasons. First, changes may
`have occurred to more than one of the base tables of the
`materialized join View during the batch window. Second, the
`changes may take many forms, including insertions, dele
`tions and updates. Third, the changes may have been made
`in a particular Sequence that is critical to the effect of the
`changes. For example, a value in a base table may have been
`updated twice during the batch window. The Sequence of the
`updates dictates that the value of the Second update must be
`reflected in the materialized join view, not the value of the
`first update.
`Based on the foregoing, it is clearly desirable to provide
`a method and System for performing incremental mainte
`nance on a materialized join View. Specifically, it is desirable
`to provide a method and System for determining how a
`materialized join View should be updated in response to
`updates made to the base tables of the materialized join
`view. It is further desirable to provide a method for per
`forming deferred incremental maintenance of materialized
`join views in a way that does not require a persistent tracking
`of the Sequence of updates to the base tables. It is further
`desirable to provide a method for performing incremental
`maintenance of materialized join Views that are defined by
`queries that contain outer joins.
`SUMMARY OF THE INVENTION
`A method and apparatus are provided for performing
`incremental refreshes to materialized views defined by one
`to-N lossless joins. Each base table of the materialized view
`is Selected to be processed as the current “Selected table'.
`The processing of the current Selected table varies
`depending on whether the Selected table is the right Side
`table of an outer join. If the selected table is not the right
`table of an outer join, then the Selected table is processed by:
`(1) deleting rows from the materialized view based on
`rows of the selected table that have been updated or
`deleted in the selected table during a batch window;
`and
`(2) inserting rows into the materialized view based on
`updates and inserts into the Selected table that occurred
`during a batch window.
`If the selected table is the right table of an outer join, then
`deletions to the Selected table are processed by processing
`each row (T) that combines with a changed row in the
`Selected table according to the rules:
`(1) if T only combines in the materialized view with
`changed rows of the Selected table, then the rows in the
`materialized view that contain Tare removed from the
`materialized view and replaced with a row in which
`Selected columns are set to NULL; and
`(2) if T combines in the materialized view with both
`changed and unchanged rows of the Selected table, then
`the rows in the materialized view that result from T.
`combining with changed rows are deleted, leaving only
`the rows in which T combines with unchanged rows of
`the selected table.
`
`Booking, Exh. 1013, Page 11
`
`

`

`S
`If the selected table is the right table of an outer join, then
`insertions to the Selected table are performed by
`(1) removing from the materialized view any rows that
`exist in the materialized view for rows from the left side
`of the outer join that, prior to the batch window, did not
`combine with any rows of the selected table but which,
`after the batch window, combine with at least one
`changed row of the Selected table; and
`(2) inserting into the materialized view rows formed by
`combinations that result from the changed rows in the
`Selected table.
`According to one embodiment of the invention, opera
`tions performed during the incremental refresh are per
`formed by issuing database statements (e.g. SQL queries) to
`a database Server.
`The incremental refresh techniques described herein are
`“memoryless” in that they do not require a record of the
`Sequence of changes that were made during a batch window.
`Techniques are described for performing the incremental
`refresh Steps through the use of database commands and
`queries.
`BRIEF DESCRIPTION OF THE DRAWINGS
`The present invention is illustrated by way of example,
`and not by way of limitation, in the figures of the accom
`panying drawings and in which like reference numerals refer
`to Similar elements and in which:
`FIG. 1 is a block diagram of two tables;
`FIG. 2a is a block diagram of the result of an inner join
`on the tables illustrated in FIG. 1;
`FIG.2b is a block diagram of the result of an outer join
`on the tables illustrated in FIG. 1;
`FIG. 3 is a block diagram of a computer System on which
`an embodiment of the invention may be implemented;
`FIG. 4a is a block diagram of two base tables at time T1;
`FIG. 4b is a block diagram of a materialized view defined
`by an outer join on the base tables in FIG. 4a at time T1;
`FIG. 4c illustrates changes made to the tables in FIG. 4a
`during a batch period;
`FIG. 5 is a flowchart that illustrates the steps involved in
`an incremental refresh operation according to one embodi
`ment of the invention;
`FIG. 6a is a block diagram of the tables from FIG. 4a at
`time T2, after the changes shown in FIG. 4c have been made;
`FIG. 6b is a block diagram of the materialized view of
`FIG. 4b after it has been incrementally refreshed according
`to an embodiment of the invention; and
`FIG. 7 is a flowchart that illustrates the steps for process
`ing the right Side of an Outer join during an incremental
`refresh according to an embodiment of the invention.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`A method and apparatus for performing deferred incre
`mental maintenance of materialized join ViewS is described.
`In the following description, for the purposes of explanation,
`numerous Specific details are Set forth in order to provide a
`thorough understanding of the present invention. It will be
`apparent, however, to one skilled in the art that the present
`invention may be practiced without these specific details. In
`other instances, well-known Structures and devices are
`shown in block diagram form in order to avoid unnecessarily
`obscuring the present invention.
`HARDWARE OVERVIEW
`FIG. 3 is a block diagram that illustrates a computer
`system 300 upon which an embodiment of the invention
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,125,360
`
`6
`may be implemented. Computer system 300 includes a bus
`302 or other communication mechanism for communicating
`information, and a processor 304 coupled with bus 302 for
`processing information. Computer System 300 also includes
`a main memory 306, Such as a random access memory
`(RAM) or other dynamic storage device, coupled to bus 302
`for Storing information and instructions to be executed by
`processor 304. Main memory 306 also may be used for
`Storing temporary variables or other intermediate informa
`tion during execution of instructions to be executed by
`processor 304. Computer system 300 further includes a read
`only memory (ROM) 308 or other static storage device
`coupled to bus 302 for storing static information and instruc
`tions for processor 304. A storage device 310, such as a
`magnetic disk or optical disk, is provided and coupled to bus
`302 for storing information and instructions.
`Computer system 300 may be coupled via bus 302 to a
`display 312, Such as a cathode ray tube (CRT), for displaying
`information to a computer user. An input device 314, includ
`ing alphanumeric and other keys, is coupled to buS 302 for
`communicating information and command Selections to
`processor 304. Another type of user input device is cursor
`control 316, Such as a mouse, a trackball, or cursor direction
`keys for communicating direction information and com
`mand Selections to processor 304 and for controlling cursor
`movement on display 312. This input device typically has
`two degrees of freedom in two axes, a first axis (e.g., X) and
`a Second axis (e.g., y), that allows the device to specify
`positions in a plane.
`The invention is related to the use of computer system 300
`for performing deferred incremental maintenance of mate
`rialized join Views. According to one embodiment of the
`invention, deferred incremental maintenance of materialized
`join views is performed by computer system 300 in response
`to processor 304 executing one or more Sequences of one or
`more instructions contained in main memory 306. Such
`instructions may be read into main memory 306 from
`another computer-readable medium, Such as Storage device
`310. Execution of the Sequences of instructions contained in
`main memory 306 causes processor 304 to perform the
`process StepS described herein. In alternative embodiments,
`hard-wired circuitry may be used in place of or in combi
`nation with Software instructions to implement the inven
`tion. Thus, embodiments of the invention are not limited to
`any Specific combination of hardware circuitry and Software.
`The term “computer-readable medium' as used herein
`refers to any medium that participates in providing instruc
`tions to processor 304 for execution. Such a medium may
`take many forms, including but not limited to, non-volatile
`media, Volatile media, and transmission media. Non-volatile
`media includes, for example, optical or magnetic disks, Such
`as storage device 310. Volatile media includes dynamic
`memory, Such as main memory 306. Transmission media
`includes coaxial cables, copper wire and fiber optics, includ
`ing the wires that comprise buS 302. Transmission media can
`also take the form of acoustic or light waves, Such as those
`generated during radio-wave and infra-red data communi
`cations.
`Common forms of computer-readable media include, for
`example, a floppy disk, a flexible disk, hard disk, magnetic
`tape, or any other magnetic medium, a CD-ROM, any other
`optical medium, punchcards, papertape, any other physical
`medium with patterns of holes, a RAM, a PROM, and
`EPROM, a FLASH-EPROM, any other memory chip or
`cartridge, a carrier wave as described hereinafter, or any
`other medium from which a computer can read.
`Various forms of computer readable media may be
`involved in carrying one or more Sequences of one or more
`
`Booking, Exh. 1013, Page 12
`
`

`

`6,125,360
`
`15
`
`7
`instructions to processor 304 for execution. For example, the
`instructions may initially be carried on a magnetic disk of a
`remote computer. The remote computer can load the instruc
`tions into its dynamic memory and Send the instructions over
`a telephone line using a modem. A modem local to computer
`system 300 can receive the data on the telephone line and
`use an infra-red transmitter to convert the data to an infra-red
`Signal. An infra-red detector can receive the data carried in
`the infra-red signal and appropriate circuitry can place the
`data on bus 302. Bus 302 carries the data to main memory
`306, from which processor 304 retrieves and executes the
`instructions. The instructions received by main memory 306
`may optionally be stored on storage device 310 either before
`or after execution by processor 304.
`Computer system 300 also includes a communication
`interface 318 coupled to bus 302. Communication interface
`318 provides a two-way data communication coupling to a
`network link 320 that is connected to a local network 322.
`For example, communication interface 318 may be an
`integrated services digital network (ISDN) card or a modem
`to provide a data communication connection to a corre
`sponding type of telephone line. AS another example, com
`munication interface 318 may be a local area network
`(LAN) card to provide a data communication connection to
`a compatible LAN. Wireless links may also be implemented.
`In any Such implementation, communication interface 318
`Sends and receives electrical, electromagnetic or optical
`Signals that carry digital data Streams representing various
`types of information.
`Network link 320 typically provides data communication
`through one or more networks to other data devices. For
`example, network link 320 may provide a connection
`through local network 322 to a host computer 324 or to data
`equipment operated by an Internet Service Provider (ISP)
`326. ISP 326 in turn provides data communication services
`through the Worldwide packet data communication network
`now commonly referred to as the “Internet” 328. Local
`network 322 and Internet 328 both use electrical, electro
`magnetic or optical signals that carry digital data Streams.
`The Signals through the various networks and the Signals on
`network link 320 and through communication interface 318,
`which carry the digital data to and from computer System
`300, are exemplary forms of carrier waves transporting the
`information.
`Computer System 300 can Send messages and receive
`data, including program code, through the network(s), net
`work link 320 and communication interface 318. In the
`Internet example, a Server 330 might transmit a requested
`code for an application program through Internet 328, ISP
`326, local network322 and communication interface 318. In
`accordance with the invention, one Such downloaded appli
`cation provides for deferred incremental maintenance of
`materialized join ViewS as described herein.
`The received code may be executed by processor 304 as
`it is received, and/or stored in storage device 310, or other
`non-volatile Storage for later execution. In this manner,
`computer system 300 may obtain appl