Reviews for paper eXrQuy: Order Indifference in XQuery, submitted to ICDE 2007.

Overall rating: accept (as full paper)

Reviewer 1

Is the paper relevant to ICDE 2007?

Yes, Definitely

Is the paper technically correct?

Yes

Originality

Weak accept (Marginally innovative)

Impact

Weak reject (Fair)

Technical Depth

Accept (High)

Presentation

Strong accept (Excellent)

Overall Rating

Weak accept (Could go either way)

How many ICDE attendees are likely to be interested in this paper?

Everyone interested in XML query processing

Should this paper be considered for a Best Paper Award?

No

Summary of main contribution and rational for your recommendation (1-2 paragraphs)

Based on a survey of the order semantics of XQuery and a translation of XQuery into an extended relational algebra developed earlier by the authors, the authors present an inference mechanism that allows to relax the strict order semantics of XQuery when possible. As a result of this inference mechanism ordering operations and several computations needed to preserve order in the general case can be avoided. Experiments measure the effect of these simplifications. The presented inference rules appear correct and are well-presented. I agree that no system exploits order modes or the unordered function in XQuery in an algorithmic fashion. However, the inference only marginally extends techniques to avoid sorting mentioned in the literature. In particular, order indifference at the level of XPath expressions and join ordering should be investigated in more detail.

Detailed comments to authors

• for sake of clarity, please mention that the result of query (3) is determined by the example document you use in the paper. In general, it might also evaluate to (false, false) or raise a type error.
• on page 3, example query (6), please remove the closing }
• on page 5, the first paragraph of \paragraph{Order interaction (1): doc -> seq}: note that the TwigStack algorithm is usually applied to a tree pattern whereas the staircase join evaluates a single location step. So TwigStack would usually implement several applications of the staircase join and hence the algebraic expression after translation of a query would look different to yours.
• In my opinion Section 4 does not contain enough new material to justify a better rating on Originality and Impact and hence a better overall rating. In particular there are research results that you could incorporate well into optimization after you have deduced order indifference.
• your discussion in Sect. 1-3 suggests that your technique really exploits all possible permutations of result nodes. However, your location-step-operator (the staircase) always returns result nodes in document order. It would be interesting to see how, e.g. reordering of location steps as discussed by Jagadish and others affects performance.
• similarly function fn:unordered allows reordering joins and chosing efficient implementations for joins. The experiments raise hope for substential performance gains. Both aspects have already been adressed in the XQuery literature. But it is unclear, how you would incorporate them into your apporach.
• Section 6: as mentioned above, there is more relevant research that relates to your work and complement your results.

Should this paper be considered for a short presentation if accepted as a full paper?

Yes

Reviewer 2

Is the paper relevant to ICDE 2007?

Yes, Definitely

Is the paper technically correct?

Yes

Originality

Strong accept (Very innovative)

Impact

Accept (High)

Technical Depth

Accept (High)

Presentation

Accept (High)

Overall Rating

Strong accept (Definitely accept)

How many ICDE attendees are likely to be interested in this paper?

I'm not familiar enough with ICDE to say

Should this paper be considered for a Best Paper Award?

Probably

Summary of main contribution and rational for your recommendation (1-2 paragraphs)

The paper is very clearly written and addresses an interesting problem: how to exploit order indifference (which may be either explicitly indicated or implicit from the query) for efficient query processing. It seems technically correct and gives a nice feeling of the difficulties and the potential speedup that can be obtained.

Detailed comments to authors

REPLACE THIS WITH YOUR ANSWER.

Should this paper be considered for a short presentation if accepted as a full paper?

Yes

Reviewer 3

Is the paper relevant to ICDE 2007?

Yes, Definitely

Is the paper technically correct?

Yes

Originality

Accept (Innovative)

Impact

Accept (High)

Technical Depth

Accept (High)

Presentation

Accept (High)

Overall Rating

Accept (Probably accept)

How many ICDE attendees are likely to be interested in this paper?

50-80

Should this paper be considered for a Best Paper Award?

Probably

Summary of main contribution and rational for your recommendation (1-2 paragraphs)

This paper exams a very interesting problem: how to detect it when the order is indifferent in query processing and how to algebraically rewrite the query to reflect so. This problem is non-trivial and intuitively, techniques that solve the problem will be able to significantly improve the query performance. This paper identifies the order semantics in XQuery and developed a set of rules to rewrite the queries when the order is semantically indifference. It observes over 100 times performance gain for some queries when the order indifference is taken care of in the query processing.

Detailed comments to authors

This paper discussed an very interesting problem and looks at the query processing and optimization of XQuery queries from a new angle. The classification of the ordering semantics is a good starting point for tackling the problem. Rules are proposed to remove the ordering requirements when order indifference is identified. However, the rules are all based on simple query blocks, with limited combinations of clauses in the FLWOR statement. It is not clear how the rules can be extended to more complicated cases. Such extension is non-trivial and is not discussed in the paper.
The proposed technique depends on a relational backend and a set of new/modified relational algebra operators. It seems that the technique proposed is fixed to such implementation and is not suitable for query processing in a native XML database system.
The presentation of the paper does have room for improvement. A better job on the key definitions, such as the relational algebra in table 1, will help improving the readability of the paper. For example, the short explanation of the first operator on the right hand side does not explain the role of b and c in it. There are also typos and grammar mistakes, for example, “It is now a only a small step……” as it appear in the first sentence in section 4.
In section 5, the query execution time is profiled for Q11. However, it is not clear whether it is a special case or a trend followed by a significant amount of queries. Figure 12 shows the speed by of the proposed techniques. However, it is not clear what it compares to. In other words, it is not clear what the default setting is when “the order indifference is NOT enabled in pathfinder”. Moreover, the experimental section does not compare the proposed techniques with other techniques as mentioned in section 6.

Should this paper be considered for a short presentation if accepted as a full paper?

No

Related Information

• final paper (PDF) — published at ICDE 2007