The importance of XML as a universal data representation format has led to several efforts to integrate XML as a construct in a programming language. There has been growing interest in the addition of update operations in these languages, for example, to languages such as XQuery [20] and XJ [8]. These update operations (whether the semantics are mutating or value-based) support concise 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. 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 polynomial time algorithms for update conflict detection when the patterns do not use branching.
By: Mukund Raghavachari; Oded Shmueli
Published in: RC23733 in 2005
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .