Abstract | ||
---|---|---|
An effective approach to support XML updates is to use XQuery extended with update operations. This approach results in very expressive languages which are convenient for users but are difficult to optimize or reason about. A crucial question underlying many static analysis problems for such languages, from optimization to view maintenance, is whether two expressions commute. Unfortunately, commutativity is undecidable for most existing XML update languages. In this article, we propose a conservative analysis for an expressive XML update language that can be used to determine commutativity. The approach relies on a form of path analysis that computes upper bounds for the nodes that are accessed or modified in a given expression. Our main result is a theorem that can be used to identify commuting expressions. We illustrate how the technique applies to concrete examples of query optimization in the presence of updates. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1145/1412331.1412341 | ACM Trans. Database Syst. |
Keywords | Field | DocType |
xquery,updates,commutativity,optimization,existing XML update language,expressions commute,additional key words and phrases: xml,Commutativity analysis,approach result,effective approach,expressive XML update language,conservative analysis,path analysis,XML updates,static analysis problem,update operation | Query optimization,Programming language,XML,Expression (mathematics),Commutative property,Computer science,XML validation,Static analysis,Theoretical computer science,XQuery,Undecidable problem | Journal |
Volume | Issue | ISSN |
33 | 4 | 0362-5915 |
Citations | PageRank | References |
13 | 0.64 | 18 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Giorgio Ghelli | 1 | 1300 | 255.19 |
Kristoffer Rose | 2 | 46 | 3.18 |
Jérôme Siméon | 3 | 1515 | 210.75 |