Recursive GraphDB Query

[ashifshereef2k]

I was looking at the MLM engine described in the link: Multi-Level Marketing in World of Warcraft using Neo4j - Neo4j Graph Data Platform

I am trying to build an engine like this. The tree is mostly binary and I am new to graph technologies. I am trying to change from the old system because of scale issues. The original one was MySQL DB, and we had traditional hierarchical queries running through our system all the time. AS userbase exploded, since this being one giant binary tree with almost near to two million, we started running out of computing. We can’t distribute the system into a micro-service too because the tree is where all the magic happens. So I was looking for a graph implementation of the same. However, how are the time complexities working out in this MLM implementation? I am concerned about that, and the compute load – whether it us linear or logarithmic. And the degrees of freedom I would have in changing the dynamics or conditions of sales compensation – and stuff like that. Would you say, this graph implementation of an MLM engine – is it production-ready?

[andrew_bowman]

What exactly are you trying to do with this? You're asking about compute load...but for doing what?
What are the main types of queries you are trying to execute on this hierarchy?

Keep in mind that Cypher alone can't do recursive queries (you can't have a query call itself), but you can create variable-length patterns which allow you to match on and perform logic on each level of a hierarchy as you traverse relationships.

If this isn't enough and you need recursive calls, then you'll need to create your own custom procedure using Java (or a JVM language) which allows pretty much any kind of complex computation.

[ashifshereef2k]

Sorry for not being clear to begin with.
Right now, the system is MySQL and The queries are mainly hierarchical recursive queries, for the purpose of displaying the tree. So, starting from a node, we have to show all the leaves of that sub-tree, recursively, up to a depth of 25. Fetching all the leaves of that tree is the purpose.

[andrew_bowman]

Okay, so as an example if we have a root node that we can match to by some means, we can get the rest of the tree down to a certain depth.

If we had :Node nodes, and lookup of the root by its id property (given as a parameter), and wanted to get a depth of 25, and we could use variable-length pattern matching like this:

MATCH (root:Node {id:$rootId})<-[:REPORTS_TO*..25]-(leaf:Node)
WHERE NOT (leaf)<-[:REPORTS_TO]-()
RETURN leaf

This assumes that the leaf nodes you want have nobody reporting to them. If that isn't a condition, then you can remove that WHERE clause.

[ashifshereef2k]

Hello Andrew,

Thanks for the reply. I haven't yet looked into cypher; I was evaluating. And if it is positive, I may want to go for an enterprise version because we are on a path of exponential growth.

I will explaim to you the scenario.

We have Alice, Bob and Jack.

Alice adds Catherine and John.

Bob adds Philip and Irene.

Jack adds Evelyn.

Now, the second "layer" starts:

Catherine adds 2 more persons, they adds more down their depth.

This goes, like an affiliate chain, and the "layers" go down to tens of thousands of rows, with possibly millions of persons in each layer or row.

So given a random person's ID, we need to fetch all the trees recursively originating from that person, and need to be reconstructed in client side. For instance, if we need to fetch Alice's tree, it needs to have Alice's tree, which will consist of Catherin's and John's tree and it recursively go down to until we hit depth 25.

I am particularly concerned about the scalability as the tree grows.

[andrew_bowman]

Thanks for the example.

You can try this out yourself with Neo4j Desktop (free, includes developer-licensed Neo4j Enterprise).

I'm still not entirely following you about the recursive part.

When you say depth 25, that's only 25 depth from the random starting person, correct? The query I provided does exactly that. So in terms of a concise query to express finding paths out to 25 depth, that's done.

And while returning a large number of results may take more time, the key is that each traversal is O(1). In a relational database that would be a table join per traversal, each of the table joins being O(log n). The timing is therefore only proportional to the part of the graph you have to traverse, and not impacted by the total number of person nodes in the database.

[ashifshereef2k]

Thank you for the reply Andrew. I am sorry that I confused you; I was trying to apply the same terminology of recursive query in case of a graph tree also. I was wrong.

[ashifshereef2k]

