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.
Uncertain version control. Version control of uncertain data has concrete applicability in open environments such as web-scale editing platforms. Most of these platforms, in particular Wikipedia 1, are facing (1) the rapid growth of the number of contributors with different level of reliability, and (2) the will to provide the users with the most trustworthy content. This latter purpose is especially challenging because of uncertainties in data inherent to unreliable contributors, recurrent conflicts (contradictions or edit wars) and frequent malicious contributions (e.g., spam). Besides that, trust is a subjective notion which sorely depends on the user preferences.
So far, within web-scale collaborative platforms like Wikipedia, version control allows maintaining the integrity of each document by tracking all contributions, as well as their history and their authors. This gives therefore the ability to revert to a given revision when some editing problems such as vandalism acts and unsourced information appear. Used version control approaches are however not necessarily intended to the versioning of uncertain data, and
Motivations. Amongst the motivations for this work, we can cite the following ones. On one hand, users may trust only some contributors and want to see the document resulting from the conciliation of their contributions, i.e., the merge of the revisions produced by these contributors. If the user preferences are known (e.g., based on her personal settings or past behaviour), a recommender system can be built on Wikipedia in order to propose to the user a version resulting from the merge of the contributions of her trusted authors. On the other hand, open platforms such as Wikipedia requires as a core functionality the merge of articles which overlap (articles related to the same topic or sharing a large common part). This operation is currently done manually and requires a lot of time and coordination between contributors. This results in a tedious and error-prone supervised merge process. Providing an automated integration processes of these articles is certainly useful. To this goal, a merging operation is needed and it has to take into account the uncertainty associated to the merged data. In this paper, we present our uncertain version control model with a merging operation that covers common deterministic merge scenarios over XML documents while managing uncertain data. We devise an efficient algorithm for merging uncertain multi-version XML documents and prove its correctness.
Outline. First, we present in Section 2 the merge and edit detection techniques used for XML documents. Then, we summarize in Section 3 our uncertain muti-version model. Section 4 concretely presents our merging operation, as well as a corresponding efficient algorithm. Finally, we conclude the paper in Section 5.
The increasing use of XML-based systems, in particular those
with a built-in version control engine, has lead to the adoption of
new XML merge techniques, e.g., [
Merging in [
In contrast, two-way merging operations in [
A multi-version (XML) document with uncertain data evolves, through uncertain updates, and leads to uncertain versions. It is represented by the means of an uncertain multi-version XML document model, that describes the version space of this document together with a probability distribution over the set of possible versions.
The following is a concise summary of the formal foundations of
our model and the evaluation of updates over it. For more details,
see [
Model: Formal Definition. A multi-version XML document Tmv with uncertainty is a couple (G , Ω) where G is a directed acyclic graph (DAG) over a set V ∪ {e0} of events e0 . . . en representing the version space of Tmv, and Ω is a function giving the possible versions of the document, as we now detail.
An event ei in V has a random nature and happens with a certain probability. It is defined as a conjunction of random Boolean variables b1 . . . bm that each model a given source of uncertainty (e.g., the source of information). This definition of the events using Boolean variables lies on the following: (i) variables are pairwise independent, that is, Pr(b j ∧ bk) = Pr(b j) × Pr(bk) for all b j 6= bk; (ii) a variable b j, correlating different events, can be reused across events; (iii) one revision variable b(i), representing more specifically the uncertainty in the content, is not shared across other events and only occurs in ei. Our version control system is state-based with events modeling the different uncertain states of the evolution of the versioned document. A state, i.e., an event, has contextual information about a given version (in the form of, first, Boolean random variables involved; second, an edit script Δi; third, possible other metadata).
The DAG G = (V ∪ {e0}, E ) keeps the history of the evolution of Tmv with: (i) the particular event e0 6∈ V , which represents the initial state of Tmv, as the root of G ; (ii) E ⊆ V 2 defines the set of directed edges of G that enable to implicitly track derivation relationships between the generated (uncertain) versions. A branch of G is a directed path in which the tail e j is reachable from the head ei by traversing a set of ordered edges in E . A rooted branch is a branch with e0 as head node.
A version of Tmv is an XML document mapping to a set of events
in G , the events whose edit scripts together made this version
happen. Such an event set is always a rooted branch in G in a
deterministic versioning case, whereas it can be arbitrary in the
uncertain setting. In the model, formally an XML document is an
unordered3 , unranked, and labeled tree T in which a node x has a
unique identifier α (x) in I and a label ϕ(x) in L with I ∩ L = 0/
(for brevity, we do not mention node identifiers when depicting
example trees). In addition, all trees considered share the same root
node (same label, same identifier). Given the set 2V of all
subsets of V and the infinite set D of all XML trees, the mapping
3We leave the extension to ordered trees open as in [
We have just defined an abstract multi-version XML document – we now provide a general and concise syntax for it, that has for semantics such a multi-version document.
Probabilistic Encoding: Syntax and Semantics. We have
introduced in [
The semantics of an encoding Tcmv, denoted JTcmvK, is an uncertain multi-version XML document (G , Ω). The DAG G does not change, whereas Ω is such that Ω(F ) := νF (Pc) for all F ⊆ V , where νF is a valuation over variables b1 . . . bm defined as follows. Let B+F be the set of all random variables occurring in one of the events of F and set B−F the set of all revision variables b(i)’s for ei not in F . Then νF sets variables of B+F to true, variables of BF − to false, and other variables to an arbitrary value. This semantics remains non-ambiguous as long as formulas occurring in Pcare expressed as formulas over the events of V , i.e., do not make use of the Boolean variables separately of the events.
Updates: Semantics and Evaluation. An edit script Δ is a set of edit operation over XML nodes. An edit operation is either an insertion or a deletion of nodes. An insertion is formally defined as ins(i,x) with i the identifier of the node where the insertion must take place and x the label of the new node to be added. As for a deletion, it is introduced as del(i) where i represents the identifier of the node to remove. The evaluation of Δ over any XML document T produces the document [T ]Δ by applying insertions and deletions to T ; if no node is selected by a given insertion or deletion, it is simply ignored.
An update operation is set up in the uncertain multi-version XML
framework as updOPΔ, e, e′ where Δ is an edit script, e is an actual
event pointing to the edited version and e′ is a fresh one
assessing the uncertainty in this update. Its semantics on Tmv = (G , Ω)
(i) updates G to (G ∪ ({e′}, {(e, e′)}) and; (ii) extends Ω to Ω′
by letting for all F ⊆ V ∪ {e′}: Ω′(F ) := Ω(F ) if e′ 6∈ F and
Ω′(F ) := [Ω(F \{e′})]Δ otherwise. The translation of this
semantics on the general syntax Tcmv = (G , Pc) is done through an update
algorithm updPrXML that first modifies G as before, and then it
evaluates operations in Δ over the p-document Pc as follows. This
is the usual implementation of updates in probabilistic XML [
• For an insertion u = ins(i,x) in Δ: fie(x) of x in Pc is set to fie(x) ∨ (e′) if x already occurs in Pc; otherwise, u inserts x in Pcwith fie(x) = e′. • For a deletion u = del(i) in Δ: the node x in Pc such that α (x) = i (if it exists) has its formula fie(x) updated to fie(x) ∧ (¬e′).
EXAMPLE 3.1. Figure 1 shows an uncertain multi-version document Tmv with: (a) the version space G with four staged events; (b) four event sets and associated versions; (c) the p-document Pc encoding all the possible versions based on staged events and their attached edit scripts, resulting in formulas attached to nodes (shown above each node). As a sketch, (e1 ∧ ¬e2) reveals that s1 was added at e1 and then removed at e2. The given four versions are exactly those modeled by deterministic systems. In contrast, the possible world mapping to {e1, e4} is only valid within our framework. It occurs with the reject of the changes introduced by event e2. Note that the probability of each possible version can be evaluated based on event sets that map to it and their probabilities. 4.
We detail in this section the translation of the usual XML merge operation within our uncertain versioning model.
A merge operation considers a set of versions and integrates their content in a single new one. We view this outcome as obtained via a three-way merge 4, that is, an integration of the changes from the inputs with respect to their common base version. We focus here on merging two versions which is the most common case in real applications. However, an extension to n > 2 versions is straightforward. In addition, we also assume that all the merged versions are only originated from updates over the base versions, i.e., we do not consider merging of versions with a different merge history – this is again for the sake of clarity of the exposition.
The merge process usually implies two steps: a) an extraction of the different sets of edit scripts that have led to the input versions and; b) a generation of the merge result by evaluating a unified set of the extracted edit scripts over the initial data. This last step must deal with possible conflicting edits (for the definition of conflicts, see next) due to concurrent changes (i.e., when two editors independently changes the same piece of data). The resolution of conflicts may yield several different content items for the merge. As a result, each possible merge outcome is obtained by making a choice between several possible edits. This naturally fits in the system with uncertainty handling because in such a setting there is no longer only one truth but several different possibilities, each with a certain probability of validity.
We first present the process of computing the edit scripts to use for the merge, as well as common merge scenarios. Then we introduce the semantics of merging uncertain multi-version XML documents, as well as an efficient algorithm on the probabilistic XML encoding. 4.1
Assume an unordered XML document under version control. Let us consider two arbitrary versions T1 and T2, along with their common lowest ancestor Ta, of this. 4A three-way merge enables a better matching of nodes and detection of conflicts.
G )
We do not assume here given any explicit edit script. Instead
of this, we include edit detection as an integral part of the merge
process for the sake of generality. We define the edit script
specifying the merge of versions T1 and T2 through the three-way diff
algorithm diff3(T1, T2, Ta) on unordered trees with unique
identifiers for nodes. The algorithm will return a script with only node
inserts and deletes as edit operations. Like in [
• diff2(Ta, T1) initially matches the nodes in trees Ta and T1 in order to find out the shared, deleted, and inserted nodes. Then, the algorithm encodes the matches in terms of a set of node insertions and deletions which evaluated on Ta give T1. A node x ∈ Ta with no match in T1 is deleted, whereas a node y ∈ T1 with no match in Ta is added. Let us denote this edit script by Δ1.
• diff2(Ta, T2) follows the same process and provides the script Δ2 leading to T2 from Ta.
A more global edit script, referred as Δ3, models the final value of the diff3; Δ3 is obtained by mixing Δ1 and Δ2. We describe this combination with three types of edits as follows.
Equivalent edits. An equivalence occurs between all edits in Δ1 and Δ2 with the same semantics and the same arguments (same identifiers and same labels). Specifically, two insertions u2 ∈ Δ1 and u4 ∈ Δ2 are equivalent if they specify the same node identifier and the same label to be added. As for deletions in Δ1 and Δ2, there is an equivalence between two if these target the same node. Given two equivalent edits, only one of the two operations is kept in Δ3. Conflicting edits. Any two given operations u2 ∈ Δ1, u4 ∈ Δ2 are conflicting edits when they come with different semantics, i.e, if u2 is an insertion, then u4 is a deletion (and conversely), and the insertion has added some new nodes as descendants of the node that is removed with the delete operation. We introduce conflicted edits in Δ3 to be those satisfying the properties given above. Given that, we refer to the set of all conflicting edits in Δ3 with ΔC . We say that a node handled by conflicted edits is a conflicted node. Independent edits. Those edits in Δ1 and Δ2 that do not belong to the two first classes. The set of equivalent and independent edits form the non-conflicted edits of a given diff algorithm. A node impacted by a non-conflicted edit is a non-conflicted node for a given merge operation. (Note that conflicted and non-conflicted nodes together form the set of all nodes impacted by edit scripts in Δ3).
Now, let us briefly present the merging scenarios (cf. usual merge
options, especially mine-conflict and theirs-conflict, in tools like
SubVersion [
A large majority of current versioning models provide three common merge scenarios that consider the resolution of possible conflicts. Recall that in most cases, this resolution is manual, that is, it requires user involvement. Let Tm be the outcome of the merge of T1 and T2. We formalize the possible merge scenarios as follows.
1. First, one would like to perform the merge based on T1 and by updating this with the non-conflicted edits from Δ2. For this
C case, we have Tm = [T1]Δ2−Δ .
2. The second scenario is symmetric to the first one: it considers as a base version T2 and fetches the non-conflicted edits from Δ1. C For this case, we set Tm = [T2]Δ1−Δ .
3. Finally, the last case maps to the update of the common version Ta with the non-conflicted edits in Δ3, that is, one would like to reject all the conflicting edits in the merge outcome. For this
C case, we set Tm = [Ta]Δ3−Δ .
It is straightforward to show that when ΔC = 0/, then we obtain the same content for the three merge scenarios. This observation is inherent to the computation of the edit scripts and the definition of the merge outcome in each scenario. Observe that we do not deal with the (intuitive and naive) merge case where the user corrects the conflicting parts with new inputs. However, this case can be simply treated by first choosing one the three outcome above and then by performing updates over this. 4.2
We now introduce our abstraction of the merge operation (covering at least the set up of the merge scenarios above) within the uncertain multi-version XML document model.
For sure, an uncertain context induces an inherent uncertain merge; involved versions and diffs come with uncertainties. Let Tmv = (G , Ω) be an uncertain multi-version XML document with n staged version control events. In addition, we consider Tcmv = (G , Pc) as the probabilistic XML encoding of Tmv. Recall again that each version of Tmv is identified with a particular event in G , the one representing the tail of the branch of G leading to this version. We reason on events instead of full versions since these are here uncertain and can be defined in an arbitrary manner using events. This section introduces the formalism of the merge operation over any uncertain multi-version XML document and the mapping algorithm over its probabilistic XML encoding. 4.2.1
With the help of the triple (e1, e2, e′), we refer in our setting with uncertainty to a merge operation as MRGe1,e2,e′ where e1 and e2 point to the two versions to be merged and e′ is a new event assessing the amount of uncertainty in the merge operation. We evaluate the semantics of such a merge operation over Tmv with uncertainty as follows.
MRGe1,e2,e′ (Tmv) := (G ∪ ({e′}, {(e1, e′), (e2, e′)}), Ω′).
On the one hand, this evaluation inserts a new event and two edges in the version space G . On the other hand, it generates a new distribution Ω′ which represents an extension of Ω with new possible versions and event sets. Let Ae1 and Ae2 be the set of all strict ancestor events in G of e1 and e2 respectively. We denote the common set by As = Ae1 ∩ Ae2 . For all subset F ∈ 2V ∪{e′}, formally we set: • if e′ 6∈ F : Ω′(F ) := Ω(F ); • if {e1, e2, e′} ⊆ F : Ω′(F ) := Ω(F \ {e′}); • if {e1, e′} ⊆ F and e2 6∈ F : Ω′(F ) := [Ω((F \ {e′}) \ (Ae2 \ As))]Δ2−ΔC ; • if {e2, e′} ⊆ F and e1 6∈ F : Ω′(F ) := [Ω((F \ {e′}) \ (Ae1 \ As))]Δ1−ΔC ; • if {e1, e2} ∩ F = 0/ and e′ ∈ F : Ω′(F ) := [Ω((F \ {e′}) \ ((Ae1 \ As) ∪ (Ae2 \ As)))]Δ3−ΔC ;
We consider the aforementioned edit scripts as all obtained via the diff3 process sketched in Section 4.1.1. For each involved case, the diff3 is executed on the (uncertain) arbitrary versions T1 = Ω((F \ {e′} ∩ Ae1 ) ∪ {e1}) and T2 = Ω((F \ {e′} ∩ Ae2 ) ∪ {e2}), and Ta = Ω(F \ {e′} ∩ As) where F is the subset of events in V ∪ {e′} considered as valid.
EXAMPLE 4.1. Figure 2 describes the process of merging two possible versions, denoted by T1 and T2, from Figure 1 given their common base Ta. In our proposal, this operation is simply encompassed with the merge specified over events e3 and e4 which point to the two input versions. On the left-hand side of the example, we provide the versions T1, T2 and Ta together with edit scripts {u2, u4} and {u3} that led to them from the base Ta. Typically, we view these scripts as given by diff functions outlined in Section 4.1.1 based on full versions. The right-hand side in Figure 2 explains the process of merging T1 and T2 (with the merge event e′ evaluating the uncertainty in the merge) as follows: (i) First, all the edits in the scripts above coming with no conflicts, i.e., here only u4 are validated for building the part of the merge (seen as an intermediate outcome) that is certain with the existence of e′; (ii) Then, generating the set of possible merge items by enumerating the different possibilities with the conflicting edits u2 and u3. The two initial possible results are obtained by propagating respectively u2 and u3 given the intermediate outcome. Such a propagation will give in the first case a merged version that only contains the sub-tree s2, and in the second case a merged version with the sub-tree s1 (including nodes p1 and p′1) in addition. Concretely, our merge approach will compute the same merged documents by first considering the input versions T1 and T2, and then by updating these with the edits without conflicts respectively from {u3} and {u2, u4}. Finally, the last possible content for the merge is obtained by discarding all the conflicting edits and by combining the concurrent nodes in the base version with the intermediate result.
The uncertain merging operation as formalized above remains however intractable since it requires to evaluate every possible version for computing the overall merge result. Below, we propose a more convenient way to do this merge. 4.2.2
We efficiently present the semantics of the merge operation in Tcmv as Algorithm 1, namely mergePrXML. Prior to a deeper description of the proposed algorithm, we start by introducing the notion of conflicted nodes in the PrXMLfie probabilistic encoding given the merge of events e1 and e2.
The history of edits over any specific node in Pcis encoded with its attached formula. We base on this for detecting the conflicted nodes. Let us set the following valuations of events in G : (i) νs setting the events in As to true and the revision variables of all other events to false; (ii) ν1 assigning a true value to the events in Ae1 ∪ {e1} and a false value to the revision variables of the other events and finally; (iii) ν2 setting the events in Ae2 ∪ {e2} to true and all the revision variables in the remaining events to false.
We first introduce the lineage of an uncertain node in the PrXMLfie p-document.
DEFINITION 4.1. (Node lineage) The lineage formula of a given node x ∈ Pc, denoted by fie↑(x), is the propositional formula resulting from the conjunction of the formula of this node x with the formulas attached to all its ancestor nodes in Pc.
Instead of its formula5, the lineage of a given node in the pdocument encodes the entire history of edits, starting from the initial event, over the path leading to this node. Given that, we can approach the conflicted nodes in the p-document using their lineage formulas as follows.
DEFINITION 4.2. (Conflicted node) Under the general syntax Tcmv, we say that a given x in Pcis a conflicted node with respect to the merge implying the events e1 and e2 when its lineage satisfies the following conditions: 1. fie↑(x) |= νs; 2. fie↑(x) 6|= ν1 (or fie↑(x) 6|= ν2) and; 3. ∃y ∈ Pc, desc(x, y): fie↑(y) 6|= νs and fie↑(y) |= ν2 (or fie↑(y) |= ν1) where desc(x, y) means that y is a descendant of the node x.
PROPOSITION 4.1. Definition 4.2 is consistent with the definition of conflicted nodes given in Section 4.1.1.
PROOF. (Sketch) Let x in Pc be a conflicted node such that 1) fie↑(x) |= νs; 2) fie↑(x) 6|= ν1; 3) fie↑(y) 6|= νs and fie↑(y) |= ν2 with desc(x, y) true. The relation 1) yields x ∈ νs(Pc) which is a document corresponding to the common lowest ancestor of the versions ν1(Pc) and ν2(Pc). The relations 2) means that x 6∈ ν1(Pc), i.e., in the history of edits that gave ν1(Pc) from νs(Pc) there was at least a deletion u2 over the node x. This is implied by the way updPrXML() proceeds. Besides that, 3) enables us to write in one side x ∈ ν2(Pc) since y ∈ ν2(Pc) and on another side y 6∈ νs(Pc). As a result, in the history of edits that led to ν2(Pc) from νs(Pc) there was an insertion u4 which added y as a child of x. In other words, u2 and u4 define two conflicted edits performed on the same node x.
A conflicted node in Pc results in conflicting descendants. We refer to the conflicted set of nodes in Pc according to the merge of events e1 and e2 as the restriction Pc|C{e1, e2} . Under this, we infer below the non-conflicted set of nodes.
DEFINITION 4.3. (Non-conflicted node) For the merge of events e1 and e2, we define a non-conflicted node x as a node in Pc\ Pc|C{e1, e2} having a formula fie(x) satisfying one of the following conditions. 5The formula just describes the semantics of edits from the event where the node was inserted for the fist time. s2 p2 t2 Pc\ Pc|C{e1, e2} is consistent with one of the following formulas. 1. Vei∈Fs (ei) ∧ ¬ Vej∈(F1∪F2) (e j) 2. Vei∈F1 (ei) ∨ Vej∈F2 (e j) 5. Vei∈F1 (ei) 6. Vei∈F2 (ei)
Let us continue this section by first describing mergePrXML, then by demonstrating its correctness with respect to the abstraction of the merge operation in Section 4.2.1.
Input: (G , Pc), e1, e2, e′ Output: Merging Uncertain XML Versions in Tcmv G := G ∪ ({e′}, {(e1, e′), (e2, e′)}); foreach non-conflicted node x in Pc\ Pc|C{e1, e2} do replace(fie(x), e1, (e1 ∨ e′)); replace(fie(x), e2, (e2 ∨ e′)); return (G , Pc)
Algorithm 1: Merge Algorithm (mergePrXML)
Algorithm 1 considers as inputs the probabilistic encoding (G , Pc) of an uncertain multi-version XML document Tmv, the events e1 and e2 of G , and the new event e′ modeling both the merge content items and the amount of uncertainty in these. Given that, mergePrXML first updates G as specified in Section 4.2.1. Then, the merge in Pc will result in a slight change in formulas attached to certain non-conflicting nodes in Pc\ Pc|C{e1, e2} . The function replace modifies such formulas by substituting all occurrences of e1 and e2 by (e1 ∨ e′) and (e2 ∨ e′) respectively. The idea is that each possible merge outcome, which occurs when e′ is valuated to true regardless of the valuation of the other events, must come with at least the non-conflicted nodes from Pc seen as valid with e1 and e2. The remaining non-conflicted nodes, whose existence are independent of e1 and e2, will depend uniquely on the valuation of their ancestor events in each given valid event set including e′. At least, the validity of a conflicting node in a merge result relies on the probability of e1 and e2 when the event is e′ certain. If e′, together with e1, are only valuated to true, we say that e1 is more probable than e2 for the merge; in this case, only conflicted nodes valid with Ae1 ∪ {e1} are chosen. The converse works in the same manner. Any conflicted node will be rejected with a valuation setting e′ to true and the revision variables in both e1 and e2 to false.
Assume an uncertain multi-version XML document Tmv = (G , Ω) and the corresponding probabilistic XML encoding Tcmv = (G , Pc). In addition, let us define J.K as the semantics operator which, applied on Tcmv, yields its correct semantics JTcmvK = (G , JPcK) such that G is the same as in Tmv and JPcK defines the same probability distribution over a subset of documents in D than Ω. Given a merge operation MRGe1,e2,e′ , we now show the main result of this paper:
PROPOSITION 4.3. The definition of Algorithm 1 is correct with respect to the semantics of the merge operation over the uncertain multi-version XML document. In other words, the following diagram commutes: mergePrXML (e1, e2, e′)
Tcmv Tcm′v
J.K J.K
JTcmvK JTcm′vK
MRGe1,e2,e′
(
MRGe1,e2,e′ (JTcmvK) = (G ′, Ω′)
Tcm′v = (G ′, Pc′) and JTcm′vK = (G ′, Ω′′)
Seeing that we reach the same version space using mergePrXML is trivial. Now, we have to show that to Ω′ will correspond JPc′K; that is, Ω′ = Ω′′. Given each set F ⊆ V ′, five scenarios must be checked for this equality.
1. For each subset F such that e′ 6∈ F , we have Ω′(F ) = Ω(F ). By definition, Ω(F ) = ν (Pc) where ν is a valuation setting the special revision variable in e′ to false and the other events to an arbitrary value. Abstracting out the formulas, we can claim that Pc ∼ Pc′ regarding mergePrXML. Since e′ 6|= ν , the result of the evaluation of ν over (e1 ∨ e′) and (e2 ∨ e′) (or their negation) only depends on the truth values of e1 and e2 respectively. Thus by replacing in formulas of Pc′ all occurrences of (e1 ∨ e′) and (e2 ∨ e′) by e1 and e2 respectively, we are sure to build a p-document Pc′′ with ν (Pc′) = ν (Pc′′). But by the definition of mergePrXML, Pc′′ is exactly Pc. As a result, we obtain ν (Pc) = ν (Pc′). Knowing beforehand that Ω′′(F ) = ν (Pc′), we can state that Ω′(F ) = Ω′′(F ) for any F ⊆ V ′ \ {e′}.
2. For each subset F such that {e1, e2, e′} ∩ F 6= 0/, we have Ω′(F ) = Ω(F \ {e′}). Let ν be a valuation setting all the events in F \ {e′} to true, the revision variable in e′ to an arbitrary value and the revision variables in the remaining events to false. Since e′ does not occur in formulas in Pc, we can write Ω(F \ {e′}) = ν (Pc) for sure. At this step, we resort to the logical consequences (e1 |= ν ) ⇒ ((e1 ∨ e′) |= ν ) and (e2 |= ν ) ⇒ ((e2 ∨ e′) |= ν ) regardless of the truth-value of the event e′. In the same way, (¬e1 6|= ν ) ⇒ (¬(e1 ∨ e′) 6|= ν ) and (¬e2 6|= ν ) ⇒ (¬(e2 ∨ e′) 6|= ν ). Therefore, by substituting in formulas of Pc′ all occurrences of (e1 ∨ e′) and (e2 ∨ e′) by e1 and e2 respectively, we obtain the old p-document Pcwith ν (Pc′) = ν (Pc) given the semantics of mergePrXML. Moreover, Ω′(F ) = ν (Pc) because Ω′(F ) = Ω(F \ {e′}) and Ω(F \ {e′}) = ν (Pc). So by inference, we can demonstrate that Ω′(F ) = Ω′′(F ) using the relations Ω′(F ) = ν (Pc), ν (Pc) = ν (Pc′) and ν (Pc′) = Ω′′(F ) 6.
3. For each subset F such that {e1, e′} ∩ F 6= 0/ and e2 6∈ F , we have Ω′(F ) = [Ω((F \ {e′}) \ (Ae2 \ As))]Δ2−ΔC . Let F1+ = ((F \ {e′}) \ (Ae2 \ As)) be the set of valid events excepting the valid ancestor events of e2 in F ∩ (Ae2 \ As). For the valuation ν setting all the events in F1+ to true and the revision variables in the remaining events to false, Scenarios 1 and 2 enable us to write ν (Pc) = Ω(F +
1 ) and ν (Pc) = ν (Pc′). Now, we just need to show that [ν (Pc′)]Δ2−ΔC = ν ′(Pc′) (ν ′ being the valuation that sets all the events in F to true and the revision variables in all others to false) to obtain the expected proof, that is, Ω′(F ) = Ω′′(F ). Let us set Δ = Δ2 − ΔC . We distinguish the two following cases. (a) For the class of nodes x in ν (Pc′) unmodified by Δ. That is, x ∈ ν (Pc′) and x ∈ [ν (Pc′)]Δ. For each node x in this class, fie↑(x) in P ′ requires the trueness of events in F + since x ∈ ν (Pc′).
c 1 Moreover, by the definition of Δ, x may be either a conflicted node or its existence is independent of the values of events in (F ∩ (Ae2 \ As)) ∪ {e2}). If x is a conflicted node, it is intuitive to see that fie↑(x) in Pc′ is satisfied if events in F + are all set to true and not if only those in (F ∩ Ae2 ) are set to 1true (cf. Definition 4.2.1 and updPrXML). In the another case, fie↑(x) is only function of the values of events in F1+ for the set F (typically when fie↑(x) is Expression 5 in Lemma 4.1 with F1 = F1+ ∩ ((Ae1 \ As) ∪ {e1})). In both cases, we can state that fie↑(x) |= ν ′ since ν ′ similarly to ν sets all the events in F1+ to true. As a result, we have x ∈ ν ′(Pc′) when x belongs to this class. (b) For the class of nodes x ∈ ν (Pc′) handled with Δ. Let x 6∈ [ν (Pc′)]Δ, that is, there is an operation u in Δ that removes x from ν (Pc′). By the construction of Δ, it is easy to show that fie(x) in Pc maps to Expression 3 in Lemma 4.1 with Fs = F1+ ∩ As, F1 = F1+ ∩((Ae1 \As)∪{e1}) and F2 = (F ∩(Ae2 \As))∪{e2}. In Pc′, this formula fie(x) is just updated across Algorithm 1 by replacing the events e1 (the disjunction) in the first member and e2 in the second one respectively by (e1 ∨ e′) and (e2 ∨ e′). Since ν ′ sets all the events in F to true, therefore the first member of fie(x) will be valuated to true while the second member will be valuated to false. As a consequence, clearly we can state that fie(x) 6|= ν ′, i.e., x 6∈ ν ′(Pc′). In summary, we proven that for each node x in ν (Pc′) deleted with Δ, x is also not chosen by ν ′ in ν ′(Pc′). Note that the case where x does not occur in ν (Pc) is trivial and it corresponds to a scenario in which fie(x) maps to Expression 1 in Lemma 4.1 with Fs = F1+ ∩ As, F1 = F1+ ∩ ((Ae1 \ As) ∪ {e1}) and F2 = (F ∩ (Ae2 \ As)) ∪ {e2}. Now, let x 6∈ ν (Pc′) and x ∈ [ν (Pc′)]Δ. That is, there is an insertion u in Δ that adds the node x as a child of a node y in ν (Pc′). Let F2+ = (F \ {e′} ∩ Ae2 ) be the set of all valid ancestor events of e2 in F . By the definition of Δ, we can state that the formula fie(x) of x in Pcmaps to Expression 4 or 6 in Lemma 4.1 with Fs = F1+ ∩ As, F1 = F1+ ∩ ((Ae1 \ As) ∪ {e1}) and F2 = (F ∩ (Ae2 \ As)) ∪ {e2}. If fie(x) is Expression 4, this formula in Pc′ is updated by Algorithm 1 which replaces e1 in the first member (the conjunction) and e2 in the second member by (e1 ∨ e′) and (e2 ∨ e′) respectively. Since ν ′ sets all the events in F to true, the first member of fie(x) will be valuated to false. As for the second member, it will be valuated to true under ν ′ because all the events in F2 are set to true and (e2 ∨ e′) |= ν ′. As a result, ν ′ 6The last relation is due by the fact that the events e1 and e2 are both valuated to true. will select x in ν ′(Pc′) since fie(x) is such that fie(x) |= ν ′. Otherwise, if fie(x) is Expression 6, it is updated in Pc′ by mergePrXML which substitutes e2 by (e2 ∨ e′). Given that it is straightforward to prove that fie(x) |= ν ′ since all the events in F2 are set to true and (e2 ∨ e′) |= ν ′.
Scenarios (a) and (b) demonstrate that when x ∈ [ν (Pc′)]Δ, then x ∈ ν ′(Pc′). Similarly, the converse can be reached. We conclude [ν (Pc′)]Δ = ν ′(Pc′) which joint with ν (Pc′) = Ω(F1+) and ν ′(Pc′) = Ω′′(F ) yield [Ω(F1+)]Δ = Ω′′(F ). At last, the result Ω′(F ) = Ω′′(F ) relies on Ω(F ) = [Ω(F1+)]Δ.
4. For each subset F such that {e2, e′} ∩ F 6= 0/ and e1 6∈ F , we have Ω′(F ) = [Ω((F \ {e′}) ∩ (Ae2 ∪ {e2}))]Δ1−ΔC . This scenario is entirely symmetric to Scenario 3.
5. For each subset F such that {e1, e2} ∩ F = 0/ and e′ ∈ F , we have Ω′(F ) = [Ω((F \ {e′}) \ ((Ae1 \ As) ∪ (Ae2 \ As)))]Δ3−ΔC . Let set F ′ = (F \ {e′}) \ ((Ae1 \ As) ∪ (Ae2 \ As)). Given a valuation ν setting all the events in F ′ to true and the revision variables in all other events to false, we can write Ω(F ′) = ν (Pc) and ν (Pc) = ν (Pc′) according to Scenarios 1 and 2. Similarly to Scenario 3, we have now to demonstrate that [ν (Pc′)]Δ3−ΔC = ν ′(Pc′) (where ν ′ is the valuation setting all the events in F to true and the revision variables of all the remaining events to false) to obtain that [Ω(F ′)]Δ3−ΔC = ν ′(Pc′). This result will be sufficient for stating that Ω′(F ) = Ω′′(F ) since by definition Ω′(F ) = [Ω(F ′)]Δ3−ΔC and ν ′(Pc′) = Ω′′(F ). Let us consider Δ = Δ3 − ΔC . For the proof, the intuition here is to see that by implementation Δ can be rewritten as (Δ1 − ΔC ) ∪ (Δ2 − ΔC ) on one side. So, if we arrive to show that for all the nodes x, y such that x ∈ [ν (Pc′)]Δ1−ΔC
C and y ∈ [ν (Pc′)]Δ2−Δ , then x ∈ ν ′(Pc′) and y ∈ ν ′(Pc′), we can trivially deduct that for each node x ∈ [ν (Pc)]Δ, then x ∈ ν ′(Pc′). These relations can be proven in the same spirit as in Scenario 3 by just noting that: (a) For the set of unmodified nodes x in ν (Pc′) with Δ, fie(x) in Pc is compatible to Expression 1 in Lemma 4.1 with F1 = F ′ ∩As, F1 = (F ∩(Ae1 \As))∪{e1}, and F1 = (F ∩(Ae2 \ As)) ∪ {e2}. (b) For the set of nodes x in ν (Pc′) handled with Δ. If the operation comes from (Δ1 − ΔC ), fie(x) is compatible to Expression 3 or 5 in case of insertions and this formula maps to Expression 4 for deletions. Concerning operations in (Δ2 − ΔC ), fie(x) is compatible to Expression 4 or 6 for insertions and to Expression 3 for deletions.
Furthermore, the inclusion in the opposite direction, that is for each node x ∈ ν ′(Pc′), then x ∈ [ν (Pc′)]Δ, is obvious for nodes unchanged by Δ. For the other nodes, we only need to verify that they are correctly handled by Δ in ν (Pc′) depending whether it corresponds to an addition or a deletion in this document. Following that, we can state that Ω′(F ) = Ω′′(F ) holds for each subset F of events in V that contains e′ but not e1 and e2.
PROPOSITION 4.4. mergePrXML performs the merge over the encoding of any uncertain multi-version XML document in time proportional to the size of the formulas of nodes impacted by the updates in merged branches.
PROOF. (Sketch) The intuition behind the time complexity is that mergePrXML results in a constant-time update of DAG G , firstly. Secondly, by viewing Pc as an amortized hash table, the algorithm retrieves any node impacted by a (non-conflicting) update in constant time. Finally, the replace method only depends on the lengths of formulas. 5.
We presented in this paper a merge operation, as well as an
efficient mapping algorithm, that supplements our uncertain
multiversion XML framework presented in [
This work was partially supported by the Île-de-France regional DROD project, and the French government under the STIC-Asia program, CCIPX project. We would like to thank the anonymous reviewers for their valuable suggestions on improving this paper.