Model graph operations

( at work our code works on permissions-controlled graphs of model objects )

It would probably be clarifying if I gave a few examples of the kinds of operation that require traversal of the model graph and decisions along the way:

1. I am deleting my dataset. My images and your images are in it. Some of the images are also in another dataset. Which images to also delete?


2. I am moving my image to a private group. However, you have added some comments to my image. What to do with those comments?


3. I have an image that shares an instrument with another image. I want to move one of the images to a different group. What to do?

( and permissions are also a constraint )

( the previous code performed poorly )

I reimplemented the operations to use a common core of graph traversal code that works more like a shortsighted rule engine: it represents the directed graph explicitly, the nodes can take various states (including, don't do anything with this and yes, we want to operate upon it), there is a list of transition rules that may match within one hop against node types and states, matching the linking property names, etc. To take, from the mini-language I had to create, a couple of real examples for moving data between groups,

• Image[I].instrument = IN:[E]{i} → IN:{r} — meaning, if we are moving an image, think about moving its instrument, if any.


• Image[E]{ia}.instrument = IN:[E]{r} → IN:{a} — meaning, if the instrument is also used by an image we are not moving, mark it to not be moved.


• IN:Instrument[E]{o} → IN:[I] — meaning, if nothing else stops the instrument from being moved, then mark it for moving.


• I1:Image[I].instrument = IN:[EI], I2:Image[E].instrument = IN triggers an error, may not move {I1} while {I2} remains as they share {IN} — the issue being that the instrument is shared between an image not being moved and an image that is.

I am glossing over a lot of detail including that the {r} node state transitions to {o} only when no other rules match, and that before accepting the above change to {a} as final we try switching it back to {r} to ensure that the rule that previously transitioned it to {a} still matches at all.

Of course, the rules are constructed so as to look out for various problems in advance, rather than checkpointing and checking if some sub-operation fails.

( this approach was difficult to devise but it works well )

I tried to keep the mini-language and its interpretation simple and restrictive. I find it interesting that I have rarely had to extend or relax the language: if it wasn't obvious how to express the rules to fulfill some requirement then some careful thought usually revealed that actually it could be done.

A worry has been that of painfully reinventing the wheel. While libraries for operating on directed graphs and upon related objects are common, I never managed to find anything that addressed the need to flexibly operate on rich subgraphs of objects in these policy-dependent ways. Surely other applications must have to address similar problems but I don't know how they do it.