Left outer join elimination on key

Details Left outer join elimination on key Left outer join elimination on key

2001-06-21

2004-04-13

Mizrahi, Diane D. (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06721730

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 that include left outer joins.
2. Description of Related Art
Since its introduction, XML, the eXtended Markup Language, has quickly emerged as a universal format for publishing and exchanging data over the World Wide Web. However, problems still exist in publishing data from relational databases as XML documents.
In the business-to-business e-commerce area, there is a widely recognized need to create XML documents by combining one or more relational tables, e.g., by creating an XML purchase order by joining a customer with information drawn from other tables. A relational join is a well-known operation that combines information from two base tables by creating pairs of matching rows.
Inner joins discard rows without any matches, while outer joins preserve all information from one or both of its arguments. Outer joins can be further categorized into left, right (single-sided), or full (two-sided) outerjoin, depending on which side needs to be preserved.
Outer joins are especially useful for exporting data from relational databases to XML documents. However, there are performance costs associated with performing such outer joins. Thus, there is a need in the art for improved techniques of performing outer joins, and especially for optimization methods for outer joins.
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 left outer join queries. A determination is made whether any column from a right quantifier of a left outer join query is projected out of the query. If not, then all predicates in an ON clause are removed from the left outer join query, the right quantifier is removed from the left outer join query, and the left outer join query is converted to a simple select query.
A number of steps are performed to determine whether any of the columns quantified by the right quantifier participate in a projection list of the query. A set of equivalence class columns is computed for the query, wherein the equivalence classes are derived from equi-join predicates in the query. A set of columns quantified by the right quantifier across the computed set of equivalence classes is computed. A determination is made whether a subset of the set of columns form a key for the right quantifier. If the right quantifier columns are not projected out of the query, then the optimization may be performed.


REFERENCES:
patent: 5412804 (1995-05-01), Krishna
patent: 5701454 (1997-12-01), Bhargava et al.
patent: 5774692 (1998-06-01), Boyer et al.
patent: 5797136 (1998-08-01), Boyer et al.
patent: 5822750 (1998-10-01), Jou et al.
patent: 5864847 (1999-01-01), Goel et al.
patent: 5875447 (1999-02-01), Goel et al.
patent: 5890148 (1999-03-01), Bhargava et al.
patent: 5960427 (1999-09-01), Goel et al.
patent: 5963933 (1999-10-01), Cheng et al.
patent: 6088691 (2000-07-01), Bhargava et al.
patent: 6253197 (2001-06-01), Lindsay et al.
patent: 6385603 (2002-05-01), Chen et al.
M.M. David, 1999, “SQL-Based XML Structured Data Access,” Web Techniques, pp. 6 and 6 figures.

Affiliated with

Also associated with

Rating

Left outer join elimination on key does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Left outer join elimination on key, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Left outer join elimination on key will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3223101