Regular tree patterns: a uniform formalism for update queries and functional dependencies in XML

Abstract : Given an XML functional dependency fd and a class of updates U, we say that fd is independent with respect to U if and only if any XML document satisfies fd after any update q of U, as soon as it did it before q. In this paper we study the following problem: is it possible to detect if an XML functional dependency fd is independent with respect to a class of updates U? We address this problem when the functional dependency and the class of updates are specified with a same formalism: the regular tree patterns. We first show that the use of regular tree patterns federates most of the known approaches for expressing XML functional dependencies while allowing to capture some of constraints not so far expressible. Then we show that in general the addressed problem is PSPACE-hard, but we exhibit a sufficient condition testable in polynomial time ensuring the independence of a functional dependency with respect to a class of updates.