Date Added: Jan 2010
The authors investigate the complexity of performing updates on probabilistic XML data for various classes of probabilistic XML documents of different succinctness. They consider two elementary kinds of updates, insertions and deletions, which are defined with the help of a locator query that specifies the nodes where the update is to be performed. For insertions, two semantics are considered, depending on whether a node is to be inserted once or for every match of the query. They first discuss deterministic updates over probabilistic XML, and then extend the algorithms and complexity bounds to probabilistic updates.