Systems and methods for transforming SQL syntax trees into relational algebra representations

• US 20050177556A1
• Filed: 02/10/2004
• Published: 08/11/2005
• Est. Priority Date: 02/10/2004
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Fang, Jun, Zabokritski, Evgueni, Zhang, Honggang, Carlin, Peter, Kambuj, Aakash
• Application Number:
  US10/776,895
• Publication Number:
  US 20050177556A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24526 Internal representations for queries

Abstract

The SQL Algebrizer of the present invention comprises a plurality of algorithms to “algebrize” SQL Trees to QP Algebra using an approach that is more consistent and much more efficient than typical algebrizers. More specifically, the Algebrizer of the present invention processes a SQL Tree using a reduced number of recursive depth-first passes by performing multiple operations in a single pass. Furthermore, the Algebrizer of the present invention also performs the operation of constant folding in this single, multi-operation pass so that the QP, upon receiving the QP Algebra, needs not perform this operation at all.

Claims

1. A method for algebrizing a syntax tree representation of a relational database query into a relational algebra representation, said syntax tree comprising a plurality of nodes, and said algebrizing comprising a plurality of operations each of which can be performed in a single pass through said syntax tree representation, said method comprising the step of performing at least two operations in a single pass through said syntax tree representation.

2. The method of claim 1 wherein said at least two operations are executed in a predetermined order at each of said plurality of nodes.

3. The method of claim 2 wherein

said at least two operations comprise a first operation and a second operation;

and

said second operation either executes or does not execute at each of said plurality of nodes and after said first operation based on a result from said first operation.

4. The method of claim 1 wherein said at least two operations comprises at least one operation from among a group of operations, said group of operations comprising:

table and column binding;

aggregate binding;

type derivation;

constant folding;

property derivation; and

tree translation.

5. The method of claim 1 wherein said at least two operations comprises at least all operations from among a group of operations, said group of operations comprising:

table and column binding;

aggregate binding;

type derivation;

property derivation; and

tree translation.

6. The method of claim 5 wherein said group of operations further comprises constant folding.

7. The method of claim 1 wherein said algebrizing comprises at least one operation from among a group of operations, said group of operations comprising:

table and column binding;

aggregate binding;

type derivation;

constant folding;

property derivation; and

tree translation.

8. The method of claim 7 wherein said group of operations further comprises constant folding.

9. The method of claim 1 wherein said algebrizing comprises constant folding.

22. The computer-readable instructions of claim 1 further comprising instructions for at least two operations to be executed in a predetermined order at each of said plurality of nodes.

23. The computer-readable instructions of claim 2 further comprising instructions for

at least two operations to comprise a first operation and a second operation;

and

executing or not executing said second operation at each of said plurality of nodes after said first operation has executed based on a result from said first operation.

24. The computer-readable instructions of claim 1 further comprising instructions whereby said at least two operations comprise at least one operation from among a group of operations, said group of operations comprising:

table and column binding;

aggregate binding;

type derivation;

constant folding;

property derivation; and

tree translation.

25. The computer-readable instructions of claim 1 further comprising instructions whereby said at least two operations comprises at least all operations from among a group of operations, said group of operations comprising:

table and column binding;

aggregate binding;

type derivation;

property derivation; and

tree translation.

26. The computer-readable instructions of claim 5 further comprising instructions whereby said group of operations further comprises constant folding.

27. The computer-readable instructions of claim 1 further comprising instructions whereby said algebrizing comprises at least one operation from among a group of operations, said group of operations comprising:

table and column binding;

aggregate binding;

type derivation;

constant folding;

property derivation; and

tree translation.

28. The computer-readable instructions of claim 7 further comprising instructions whereby said group of operations further comprises constant folding.

29. The computer-readable instructions of claim 1 further comprising instructions whereby said algebrizing comprises constant folding.

10. A method for algebrizing a syntax tree representation of a relational database query into a relational algebra representation, said syntax tree comprising a plurality of nodes, and said algebrizing comprising a plurality of operations, said method comprising the inclusion of constant folding as an operation among said plurality of operations.

11. A system for algebrizing a syntax tree representation of a relational database query into a relational algebra representation, said syntax tree comprising a plurality of nodes, said system comprising:

a plurality of operations; and

a subsystem for performing at least two operations in a single pass through said syntax tree representation.

12. The system of claim 11 wherein said system executes at least two operations in a predetermined order at each of said plurality of nodes during said single pass through said syntax tree representation.

13. The system of claim 12 wherein

said at least two operations comprise a first operation and a second operation;

said subsystem executes said first operation before said second operation at each of said plurality of nodes, and receives a result from said first operation at each of said plurality of nodes; and

said subsystem either executes or does not execute said second operation at each of said plurality of nodes, on a node by node basis, based on a result from said first operation.

14. The system of claim 11 wherein said at least two operations comprises at least one operation from among a group of operations, said group of operations comprising:

table and column binding;

aggregate binding;

type derivation;

constant folding;

property derivation; and

tree translation.

15. The system of claim 11 wherein said at least two operations comprises at least all operations from among a group of operations, said group of operations comprising:

table and column binding;

aggregate binding;

type derivation;

property derivation; and

tree translation.

16. The system of claim 15 wherein said group of operations further comprises constant folding.

17. The system of claim 11 wherein said algebrizing comprises at least one operation from among a group of operations, said group of operations comprising:

table and column binding;

aggregate binding;

type derivation;

constant folding;

property derivation; and

tree translation.

18. The system of claim 17 wherein said group of operations further comprises constant folding.

19. The system of claim 11 wherein said algebrizing comprises constant folding.

20. A system for algebrizing a syntax tree representation of a relational database query into a relational algebra representation, said syntax tree comprising a plurality of nodes, said system comprising:

a plurality of operations; and

constant folding as an operation among said plurality of operations.

21. A computer-readable medium comprising computer-readable instructions for algebrizing a syntax tree representation of a relational database query into a relational algebra representation, said syntax tree comprising a plurality of nodes, and said algebrizing comprising a plurality of operations each of which can be performed in a single pass through said syntax tree representation, said computer-readable instructions comprising instructions for performing at least two operations in a single pass through said syntax tree representation.

30. A computer-readable medium comprising computer-readable instructions for algebrizing a syntax tree representation of a relational database query into a relational algebra representation, said syntax tree comprising a plurality of nodes, and said algebrizing comprising a plurality of operations, said computer-readable instructions comprising instructions for constant folding as an operation among said plurality of operations.