US5724568A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Reordering complex SQL queries containing inner and outer join operations using hypergraphs and required sets
Assignee: International Business Machines Corp
•
Filing: 1995-06-05
•
Granted: 1998-03-03
•
Expires: 2015-06-05
Abstract
Abstract A method and apparatus for reordering complex SQL queries containing joins, outer and full outer joins. The method and apparatus first translates the query into a hypergraph representation. Required sets, conflict sets and preserved sets are then generated for the query hypergraph. Using the required sets, a plurality of plans are enumerated, wherein the plans represent associative reorderings of relations in the query. SQL operators are selectively assigned to each of the enumerated plans using the conflict sets and/or preserved sets, so that the results from the plans are identical to the original query. A novel Modified General Outer Join (MGOJ) operator may be assigned to the root of a sub-tree, wherein the MGOJ operator is a compensation operator. The operator assignment is performed recursively for the root of each sub-tree in the plan. One of the enumerated plans (generally the most optimal) is then selected for execution.
Inventors
- 👤 Gautam Bhargava
- 👤 Piyush Goel
- 👤 Balakrishna Ragmavendra Iyer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 21:18
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24542; G06F16/24544; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
168 words
A method of representing an SQL query in a memory of a computer, comprising the steps of: (a) generating a set of nodes in the memory of the computer corresponding to relations referenced in the query; (b) generating an edge between two of the nodes in the memory of the computer corresponding to a first operation involving a predicate between the two nodes wherein the first operation comprises a join operation; (c) generating one or more hyperedges between two of the nodes in the memory of the computer corresponding to a second operation involving a predicate that references a plurality of relations in the query, wherein the second operation is selected from a group comprising a left outer join, a right outer join, or a full outer join operation; and (d) enumerating all required sets that identify constraints on associative re-orderings of the relations in the query using the generated hyperedges, wherein the required sets are generated only for left, right, and full outer joins in the query.
Claim 2
Independent Claim
168 words
A method of representing an SQL query in a memory of a computer, comprising the steps of: (a) generating a set of nodes in the memory of the computer corresponding to relations referenced in the query; (b) generating an edge between two of the nodes in the memory of the computer corresponding to a first operation involving a predicate between the two nodes wherein the first operation comprises a join operation; (c) generating one or more hyperedges between two of the nodes in the memory of the computer corresponding to a second operation involving a predicate that references a plurality of relations in the query, wherein the second operation is selected from a group comprising a left outer join, a right outer join, or a full outer join operation; and (d) enumerating all required sets that identify constraints on associative re-orderings of the relations in the query using the generated hyperedges, wherein the required sets are generated only for left, right, and full outer joins in the query.
Claim 3
Dependent Claim
18 words
The method of claim 1, wherein the nodes, edges, and hyperedges comprise a hypergraph representation of the query.
Claim 4
Dependent Claim
29 words
The method of claim 1, further comprising generating a path from a first node to a second node, wherein the path comprises an alternating sequence of nodes and edges.
Claim 5
Dependent Claim
21 words
The method of claim 1, wherein the edge is directed when it represents a one-sided outer join operation in the query.
Claim 6
Dependent Claim
21 words
The method of claim 1, wherein the edge is bi-directed when it represents a full outer join operation in the query.
Claim 7
Dependent Claim
21 words
The method of claim 1, wherein the hyperedge is directed when it represents a one-sided outer join operation in the query.
Claim 8
Dependent Claim
21 words
The method of claim 1, wherein the hyperedge is bi-directed when it represents a full outer join operation in the query.
Claim 9
Dependent Claim
175 words
A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for representing an SQL query, the method comprising the steps of: (a) generating a set of nodes in the computer corresponding to relations referenced in the query; (b) generating an edge between two of the nodes in the computer corresponding to a first operation involving a predicate between the two nodes wherein the first operation comprises a join operation; (c) generating one or more hyperedges between two of the nodes in the computer corresponding to a second operation involving a predicate that references a plurality of relations in the query, wherein the second operation is selected from a group comprising a left outer join, a right outer join, or a full outer join operation; and (d) enumerating all required sets that identify constraints on associative re-orderings of the relations in the query using the generated hyperedges, wherein the required sets are generated only for left, right, and full outer joins in the query.
Claim 10
Dependent Claim
175 words
A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for representing an SQL query, the method comprising the steps of: (a) generating a set of nodes in the computer corresponding to relations referenced in the query; (b) generating an edge between two of the nodes in the computer corresponding to a first operation involving a predicate between the two nodes wherein the first operation comprises a join operation; (c) generating one or more hyperedges between two of the nodes in the computer corresponding to a second operation involving a predicate that references a plurality of relations in the query, wherein the second operation is selected from a group comprising a left outer join, a right outer join, or a full outer join operation; and (d) enumerating all required sets that identify constraints on associative re-orderings of the relations in the query using the generated hyperedges, wherein the required sets are generated only for left, right, and full outer joins in the query.
Claim 11
Dependent Claim
20 words
The program storage device of claim 8, wherein the nodes, edges, and hyperedges comprise a hypergraph representation of the query.
Claim 12
Dependent Claim
31 words
The program storage device of claim 8, further comprising generating a path from a first node to a second node, wherein the path comprises an alternating sequence of nodes and edges.
Claim 13
Dependent Claim
23 words
The program storage device of claim 8, wherein the edge is directed when it represents a one-sided outer join operation in the query.
Claim 14
Dependent Claim
23 words
The program storage device of claim 8, wherein the edge is bi-directed when it represents a full outer join operation in the query.
Claim 15
Dependent Claim
23 words
The program storage device of claim 8, wherein the hyperedge is directed when it represents a one-sided outer join operation in the query.
Claim 16
Dependent Claim
23 words
The program storage device of claim 8, wherein the hyperedge is bi-directed when it represents a full outer join operation in the query.
Claim 17
Independent Claim
201 words
An apparatus for representing an SQL query, comprising: a computer having a memory, wherein the SQL query is used by the computer to direct information retrieval from a relational database stored in an electronic storage device in communication with the computer, the computer further comprising: means for generating a set of nodes in the memory of the computer corresponding to relations referenced in the query; means for generating an edge between two of the nodes in the memory of the computer corresponding to a first operation involving a predicate between the two nodes wherein the first operation comprises a join operation; and means for generating one or more hyperedges between two of the nodes in the memory of the computer corresponding to a second operation involving a predicate that references a plurality of relations in the query, wherein the second operation is selected from a group comprising a left outer join, a right outer join, or a full outer join operation; and means for enumerating all required sets that identify constraints on associative re-orderings of the relations in the query using the generated hyperedges, wherein the required sets are generated only for left, right, and full outer joins in the query.
Claim 18
Independent Claim
201 words
An apparatus for representing an SQL query, comprising: a computer having a memory, wherein the SQL query is used by the computer to direct information retrieval from a relational database stored in an electronic storage device in communication with the computer, the computer further comprising: means for generating a set of nodes in the memory of the computer corresponding to relations referenced in the query; means for generating an edge between two of the nodes in the memory of the computer corresponding to a first operation involving a predicate between the two nodes wherein the first operation comprises a join operation; and means for generating one or more hyperedges between two of the nodes in the memory of the computer corresponding to a second operation involving a predicate that references a plurality of relations in the query, wherein the second operation is selected from a group comprising a left outer join, a right outer join, or a full outer join operation; and means for enumerating all required sets that identify constraints on associative re-orderings of the relations in the query using the generated hyperedges, wherein the required sets are generated only for left, right, and full outer joins in the query.
Claim 19
Dependent Claim
18 words
The apparatus of claim 15, wherein the nodes, edges, and hyperedges comprise a hypergraph representation of the query.
Claim 20
Dependent Claim
31 words
The apparatus of claim 15, further comprising means for generating a path from a first node to a second node, wherein the path comprises an alternating sequence of nodes and edges.
Claim 21
Dependent Claim
21 words
The apparatus of claim 15, wherein the edge is directed when it represents a one-sided outer join operation in the query.
Claim 22
Dependent Claim
21 words
The apparatus of claim 15, wherein the edge is bi-directed when it represents a full outer join operation in the query.
Claim 23
Dependent Claim
21 words
The apparatus of claim 15, wherein the hyperedge is directed when it represents a one-sided outer join operation in the query.
Claim 24
Dependent Claim
21 words
The apparatus of claim 15, wherein the hyperedge is bi-directed when it represents a full outer join operation in the query.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-03-02 | 2001-09-01 | 2002-03-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-03-02 | 2005-09-01 | 2006-03-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-03-02 | 2009-09-01 | 2010-03-03 | $7700.00 | Window Closed / Lapsed |