Thursday, November 3, 2011

Details on the ontology engine

Using convolution model, consider two graphs, G1,G2:
G1 = (a.b,b.c.d,g.k.l)
G2 = (x.y,a.b,g.b.(c,x,g.k))

how is G3 = convolve(G1,G2) = (a.b,b.c,g.k) computed?
For each of the (comma separated) subgraphs, G1[i], compute:
G3partial = convolve(G1[i],G2). The traversal breaks down into a continual subdivision of convolutions.

In the execution engine there is a hand off between G1 and G2. G1 traverses G2 until G1 requires a match. G2 then takes over attempting to traverse G1 down to a match. If either branch is traversed to a null teminator, then the G3 pointer is backed up and recent G3 creation is deleted as both G1 and G2 back up and retry. If G and G2 find match their mutual nodes, then the G3 stack is updated and recent G3 updates retained. We get relative traversal, each graph traversing the other. We are guaranteed to traverse all matches between G1 and G2.


Astute readers may note that the outcome, G3, depends on the peculiarities of what is a match.

The main loop of the open source ontology engine:

Traverse G1 until node match required.  
Traverse G2 until node match required.
If keywords match then push G3, otherwise pop G3.
Jump back on G1 and G2 to the next node in line and/or continue.

Gremlin graph script appears in node sequences in either G1 or G2. Most Gremlin operations are simple pass, but conditional operators in Gremlin become match required. Each of the gremlin nodes can update G3, update its own keywords, but cannot update the opposing graph.

No comments: