Regular tree patterns: a uniform formalism for update queries and functional dependencies in XML - Archive ouverte HAL Access content directly
Conference Papers Year : 2010

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

(1) , (1)
1

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.
Not file

Dates and versions

hal-00662995 , version 1 (25-01-2012)

Identifiers

Cite

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⟩

Collections

UNIV-PARIS1 CRI
41 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More