Although much work has been done on specifying relational storage
strategies for XML, this paper is a first attempt to study the problem of
how XML constraints are propagated to a relational view of XML data.  We
consider an important class of constraints, XML keys, and investigate
their
associated propagation problem: whether a functional dependency must hold
on the relational view provided that a set of XML keys holds on the XML
data.  To define the relational view, we adopt a simple specification
language for transforming XML data to relations and demonstrate that it is
capable of expressing transformations commonly found in practice.  For
this
language we provide a polynomial time algorithm to determine propagation
of
XML keys. In contrast, we show that for an extension of our specification
language the key propagation problem is undecidable.

These results are important in designing consistent and efficient
relational storage for XML data (e.g. normal forms), and in formulating
and
optimizing XML queries and updates via its relational view.  In addition,
our algorithm for key propagation can be generalized and incorporated into
relational storage techniques published in the literature.  These results
are also useful in understanding XML to XML transformations, which subsume
XML to relational transformations. In particular, as an immediate
consequence, the key propagation problem is undecidable when XQuery is
used
to specify transformations since it subsumes the undecidable extension of
our specification language; and a fragment of XQuery and other popular
query languages possesses a PTIME algorithm for XML key propagation.