And Andrew, just reconfirming. We can fetch the entire tree starting from any random node.
Now, the next business scenario would be to update the values in all the leaves in a particular sub-tree starting from a node. I am just evaluating my options from a business point of view.

[andrew_bowman]

Yes, no problems there. You already have a query to get the nodes you're interested in updating. At that point it's just a SET operation on that one variable, and that will be applied to all of those leaf nodes from the pattern match.

MATCH (start:Node {id:$startId})<-[:REPORTS_TO*..25]-(leaf:Node)
WHERE NOT (leaf)<-[:REPORTS_TO]-()
SET leaf.evaluated = true

So the only difference in the MATCH is that we're supplying the id of a node somewhere in your tree, not necessarily the root. The only thing that really changed was an adjustment of the variable from root to start for clarification, though that has no real bearing on the query. In fact, since you're not doing anything with the root or start, you can omit the variable on that node anyone, it was only present for readability purposes.

[ashifshereef2k]

Thank you Bowman. Let me try.

[ashifshereef2k]

Hello Bowman. I have this particular graph structure. As you can see, it is a binary tree-like implementation of a sales engine. With the following variable length Query, I am able to fetch all the nodes:

MATCH (d1:Distributor)-[*1..2]->(d2:Distributor)
WHERE d1.name = 'Ashif'
RETURN d1,d2

However, as you can see, I have two relationship types. Left and Right.
I need those relationship types also to be returned in the result. How can I do that?

[andrew_bowman]

You can use a path variable in the pattern, and from that you can either return the paths, or you can use nodes(path) and relationships(path) to get the list of nodes or relationships per path.

MATCH path = (d1:Distributor)-[*1..2]->(d2:Distributor)
WHERE d1.name = 'Ashif'
RETURN d2, path, nodes(path) as nodes, relationships(path) as rels

[ashifshereef2k]

Thank you Andrew. This is for the purpose of displaying it as an interactive graph in an HTML Webpage. So, a nested JSON structure seems to simplify the process. I took a look at the current data returned and it is fine - the data is there. However, it is another thing to take that JSON data and plot a tree in HTML.
Do we have some sort of mechanism which would make it easier for me to do that?
This is the current way in which data is returned.

