United States Patent [19J
`Shan et al.
`
`[54]
`
`[75]
`
`VIEW COMPOSITION IN A DATA BASE
`MANAGEMENT SYSTEM
`
`Inventors: Ming·Chien Shan, San Jose; Peter
`Lyngbaek, Mountain View, both of
`Calif.
`
`[73]
`
`Assignee: Hewlett-Packard Company, Palo
`Alto, Calif.
`
`[21]
`
`Appl. No.: 595,717
`
`[22]
`
`Filed:
`
`Oct. 9, 1990
`
`[63]
`
`[51]
`[52]
`
`[58]
`
`[56]
`
`Related U.S. Application Data
`Continuation of Ser. No. 131,876, Dec. II, 1987, aban(cid:173)
`doned.
`
`Int. CI.s ............................................ G06F 15/403
`U.S. CI ..................................... 395/600; 364/974;
`364/974.6; 364/978; 364/DIG. 2
`Field of Search ....... 395!600; 364/DIG.l, DIG. 2
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,497,039 1/1985 Kitakami et al. ................... 364/900
`4,506,326 3/1985 Shaw et al. ......................... 364/300
`4,631,673 12/1986 Haas eta!. .......................... 364/300
`4,644.471 2/1987 Kojima et al. ...................... 364/300
`4,688,195 8/1987 Thompson et al. ................. 364/300
`4,769,772 9/1988 Dwyer ................................ 364/300
`4,791,561 12/1988 Huber .................................. 395/600
`4,805,099 2/1989 Huber .................................. 364/300
`4,888,690 12/1989 Huber .................................. 395/600
`4,918,593 4/1990 Huber .................................. 395/600
`4,930,071 5/1990 Tou et al. ............................ 395!600
`5,097,408 3/1992 Huber .................................. 395!600
`
`FOREIGN PATENT DOCUMENTS
`2172130 3/1986 Japan .
`
`OTHER PUBLICATIONS
`Roussopoulos, Nicholas: "View Indexing in Relational
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`US005276870A
`[Ill Patent Number:
`[45] Date of Patent:
`
`5,276,870
`Jan. 4, 1994
`
`Databases", ACM Transactions on Database Systems,
`vol. 7, No. 2, Jun. 1982, pp. 258-290.
`Rowe et a!: "Data Abstraction, Views and Updates in
`RIGEL", The Ingres Papers: Anatomy of a Relational
`Database System, Addison-Wesley Pub!., 1986, pp.
`278-294.
`Dayal et al. "On the Updatability of Relational Views",
`Proceedings of 4th Intematinoal Conf. on Very Large
`Databases, Sep. 1978, pp. 368-377.
`K. C. Kinsley eta!.: "A Generalized Method for Main(cid:173)
`taining Views", AFIPS Conference Las Vegas, Ne(cid:173)
`vada, Jul. 9-12, 1984, pp. 587-593.
`S. Talbot: "An Investigation into Logical Optimization
`of Relational Query Languages" The Computer Jour(cid:173)
`nal, vol. 27, No.4, No. 1984, pp. 301-309.
`S. Hanara et al: "Conversational Database Query Lan(cid:173)
`guage", Review of the Electrical Communication Lab(cid:173)
`oratories, vol. 29, Nos. 1-2, Jan./Feb. 1981, pp. 32-50.
`C. J. Date: "An Introduction to Data Base Systems",
`3rd Edition, Section 9, The External Level of System
`R, Nov. 1974, pp. 159-168.
`Primary Examiner-Thomas C. Lee
`Assistant Examiner-MariaN. Von Buhr
`[57]
`ABSTRACT
`In a database management system that operates accord(cid:173)
`ing to the Structured Query Language standard, a
`query containing a reference to a view is processed by
`dynamidtlly materializing the view through execution
`of the view definition. Once the view is materialized, it
`is treated as any other base table. To enable a query
`optimization plan to refer to the materialized view, a
`view node is introduced into the execution plan. The
`view node includes a subquery that results in the cre·
`ation of the virtual table defined by the view. This cre(cid:173)
`ated table is temporarily stored in a memory. The query
`optimizer can treat view nodes in the same manner as
`stored base tables, and thereby overcomes restrictions
`that were placed upon views by previous view decol:n·
`position approaches.
`
`3 Claims, 3 Drawing Sheets
`
`CONTROL PROGRAt.4
`
`001
`
`

`

`INPUT l)4
`
`00
`
`CPU
`
`A
`['r--'
`
`06
`
`OUTPUT
`
`CONTROL PROGRAM
`
`.
`I I I II
`BASE
`TABLE
`
`18_../
`
`..
`"
`
`I I I I
`
`I I I I I
`
`BASE
`TABLE
`
`BASE
`TABLE
`
`18./ 18--'
`
`TEMP
`
`2t
`
`TEMP
`INDEX
`
`~ 20 ~ 20
`TABLE 04
`I TUPLE REG G=22
`24'
`TEMP LJ
`TABLE G
`261
`
`J\
`
`TEMP
`INDEX
`
`FIG 1
`
`FIG 2
`
`...
`U1
`~
`-.l
`...
`0\
`00
`-.l
`0
`
`002
`
`

`

`U.S. Patent
`
`Jan. 4, 1994
`
`Sheet 2 of 3
`
`5,276,870
`
`JOIN
`
`JOIN
`
`I
`
`TABLE NODE
`T1
`
`TABLE NODE
`T2
`
`VIEW NODE
`v
`
`QUERY TREE
`FOR VIEW V
`
`FIG 3
`
`JOIN
`I
`T3
`
`I
`
`VIEW
`
`JOIN
`
`I
`I
`T2
`T1
`FIG 4
`
`003
`
`

`

`U.S. Patent
`US. Patent
`
`Jan. 4, 1994
`Jan. 4, 1994
`
`Sheet 3 of 3
`Sheet 3 of 3
`
`5,276,870
`5,276,870
`
`0
`o
`F‘
`.......- ~
`1-
`.—
`
`I...-
`
`O)
`0)
`i...
`1-
`
`X
`5:,
`1.&.1
`_]
`-1
`0
`0..
`g"
`~
`0
`(.)
`
`oo
`
`“D
`(0
`>
`
`>
`
`0
`0
`
`-o
`‘O
`
`co
`00
`U)
`L()
`>
`1-
`>l--
`
`-o
`'0
`
`“J
`LLI
`23
`...J
`(.!)
`-
`z
`5
`en
`(n
`
`X
`:5
`1.&.1
`-1
`g
`0..
`~
`0
`8
`(.)
`
`o
`0
`
`CV
`N
`>
`>
`
`0
`°
`
`()
`
`1.&.1
`Eu
`...J
`0..
`5
`~ -
`en
`
`..q-
`>
`
`-o
`‘7
`
`.......-
`
`,......
`[\
`1-
`*-
`.In
`
`a
`
`..__
`
`on.
`(0
`1-—
`1-
`
`a
`
`~
`
`+-
`1-
`
`()
`
`1.&.1
`-1
`0..
`
`SIMPLE
`::E -(/)
`
`~
`
`V1
`> f.--
`
`"'0
`
`SIMPLEmen
`
`1'0
`1-
`
`()
`
`1'0
`>
`
`-o
`
`1.&.1
`-1
`0..
`~ -
`
`(/)
`
`004
`
`L()
`.......- 1-
`
`an
`
`..q-
`1-
`
`I...-
`
`004
`
`

`

`1
`
`VIEW COMPOSITION IN A DATA BASE
`MANAGEMENT SYSTEM
`
`5,276,870
`
`2
`With this view created, the original query would then
`become:
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`This is a continuation of copending application
`7/131,876 filed on Dec. il, 1987, now abandoned.
`
`5
`
`SELECT •
`FROM Emptoy
`
`(where the character "*" is a universal character to
`designate all fields in the table or view). As can be seen,
`10 the prior definition of the view makes the query much
`easier to formulate.
`In addition, this view can be the subject of a further
`query. For example, to obtain the salary of all employ(cid:173)
`ees named Johnson in the toy department, the following
`query can be entered:
`
`15
`
`SELECT Salary
`FROM
`Emptoy
`WHERE Name = "Johnson"
`20 ------------------------------------------
`
`As noted above, the data which makes up the virtual
`table Emptoy is not actually stored as such in the data
`base. Rather, only the definition of the view is stored.
`Accordingly, when a query which references a view is
`entered, a process known as view decomposition is
`carried out to translate the query into an equivalent
`query which references only stored base tables. In es(cid:173)
`sence, the view decomposition process comprises the
`steps of replacing the reference to the view in the query
`with the definition of that view. Thus, in the example
`given above, the query for obtaining the salary of the
`employees named Johnson in the toy department would
`be modified to produce the following equivalent query:
`
`BACKGROUND OF THE INVENTION
`The present invention is directed to data base sys(cid:173)
`tems, and more particularly to a technique which ena(cid:173)
`bles data to be efficiently retrieved with the use of views
`having complex definitions. Although not limited
`thereto, the invention is particularly concerned with the
`standard for relational data bases known as "Structured
`Query Language" (SQL) and the constraints imposed
`thereby. For further detailed information relating to
`thl·s standard re"erence 1's made to Date A Guz'de To The
`11
`~I ~.
`SQL Standard (1987) and Date, A Guide To DB2 (1985).
`'
`'
`In relational data base management systems of the
`type to which the SQL standard pertains, data is stored
`in the form of base tables. Each base table essentially
`consists of a series of fields which define columns of the 25
`table. Each row of the table comprises a single record,
`also referred to as a "tuple." For each row of data in a
`table, a counterpart of that data is physically stored in
`the data base. When the data base user accesses a base
`table, the appropriate portion of the stored data is re- 30
`trieved and presented to him in the form of a table.
`In addition to base tables, data can also be accessed by
`means of "views." In contrast to a base table, a view is
`a "virtual" table in that the table does not directly exist
`in the data base as such, but appears to the user as if it 35
`did. In fact, the view is stored in the data base only in
`terms of its definition. For example, a view might com-
`prise a subset of a base table, such as those tuples of the
`SELECT Salary
`FROM
`Employee
`table which have a predetermined value in a particular
`WHERE Name= "Johnson" and Dept= "Toy"
`field. As another example, a view could comprise a join 40 _____ __:;.:.::;:;;.::._:....:.;;.:.:;_ ____________ ....:.... ____ .....;... ____ __
`operation, e.g. union, of two or more tables, where
`these other tables can be base tables, other views or a
`combination of both.
`In relational data base systems that comply with the
`SQL standard. desired information is searched for and 45
`retrieved by means of expressions known as queries.
`For example, if a table named "Employee" contains the
`fields "Name", "Dept", "Age" and "Salary", and a user
`desires to find the subset of employees who work in the
`toy department, the following query can be used:
`
`As can be seen, the modified query refers only to base
`tables and fields within that table.
`In principle, it should be possible for a query to refer(cid:173)
`ence any view defined by an arbitrary query, and to
`translate that query into an equivalent operation on the
`underlying base tables. In practice, however, the appli(cid:173)
`cability of this procedure is quite limited because of
`restrictions imposed by the SQL standard. For example,
`50 a view labeled "A vgsal" can be defined from two base
`tables Dept and Emp. The table Dept contains the fields
`"Dno" (department number), "Dname", "Mgrname"
`and "Loc", and the table Emp contains the fields "Eno"
`(employee number), "Dna", "Salary" and "Jobtitle".
`55 The definition of the view A vgsal which describes a
`department by its department number, department
`name and the average salary of its employees could
`appear as follows:
`
`SELECT Name. Salary, Age
`FROM
`Employee
`WHERE Dept = "Toy"
`
`If it is known that the information produced by this
`query will be used several times, a view can be defined,
`to thereby avoid the need to reformulate the query each
`time the information is desired. A view named "Emp- 60 --------------------------------------------
`toy" which produces the same information can be de-
`CREATE VIEW Avgsal
`(Dno, Dname, Avgsalary) AS
`SELECT
`Dno, Dname, A VG(Salary)
`fined by means of the following statement:
`FROM
`Dept. Emp
`WHERE
`Dept.Dno = Emp.Dno
`GROUP BY
`Dno
`
`CREATE VIEW
`SELECT
`FROM
`WHERE
`
`Emptoy (Name. Salary, Age) AS
`Name, Salary. Age
`Employee
`Dept= "Toy"
`
`65
`
`A query that asks for the location of all departments
`whose employees have an average salary greater than
`$30,000 would require a join operation on the base table
`
`005
`
`

`

`3
`Dept and the view A vgsal and could appear as follows:
`
`5,276,870
`
`4
`FIG. 3 is a block diagram representation of a query
`execution plan utilizing view composition;
`FIG. 4 is a block diagram representation of another
`query execution plan utilizing view composition; and
`FIG. 5 is a block diagram representation of a query
`execution plan which employs both view composition
`and view decomposition.
`
`SELECT Loc
`FROM
`Dept, A vgsal
`WHERE Dept.Dno = Avgsal.Dno and
`A vgsai.A vgsalary > 30,000
`
`5
`
`l!nfortuna~ely, the limitations of the view decomposi(cid:173)
`tion techmque prevent the processing of this query. 10
`More particularly, the query cannot be processed be(cid:173)
`cause the WHERE clause contains reference to a vir(cid:173)
`tual column A vgsalary which does not correspond to
`an existing column of a base table.
`Basically, the translated form of an original query 15
`must always be a legal query itself. Thus, the applicabil-
`ity of view decomposition is limited to views which are
`relatively simple. Hence, it is desirable to provide a
`technique which enables views with a greater degree of
`complexity to be referenced in queries, and thereby
`expand the processing power of a database system.
`
`20
`
`25
`
`30
`
`35
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`Referring to FIG. 1, a general overview of a database
`system is illustrated in block diagram form. The main
`components of the system comprise a central processing
`unit 10, a permanent memory unit 12 such as a magnetic
`disk or tape, and a main or non-permanent memory unit
`13 such as a RAM. To enable the user to enter data and
`retrieve information, a suitable input device 14, such as
`a keyboard, is connected to the CPU 10. In addition, the
`i~formation retrieved by the database system is pro(cid:173)
`VIded to the user through a suitable output device 16,
`such as a video monitor and/or a printer.
`Within the permanent memory unit 12, a control
`program is stored along with the data that makes up the
`BRIEF STATEMENT OF THE INVENTION
`. In accor?ance ~ith t.he present invention, the Jimita-
`database. Examples of relational database management
`systems that operate according to the SQL standard
`twns associated w1th v1ew decomposition can be over-
`come by means of a technique that is referred to herein
`include SQL/DS and DB2 of IBM Corp., and RTI
`lngres. The data entered by the user is stored in the
`as view composition. In this technique, a query contain-
`permanent memory unit 12 in the form of base tables 18.
`ing a reference to a view is processed by dynamically
`composing, or m~terializing, the view at run time
`At the outset, the user defines each table, including the
`through the executiOn of the corresponding view defini-
`headings for each column in the table and the parame-
`ters of each column. Thereafter, data is entered to fill in
`tion. Once the view is composed, it can be subsequently
`treated as any other base table. If a view contains a
`the tuples of the various base tables.
`In addition, views can be defined to indicate a subset
`reference to other views, the other views are first pro-
`cessed to provide the information for the subsequently
`of a particular table, a relationship between two or more
`tables, or an operation upon the information in one or
`composed view.
`more base tables. While the information obtained by the
`Since the materialized view is treated as a base table,
`definition of a view is presented to the user at the output
`reference must be made to this materialized view in a
`device 16 in the form of another table, this table is not
`query execution plan. To perform this function, a new
`type o~ node, referred to her~in as a view node, is intro- 40 permanently stored as such in the memory unit 12.
`duced mto the query executiOn plan to represent views
`Rather, only the definition 20 itself is permanently
`and their materialization. A view node functions simi-
`stored in the memory.
`larly to a table node that represents a stored base table.
`When a query is to be processed, it is first presented
`However, in contrast to a table node there is no perma-
`to an optimizer which comprises a portion of the con-
`nent stored table in the database which corresponds to 45 trol program. The optimizer evaluates the query and the
`t~bles referenced thereby, and develops a query execu-
`the view node. Rather, the view node has a subquery
`that defines the creation of the virtual table. The query
`tlon plan that is intended to optimize the performance of
`optimizer can treat view nodes in exactly the same
`the system in the processing of the query. Basically, the
`manner as stored base tables. As a result, restrictions
`optimizer takes into account the cardinality, i.e., the
`t~at were placed upon views by the view decomposi- 50 number of tuples, in each table, the selectivities of the
`tlon process are removed.
`search conditions, and indexes which may be defined on
`To enable the query optimizer to treat a view as a
`each table. Based upon this information, the optimizer
`develops an execution plan that results in efficient utili-
`table, certain statistical information (for example, the
`number of tuples in a view) is needed. In the past, this
`zation of the processing power of the CPU.
`type of information has only been available for base 55
`For example, a query which requires a join operation
`on three base tables T1, T2 and T3 might appear as
`tables, and not for views. In accordance with one aspect
`of the present invention, however, such information is
`follows:
`maintained for views as well.
`Further features of the invention and the advantages
`offered thereby are described hereinafter in greater 60
`detail with reference to specific examples and with the
`aid of the accompanying drawings.
`·
`
`SELECT*
`FROM Tl, T2, T3
`WHERE Tl.fl = T2.f2 and Tl.fl - T3.f3
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a generalized block diagram of a database
`system;
`FIG. 2 is a block diagram representation of a query
`execution plan;
`
`In the foregoing statement, the term "Tl.fl" represents
`the first field in the base table T1, "T2.f2" represents the
`65 second field in the base table T2, etc. In response to this
`query, the optimizer might generate a query execution
`plan as shown in FIG. 2. Basically, this plan indicates
`that the join operation on the tables T1 and T2 is first
`
`006
`
`

`

`5,276,870
`
`5
`carried out, i.e., the tuples where Tl.fl = T2.f2 are lo(cid:173)
`cated. The results of this first join operation are then
`joined with table T3 to produce the final result, which
`is provided to the user on the output device 16.
`The particular position of each table in the execution 5
`plan is significant. In operation, the table on the left
`hand side of a join node functions as the outer, or pri(cid:173)
`mary, table. Each tuple of the outer table is selected
`once, and for each such selection all of the tuples of the
`inner, or secondary, table on the right hand side of the 10
`node are scanned. Hence, in the example of FIG. 2, the
`inner table T2 will be scanned a number of times equal
`to the number of tuples in the outer table T1. Then, the
`upper node 21 will sequentially request the tuples in the
`result of this first join operation and the inner table T3 15
`will be scanned for each such tuple.
`In accordance with the present invention, a query
`which references a view can be processed by dynami(cid:173)
`cally executing the definition of the view during the
`run-time for the query. For a given query, a view might 20
`be processed by such execution or by view decomposi(cid:173)
`tion. The execution of the definition results in the corn(cid:173)
`position of a table that can be subsequently treated in
`the manner of base tables during the query execution. In
`the prior art data retrieval technique which employed
`only view decomposition, a query which referenced a
`view was translated into an equivalent query that re(cid:173)
`ferred only to base tables. Hence, it was unnecessary for
`the query execution plan to refer to views. However, a 30
`query execution plan which is produced by the view
`composition technique of the present invention must be
`able to refer to views as well as base tables. To meet this
`need, another type of node referred to as a view node is
`introduced into the query execution plan to represent 35
`views and their materialization. A view node is essen(cid:173)
`tially similar to a table node which represents a stored
`base table. However, in contrast to the table node there
`is no permanent stored table in the database memory 12
`which corresponds to a given view node. Rather, the 40
`view node comprises a subquery that defines a table.
`To further illustrate, a view might be defined as a join
`operation on base tables T1 and T2 according to the
`following statement:
`
`25
`
`6
`a join node in a query execution plan, giving the query
`optimizer more options in selecting an optimal strategy.
`Different approaches can be used for composing the
`view. In one possible implementation of the view com(cid:173)
`position approach, the tuples of a view are materialized
`on demand as they are requested by the parent of the
`view node. This strategy may be the most preferable in
`situations such as a nested loop join operation in which
`the view is chosen as the outer, i.e., left hand, table in
`the execution plan. In operation, the first tuple of the
`view is materialized when called for by the parent of the
`view node. This materialized tuple can be temporarily
`stored in a register or buffer 22 in the system memory
`(FIG. 1). Preferably, this register is located in the tem(cid:173)
`porary memory 13, rather than a permanent memory
`such as the memory unit 12. When the next tuple is
`requested during query execution, it is materialized and
`replaces the previous tuple in the register 22.
`A second possible implementation of the view com(cid:173)
`position approach materializes the entire view at once
`when the view node is first addressed in the query exe(cid:173)
`cution plan. The materialized view is stored as a tempo(cid:173)
`rary table 24 in the memory unit 12. Normal cache
`techniques can be applied to transfer the temporary
`table to the main memory 13 where the transferred table
`24' is operated upon during query execution. When the
`tuples of the materialized view are requested by the
`node immediately above the view node, they are ob(cid:173)
`tained from one of the temporary tables 24 or 24', de(cid:173)
`pending on whether the temporary table has been
`cached. This approach introduces the cost of creating
`and populating a temporary table, so that it is preferable
`to use it only in those situations in which the view is to
`be referred to more than once. For example, this situa(cid:173)
`tion might occur in nested loop join operations in which
`the view is chosen as the inner table, or in queries with
`multiple references to the same view.
`If the query optimizer deems it worthwhile, tempo(cid:173)
`rary indexes may be generated for the materialized
`views. For example, an index 26 may be generated and
`stored in the memory unit 12 or, if preferred, an index
`26' may be generated and stored in the main memory 13
`if the materialized view is to be accessed on the same
`columns more than one time.
`As noted above, the materialization of a view offers
`greater flexibility to the optimizer. For example, statisti(cid:173)
`cal information that is important for query optimization,
`such as the cardinality and selectivity of a view, can be
`generated. In addition, the materialization of the view
`SO increases the functionality of the database system. For
`example, the tuples of a materialized view can be
`scanned in accordance with a certain order or grouping,
`and mathematical or statistical operations can be per(cid:173)
`formed on them.
`A materialized view, whether stored tuple by tuple in
`the register 22 or as an entire table in the temporary
`table 24, is only maintained until the termination of the
`execution of the query in which the view is material(cid:173)
`ized. Thus, it is not necessary to maintain consistency
`60 between materialized views and their underlying base
`tables.
`Although the view composition approach adds the
`expense of materializing a view, the enhanced perfor(cid:173)
`mance which it provides, particularly the ability to
`65 support queries which reference complex views, more
`than justifies the expense. A query which specifies a join
`operation on the vie\\· V and another table T3 might
`appear as follows:
`
`45
`
`CREATE VIEW V AS
`SELECT •
`FROM Tl, T2
`WHERE Tl.fl = T2.f2
`
`An example of a query execution plan with a view node
`which specifies the materialization of the view V is
`shown in FIG. 3 for the following query:
`_____________________________________ ss
`
`SELECT •
`FROM T!, T2, V
`WHERE Tl.f2 = T2.fl and T2.f2 = V.f3
`
`A particular advantage of the view composition tech(cid:173)
`nique is that it enables the query optimizer to treat view
`nodes in the same manner as table nodes, with all their
`explicit and implicit ordering properties as well as em(cid:173)
`ploy other necessary statistical data normally associated
`with tables, e.g. cardinality, selectivity, etc. In conven(cid:173)
`tional practice, only base tables were considered as
`inner nodes. However, with the view composition ap(cid:173)
`proach, a view node can appear as the inner subtree of
`
`007
`
`

`

`5,276,870
`
`7
`
`SELECT •
`FROMV, T3
`WHERE V.fl = T3.f3
`
`20
`
`8
`view is processed in the decomposition mode, where d
`means decomposition of the view and c means composi(cid:173)
`tion of the view. On the right side is an indication of
`how the view is processed in the composition mode.
`5 The views V6 and V2 will always be materialized since
`they are complex and the view V5 will always be de(cid:173)
`composed since it is a single table view. However, the
`query optimizer will consider both view composition
`and view decomposition for views Vl, V3 and V4, and
`choose the most efficient.
`In the example given above, the views Vl, V3, and
`V4 can always be processed by the same technique,
`depending on whether the decomposition mode or the
`composition made is chosen. It may be preferable, how(cid:173)
`ever, to consider mixed strategies for simple views In
`this regard the temporary tables resulting from view
`materialization may have indexes defined on them to
`facilitate subsequent accesses to the temporary tables.
`While the concept of materialization has been pres-
`ented with regard to views in query plans, it can be
`generalized to subtrees of query trees. Any subtree of a
`given query tree can be materialized and possibly stored
`in a temporary table. This technique can be used in
`query optimization exactly for the same reasons view
`composition may benefit query performance For exam(cid:173)
`ple, if a query tree has a subtree that is executed many
`times, the query may be optimized by materializing the
`subtree and storing the result in a temporary table the
`first time the subtree is materialized. Successive execu(cid:173)
`tions of the subtree thereby reduce to scans of the tem(cid:173)
`porary table. Such an approach to query optimization is
`advantageous if the cardinality of the materialized sub(cid:173)
`tree is small or the computation of the subtree is expen-
`sive.
`It may be beneficial to store the result of a subtree
`that is executed many times in a temporary table only if
`the subtree has the same value in each materialization
`i.e., no correlated variables appear in the subtree. How-
`ever, even if the value of a subtree depends on a corre(cid:173)
`lated variable it may still be worthwhile to materialize
`and temporarily store a less restricted table which does
`not depend on the value of the correlated variable. The
`result of the subtree can then be obtained by further
`processing the temporary table.
`The following query illustrates an example of this
`approach to query optimization:
`
`If the view decomposition approach is utilized, a possi(cid:173)
`ble query execution plan may appear as shown in FIG.
`2. However, this may not be the optimal plan in some
`situations. For example, if all three base tables are large, 10
`but the cardinality of the view V is small, an optimal
`query plan based on view composition might appear as
`shown in FIG. 4. With this approach, the temporary
`table that results from the view composition requires a
`join operation on tables Tl and T2, which might be
`expensive, to be carried out only once, rather than for 15
`each tuple in the table T3 as required by the decomposi(cid:173)
`tion approach. If the view is small enough to fit in the
`main memory 13 of the data management system, the
`join operation on the table T3 and the materialized view
`will be.performed even more efficiently.
`While view composition might be the better ap(cid:173)
`proach in many types of queries, certain situations will
`still provide optimal performance if view decomposi(cid:173)
`tion is employed. Thus, a preferred optimizer should
`consider both approaches in developing an optimal 25
`query execution plan. In a relatively simple implementa(cid:173)
`tion of this concept, the optimizer could utilize view
`decomposition for all single-table views, i.e., those
`views which reference only a single base table, and
`view composition for all other views. However, queries 30
`which contain certain other types of simple views that
`reference more than a single base table might also per(cid:173)
`form better with view decomposition. Thus, a more
`preferable optimizer would classify views into three
`types:
`I) Single-table views, i.e., those which reference only
`a single base table;
`2) Complex views, i.e., those which use any one or
`more of the statements UNION, ORDER BY,
`GROUP BY, DISTINCT, or which derive col- 40
`umns from built-in functions or operational expres(cid:173)
`sions, or which reference other complex views;
`3) Simple views, i.e., all views other than single-table
`views and complex views.
`In operation, the optimizer would structure an execu- 45
`tion plan so that all complex views are processed by
`view composition, all single-table views are processed
`by view decomposition, and simple views are processed
`by either approach in dependence upon which is the
`most efficient.
`An example of a query execution plan which employs
`the foregoing principles is shown in FIG. 5. This query
`represents a join operation on a table Tl and two views
`Vl and V2. The view Vl is defined as a join operation
`on a view V3 and a table T3. The view V3 is defined as 55
`a join operation on two tables T4 and T5 and is a simple
`view. The view V2 is defined as the join operation
`involving three views V4, V5 and V6. The view V4 is
`a simple view defined as the join operation involving
`two tables T6 and T7. The view V5 is a single table 60
`view defined on the tableTS. The view V6 is a complex
`view defined as a join operation on two tables T9 and
`TIO. The view V2 is defined as a complex view since it
`references the complex view V6.
`The query tree shown in FIG. 5 is annotated to indi- 65
`cate how each view is processed in each of two modes
`referred to as decomposition and composition. On the
`left side of each view node is an indication of how the
`
`35
`
`50
`
`SELECT •
`FROM Tl
`WHERE TJ.fl IN (
`SELECT T3.fl
`FROM V, T3
`WHERE T3.f3 = V.fl and V.f2 = TJ.fl)
`
`The tables Tl, T2, and T3 and the view V are as
`described previously with regard to the example of
`FIG. 4. The subquery is executed for each tuple in Tl.
`The cost of repeatedly executing the view V can be
`avoided if the view is materialized once and the result
`stored in a temporary table. Even if the view is material(cid:173)
`ized, it is still necessary to do a fair amount of work,
`e.g., to join T3 and selected tuples of the materialized
`view, in order to compute the result of the subquery.
`This work must be repeated for every tuple in Tl. The
`re-computations of the subquery can be avoided by
`materializing the entire subquery once and storing it in
`a temporary table.
`
`008
`
`

