13

I'm hoping to write an algorithm to synchronize two hierarchical structures. These structures could be object graphs, data stored in relational database tables, etc (even two different structures, so long as they have comparable keys). The synchronization will be one-way, i.e., one structure will be the prototype, and the other will be modified to match.

Let's say we have a sync function. It would need to accept the following:

  1. objA -- the prototype
  2. objB -- the object to be modified
  3. keyA -- key generating function for objA
  4. keyB -- key generating function for objB
  5. addB -- function to create an objB (returns id of new objB)
  6. setB -- function to update objB
  7. remB -- function to delete an objB
  8. parB -- id of objB's parent -- this is passed to addB for context

So we have this:

let sync (objA:'a) (objB:'b) (keyA:'a -> 'k) (keyB:'b -> 'k)
         (addB:'p * 'a -> 'p) (setB:'a * 'b -> unit) (remB:'b -> unit) 
         (parB:'p) = ...

Now here's where I'm having trouble. 'a and 'b are hierarchical, so the function needs to know which properties of 'a and 'b it should traverse (once it compares their keys and decides they match thus far and should be further traversed). For these "child" properties, it needs all the same arguments passed to sync, but for their respective types.

This is when it became apparent this is a data structure problem. How can I chain together this information such that the root object can be passed to sync and it can traverse the graphs downward? My initial thought was to incorporate all of the arguments into a class, which would have a children property (a ResizeArray of the same type). But with various properties having different types, I couldn't figure out a way to make it work, short of throwing types out the window and making most or all of the type arguments obj.

So here are my questions:

  1. Is there a well-established method for doing this already (I haven't been able to find anything)
  2. What data structure might I use to encapsulate the data necessary to make this work?

I've tried my best to explain this thoroughly, but if anything remains unclear, please ask, and I'll try to provide better information.

Daniel
  • 47,404
  • 11
  • 101
  • 179
  • I guess you will need a intermediate data structure on which this algorithm will work, also for various type of data, you would need to transform that data to the intermediate data structure, run the algo and then transform it back to original data form – Ankur Aug 23 '11 at 05:19

2 Answers2

1

I'm sure this is oversimplifying it but here's my idea.

If this is a DAG you could do a breadth-first traversal of objA. When you enqueue a node from objA include objB and any other information you need (tuple). Then when you dequeue you fix up objB.

You could use a discriminated union to handle different child types in your enqueueing.

gradbot
  • 13,732
  • 5
  • 36
  • 69
  • Interesting idea. It might be a day or two before I can try it out. Will get back to you. Thanks for the suggestion! – Daniel Aug 21 '11 at 02:07
  • This retains the original problem which is the diverse types of the child nodes. – Daniel Aug 22 '11 at 16:12
0

Generate diffgrams from the two data structures and map the transforms to the transformed problem.

Jeremy E
  • 3,704
  • 2
  • 28
  • 46