How to use SurrealDB store a tree data?

[songispm]

I want every node in the tree can be selected from database alone. then how to flat the tree and store the single node alone, and how to store the relations of every nodes?
The depth of the tree is Infinite.

In MySQL or MongoDB,

If I store a whole json tree in one row, then select whole tree is easy, select a single node is difficult.
If I flat the tree and use parentId or childrenIds to describe the relation in every node, it is easy to select a single node, but complex to select a whole tree or child tree.

Can SurrealDB simplify this data model?
I hope the CRUDs are all extremely flexible.

[wtf-jik]

Wondering the same thing. Documentation doesn't seem to mention this as a use case? Worse case scenario I think we just need to adapt a de/serializer, but I'd expect to be able to do this with surreal.

[stevefan1999-personal]

Recursive data structures. There are many ways to do this in relational database though, for example you could just treat each of them as an independent document and put relations in an external table. This is known as closure tables.

[auipga]

What about a Nested Set? Or is this old-school relational database thinking?

[auipga]

This is how i implemented Nested Sets

LET $tableName = 'tree';

REMOVE TABLE tree;
DEFINE TABLE tree SCHEMALESS;
DEFINE FIELD treeroot ON TABLE tree TYPE option<record<tree>>;
DEFINE FIELD parent ON TABLE tree TYPE option<record<tree>>;
DEFINE FIELD lft ON TABLE tree TYPE option<number>;
DEFINE FIELD rgt ON TABLE tree TYPE option<number>;
DEFINE FIELD lvl ON TABLE tree TYPE option<number>;

DEFINE EVENT insertRootNode ON TABLE tree WHEN $event = "CREATE" AND $after.parent IS NONE THEN {
    /* Initialize the new node as a root node */
    UPDATE type::table($tableName) SET lft = 1, rgt = 2, lvl = 0, treeroot = $after.id WHERE id = $after.id;
};

DEFINE EVENT insertNode ON TABLE tree WHEN $event = "CREATE"
 AND $after.parent IS NOT NONE THEN {
    /* Update the lft values of all nodes that come after the parent node in the tree */
    UPDATE type::table($tableName) SET lft = lft + 2 WHERE lft > $after.parent.rgt;
    /* Update the rgt values of all nodes that come after the parent node in the tree and the parent node itself */
    UPDATE type::table($tableName) SET rgt = rgt + 2 WHERE rgt >= $after.parent.rgt;
    /* Update the lft, rgt, and lvl values of the new node */
    UPDATE type::table($tableName) SET
        // >>>>> I have a question here. Why do i need to subtract? <<<<<
        lft = $after.parent.rgt - 2,
        rgt = $after.parent.rgt - 1,
        // >>>>> this is what I thought would be correct, but it's not <<<<<
        // lft = $after.parent.rgt,
        // rgt = $after.parent.rgt + 1,
        lvl = $after.parent.lvl + 1,
        treeroot = $after.parent.treeroot
    WHERE id = $after.id;
};

DEFINE EVENT deleteNode ON TABLE tree WHEN $event = "DELETE" THEN {
  /* shift children up aka */
  /* Decrement the lft, rgt and lvl values of all children nodes by one */
  UPDATE type::table($tableName) SET lft = lft - 1, rgt = rgt - 1, lvl = lvl - 1 WHERE lft > $before.lft AND rgt < $before.rgt;
  /* subtract 2 from all following values aka: */
  /* Decrement the lft and rgt values of all nodes that come after the deleted node in the tree by two */
  UPDATE type::table($tableName) SET lft = lft - 2 WHERE lft > $before.rgt;
  UPDATE type::table($tableName) SET rgt = rgt - 2 WHERE rgt > $before.rgt;
};

Demo 1

DELETE tree WHERE treeroot = tree:root;

CREATE ONLY tree:root;
CREATE ONLY tree:1 SET parent = tree:root;
CREATE ONLY tree:2 SET parent = tree:root;
CREATE ONLY tree:3 SET parent = tree:root;
CREATE ONLY tree:2_1 SET parent = tree:2;
CREATE ONLY tree:2_1_1 SET parent = tree:2_1;

SELECT * FROM tree WHERE treeroot = tree:root ORDER BY lft ASC, rgt DESC;

Demo 2

Example from Wikipedia | Nested set model

DELETE tree WHERE treeroot = tree:Clothing;

CREATE ONLY tree:Clothing;
CREATE ONLY tree:Men           SET parent = tree:Clothing;
CREATE ONLY tree:Women         SET parent = tree:Clothing;
CREATE ONLY tree:Suits         SET parent = tree:Men;
CREATE ONLY tree:Slacks        SET parent = tree:Suits;
CREATE ONLY tree:Jackets       SET parent = tree:Suits;
CREATE ONLY tree:Dresses       SET parent = tree:Women;
CREATE ONLY tree:Skirts        SET parent = tree:Women;
CREATE ONLY tree:Blouses       SET parent = tree:Women;
CREATE ONLY tree:Evening_Gowns SET parent = tree:Dresses;
CREATE ONLY tree:Sun_Dresses   SET parent = tree:Dresses;

SELECT * FROM tree ORDER BY lft ASC, rgt DESC;

[mateothegreat]

I just tackled this issue, see if https://matthewdavis.io/surrealdb-recursive-graph-query/ helps you out.

TL;DR:

DEFINE FUNCTION fn::recurse($e: any) {
    RETURN (
        SELECT *,fn::recurse(component_link.out) FROM <-component_link.in
    );
};

SELECT *,fn::recurse($this) AS children FROM component;

[stevefan1999-personal]

I just tackled this issue, see if https://matthewdavis.io/surrealdb-recursive-graph-query/ helps you out.

TL;DR:

DEFINE FUNCTION fn::recurse($e: any) {
    RETURN (
        SELECT *,fn::recurse(component_link.out) FROM <-component_link.in
    );
};

SELECT *,fn::recurse($this) AS children FROM component;

That's gonna take O(nh) space and likely blow up by degrading further into quadratic space

[mateothegreat]

Got an alternative?

[stevefan1999-personal]

Got an alternative?

Well a graph data structure can be seen as a closure table in some sense...that's called an edge list. If we can flatten it out. Also another problem with your recursive approach is that you didn't account for cycles, so you also need at least a hash table and memorize the walked nodes.