This paper introduces tree multivalued dependencies (TMVDs) for XML documents by extending multivalued dependencies in relational
databases and recent research about tree functional dependencies (TFDs). We show the existence of the TMVDs in XML documents
that produce redundancies and update anomalies. Secondly, the precise definition of TMVDs is proposed, which is based on the
tree structure and deep equality. Moreover, we introduce the concept of recomposition that is a reconstruction of an XML database
by moving or adding nodes. The right side of TMVDs is characterized by single attribute and multiple attributes, for which
there are different recompositions. In addition, the relationship between TFDs and TMVDs is investigated, and we demonstrate
that a TMVD is a generalized TFD. Furthermore, we present a theorem showing the recomposition by TMVDs saves space. Finally,
we exhibit a recomposition that is not equivalent to any relational data.
This research was made possible through funding from the Natural Sciences and Engineering Research Council of Canada.