Merging uncertain multi-version XML documents

Merging is a fundamental operation in revision control systems that enables integrating different changes made to the same documents. In open platforms, such as Wikipedia, uncertainty is ubiquitous, essentially due to a lack of knowledge about the reliability of contributors. We propose in [2] a version control framework designed for uncertain multi-version tree-structured documents, based on a probabilistic XML model. In this paper, we define a merge operation that complements our framework and enables the conciliation of uncertain versions. We devise an efficient algorithm that implements the merge operation and prove its correction.