Context quantifier transformation in XML query rewrite

• US 7,165,063 B2
• Filed: 11/19/2003
• Issued: 01/16/2007
• Est. Priority Date: 11/19/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ozcan, Fatma, Seemann, Normen, Beyer, Kevin S., Cochrane, Roberta J.
• Primary Examiner(s): Pham; Khanh B.
• Assistant Examiner(s): Ebirim; Emeka
• Application Number:
  US10/717,870
• Publication Number:
  US 20050108209A1
• Time in Patent Office: 1,154 Days
• Field of Search: 707 1- 10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/8358 Query translation
• CPC Class Codes: G06F 16/8365 Query optimisation
• 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

An XML query compilation processor (20) includes an execution compiler (42) that transforms an XML query into an executable XML query plan (22). A query rewrite processor (34) performs query transformations on the XML query. Said query transformations include transforming an expression input (60) received by an expression (62) conditional upon a set of items defined by an output (64) of the expression (62) being independent of grouping of items in the expression input (60).

Claims

1. An XML query rewrite method processing an XML query, the XML query rewrite method comprising:

identifying an expression of the XML query that receives a sequence of concatenated XML items as an expression input;

determining of whether a set of items defined by an output of the expression is independent of grouping of items in the expression input by determining a granularity property according to;

2. The XML query rewrite method as set forth in claim 1, wherein the transforming of the expression input into a transformed data stream input comprises:

transforming the sequence of concatenated XML items into a data stream of individual unconcatenated XML items.

3. The XML query rewrite method as set forth in claim 1, further comprising:

determining a duplication property according to;

∀

i,j in LET(I) with POSITION(LET(I),i)≠

POSITION(LET(I),j) holds SET(EVAL(exp,i))∩

SET(EVAL(exp,j))={ }, and

determining an ordering dependence property according to;

∀

i,j in LET(I) holds

POSITION(LET(I),i)<

POSITION(LET(I),j)

∃

e_i in EVAL(exp,i),e_j in EVAL(exp,j)such that e_i>

>

e_j,

wherein POSITION returns ordinal position of an element within a sequence, and the transforming is further conditioned upon the duplication property being true and upon the ordering dependence property being true.

4. An XML query rewrite method processing an XML query, the XML query rewrite method comprising:

identifying an expression of the XML query that receives an expression input;

determining of whether a set of items defined by an output of the expression is independent of a grouping of items in the expression input by determining a granularity property including at least;

5. The XML query rewrite method as set forth in claim 4, wherein the transforming of the expression input into a data stream input comprises:

removing an imposition of a grouping of XML items corresponding to a quantifier that imposes a selected grouping of XML items on the expression input.

6. The XML query rewrite method as set forth in claim 5, wherein the XML query is an XQuery, and the removing of an imposition of a grouping of XML items corresponding to a quantifier comprises:

removing an imposition of a grouping of XML items corresponding to a quantifier selected from a group consisting of an XQuery LET quantifier and an XQuery FOR quantifier.

7. The XML query rewrite method as set forth in claim 4, further comprising:

determining a duplication property according to;

∀

p_i,p_j in I holds SET(EVAL(exp,p_i))∩

SET(EVAL(exp, p_j))={ }

and determining an ordering property according to;

∀

p_i, p_j in I;

p_i occurs before p_j in I

∃

e_i in EVAL(exp, p_i), e_j in EVAL(exp, p_j)such that e_i>

>

e_j

wherein the transforming is further conditioned upon the duplication property being true and upon the ordering dependence property being true.

8. An article of manufacture including a program storage medium storing instructions executable by an associated computer, the instruction embodying an XML query compilation processor comprising:

an execution compiler transforming an XML query into an executable XML query plan; and

a query rewrite processor is performing query transformations on the XML query, said query transformations including transforming an expression input received by an expression that produces an output stream of individual XML items conditional upon a set of items defined by the output stream of individual XML items being independent of grouping of items in the expression input and being adapted to perform the expression input transformation by;

determining a granularity property according to;

9. The XML query compilation processor as set forth in claim 8, wherein the query rewrite processor is adapted to perform the expression input transformation by further;

determining a duplication property for each consumer of the output stream of individual XML items indicating whether duplicates in the output stream of individual XML items are problematic for that consumer; and

determining an ordering dependence property for each consumer indicating whether a selected ordering is required for that consumer; and

applying one or more corrections including at least one of;

removing duplicates from the output stream of individual XML items flowed to a consumer for which said duplicates are problematic, and

sorting the output stream of individual XML items into a selected ordering required for a consumer.

10. The XML query compilation processor as set forth in claim 8, wherein the XML query compilation processor processes XQuery XML queries, the expression input is a concatenated sequence input corresponding to an XQuery LET clause, and the query rewrite processor is adapted to perform the expression input transformation by further;

transforming the concatenated sequence input into a data stream of individual unconcatenated XML items corresponding to an XQuery FOR clause.

11. An article of manufacture including a program storage medium storing instructions executable by an associated computer, the instruction embodying an XML query compilation processor as comprising:

an execution compiler transforming an XML query into an executable XML query plan; and

a query rewrite processor is performing query transformations on the XML query, said query transformations including transforming an expression input received by an expression that produces an output stream of individual XML items conditional upon a set of items defined by the output stream of individual XML items being independent of grouping of items in the expression input and being adapted to perform the expression input by;

determining a granularity property including sub-properties (i), (ii), and (iii) according to;