Can graph query (non-cyclic, non-duplicated) ancestors and descendants?

graph

(Will Fitzgerald) #1

So assume we have documents have a field children, which can contain the ids of other documents. For example:

{_id: 1 :children [2, 3, 4]}
{_id: 2 :children [5, 6]}
{_id: 3}
{_id: 4}
{_id: 5 :children [6, 7, 8]}
{_id: 6}
{_id: 7}
{_id: 8}

Is there a graph query that will gather all the ancestors of 8? (i.e., [1, 2, 5]) All the descendants of 2 (i.e, [5, 6, 7, 8])? The ancestors of 5 (i.e., [1,2])? The descendants of 5 (i.e., [6, 7, 8]).

This, of course, in one query call.

Can the ancestors query be done efficiently (with, perhaps, a total depth of 10)?

Can the descendants query be done efficiently (with, perhaps, thousands or tens of thousands of descendants)?


Graphing parent-child relationship tree
(Mark Harwood) #2

Short answer is "no" plus here is the longer answer:

Is there a graph query that will gather all the ancestors...in one query call

Not with that data structure. The challenge is you have to take a value from one field, "_id" and use it in a query to another, "children" then vice-versa. This would require you to tell us about these fields where values from one can be used in another to map out the link structure. That's a level of complexity we've chosen not to add at this stage.

I did consider an alternative data model with a "MeAndMyParent" field with two values e.g. "MeAndMyParent": [6,5] but another implicit part of an ancestor crawl is that you don't go up to a parent ID then follow down to brothers and cousins etc. The general-purpose graph exploration logic doesn't have any in-built support for enforcing the special-case rules that apply to following up tree structures.

Cheers
Mark


(system) #3