Patent US5732258A successfully refreshed from Google Patents.
US5732258A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for efficiently evaluating exists and not exists equivalent subqueries
Assignee: Oracle International Corp
•
Filing: 1996-02-08
•
Granted: 1998-03-24
•
Expires: 2016-02-08
Abstract
Abstract A method for transforming database queries that have EXISTS-equivalent subqueries (i.e. subqueries that are semantically equivalent to EXISTS or NOT EXISTS subqueries) is disclosed. Logical expressions are removed from a WHERE CLAUSE in the original EXISTS-equivalent subquery to produce a revised subquery. For each of the logical expressions that are removed, a substitute query component is generated based on whether (1) the logical expression contains any reference to any table in a FROM-list in the EXISTS-equivalent subquery and (2) the original EXISTS-equivalent subquery is equivalent to an EXISTS or a NOT EXISTS subquery. The transformed query is created by replacing the original EXISTS-equivalent subquery with the revised subquery and the query components that were generated for each of removed logical expressions. Some of the substitute query components, including the revised subquery, may be merged based on knowledge of access paths. These transformation techniques may be applied after converting the EXISTS-equivalent subquery to an EXISTS or NOT EXISTS subquery. Alternatively, the techniques may be applied directly to queries that contain EXISTS-equivalent subqueries without converting the EXISTS-equivalent subqueries to EXISTS or NOT EXISTS subqueries. The transformed queries produced by this technique may be processed more efficiently by database applications than the original queries.
Inventors
- 👤 Hakan Jakobsson
- 👤 Atif Chaudhry
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 14:06
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24535; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99935; Y10S707/99936
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
171 words
A computer-implemented method of transforming an EXISTS-equivalent subquery to query components that may be processed more efficiently than the EXISTS-equivalent subquery, the method comprising the steps of: A) removing at least one logical expression from a WHERE clause in said EXISTS-equivalent subquery to produce a revised EXISTS-equivalent subquery; B) generating one or more substitute query components by performing the following steps for each of said at least one logical expression removed from said WHERE clause: B1) determining whether said logical expression contains a reference to a table in a FROM list of a SELECT statement in said EXISTS-equivalent subquery, B2) determining a substitute query component for said logical expression based on a) whether said logical expression contains a reference to a table in said FROM list of said SELECT statement in said EXISTS-equivalent subquery, and b) whether said EXISTS-equivalent subquery is equivalent to an EXISTS subquery or to a NOT EXISTS subquery; and C) replacing the EXISTS-equivalent subquery with said revised EXISTS-equivalent subquery and said one or more substitute query components.
Claim 2
Dependent Claim
171 words
A computer-implemented method of transforming an EXISTS-equivalent subquery to query components that may be processed more efficiently than the EXISTS-equivalent subquery, the method comprising the steps of: A) removing at least one logical expression from a WHERE clause in said EXISTS-equivalent subquery to produce a revised EXISTS-equivalent subquery; B) generating one or more substitute query components by performing the following steps for each of said at least one logical expression removed from said WHERE clause: B1) determining whether said logical expression contains a reference to a table in a FROM list of a SELECT statement in said EXISTS-equivalent subquery, B2) determining a substitute query component for said logical expression based on a) whether said logical expression contains a reference to a table in said FROM list of said SELECT statement in said EXISTS-equivalent subquery, and b) whether said EXISTS-equivalent subquery is equivalent to an EXISTS subquery or to a NOT EXISTS subquery; and C) replacing the EXISTS-equivalent subquery with said revised EXISTS-equivalent subquery and said one or more substitute query components.
Claim 3
Dependent Claim
103 words
The method of claim 1 further comprising the steps of: determining whether said EXISTS-equivalent subquery is equivalent to an EXISTS subquery or to a NOT EXISTS subquery; if said EXISTS-equivalent query is equivalent to an EXISTS subquery, then combining said revised EXISTS-equivalent query and said one or more substitute queries with a disjunctive operator to create an expression semantically equivalent to said EXISTS-equivalent subquery; and if said EXISTS-equivalent query is equivalent to a NOT EXISTS subquery, then combining said revised EXISTS-equivalent query and said one or more substitute queries with a conjunctive operator to create an expression semantically equivalent to said EXISTS-equivalent subquery.
Claim 4
Dependent Claim
49 words
The method of claim 1 further comprising the step of merging said revised EXISTS-equivalent query and said one or more substitute query components based upon access paths used by a database application to identify data satisfied by said revised EXISTS-equivalent query and said one or more substitute query components.
Claim 5
Dependent Claim
170 words
The method of claim 1 wherein said step of determining a substitute query component for said logical expression comprises: if said logical expression contains a reference to a table in said FROM list of said SELECT statement in said EXISTS-equivalent subquery, then establishing as said substitute query component a new subquery that has a SELECT statement identical to said SELECT statement in said EXISTS-equivalent subquery, and which has a WHERE clause that consists of said logical expression; if said logical expression does not contain a reference to a table in said FROM list of said SELECT statement in said EXISTS-equivalent subquery and said EXISTS-equivalent subquery is equivalent to an EXISTS subquery, then establishing as said substitute query component said logical expression; and if said logical expression does not contain a reference to a table in said FROM list of said SELECT statement in said EXISTS-equivalent subquery and said EXISTS-equivalent subquery is equivalent to a NOT EXISTS subquery, then establishing as said substitute query component a negative of said logical expression.
Claim 6
Dependent Claim
93 words
The method of claim 1 wherein said EXISTS-equivalent subquery is not an EXISTS subquery nor a NOT EXISTS subquery, the method further comprising the steps of: if said EXISTS-equivalent subquery is semantically equivalent to an EXISTS subquery, then transforming said EXISTS-equivalent subquery into an EXISTS subquery prior to performing the step of removing at least one logical expression; and if said EXISTS-equivalent subquery is semantically equivalent to a NOT EXISTS subquery, then transforming said EXISTS-equivalent subquery into a NOT EXISTS subquery prior to performing the step of removing at least one logical expression.
Claim 7
Dependent Claim
14 words
The method of claim 1 wherein said EXISTS-equivalent subquery is a NOT IN subquery.
Claim 8
Dependent Claim
173 words
A computer-readable medium having stored thereon sequences of instructions, said sequences of instructions including instructions which, when executed by a processor, cause said processor to perform the steps of: A) removing at least one logical expression from a WHERE clause in an EXISTS-equivalent subquery to produce a revised EXISTS-equivalent subquery; B) generating one or more substitute query components by performing the following steps for each of said at least one logical expression removed from said WHERE clause: B1) determining whether said logical expression contains a reference to a table in a FROM list of a SELECT statement in said EXISTS-equivalent subquery, B2) determining a substitute query component for said logical expression based on a) whether said logical expression contains a reference to a table in said FROM list of said SELECT statement in said EXISTS-equivalent subquery, and b) whether said EXISTS-equivalent subquery is equivalent to an EXISTS subquery or to a NOT EXISTS subquery; and C) replacing the EXISTS-equivalent subquery with said revised EXISTS-equivalent subquery and said one or more substitute query components.
Claim 9
Dependent Claim
173 words
A computer-readable medium having stored thereon sequences of instructions, said sequences of instructions including instructions which, when executed by a processor, cause said processor to perform the steps of: A) removing at least one logical expression from a WHERE clause in an EXISTS-equivalent subquery to produce a revised EXISTS-equivalent subquery; B) generating one or more substitute query components by performing the following steps for each of said at least one logical expression removed from said WHERE clause: B1) determining whether said logical expression contains a reference to a table in a FROM list of a SELECT statement in said EXISTS-equivalent subquery, B2) determining a substitute query component for said logical expression based on a) whether said logical expression contains a reference to a table in said FROM list of said SELECT statement in said EXISTS-equivalent subquery, and b) whether said EXISTS-equivalent subquery is equivalent to an EXISTS subquery or to a NOT EXISTS subquery; and C) replacing the EXISTS-equivalent subquery with said revised EXISTS-equivalent subquery and said one or more substitute query components.
Claim 10
Dependent Claim
117 words
The computer-readable medium of claim 7 further containing instructions which, when executed by said processor, would cause said processor to perform the steps of: determining whether said EXISTS-equivalent subquery is equivalent to an EXISTS subquery or to a NOT EXISTS subquery; if said EXISTS-equivalent query is equivalent to an EXISTS subquery, then combining said revised EXISTS-equivalent query and said one or more substitute queries with a disjunctive operator to create an expression semantically equivalent to said EXISTS-equivalent subquery; and if said EXISTS-equivalent query is equivalent to a NOT EXISTS subquery, then combining said revised EXISTS-equivalent query and said one or more substitute queries with a conjunctive operator to create an expression semantically equivalent to said EXISTS-equivalent subquery.
Claim 11
Dependent Claim
63 words
The computer-readable medium of claim 7 further containing instructions which, when executed by said processor, would cause said processor to perform the steps of: merging said revised EXISTS-equivalent query and said one or more substitute query components based upon access paths used by a database application to identify data satisfied by said revised EXISTS-equivalent query and said one or more substitute query components.
Claim 12
Dependent Claim
171 words
The computer-readable medium of claim 7 wherein said step of determining a substitute query component for said logical expression comprises: if said logical expression contains a reference to a table in said FROM list of said SELECT statement in said EXISTS-equivalent subquery, then establishing as said substitute query component a new subquery that has a SELECT statement identical to said SELECT statement in said EXISTS-equivalent subquery, and which has a WHERE clause that consists of said logical expression; if said logical expression does not contain a reference to a table in said FROM list of said SELECT statement in said EXISTS-equivalent subquery and said EXISTS-equivalent subquery is equivalent to an EXISTS subquery, then establishing as said substitute query component said logical expression; and if said logical expression does not contain a reference to a table in said FROM list of said SELECT statement in said EXISTS-equivalent subquery and said EXISTS-equivalent subquery is equivalent to a NOT EXISTS subquery, then establishing as said substitute query component a negative of said logical expression.
Claim 13
Dependent Claim
108 words
The computer-readable medium of claim 7 wherein said EXISTS-equivalent subquery is not an EXISTS subquery nor a NOT EXISTS subquery, the computer-readable medium further containing instructions which, when executed by said processor, would cause said processor to perform the steps of: if said EXISTS-equivalent subquery is semantically equivalent to an EXISTS subquery, then transforming said EXISTS-equivalent subquery into an EXISTS subquery prior to performing the step of removing at least one logical expression; and if said EXISTS-equivalent subquery is semantically equivalent to a NOT EXISTS subquery, then transforming said EXISTS-equivalent subquery into a NOT EXISTS subquery prior to performing the step of removing at least one logical expression.
Claim 14
Dependent Claim
81 words
A computer-implemented method of transforming an EXISTS-equivalent subquery to query components that may be processed more efficiently than the EXISTS-equivalent subquery, the method comprising the steps of: A) removing at least one logical expression from a clause in said EXISTS-equivalent subquery to produce a revised EXISTS-equivalent subquery; B) determining one or more substitute query components for said at least one logical expression; and C) replacing the EXISTS-equivalent subquery with said revised EXISTS-equivalent subquery and said one or more substitute query components.
Claim 15
Dependent Claim
81 words
A computer-implemented method of transforming an EXISTS-equivalent subquery to query components that may be processed more efficiently than the EXISTS-equivalent subquery, the method comprising the steps of: A) removing at least one logical expression from a clause in said EXISTS-equivalent subquery to produce a revised EXISTS-equivalent subquery; B) determining one or more substitute query components for said at least one logical expression; and C) replacing the EXISTS-equivalent subquery with said revised EXISTS-equivalent subquery and said one or more substitute query components.
Claim 16
Dependent Claim
29 words
The method of claim 12 wherein said step of removing at least one logical expression from a clause includes removing at least one logical expression from a WHERE clause.
Claim 17
Dependent Claim
30 words
The method of claim 12 wherein the one or more substitute query components are determined based on whether said at least one logical expression contains a particular type of reference.
Claim 18
Dependent Claim
70 words
The method of claim 14 wherein: the method further comprises the step of determining whether said logical expression contains a reference to a table in a FROM list of a SELECT statement in said EXISTS-equivalent subquery; and the one or more substitute query components are determined based on whether said logical expression contains a reference to a table in a FROM list of a SELECT statement in said EXISTS-equivalent subquery.
Claim 19
Dependent Claim
33 words
The method of claim 12 wherein the one or more substitute query components are determined based on whether said EXISTS-equivalent subquery is equivalent to an EXISTS subquery or to a NOT EXISTS subquery.
Claim 20
Dependent Claim
31 words
The method of claim 16 wherein the one or more substitute query components are also determined based on whether said at least one logical expression contains a particular type of reference.
Claim 21
Dependent Claim
70 words
The method of claim 17 wherein: the method further comprises the step of determining whether said logical expression contains a reference to a table in a FROM list of a SELECT statement in said EXISTS-equivalent subquery; and the one or more substitute query components are determined based on whether said logical expression contains a reference to a table in a FROM list of a SELECT statement in said EXISTS-equivalent subquery.
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-23 | 2001-09-22 | 2002-03-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-03-23 | 2005-09-22 | 2006-03-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-03-23 | 2009-09-22 | 2010-03-24 | $7700.00 | Window Closed / Lapsed |