XML document correction based on update conflict detection

An invalid XML document that does not satisfy its schema constraints requires correction. In this paper, a correction method based on the conflict detection of update operations is proposed. First, a schema 6-tuple model is introduced to flatten the hierarchical structure of the schema. Second, a path set that is equivalent to the invalid XML tree is built, and a correction approach is proposed to search for all valid path sets that are as close as possible to the user´s update intention. In this correction approach, a node path is considered as a string, and a dynamic programming algorithm based on the string-to-string correction method is introduced. A correction rule based on the conflict detection of the update operations is applied during the execution of the correction. The experimental results show that our algorithm is fast and has good performance even when dealing with an invalid node that follows a starred regular expression.