Reviews for paper Scalable XQuery Type Matching, submitted to EDBT 2008.
Overall rating: accept
Definitely relevant
One step forward
Good work
Well written
Probably accept
The paper considers how to perform matching of XML data against XML types when an XQuery query is evaluated. It assumes the data has detailed type information. The problem is that matching involves comparisons against a type hierarchy, defined in the XML schema. The main achievement is an efficient implementation of this run-time operation, using for type hierarchies techniques used previously for storing XML data in a way that supports efficient containment checks, and also using the efficiency of aggregation in database systems.
A nice result. The experiments show orders of magnitude efficiency improvements. The author notes a similar technique used in a certain Java compiler for subtype checking. Actually, such ideas were explored in OO languages to a larger extent than the author seems to be aware of. Thus, the idea itself is not very novel, its implementation in a database environment is.
Comments for author:
You note that a similar technique was used in Jalapeno. I know that the idea to improve run-time subtype checking was explored not just in that compiler, nor only in Java (but I do not have handy references). It would be appropriate to explore the literature a bit more, and include a couple more references.
Definitely relevant
One step forward
Weak content
Well written
Lean towards acceptance
XPath and XQuery both support examples of run-time typematching operations, which compare the type annotations of a sequence of idtems with an XSD type. The operation is not totally trivial because a hierarchy is defined on XML types, hence it is necessary to verify whether the type annotation is a descendent of the type to be matched in the derivation tree. Moreover, the XSD type may have a cardinality constraint that has to be checked as well.
The author observes that an interval encoding, similar to that used to represent nodes in a relational representation of an XML documents, allows the system to perform the "descendent of" check in constant time, using the standard interval-inclusion technique. He further observes that, in order to verify whether all elements in a sequence satisfy the check, one may precompute the intersection of the intervals of the various elements, and perform the test on the intersection. Finally, the author shows how this technique allows typematching to be implemented using group-by in an XQuery engine implemented on top of a relational system.
The paper is clear and technically sound. I have some reservations about the actual meaning of the experiments, since the author compares its group-by solution with a soluton based on an unoptimized self-join, which seems totally unrealistic to me; I really hope that no system around uses that technique.
I am also not really convinced that the issues studied by the author are very relevant in practice, because typical XSD specialization hierarchies are extremely flat, which means that their transitive closure can be precomputed with little effort, and in many situations type-matching is performed on item rather than sequences. However, in the specific setting studied by the author, i.e. loop-lifted relational-based implementations, the presented solution is efficient and original.
For the author only:
I believe you exchanged 'true' and 'false' in figure 8a and 8b.
Appropriate to the point
One step forward
Solid work
Excellently written
Lean towards acceptance
The paper discusses treatment of type annotations in XQuery execution plans. Type matching in XQuery is basically a relationship test of two types in the type hierarchy. The idea of the paper is to apply query processing techniques for trees (e.g. pre/post encoding), by treating the type hierarchy(/hierarchies) as a labeled document tree of its own. This converts complex type matching operations to simple primitives.
Pro:
P1 well written
P2 type-related run-time issues in scalable XQuery implementation have not yet received sufficient attention. Existing type-related work is usually focused on compile-time techniques. This is the main reason for my positive overall recommendation.
P3 type aggregation is an innovative concept (more so than type ranks)
Con:
C1 the paper fails to convince me that the problem solved by type ranks is real, i.e. why is simple caching of type matching operations insufficient? This obvious issue is not investigated in the experimental section...
C2 the paper should develop the concept of type aggregation independently of type ranks (i.e. aggregation of type information is orthogonal to the representation of the type annotation)
C3 The summary section seems overly ethusiastic - the limitations of the technique are insuffiently discussed, what about modular schemas (i.e. import/include/redefine, possibly with chameleon components) - how do you type rank them?