Static and dynamic semantics of NoSQL languages
Véronique Benzaken, Giuseppe Castagna, et al.
POPL 2013
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. © 2008 ACM.
Véronique Benzaken, Giuseppe Castagna, et al.
POPL 2013
Mandana Vaziri, Louis Mandel, et al.
Onward! 2017
Mary Fernández, Nicola Onose, et al.
SIGMOD 2004
Matthew Arnold, David Grove, et al.
IBM J. Res. Dev