Diffing and journaling xml documents

I am somewhat sleepy but I think its time I ill advisedly hurled some thoughts into my blog.

I inherited a project recently that I got around to finally working on involving synchronizing network device data in a db using diffing/journaling using xml documents.

The problem with finding the difference between two xml documents or anything for that matter is deciding on a set of operations that will be used to transform one to the other. Then real problem though in the case of my problem is given two xml documents what is the optimal set edits that transform one to the other.

Traditionally utilities like diff find the LCS to minimize the number of edits. In this case I wanted the edits to be as granular and as simple as possible. With a one to one correspondence it makes updating things like a database with the change set an easy task.

The method for actually determining what is different in an xml document is the interesting part however. In the case of structured data like xml you often have collections of entities such as network interfaces which all have some defining characteristic such as a name or id code. This can be used as a key to compare the nodes in the xml tree so that even if they are out of order they can still be properly compared.

The reason for wanting to be able to handle unordered collections of things (sets some might call them) stems from the initial problem it self mainly lack of information. If for some reason the interface is discovered in a different order you really don't want adds and deletes generated simply because it moved.

The way this all ends up being computes is using xpath expressions. One expression expression to determine a node set in each document that is potentially comparable and another to which is applied to each individual node in each document which returns the key used for determining if the nodes have the same name/identity.

Sometimes problems are only as simple as you allow them to be. In this case a fully generic diff or comparison on a pair of xml documents hardly makes sense. Without some information about the meaning of the documents the data that would have a high potential for being unwieldy and useless.

Of course I have thought about abandoning the diff/journaling model all together but unfortunately having a list of exact changes that have taken place is too useful.