Updates and Incremental Validation of XML Documents

We consider the incremental validation of updates on XML documents. When a valid XML document (i.e., one satisfying some constraints) is updated, it has to be verified that the new document still conforms to the imposed constraints. Incremental validation of updates leads to significant savings on computing time when compared to brute-force validation of an updated document from scratch. This paper introduces a correct and complete set of update operations that can be integrated in an XML manipulation language. Indeed, any document generated by a composition of our update operations is valid, and, every valid document can be generated by a composition of our update operations (from the empty document). To accept an update, the validity of the result is checked first (without any change on the original document). Validation tests are performed incrementally, i.e., only the validity of the part of the document directly affected by the update is checked. Changes to the original document are effectively performed only when the update is accepted.