Efficient evaluation of queries using translation

• US 20050289125A1
• Filed: 09/22/2004
• Published: 12/29/2005
• Est. Priority Date: 06/23/2004
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Manikutty, Anand, Arora, Vikas, Krishnaprasad, Muralidhar, Liu, Zhen Hua, Kotsovolos, Susan M., Warner, James, Zhang, Hui X.
• Granted Patent: US 7,516,121 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2448 for particular applications; for extensibility, e.g. user defined types
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 16/8358 Query translation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

Techniques are provided for processing a query including receiving the query, where the query specifies certain operations; determining that the query includes a first portion in a first query language and a second portion in a second query language; generating a first in-memory representation for the first portion; generating a second in-memory representation for the second portion; generating a third in-memory representation of the query based on the first in-memory representation and the second in-memory representation; and performing the certain operations based on the third in-memory representation.

Claims

1. A method of processing a query, comprising:

receiving the query, wherein the query specifies certain operations;

determining that the query comprises a first portion in a first query language and a second portion in a second query language;

generating a first in-memory representation for the first portion;

generating a second in-memory representation for the second portion;

generating a third in-memory representation of the query based on the first in-memory representation and the second in-memory representation; and

performing the certain operations based on the third in-memory representation.

2. The method of claim 1, wherein the first in-memory representation and the third in-memory representation are formatted in a first abstract syntax and the second in-memory representation is formatted in a second abstract syntax, and wherein the step of generating the third in-memory representation comprises:

generating a fourth in-memory representation in the first abstract syntax based on the second in-memory representation; and

generating the third in-memory representation based on the first in-memory representation and the fourth in-memory representation.

3. The method of claim 2, wherein the second in-memory representation comprises one or more in-memory representations of query elements in the second abstract syntax, and wherein generating the fourth in-memory representation comprises:

determining a second set of one or more equivalent in-memory representations of query elements in the first abstract syntax for the one or more in-memory representations of query elements in the second abstract syntax; and

generating the fourth in-memory representation in the first abstract syntax based on the second set of one or more equivalent in-memory representations of query elements in the first abstract syntax.

4. The method of claim 3, wherein each in-memory representation of query elements in the one or more in-memory representations of query elements in the second abstract syntax corresponds to one or more in-memory representation of query elements in the second set of one or more equivalent in-memory representations of query elements in the first abstract syntax.

5. The method of claim 1, wherein one or more of the first in-memory representation, the second in-memory representation, and the third in-memory representation are represented in memory as abstract syntax trees.

6. The method of claim 1, wherein the first query language is Structured Query Language.

7. The method of claim 1, where in the second query language is a markup query language.

8. The method of claim 1, wherein the second query language is XQuery.

9. The method of claim 1, wherein the second query language is XQueryX.

10. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XQuery aggregation in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL subquery in the first abstract syntax to compute the aggregation, said SQL subquery being generated based on the XQuery aggregation in the second abstract syntax.

11. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises a literal expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL literal in the first abstract syntax based on the literal expression in the second abstract syntax.

12. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XQuery cast expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating one of an SQL cast function and an SQL convert function in the first abstract syntax based on the XQuery cast expression in the second abstract syntax.

13. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises a set expressions in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating one of an SQL UNION, an SQL MINUS, and an SQL INTERSECT in the first abstract syntax based on the set expressions in the second abstract syntax.

14. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XQuery arithmetic expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL arithmetic expression in the first abstract syntax based on the XQuery arithmetic expression in the second abstract syntax.

15. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XQuery comparison in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL comparison in the first abstract syntax based on the XQuery comparison in the second abstract syntax.

16. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XQuery FLWOR order by clause in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL order by clause in the first abstract syntax based on the XQuery FLWOR order by clause in the second abstract syntax.

17. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XML logical expressions in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL logical expressions element in the first abstract syntax based on the XML logical expressions in the second abstract syntax.

18. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XML FLWOR expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL select expressions element in the first abstract syntax based on the XML FLWOR expression in the second abstract syntax.

19. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XML Path expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL path expression in the first abstract syntax based on the XML Path expression in the second abstract syntax.

20. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XML if-then-else expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL case-when expression in the first abstract syntax based on the XML if-then-else expression in the second abstract syntax.

21. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XML quantified expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL Exists expression in the first abstract syntax based on the XML quantified expression in the second abstract syntax.

22. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an SQL/XML construction expression in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL construction expression in the first abstract syntax based on the SQL/XML construction expression in the second abstract syntax.

23. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XML operator in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL operator in the first abstract syntax based on the XML operator in the second abstract syntax.

24. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XQuery sequence type operation in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL type operation in the first abstract syntax based on the XQuery sequence type operation in the second abstract syntax.

25. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XQuery type constructor in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL scalar constructor in the first abstract syntax based on the XQuery type constructor in the second abstract syntax.

26. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XQuery validate operation in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating one of an SQL/XML IsValid operation and an SQL/XML Validate operation in the first abstract syntax based on the XQuery validate operation in the second abstract syntax.

27. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises a polymorphic XQuery arithmetic operator in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating one of a polymorphic SQL arithmetic operator in the first abstract syntax based on the polymorphic XQuery arithmetic operator in the second abstract syntax.

28. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises a polymorphic XQuery comparison operator in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating one of a polymorphic SQL value comparison operator in the first abstract syntax based on the polymorphic XQuery comparison operator in the second abstract syntax.

29. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XQuery function call in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an SQL function call in the first abstract syntax based on the XQuery function call in the second abstract syntax.

30. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises a user-defined XQuery function in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating a user-defined PL/SQL function in the first abstract syntax based on the user-defined XQuery function in the second abstract syntax.

31. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an external XQuery function in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating an external SQL function in the first abstract syntax based on the external XQuery function in the second abstract syntax.

32. The method of claim 2, wherein the first abstract syntax is an SQL-related abstract syntax and the second abstract syntax is an XQuery-related abstract syntax;

wherein the second portion comprises an XQuery module in the second abstract syntax; and

wherein the step of generating the fourth in-memory representation comprises generating a PL/SQL package in the first abstract syntax based on the XQuery module in the second abstract syntax.

35. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

36. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

37. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

38. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

39. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

40. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

41. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

42. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

43. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

44. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

45. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

46. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

47. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.

48. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 14.

49. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 15.

50. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 16.

51. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 17.

52. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 18.

53. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 19.

54. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 20.

55. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 21.

56. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 22.

57. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 23.

58. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 24.

59. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 25.

60. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 26.

61. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 27.

62. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 28.

63. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 29.

64. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 30.

65. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 31.

66. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 32.

33. A method of processing a query comprising:

receiving the query, wherein the query specifies certain operations and is querying data stored in a markup language;

generating a first in-memory representation of the query;

generating a second in-memory representation based on the first in-memory representation, wherein the second in-memory representation is in the same form as would have been produced by processing an equivalent query that is querying a relational database; and

performing the certain operations based on the second in-memory representation.

34. The method of claim 33, wherein the step of performing the certain operations comprises performing the certain operations by executing commands specified in the second in-memory representation against the relational database.

67. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 33.

68. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 34.