Deriving uniqueness for indices on summary tables

Details Deriving uniqueness for indices on summary tables Deriving uniqueness for indices on summary tables

1999-12-21

2003-01-28

Rones, Charles L. (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06513034

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to database management systems performed by computers, and in particular, to the optimization of queries using indices for summary tables.
2. Description of Related Art
Computer systems incorporating Relational DataBase Management System (RDBMS) software using a Structured Query Language (SQL) interface are well known in the art. The SQL interface has evolved into a standard language for RDBMS software and has been adopted as such by both the American Nationals Standard Institute (ANSI) and the International Standards Organization (ISO).
For most RDBMS software, combinations of base tables and views are used to access data stored in the database. A view definition includes a query that, if processed, provides a temporary result table based on the results of the query at that point in time. Using an INSERT statement and an appropriately defined table in the database, the temporary results table can be stored in the database. To refresh this table, the user would need to perform a DELETE from the table and then perform the INSERT again.
Users can directly query against a table in this manner, provided that the users are aware how the results were derived. Generally, the RDBMS software is not aware that such a table is any different from any other table in the database. However, this table cannot be used by an optimizer within the RDBMS software to improve performance, even though the table may contain data that would drastically improve the performance of other queries.
This leads to the idea of summary tables (also known as materialized views) as envisioned by the present invention. These tables are similar to the created table described above, except that the definition of the table is based on a “full select” (much like a view) that is materialized in the table. The columns of the table are based on the elements of the select list of the full select.
Summary tables are important for query optimization in data warehouse applications. There are extensive research activities and literature on summary tables and materialized views, as disclosed in the following publications, all of which are incorporated by reference herein:
1. L. S. Colby, R. L. Cole, E. Haslam, N. Jazaeri, G. Johnson, W. J. McKenna, L. Schumacher, D. Wilhite. Red Brick Vista: Aggregate Computation and Management. Proceedings of the 14
th
Int'l. Conference on Data Engineering, Orlando, Fla., 1998.
2. R Bello, K. Dias, A. Downing, J. Feenan, J. Finnerty, W. Norcott, H. Sun, A.
Witkowski, M. Ziauddin. Materialized Views In Oracle. Proceedings of the 24
th
VLDB Conference, New York, 1998.
3. D. Srivastava, S. Dar, H. Jagadish, A. Levy. Answering Queries with Aggregation Using Views. Proceedings of the 22
nd
VLDB Conference, Mumbai, India, 1996.
So far, the state of the art has focused on query rerouting using materialized views and incremental maintenance of materialized views. However, there is increasing need to optimize queries through the use of indices, especially unique indices that are defined on base tables referenced in the materialized views.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, apparatus, and article of manufacture for optimizing a query by deriving uniqueness for indices on the summary tables. The query is analyzed to determine whether a summary table can be used to answer the query. A determination is made whether an index of the summary table is unique based on a query definition of the summary table. During query optimization phase, proving the existence of a unique index on the summary table further enables query optimization. For example, proving uniqueness may allow an optimizer function to remove a sort requirement by proving the generalized 1-tuple condition based on the techniques described in U.S. Pat. No. 5,615,361, entitled “Exploitation of Uniqueness Properties using 1-Tuple Condition for the Optimization of SQL Queries”, issued Mar. 25, 1997, to Ting Y. Leung et al., which patent is incorporated by reference herein. Similarly, proving index uniqueness may allow the optimizer to generate an efficient “early-out” plan when at most one row will be returned as the answer set.


REFERENCES:
patent: 5133075 (1992-07-01), Risch
patent: 5276870 (1994-01-01), Shan et al.
patent: 5535385 (1996-07-01), Griffin et al.
patent: 5600831 (1997-02-01), Levy et al.
patent: 5603025 (1997-02-01), Tabb et al.
patent: 5615361 (1997-03-01), Leung et al.
patent: 5682535 (1997-10-01), Knudsen
patent: 5706495 (1998-01-01), Chadha et al.
patent: 5761653 (1998-06-01), Schiefer et al.
patent: 5822750 (1998-10-01), Jou et al.
patent: 5963933 (1999-10-01), Cheng et al.
patent: 5991754 (1999-11-01), Raitto et al.
patent: 6105020 (2000-08-01), Lindsay et al.
patent: 6339768 (2002-01-01), Leung et al.
patent: 0079465 (1983-05-01), None
L.S. Colby, R.L. Cole, E. Haslam, N. Jazayeri, G. Johnson, W.J. McKenna, L. Schumacher, D. Wilhite. Red Brick Vista: Aggregate Computation and Management. Proceedings of the 14thInt'l. Conference on Data Engineering, Orlando, FL, 1998, pp. 174-177.
R. Bello, K. Dias, A. Downing, J. Feenan, J. Finnerty, W. Norcott, H. Sun, A. Witkowski, M. Ziauddin. Materialized Views In Oracle. Proceedings of the 24thVLDB Conference, New York, 1998, 659-664.
D. Srivastava, S. Dar, H. Jagadish, A. Levy. Answering Queries with Aggregation Using Views. Proceedings of the 22ndVLDB Conference, Mumbai, India, 1996, 318-329.
H. Pirahesh, “Extensible/Rule Based Query Rewrite Optimization in Starburst”, ACM SIGMOD Conference on Management of Data, vol., 21, No. 2, Jun. 1992, pp 39-48.

Affiliated with

Also associated with

Rating

Deriving uniqueness for indices on summary tables does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Deriving uniqueness for indices on summary tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deriving uniqueness for indices on summary tables will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3068079