Is there some data structure or database that can handle path expression statements and path expression queries?

Question

I need to model a graph (or could be seen as a recursive tree(s) since it typically as a single or small number of roots) based on things having children:

a hasChildren (b, c)
b hasChildren (d, e)
c hasChildren (f, g)
d hasChildren (h, a)

Now there are implicit paths, a/c/f and recursive ones as well: a/b/d/a/b/d/...

And then I need to set things on the graph via a path expression, both properties about them (these paths have color: blue, or such) and also changing their children--perhaps removing/hiding them, or adding new children.

By path expression, I mean something like this:

a/b/** -> color = "blue"

would mean that all paths that start with a/b/ have the property color = "blue". So, if I queried for the color of a/b/d/a/b/d/a, it would return blue. But if I queried for the color of just a, at this point there is none.

Other expressions might be:

**/d/h
a/b/[color="blue"]
a/**/h

So, that would be used to make statements. I need similar way of doing querying. I need simple queries such as:

a/b/d

and more complex ones like:

a/**[color="blue"]  -- descendants that have attribute color = "blue". This could be infinite in recursive case so we can put a restriction on this type of query to have it make sense, like does such a path exist, or just return first one or something.

Also, more nodes might be added at any time.

a hasChildren (b, c, x, y, z)

I need the queries after that to match appropriately all the statements. So in other words, I can't just run a query and set a property on all the results, since then it won't apply to new things added later.

And of course, I need it to be very fast :) I would have on the order of 1000's of nodes, 1000's of path expression statements, and query on 100,000's of path expressions.

Is there something that handles this type of thing well?

I looked into RDF/OWL kind of thing but it doesn't seem to have any support for paths.

Answer 1

If I understand your question correctly, you are talking about querying against inferences made against object relationships. If so, you need to take a look at RDF and SPARQL http://www.w3.org/TR/rdf-sparql-query/ and the whole field of semantic content.

Answer 2

On a similar problem, I ended up implementing my own Trie (in my case, in Java) with a Node class that contains Node children and is able to check if the leftover path matches it (which implies that all its ancestors green lighted their chunk of the path before it.

It's pretty fast and the code's quite compact. Hope it helps!