Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2002-08-09
2004-12-28
Rones, Charles (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C706S051000
Reexamination Certificate
active
06836770
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to computer-implemented methods and in particular to a computer-implemented method for the transformation of SQL queries.
BACKGROUND OF THE INVENTION
The SQL (Structured Query Language) language provides mechanisms for users to define queries to a database. Because of its richness and the number of available implementations, SQL has become a widely used language. A standard definition of the SQL database query language is the ISO 90975 standard. SQL as defined in ISO 90975 and in the SQL3 standard supports 3-valued logic: all truth values in the language may be TRUE, FALSE or UNKNOWN. This means that values can be NULL (meaning unknown or unspecified) and use of these NULL values in predicates results in UNKNOWN truth values. The ISO 90975 standard is defined such that compliant database systems accept these NULL data values and UNKNOWN truth values and work consistently and correctly with them.
However, computers, at their hardware level and most common programming languages, work exclusively with exactly two Boolean truth values: TRUE and FALSE. Hence for a computer system that implements the SQL language to process an SQL query which is expressed in 3-valued logic, that system must be designed to carry out a simulation of the 3-valued logic to provide for all the logical operations that are possible in this SQL standard. This is typically costly in terms of execution time and the simulation itself is also error prone.
Further, the SQL language also allows the incorporation of subqueries in a query. A subquery is similar to a complete query in that it is evaluated completely every time that the expression in which it appears is evaluated. This provides the SQL language with the ability to express complex iterations over the tables in the database. On the other hand, it is inefficient to evaluate a subquery every time that an expression is evaluated. As a result, it is advantageous for query processing to include optimizations that may be carried out to make such sub-query evaluations more efficient.
It is therefore desirable to provide a computer-implemented method for transforming SQL queries such that the queries may be executed using 2-valued logic and such that the need for the evaluation of sub-queries on SQL query execution is reduced.
SUMMARY OF THE INVENTION
According to an aspect of the invention, an improved computer-implemented method of SQL query transformation is provided.
According to another aspect of the invention, a computer-implemented method is provided which uses replacement rules to transform the WHERE clause in an SQL query expressed in 3-valued logic into an equivalent query in 2-valued logic. According to another aspect of the invention, the above computer-implemented method further includes transformation rules for removing, or transforming into MINUS (set difference) operations, subqueries in the SQL query.
According to another aspect of the invention there is provided a computer-implemented method for the transformation of an SQL query including a WHERE clause having nested SELECT expressions, the method including the following steps:
iteratively transforming the nested SELECT expressions in the WHERE clause of the SQL query into a corresponding and logically equivalent first step expression whereby the first step expression is defined to include ThereExists expressions and associated truth-value expressions,
generating a truth expression having the form “(search_condition) IS TRUE” where the first step expression derived from the WHERE clause defines “search_condition” in the truth expression;
transforming the truth expression by iteratively applying a set of 3-valued to 2-valued logic rules to push the IS operator to the bottom of a truth expression tree corresponding to the truth expression and to replace the resulting IS operator expressions with logically equivalent expressions such that a second step expression is defined to be logically equivalent to the truth expression and to be expressed in 2-valued logic; and
transforming the second step expression by iteratively applying a set of NOT removal rules to push any NOT expressions to the bottom of a second step expression tree corresponding to the second step expression, to remove the NOT expressions and to remove the ThereExists expressions,
whereby the WHERE clause is transformed to an expression in 2-valued logic in which nested SELECT expressions are simplified.
According to another aspect of the invention there is provided a computer-implemented method for the transformation of an SQL query including a WHERE clause having nested SELECT expressions, the method including the following steps:
iteratively transforming the nested SELECT expressions in the WHERE clause of the SQL query into a corresponding and logically equivalent first step expression whereby the first step expression is defined to include ThereExists expressions and associated truth-value expressions; and
transforming the first step expression by iteratively applying a set of NOT removal rules to push any NOT expressions to the bottom of the first step expression tree corresponding to the first step expression, to remove the NOT expressions and to remove the ThereExists expressions,
whereby the WHERE clause is transformed to an expression in which nested SELECT expressions are simplified.
According to another aspect of the invention there is provided a computer-implemented method for the transformation of an SQL query including a WHERE clause including a condition expression, the method including the following steps:
generating a truth expression having the form “(search_condition) IS TRUE” where the WHERE clause condition expression defines “search_condition” in the truth expression; and
transforming the truth expression by iteratively applying a set of 3-valued to 2-valued logic rules to push the IS operator to the bottom of a truth expression tree corresponding to the truth expression and to replace the resulting IS operator expressions with logically equivalent expressions such that a second step expression is defined to be logically equivalent to the truth expression and to be expressed in 2-valued logic, whereby the WHERE clause is transformed to an expression in 2-valued logic.
According to another aspect of the invention there is provided a computer program product including a computer usable medium tangibly embodying computer readable program code means for transforming an SQL query, the computer readable program code means comprising code means for carrying out the steps of the above methods.
Advantages of the invention include a simplification of subquery evaluation and the representation of SQL queries in 2-valued logic.
REFERENCES:
patent: 5724570 (1998-03-01), Zeller et al.
patent: 5822747 (1998-10-01), Graefe et al.
patent: 5822750 (1998-10-01), Jou et al.
patent: 5978789 (1999-11-01), Griffin et al.
patent: 2002/0123984 (2002-09-01), Prakash
Joint Technology Corporation
Rones Charles
LandOfFree
Method for transforming SQL queries 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 for transforming SQL queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for transforming SQL queries will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3274171