Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-04-20
2003-09-09
Vu, Kim (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06618729
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 a star join operation in a relational database management system using a bitmap index structure.
2. Description of Related Art
Relational DataBase Management Systems (RDBMS) 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 National Standards Institute (ANSI) and the International Standards Organization (ISO).
In an RDBMS, all data is externally structured into tables. A table in a relational. database is two dimensional, consisting of rows and columns. Each column has a name, typically describing the type of data held in that column. As new data is added, more rows are inserted into the table. A user query selects some rows of the table by specifying clauses that qualify the rows to be retrieved based on the values in one or more of the columns.
The SQL interface allows users to formulate relational operations on the tables either interactively, in batch files, or embedded in host languages such as C, COBOL, etc. Operators are provided in SQL that allow the user to manipulate the data, wherein each operator performs functions on one or more tables and produces a new table as a result. The power of SQL lies on its ability to link information from multiple tables or views together to perform complex sets of procedures with a single statement.
The SQL interface allows users to formulate relational operations on the tables. One of the most common SQL queries executed by the RDBMS is the SELECT statement. In the SQL standard, the SELECT statement generally comprises the format: “SELECT <clause>FROM <clause>WHERE <clause>GROUP BY <clause>HAVING <clause>ORDER BY <clause>.” The clauses generally must follow this sequence, but only the SELECT and FROM clauses are required.
Generally, the result of a SELECT statement is a subset of data retrieved by the RDBMS from one or more existing tables stored in the relational database, wherein the FROM clause identifies the name of the table or tables from which data is being selected. The subset of data is treated as a new table, termed the result table.
A join operation is usually implied by naming more than one table in the FROM clause of a SELECT statement. A join operation makes it possible to combine tables by combining rows from one table with another table. The rows, or portions of rows, from the different tables are concatenated horizontally. Although not required, join operations normally include a WHERE clause that identifies the columns through which the rows can be combined. The WHERE clause may also include a predicate comprising one or more conditional operators that are used to select the rows to be joined.
Star joins involve one or more dimension tables joined to a fact table. Star join operations can also be costly in terms of performance time.
Techniques have been developed for minimizing the time required to perform a star join operation. However, there is still a need in the art for additional optimization techniques for star join operations.
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 star join operation in relational database management systems (RDBMS). A cross-product is generated from a plurality of dimension tables referenced by the star join. The join columns of the cross-product are then hashed to create a hash-row value. Using the hash-row value, a Star Map is probed to determine whether a record that corresponds to the cross-product exists in a fact table, wherein a first portion of the hash-row value is used to select a row of the Star Map and a second portion of the hash-row value is used to select a column of the selected row of the Star Map. The fact table is accessed to perform a join with the cross-product when the selected column of the selected row of the Star Map indicates that the record might exist in the fact table.
REFERENCES:
patent: 5222233 (1993-06-01), Parks
patent: 5426760 (1995-06-01), Moreland
patent: 5706495 (1998-01-01), Chadha et al.
patent: 5781896 (1998-07-01), Dalal
patent: 5787435 (1998-07-01), Burrows
patent: 5802521 (1998-09-01), Ziauddin et al.
patent: 5864842 (1999-01-01), Pederson et al.
patent: 5893104 (1999-04-01), Srinivasan et al.
patent: 5905985 (1999-05-01), Malloy et al.
patent: 5937408 (1999-08-01), Shoup et al.
patent: 5953723 (1999-09-01), Linoff et al.
patent: 5960428 (1999-09-01), Lindsay et al.
patent: 5960434 (1999-09-01), Schimmel
patent: 5963933 (1999-10-01), Cheng et al.
patent: 5963954 (1999-10-01), Burrows
patent: 6049804 (2000-04-01), Burgess et al.
Bontempo et al., Accelerating Indexed Searching, copyright 1997 Miller Freeman Inc., <http://www.dbpd.com/vault/bontempo.htm>.*
Cormen et al., Introduction to Algorithms, ISBN 0-07-0131143-0, pp. 219-243.
Bhashyam Ramesh
Kostamaa Olli Pekka
Gates & Cooper LLP
NCR Corporation
Pham Hung
Vu Kim
LandOfFree
Optimization of a star join operation using a bitmap index... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimization of a star join operation using a bitmap index..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of a star join operation using a bitmap index... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3103675