I have to model a graph (or might be seen as an recursive tree(s) because it typically like a single or few roots) according to things getting children:

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

Now you will find implicit pathways, a/c/f and recursive ones too: a/b/d/a/b/d/...

After which I have to set things around the graph using a path expression, both qualities about the subject (these pathways have color: blue, or such) as well as altering their kids--possibly getting rid of/hiding them, or adding new children.

By path expression, I am talking about something similar to this:

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

indicates all pathways that begin with a/b/ possess the property color = "blue". So, basically queried for that colour of a/b/d/a/b/d/a, it might return blue. But when I queried for that colour of only a, at this time there's none.

Other expressions may be:


So, that might be accustomed to make claims. I want similar method of doing querying. I want simple queries for example:


and much 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 may be added anytime.

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

I want the queries next to complement properly all of the claims. So quite simply, I can not just operate a query and hang a house on all of the results, since that time it will not affect something totally new added later.

Not to mention, I want so that it is extremely fast :) I'd dress in an order of thousands of nodes, thousands of path expression claims, and query on 100,000's of path expressions.

Can there be something which handles this kind of factor well?

I investigated RDF/OWL type of factor however it does not appear to possess any support for pathways.

Basically understand your question properly, you're speaking about querying against implications made against object associations. If that's the case, you have to have a look at RDF and SPARQL http://www.w3.org/TR/rdf-sparql-query/ and also the whole area of semantic content.

On the similar problem, I wound up applying my very own Trie (during my situation, in Java) having a Node class that consists of Node children and has the capacity to see if the leftover path matches it (which suggests that its forefathers eco-friendly lighted their slice of the road before it.

It's pretty fast and also the code's quite compact. Hope it will help!

unsure if this is just what you'll need but in my experience it may sound like oracle's CONNECT BY and begin WITH clauses.

for example you might have a table known as NODES with one of these posts:

  • ID as primary key
  • PARENT_ID pointing to ID of the same table
  • COLOR ... and other things you'll need

and then suggest this type of query


adding whatever clause you'll need i.e. WHERE COLOR='BLUE' additionally, it includes a nocycle condition for the a/b/d/a/b/d example

here's more information


From things i understand from the question you need to model a tree that may support recursive. I'm able to answer from sql table design perspective. You will find two ways to get this done 1) make use of an adjaceny model in which you will keep type in one column and also the child within the other

Parent Child
Null   A
A      B
A      C
B      D
B      E

2) Use a Left Hands Value and Right Hands Value as understood to be a Nested Set Model which has good performance. Look at this article in the SQL guru Joe Celko and you'll have more hints http://en.wikipedia.org/wiki/Nested_set_model