Conflicting XML Updates

摘要

There has been growing interest in the addition of update operations to languages that operate on XML data, for example, XQuery and XJ. These update operations support efficient and declarative specification of transformations of XML data. The presence of update operations raises the question of detecting data dependencies between reads and updates of XML documents. The ability to optimize the execution of update operations depends on the ability to detect such conflicts. In this paper, we formalize the notions of updates on XML data and conflicts between update operations. We show that conflict detection is NP-complete when the update operations are specified using XPath expressions that support the use of the child and descendant axis, wildcard symbols, and branching. We also provide efficient polynomial algorithms for update conflict detection when the patterns do not use branching.