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.
Document type :
Conference papers
Complete list of metadatas

https://hal-paris1.archives-ouvertes.fr/hal-00662995
Contributor : Hicham Idabal <>
Submitted on : Wednesday, January 25, 2012 - 5:11:11 PM
Last modification on : Wednesday, January 25, 2012 - 5:11:11 PM

Identifiers

Collections

Citation

Françoise Gire, Hicham Idabal. Regular tree patterns: a uniform formalism for update queries and functional dependencies in XML. Updates in XML collocated with EDBT/ICDT 2010 (Updates 2010), Mar 2010, lausanna, Switzerland. pp.1-9, ⟨10.1145/1754239.1754260⟩. ⟨hal-00662995⟩

Share

Metrics

Record views

57