`

`5,276,870
`
`9
`In some cases, this approach may not be totally feasi(cid:173)
`ble since the result of the subquery depends on the value
`of Tl.fl. As an alternative, a less restricted subquery,
`defined below as the join involving table T3 and the
`view V, could be materialized:
`
`5
`
`10
`classifying any view that is defined in terms of only
`one base table as a single-table view;
`classifying any view that is not a single-table view
`and that is defined in terms of execution of a prede(cid:173)
`termined operation on a base tables as a complex
`view;
`classifying any view that is not a single-table view
`and that is not a complex view as a simple view;
`determining whether the computer would evaluate
`the query more rapidly by composing a view table
`according to the definition of each complex view
`that is referenced by the query or by not compos(cid:173)
`ing such view table;
`selecting each complex view that is referenced by the
`query if an only if the result of the preceding step is
`that the computer would evaluate the query more
`rapidly by composing such view table;
`composing a view table according to the definition of
`each selected view by retrieving the stored data
`and manipulating the retrieved data in the com(cid:173)
`puter according to said definition to provide tuples
`of the view table;
`evaluating the query by manipulating the provided
`view table tuples in the computer according to the
`query to obtain a result; and
`providing a result of the evaluation.
`3. In a database system having data and a plurality of
`view definitions stored in a memory of a computer, the
`data arranged in base tables and each view definition
`defining a view in terms of the base tables, a method of
`processing a query that references one or more of the
`views, the method comprising:
`classifying any view that is defined in terms of only
`one base _table as a single-table view;
`classifying any view that is not