Automatically merging relational data Background
Semiautomated file merging is a critical part of version control systems (all the ones I've used anyway!). This is usually accomplished on textual source code without the tool understanding the underlying language – although semantic merging also exists.
I'm interested in whether merging relational data has been researched, and what the findings have been.
Specifically, I'm imagining that a single relational database is &quot;forked&quot; in to two (or more) independent copies. That independent changes are made to these copies, and that we then want to recombine these databases in to one again, which reflects the changes in each.
What this question isn't
I'm not asking a question about specific technologies here, although that would be interesting. I'm definitely not asking about SQL based technology sepecificaly. I'm also specifically interested in relational data, and not tree data like XML, JSON, or ASTs, etc.
I'm also not asking about integrating heterogeneous databases or information stores, which seems to be the subject of Data integration. For the purposes of this question, it can be assumed that the databases will have the same schema and this doesn't change.
Some ideas about how this might work
Relational data is, basically, sets. Sets, in principle, have (several) sensible merge semantics, even when the common base isn't known, such as for a commutative replicated datatype set.
There are obviously some basic issues, such as generating identities. If identities are simple incrementing numbers, then these become extremely hard to merge. This problem seems to be solved by using globally unique identifiers.
Incrementing identifiers seems to be a specific case of a more general problem. It is an example of inserting a new fact in to the database that has been derived from the current state of the database.
In general, I suspect that any fact added to the database that is derived from the existing facts in the database, rather than simply new information collected from the outside world, is a potential source of difficulty during a merge. I wonder if this is a huge problem, or one that can be avoided for the most part by something like normalisation?
For example: if we adjust a balance by looking up the current balance and adding or decrementing, then this is hard or impossible to merge. However, if we store individual increments and decrements, this information is trivial to merge. When we need the balance, we should compute it from the data we've got.
Problems also arise for integrity constraints. Following naive set merging, a primary key may no longer be a primary key. However, it seems like it might be possible to automatically determine where this could happen from the database schema, and then have the user choose a resolution scheme, or default to some sensible one if such a schema exists. Note: it is possible to keep an audit, show conflicts as they arise, and have a user revert a decision later, as is done with version control systems.
I'm interested in whether merging relational data has been researched, and what the findings have been.


Here are several papers mainly on the tree-to-tree editing problem. A lot of good stuff is related to XML documents.


Diffing, Patching and Merging XML Documents
The tree-to-tree editing problem
The Tree-to-Tree Correction Problem
Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
Change Detection in Hierarchically Structured Information
Efficient Snapshot Differential Algorithms for Data Warehousing
Detecting Changes in XML Documents
Meaningful Change Detection in Structured Data


A record in a database can be considered a simple tree of just a single row of children (the fields) or perhaps extending to the relations the record points to. With that you can do tree diffing/merging using the techniques outlined in these papers, and adding to it any column-specific string diffing techniques.

You could then add extra database-specific heuristics to the diffing system to make it more useful. For example, you have the extra metadata of the schema of the database, which provides a lot of information.