[
  {
    "d2": {
      "identity": 0,
      "labels": [
        "Distributor"
      ],
      "properties": {
        "name": "Ashif",
        "left": "Bibin",
        "right": "Althaf"
      }
    },
    "path": {
      "start": {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      },
      "end": {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      },
      "segments": [],
      "length": 0
    },
    "nodes": [
      {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      }
    ],
    "rels": []
  },
  {
    "d2": {
      "identity": 1,
      "labels": [
        "Distributor"
      ],
      "properties": {
        "name": "Althaf",
        "left": "Chris",
        "right": "Arjun"
      }
    },
    "path": {
      "start": {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      },
      "end": {
        "identity": 1,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Althaf",
          "left": "Chris",
          "right": "Arjun"
        }
      },
      "segments": [
        {
          "start": {
            "identity": 0,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Ashif",
              "left": "Bibin",
              "right": "Althaf"
            }
          },
          "relationship": {
            "identity": 1,
            "start": 0,
            "end": 1,
            "type": "RIGHT",
            "properties": {}
          },
          "end": {
            "identity": 1,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Althaf",
              "left": "Chris",
              "right": "Arjun"
            }
          }
        }
      ],
      "length": 1
    },
    "nodes": [
      {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      },
      {
        "identity": 1,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Althaf",
          "left": "Chris",
          "right": "Arjun"
        }
      }
    ],
    "rels": [
      {
        "identity": 1,
        "start": 0,
        "end": 1,
        "type": "RIGHT",
        "properties": {}
      }
    ]
  },
  {
    "d2": {
      "identity": 6,
      "labels": [
        "Distributor"
      ],
      "properties": {
        "name": "Arjun",
        "left": "Yasin",
        "right": "Misaj"
      }
    },
    "path": {
      "start": {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      },
      "end": {
        "identity": 6,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Arjun",
          "left": "Yasin",
          "right": "Misaj"
        }
      },
      "segments": [
        {
          "start": {
            "identity": 0,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Ashif",
              "left": "Bibin",
              "right": "Althaf"
            }
          },
          "relationship": {
            "identity": 1,
            "start": 0,
            "end": 1,
            "type": "RIGHT",
            "properties": {}
          },
          "end": {
            "identity": 1,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Althaf",
              "left": "Chris",
              "right": "Arjun"
            }
          }
        },
        {
          "start": {
            "identity": 1,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Althaf",
              "left": "Chris",
              "right": "Arjun"
            }
          },
          "relationship": {
            "identity": 5,
            "start": 1,
            "end": 6,
            "type": "RIGHT",
            "properties": {}
          },
          "end": {
            "identity": 6,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Arjun",
              "left": "Yasin",
              "right": "Misaj"
            }
          }
        }
      ],
      "length": 2
    },
    "nodes": [
      {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      },
      {
        "identity": 1,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Althaf",
          "left": "Chris",
          "right": "Arjun"
        }
      },
      {
        "identity": 6,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Arjun",
          "left": "Yasin",
          "right": "Misaj"
        }
      }
    ],
    "rels": [
      {
        "identity": 1,
        "start": 0,
        "end": 1,
        "type": "RIGHT",
        "properties": {}
      },
      {
        "identity": 5,
        "start": 1,
        "end": 6,
        "type": "RIGHT",
        "properties": {}
      }
    ]
  },
  {
    "d2": {
      "identity": 3,
      "labels": [
        "Distributor"
      ],
      "properties": {
        "name": "Chris"
      }
    },
    "path": {
      "start": {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      },
      "end": {
        "identity": 3,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Chris"
        }
      },
      "segments": [
        {
          "start": {
            "identity": 0,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Ashif",
              "left": "Bibin",
              "right": "Althaf"
            }
          },
          "relationship": {
            "identity": 1,
            "start": 0,
            "end": 1,
            "type": "RIGHT",
            "properties": {}
          },
          "end": {
            "identity": 1,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Althaf",
              "left": "Chris",
              "right": "Arjun"
            }
          }
        },
        {
          "start": {
            "identity": 1,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Althaf",
              "left": "Chris",
              "right": "Arjun"
            }
          },
          "relationship": {
            "identity": 4,
            "start": 1,
            "end": 3,
            "type": "LEFT",
            "properties": {}
          },
          "end": {
            "identity": 3,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Chris"
            }
          }
        }
      ],
      "length": 2
    },
    "nodes": [
      {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      },
      {
        "identity": 1,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Althaf",
          "left": "Chris",
          "right": "Arjun"
        }
      },
      {
        "identity": 3,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Chris"
        }
      }
    ],
    "rels": [
      {
        "identity": 1,
        "start": 0,
        "end": 1,
        "type": "RIGHT",
        "properties": {}
      },
      {
        "identity": 4,
        "start": 1,
        "end": 3,
        "type": "LEFT",
        "properties": {}
      }
    ]
  },
  {
    "d2": {
      "identity": 2,
      "labels": [
        "Distributor"
      ],
      "properties": {
        "name": "Bibin",
        "left": "Aiju",
        "right": "Akhil"
      }
    },
    "path": {
      "start": {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      },
      "end": {
        "identity": 2,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Bibin",
          "left": "Aiju",
          "right": "Akhil"
        }
      },
      "segments": [
        {
          "start": {
            "identity": 0,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Ashif",
              "left": "Bibin",
              "right": "Althaf"
            }
          },
          "relationship": {
            "identity": 0,
            "start": 0,
            "end": 2,
            "type": "LEFT",
            "properties": {}
          },
          "end": {
            "identity": 2,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Bibin",
              "left": "Aiju",
              "right": "Akhil"
            }
          }
        }
      ],
      "length": 1
    },
    "nodes": [
      {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      },
      {
        "identity": 2,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Bibin",
          "left": "Aiju",
          "right": "Akhil"
        }
      }
    ],
    "rels": [
      {
        "identity": 0,
        "start": 0,
        "end": 2,
        "type": "LEFT",
        "properties": {}
      }
    ]
  },
  {
    "d2": {
      "identity": 5,
      "labels": [
        "Distributor"
      ],
      "properties": {
        "name": "Akhil"
      }
    },
    "path": {
      "start": {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      },
      "end": {
        "identity": 5,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Akhil"
        }
      },
      "segments": [
        {
          "start": {
            "identity": 0,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Ashif",
              "left": "Bibin",
              "right": "Althaf"
            }
          },
          "relationship": {
            "identity": 0,
            "start": 0,
            "end": 2,
            "type": "LEFT",
            "properties": {}
          },
          "end": {
            "identity": 2,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Bibin",
              "left": "Aiju",
              "right": "Akhil"
            }
          }
        },
        {
          "start": {
            "identity": 2,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Bibin",
              "left": "Aiju",
              "right": "Akhil"
            }
          },
          "relationship": {
            "identity": 3,
            "start": 2,
            "end": 5,
            "type": "RIGHT",
            "properties": {}
          },
          "end": {
            "identity": 5,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Akhil"
            }
          }
        }
      ],
      "length": 2
    },
    "nodes": [
      {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      },
      {
        "identity": 2,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Bibin",
          "left": "Aiju",
          "right": "Akhil"
        }
      },
      {
        "identity": 5,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Akhil"
        }
      }
    ],
    "rels": [
      {
        "identity": 0,
        "start": 0,
        "end": 2,
        "type": "LEFT",
        "properties": {}
      },
      {
        "identity": 3,
        "start": 2,
        "end": 5,
        "type": "RIGHT",
        "properties": {}
      }
    ]
  },
  {
    "d2": {
      "identity": 4,
      "labels": [
        "Distributor"
      ],
      "properties": {
        "name": "Aiju"
      }
    },
    "path": {
      "start": {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      },
      "end": {
        "identity": 4,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Aiju"
        }
      },
      "segments": [
        {
          "start": {
            "identity": 0,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Ashif",
              "left": "Bibin",
              "right": "Althaf"
            }
          },
          "relationship": {
            "identity": 0,
            "start": 0,
            "end": 2,
            "type": "LEFT",
            "properties": {}
          },
          "end": {
            "identity": 2,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Bibin",
              "left": "Aiju",
              "right": "Akhil"
            }
          }
        },
        {
          "start": {
            "identity": 2,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Bibin",
              "left": "Aiju",
              "right": "Akhil"
            }
          },
          "relationship": {
            "identity": 2,
            "start": 2,
            "end": 4,
            "type": "LEFT",
            "properties": {}
          },
          "end": {
            "identity": 4,
            "labels": [
              "Distributor"
            ],
            "properties": {
              "name": "Aiju"
            }
          }
        }
      ],
      "length": 2
    },
    "nodes": [
      {
        "identity": 0,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Ashif",
          "left": "Bibin",
          "right": "Althaf"
        }
      },
      {
        "identity": 2,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Bibin",
          "left": "Aiju",
          "right": "Akhil"
        }
      },
      {
        "identity": 4,
        "labels": [
          "Distributor"
        ],
        "properties": {
          "name": "Aiju"
        }
      }
    ],
    "rels": [
      {
        "identity": 0,
        "start": 0,
        "end": 2,
        "type": "LEFT",
        "properties": {}
      },
      {
        "identity": 2,
        "start": 2,
        "end": 4,
        "type": "LEFT",
        "properties": {}
      }
    ]
  }
]

[andrew_bowman]

There's the apoc.convert.toTree() procedure, that might be close to what you want. Here are a few threads on its usage:

Return certain properties from apoc.convert.toTree

Ah ok, its possible that this will do it: nodes: map of list, a key is the name of the label, value is a list of properties that can be included or excluded. e.g nodes:{LABEL:<[prop1, prop2]/[-prop1, -prop2]>} github changeset So: MATCH r=(p:Plaza)-[:in_plaza]->(rs:Restaurant) WITH COLLECT(r) AS rs CALL apoc.convert.toTree(rs, { nodes: {Plaza: ['name'], Restaurant: ['name']} }) yield value RETURN value might do it no promises!

and

Using Cypher to return nested, hierarchical JSON from a tree