Method of optimally determining lossless joins

Details Method of optimally determining lossless joins Method of optimally determining lossless joins

2002-05-23

2003-07-29

Breene, John E. (Department: 2177)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

06601063

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 a method of optimally determining lossless join operations.
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).
In a data warehouse, referential integrity constraints are often created to maintain the data integrity across different tables. Referential integrity imposes a constraint between tables such that whenever a tuple is inserted into a child table, there will be exactly one matched row in the parent table. In other words, the join of parent and child tables does not reduce the number of rows of the child table that satisfy a WHERE condition. Therefore, the join is considered a lossless join.
It is well-known in research literature that the parent table can be eliminated from the query if its columns are not selected, and hence there is a need in the art for an optimizing method that eliminates parent tables where the join between the parent and child table is a lossless join. Specifically, there is a need in the art for identifying which joins are lossless and which tables are eligible for removal.
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 being performed by a computer system to retrieve data from a database stored on the computer system. The query is analyzed to identify any joins therein that are lossless and to identify any tables of the identified joins that are eligible for removal. This analysis includes partitioning the joins into lossless and lossy joins, and partitioning the tables of the joins according to their associated quantifiers, wherein each of the quantifiers has a quantifier state indicating whether the table participates in a join that is lossless. The query is then rewritten to eliminate the identified tables that are eligible for removal.


REFERENCES:
patent: 5542073 (1996-07-01), Schiefer et al.
patent: 5548758 (1996-08-01), Pirahesh et al.
patent: 5590324 (1996-12-01), Leung et al.
patent: 5659725 (1997-08-01), Levy et al.
patent: 5671403 (1997-09-01), Shekita et al.
patent: 5822750 (1998-10-01), Jou et al.
patent: 5832477 (1998-11-01), Bhargava et al.
patent: 5848406 (1998-12-01), Mani et al.
patent: 5864842 (1999-01-01), Pederson et al.
patent: 5930785 (1999-07-01), Lohman et al.
patent: 5960427 (1999-09-01), Goel et al.
patent: 5991754 (1999-11-01), Raitto et al.
patent: 6134543 (2000-10-01), Witkowski et al.
patent: 6438542 (2002-08-01), Koo et al.
patent: 6449606 (2002-09-01), Witkowski
patent: 2168287 (1996-10-01), None
patent: 0 877 327 (1998-11-01), None
K.V.S.V.N. Raju and Arun K. Majumdar, “Fuzzy Functional Dependencies and Lossless Join Decomposition of Fuzzy Rational Database System”, ACM, pp. 129-166, 1988.*
U. Chakravarthy et al., “Logic-Based Approach to Semantic Query Optimization”, ACM Transactions on Database Systems, vol. 15, No. 2, 1990, pp. 162-207.
Sreekumar T. Shenoy et al., “A System for Semantic Query Optimization”, ACM 0-89791-236-5/87/0005/0181, 1987, pp. 181-188.
J.K. Mullin, “Estimating the Size of a Relational Join”,Informational Systems, vol., 18, No. 3, pp. 189-196 Apr. 1993 (Abstract only -1pp).
T. Zurek, “Optimisation of Partitioned Temporal Joins”,Advances in Database: 15thBritish National Conference on Databases, BNCOD 15. (proceedings), pp. 101-115, Published: Berlin, Germany, 1997, (Abstract only -1pp).
K. Munakata, “Integration of Maximum Information Using Outerjoins, Predicates and Foreign Functions”,IEICE Transactions on Information and Systems, vol. E82-D, No. 1, Jan. 1999, pp. 64-75, (Abstract only -1pp.).
IBM Research Disclosure, “Implement IDAP Search Queries with SQL”, Document No. 41695, Dec. 1998, pp. 1663-1665.

Affiliated with

Also associated with

Rating

Method of optimally determining lossless joins does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of optimally determining lossless joins, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of optimally determining lossless joins will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3090168