Method for transforming SQL queries

• US 20040030679A1
• Filed: 08/09/2002
• Published: 02/12/2004
• Est. Priority Date: 08/09/2002
• Status: Active Grant

• Current Assignee: Progress Software Corporation
• Original Assignee: Joint Technology Corporation
• Inventors: Gonnet, Gaston Henry
• Granted Patent: US 6,836,770 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A computer-implemented method for transforming an SQL query comprising a WHERE clause having nested SELECT expressions. The expression in the WHERE clause being transformed by the iterative application of rules to comprise ThereExists expressions and associated truth-value expressions. Further transforming the expression to form a truth expression having the IS operator and iteratively applying further rules to translate 3-valued logic to 2-valued logic. Carrying out a further transformation to remove NOT expressions from the expression and to remove any ThereExists expressions so as to define an expression in 2-valued logic with simplified SELECT expressions.

Claims

1. A computer-implemented method for the transformation of an SQL query comprising a WHERE clause having nested SELECT expressions, the method comprising the following steps:

a) 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 comprise ThereExists expressions and associated truth-value expressions,

b) 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;

c) 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

d) 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.

2. The computer-implemented method of claim 1 in which the ThereExists expressions comprise a ThereExists function having the following properties:

3. The computer-implemented method of claim 1 in which the step of iteratively transforming the nested SELECT expressions in the WHERE clause of the SQL query comprises the step of applying the following transformation rules:

4. The computer-implemented method of claim 3 in which the ThereExists expressions comprise a ThereExists function having the following properties:

5. The computer-implemented method of claim 1 in which the step of transforming the truth expression by iteratively applying a set of 3-valued to 2-valued logic rules comprises the step of applying the following transformation rules:

6. The computer-implemented method of claim 3 in which the step of transforming the truth expression by iteratively applying a set of 3-valued to 2-valued logic rules comprises the step of applying the following transformation rules:

7. The computer-implemented method of claim 5 in which the ThereExists expressions comprise a ThereExists function having the following properties:

8. The computer-implemented method of claim 6 in which the ThereExists expressions comprise a ThereExists function having the following properties:

9. The computer-implemented method of claim 1 in which the step of transforming the second step expression by iteratively applying a set of NOT removal rules comprises the step of applying the following transformation rules:

10. The computer-implemented method of claim 3 in which the step of transforming the second step expression by iteratively applying a set of NOT removal rules comprises the step of applying the following transformation rules:

11. The computer-implemented method of claim 9 in which the ThereExists expressions comprise a ThereExists function having the following properties:

12. The computer-implemented method of claim 10 in which the ThereExists expressions comprise a ThereExists function having the following properties:

17. A computer program product comprising 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 method of claim 1.

18. A computer program product comprising 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 method of claim 2.

19. A computer program product comprising 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 method of claim 3.

20. A computer program product comprising 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 method of claim 4.

21. A computer program product comprising 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 method of claim 5.

22. A computer program product comprising 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 method of claim 6.

23. A computer program product comprising 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 method of claim 7.

24. A computer program product comprising 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 method of claim 8.

25. A computer program product comprising 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 method of claim 9.

26. A computer program product comprising 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 method of claim 10.

27. A computer program product comprising 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 method of claim 11.

28. A computer program product comprising 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 method of claim 12.

13. A computer-implemented method for the transformation of an SQL query comprising a WHERE clause having nested SELECT expressions, the method comprising the following steps:

a) 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 comprise ThereExists expressions and associated truth-value expressions; and

b) 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.

14. The computer-implemented method of claim 13 in which the ThereExists expressions comprise a ThereExists function having the following properties:

29. A computer program product comprising 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 method of claim 13.

30. A computer program product comprising 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 method of claim 14.

15. A computer-implemented method for the transformation of an SQL query comprising a WHERE clause comprising a condition expression, the method comprising the following steps:

a) 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

b) 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.

16. The computer-implemented method of claim 15 in which the set of 3-valued to 2-valued logic rules comprises the following rules:

31. A computer program product comprising 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 method of claim 15.

32. A computer program product comprising 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 method of claim 16.