Revision Tracking Graph

Question

Define the Revision Tracking Graph (RTG), which is an oriented graph (without circles) where each node x has a set C(x) associated with it. C(x) contains all edges on all paths from a node 0 ( C(0) = {} ). Each edge can be in a set at most once!

You can also describe this data structure by the rules for its growth:

1. Start with node 0 with associated empty set C(0) = {} = creating new object
2. For any node x create a new node y where (x,y) is oriented edge from x to y and C(y) = C(x) union { (x,y) } = versioning and branching
3. For any nodes f and t, create node r, where (f,r) and (t,r) are oriented edges and C(r) = C(f) union C(t) union { (f,r), (t,r) } = merging

Note: You can see there is no mathematical difference between creating new version and a branch. It is a semantical difference depending on whether there is already an edge leading from the node or not.

Base node is defined as a node b, such as C(b) = C(f) intersect C(t), where f and t are nodes representing two versions to be merged.

Simple Merge equation Result=To + (From-Base) = means that if we subtract every edge in C(b) from C(f) and add all edges in C(t) we get a resulting C(r) minus (f,r) and (t,r) edges exactly. No edge would appear twice and all edges in C(f) and C(t) would be represented. = 3-way merge

Complex merge equation Result = To + Sum(i=1..n) for (Fi-Bi), where Fn = From. Each edge can be in exactly one of the sets To, (Fi-Bi). For n=1 this turns into a simple merge equation. In case there exist no base in simple case, we might find sequence of F,B nodes to fit the complex equation. (1+2n)-way merge

I have actually several questions pertaining to this data structure. I am posing the first 3 for "frame of mind", as I already know the answers. And I believe question 4 directly leads to answering question 5, which I really try to get answered.

1. Prove there can be no circles in the graph
2. Prove that for certain graphs there are such nodes F,T for which base cannot be found as specified in simple equation.
3. Create algorithm to find B in simple case where n = 1.
4. Prove that for each RTG and each pair of nodes F and T, there is a set of n pairs of nodes Fi,Bi, where i=1..n to fit the complex merge equation.
5. Create algorithm to find minimum n and Fi,Bi for i=1..n where n > 1.

Answer 1

If you insist that the edges in the complex merge equation don't appear twice (eg. that the + you use is actually a disjunctive union), and you only subtract sets that are superset of one another (*), I think the assertion you want to prove (4) is actually false. Imagine RTG with 5 vertices and 6 edges:

V = { 0, a, b, c, d }
E = { (0,a), (0,b), (a,c), (a,d), (b,c), (b,d) }

now, if To = c and F = d: C(c) contains already all the edges except (b,d) and (c,d), So Sum (Fi-Bi) has to be exactly those edges. Since these edges are only contained in C(d), they must be (not necessarily both) contained in summand d-B for some B. But that is not possible, because whatever B we choose, we add also edges that are already in C(To).

(*) otherwise the assertion (2) is actually false: Result = To + (From - To) satisfies the simple merge equation for all From and To (even if it looks bizarre).

Long story short: You gave inadequate or incomplete definitions.

Q: Why do we have to state definitions rigorously if the proofs are usually trivial if the definitions are right?

A: The definitions are almost always wrong.