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.
Type de document :
Communication dans un congrès
Updates in XML collocated with EDBT/ICDT 2010 (Updates 2010), Mar 2010, lausanna, Switzerland. pp.1-9, 2010, 〈10.1145/1754239.1754260〉
Liste complète des métadonnées

https://hal-paris1.archives-ouvertes.fr/hal-00662995
Contributeur : Hicham Idabal <>
Soumis le : mercredi 25 janvier 2012 - 17:11:11
Dernière modification le : mercredi 25 janvier 2012 - 17:11:11

Identifiants

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, 2010, 〈10.1145/1754239.1754260〉. 〈hal-00662995〉

Partager

Métriques

Consultations de la notice

45