Method to generate semantically valid queries in the XQuery language

• US 7,680,782 B2
• Filed: 10/18/2006
• Issued: 03/16/2010
• Est. Priority Date: 10/18/2006
• Status: Active Grant

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Cialini, Enzo, Pomeroy, Ronald James, Mathew, Ciby, Chen, Wallace W Y, Loreto, Anthony Di, Godwin, David Richard
• Primary Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US11/550,580
• Publication Number:
  US 20080097974A1
• Time in Patent Office: 1,245 Days
• Field of Search: 707 1- 10
• US Class Current: 1/1
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases
• CPC Class Codes: G06F 16/832 Query formulation
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A computer implemented method, apparatus, and computer usable program code for automatically generating a query. Data and occurrence is described using a sequence type. The data and occurrence from the sequence type are matched to a sequence type pattern. Sentences in a query language are generated automatically using the sequence type pattern for testing an ability of a query processing engine to interpret queries.

Claims

1. A computer implemented method for automatically generating a query to test a query processing engine that processes queries received by the query processing engine, the computer implemented method comprising:

describing data and occurrence using a sequence type;

matching the data and the occurrence from the sequence type to a sequence type pattern;

automatically generating, by a computer processor, sentences in a query language using the sequence type pattern;

testing an ability of the query processing engine to interpret queries using the sentences that are automatically generated by the computer implemented method;

defining a grammar wherein the grammar uses the sequence type pattern to drive sentence generation by producing a plurality of tokens in the grammar automatically, wherein the plurality of tokens is consistent with the sequence type pattern, and translating the plurality of tokens into a syntactically valid query in a target language automatically; and

defining the sequence type pattern wherein the sequence type pattern abstracts a class of query.

2. The computer implemented method of claim 1, wherein the target language of the sentences that are automatically generated is XQuery.

3. The computer implemented method of claim 1, further comprising:

generating the syntactically valid query automatically based on random or historic queries for testing the query processing engine.

4. The computer implemented method of claim 1, wherein the query is used for testing a database system.

5. The computer implemented method of claim 1, further comprising:

generating code for a rule clause; and

executing the rule clause to generate a syntax tree, wherein the syntax tree includes intermediate semantic nodes and terminal syntactic nodes and terminal semantic nodes.

6. The computer implemented method of claim 5, comprising:

processing the syntax tree to perform data generation.

7. The computer implemented method of claim 1, wherein the generating step is performed using rule-specification grammar and further comprising:

translating the rule-specification grammar into a programming language.

8. The computer implemented method of claim 6, wherein the processing step further comprises:

typing the intermediate semantic nodes in leaves in order to generate primary expressions in the query language.

9. The computer implemented method of claim 1, wherein the describing step, matching step, and generating step are performed by a XQuery generator that sends the automatically generated sentences to the query processing engine.

10. The computer implemented method of claim 5, wherein the terminal syntactic nodes represent keywords, wherein leaf semantic nodes are primary expressions.

11. A data processing system comprising:

a bus system;

a communications system connected to the bus system;

a memory connected to the bus system, wherein the memory includes a set of instructions for a XQuery code generator that is operable for automatically generating a query to test a query processing engine that processes queries received by the query processing engine; and

a processing unit connected to the bus system, wherein the processing unit executes the set of instructions to describe data and occurrence using a sequence type, match the data and the occurrence from the sequence type to a sequence type pattern, automatically generate sentences in XQuery language using the sequence type pattern, test an ability of the query processing engine to interpret queries using the sentences that are automatically generated, define a grammar wherein the grammar uses the sequence type pattern to drive sentence generation by producing a plurality of tokens in the grammar automatically, wherein the plurality of tokens is consistent with the sequence type pattern, translate the plurality of tokens into a syntactically valid query in a target language automatically, and define the sequence type pattern wherein the sequence type pattern abstracts a class of query.

12. The data processing system of claim 11, wherein the sentences are generated randomly for testing features of the query processing engine.

13. The data processing system of claim 11, wherein the set of instructions receives a goal and builds a syntax tree, wherein the syntax tree is processed to generate the sentences.

14. A computer program product comprising a computer usable medium including computer usable program code stored thereon for automatically generating a query to test a query processing engine that processes queries received by the query processing engine when executed in a memory, the computer program product comprising:

computer usable program code for describing data and occurrence using a sequence type;

computer usable program code for matching the data and the occurrence from the sequence type to a sequence type pattern;

computer usable program code for automatically generating sentences in a query language using the sequence type pattern;

computer usable program code for testing an ability of the query processing engine to interpret queries using the sentences that are automatically generated;

computer usable program code for defining a grammar wherein the grammar uses the sequence type pattern to drive sentence generation by producing a plurality of tokens in the grammar automatically, wherein the plurality of tokens is consistent with the sequence type pattern, and translating the plurality of tokens into a syntactically valid query in a target language automatically; and

computer usable program code for defining the sequence type pattern wherein the sequence type pattern abstracts a class of query.

15. The computer program product of claim 14, further comprising:

computer usable program code for generating code for a rule clause;

computer usable program code for executing the rule clause to generate a syntax tree; and

computer usable program code for processing the syntax tree to perform data generation.