1

https://www.mongodb.com/docs/manual/tutorial/model-tree-structures-with-parent-references/ describes 5 ways to model tree-like structures in MongoDB, and recommends to use $graphlookup to traverse the tree.

All examples of $graphlookup return a flat array of the referenced documents tho, and it's not quite clear how should I use it to return the tree structure of subdocuments within subdocuments within subdocuments etc.

I am flexible with data structure as long as I can get each document by _id regardless of how far from the root it is, and retrieve the whole tree of dereferenced/embedded documents:

[
  {
    "_id": "a",
    "label": "Cat",
    "children": [
      {
        "_id": "b",
        "label": "Big cat",
        "children": [
            {
              "_id": "c",
              "label": "Lion"
            },
            {
              "_id": "d",
              "label": "Jaguar"
            },
            {
              "_id": "e",
              "label": "Tiger"
            }
          ]
      },
      {
        "_id": "f",
        "label": "Small cat",
        "children": [
            {
              "_id": "g",
              "label": "Bay cat"
            },
            {
              "_id": "h",
              "label": "Desert lynx"
            },
            {
              "_id": "i",
              "label": "Leopardus",
              "children": [
                {
                  "_id": "j",
                  "label": "Guina"
                },
                {
                  "_id": "k",
                  "label": "Tigrillo"
                },
                {
                  "_id": "l",
                  "label": "Ocelot"
                }
              ]
            },
            {
              "_id": "m",
              "label": "Lynx"
            },
            {
                "_id": "n",
                "label": "Felis",
                "children": [
                  {
                    "_id": "o",
                    "label": "Jungle cat"
                  },
                  {
                    "_id": "p",
                    "label": "Sand cat"
                  },
                  {
                    "_id": "q",
                    "label": "Wildcat",
                    "children": [
                        {
                          "_id": "r",
                          "label": "African wildcat"
                        },        
                        {
                          "_id": "s",
                          "label": "European wildcat"
                        },        
                        {
                          "_id": "t",
                          "label": "Domestic cat"
                        }        
                      ]
                  }
                ]
              }    
          ]
      }
    ]
  }
]

How should I store all these animals, and what pipeline operators can recursively populate the nested structure?

I have created the flat list of these cats in https://mongoplayground.net/p/7D8SgIh-85W to play with.

Alex Blex
  • 34,704
  • 7
  • 48
  • 75
  • The `"depthField"` in `"$graphLookup"` can be used to determine the parents, children, and siblings. If you provide a mongoplayground.net configuration with a flattened collection, I can demonstrate it. – rickhg12hs Sep 25 '22 at 16:16
  • To capture the parent/child relationship in a flattened collection, the fields need to be explicitly added. – rickhg12hs Sep 25 '22 at 16:28
  • @rickhg12hs thanks. could you elaborate your comment? If I understand https://www.mongodb.com/docs/manual/reference/operator/aggregation/graphLookup/ depthField holds the numeric value of the depth of the recursion. I fail to see how to apply it to populate children arrays. – Alex Blex Sep 25 '22 at 16:28
  • @rickhg12hs I am happy to add any parent-child references. As I mentioned I learned all 5 ways mongo recommends to use. None of them allow to return the tree tho. – Alex Blex Sep 25 '22 at 16:32

1 Answers1

2

It's possible to create a flat collection and still be able to reconstruct the tree by modeling each document as a graph node with a connection list. Something like:

db={
  "catTree": [
    {
      "_id": "a",
      "label": "Cat",
      "children": ["b", "f"],
      "parent": null
    },
    {
      "_id": "b",
      "label": "Panthera",
      "children": ["c", "d", "e"],
      "parent": "a"
    },
    {
      "_id": "c",
      "label": "Lion",
      "children": [],
      "parent": "b"
    },
    {
      "_id": "d",
      "label": "Jaguar",
      "children": [],
      "parent": "b"
    },
    {
      "_id": "e",
      "label": "Tiger",
      "children": [],
      "parent": "b"
    },
    {
      "_id": "f",
      "label": "Small cats",
      "children": ["g", "h", "i", "m", "n"],
      "parent": "a"
    },
    {
      "_id": "g",
      "label": "Bay cat",
      "children": [],
      "parent": "f"
    },
    {
      "_id": "h",
      "label": "Desert lynx",
      "children": [],
      "parent": "f"
    },
    {
      "_id": "i",
      "label": "Leopardus",
      "children": ["j", "k", "l"],
      "parent": "f"
    },
    {
      "_id": "j",
      "label": "Guina",
      "children": [],
      "parent": "i"
    },
    {
      "_id": "k",
      "label": "Tigrillo",
      "children": [],
      "parent": "i"
    },
    {
      "_id": "l",
      "label": "Ocelot",
      "children": [],
      "parent": "i"
    },
    {
      "_id": "m",
      "label": "Lynx",
      "children": [],
      "parent": "f"
    },
    {
      "_id": "n",
      "label": "Felis",
      "children": ["o", "p", "q"],
      "parent": "f"
    },
    {
      "_id": "o",
      "label": "Jungle cat",
      "children": [],
      "parent": "n"
    },
    {
      "_id": "p",
      "label": "Sand cat",
      "children": [],
      "parent": "n"
    },
    {
      "_id": "q",
      "label": "Wildcat",
      "children": ["r", "s", "t"],
      "parent": "n"
    },
    {
      "_id": "r",
      "label": "African wildcat",
      "children": [],
      "parent": "q"
    },
    {
      "_id": "s",
      "label": "European wildcat",
      "children": [],
      "parent": "q"
    },
    {
      "_id": "t",
      "label": "Domestic cat",
      "children": [],
      "parent": "q"
    }
  ]
}

Using "$graphLookup", a "root" document can be specified and all "children" will be returned, to any depth. Adapting list_to_tree from another javascript answer, the tree can be reconstructed.

db.catTree.aggregate([
  {
    "$match": {
      "_id": "a"
    }
  },
  {
    "$graphLookup": {
      "from": "catTree",
      "startWith": "$children",
      "connectFromField": "children",
      "connectToField": "_id",
      "as": "theKids",
      "depthField": "level"
    }
  },
  {
    "$set": {
      "children": {
        "$function": {
          "body": "function(root, list) {let map = {}, node, roots = [], i;for (i = 0; i < list.length; i += 1) {map[list[i]._id] = i;list[i].children = [];node = list[i];if (node.parent !== root) {list[map[node.parent]].children.push(node);} else {roots.push(node);}}return roots}",
          "args": [
            "$_id",
            {
              "$sortArray": {
                "input": "$theKids",
                "sortBy": {"level": 1}
              }
            }
          ],
          "lang": "js"
        }
      }
    }
  },
  {"$unset": "theKids"}
])

Example output:

[
  {
    "_id": "a",
    "children": [
      {
        "_id": "b",
        "children": [
          {
            "_id": "c",
            "children": [],
            "label": "Lion",
            "level": NumberLong(1),
            "parent": "b"
          },
          {
            "_id": "d",
            "children": [],
            "label": "Jaguar",
            "level": NumberLong(1),
            "parent": "b"
          },
          {
            "_id": "e",
            "children": [],
            "label": "Tiger",
            "level": NumberLong(1),
            "parent": "b"
          }
        ],
        "label": "Panthera",
        "level": NumberLong(0),
        "parent": "a"
      },
      {
        "_id": "f",
        "children": [
          {
            "_id": "h",
            "children": [],
            "label": "Desert lynx",
            "level": NumberLong(1),
            "parent": "f"
          },
          {
            "_id": "g",
            "children": [],
            "label": "Bay cat",
            "level": NumberLong(1),
            "parent": "f"
          },
          {
            "_id": "m",
            "children": [],
            "label": "Lynx",
            "level": NumberLong(1),
            "parent": "f"
          },
          {
            "_id": "n",
            "children": [
              {
                "_id": "q",
                "children": [
                  {
                    "_id": "t",
                    "children": [],
                    "label": "Domestic cat",
                    "level": NumberLong(3),
                    "parent": "q"
                  },
                  {
                    "_id": "r",
                    "children": [],
                    "label": "African wildcat",
                    "level": NumberLong(3),
                    "parent": "q"
                  },
                  {
                    "_id": "s",
                    "children": [],
                    "label": "European wildcat",
                    "level": NumberLong(3),
                    "parent": "q"
                  }
                ],
                "label": "Wildcat",
                "level": NumberLong(2),
                "parent": "n"
              },
              {
                "_id": "p",
                "children": [],
                "label": "Sand cat",
                "level": NumberLong(2),
                "parent": "n"
              },
              {
                "_id": "o",
                "children": [],
                "label": "Jungle cat",
                "level": NumberLong(2),
                "parent": "n"
              }
            ],
            "label": "Felis",
            "level": NumberLong(1),
            "parent": "f"
          },
          {
            "_id": "i",
            "children": [
              {
                "_id": "k",
                "children": [],
                "label": "Tigrillo",
                "level": NumberLong(2),
                "parent": "i"
              },
              {
                "_id": "j",
                "children": [],
                "label": "Guina",
                "level": NumberLong(2),
                "parent": "i"
              },
              {
                "_id": "l",
                "children": [],
                "label": "Ocelot",
                "level": NumberLong(2),
                "parent": "i"
              }
            ],
            "label": "Leopardus",
            "level": NumberLong(1),
            "parent": "f"
          }
        ],
        "label": "Small cats",
        "level": NumberLong(0),
        "parent": "a"
      }
    ],
    "label": "Cat",
    "parent": null
  }
]

Try it on mongoplayground.net.

rickhg12hs
  • 10,638
  • 6
  • 24
  • 42
  • Thank you. I guess it spells there is no way to do it without function. There are few issues with server-side scripts. Apart from performance hit, CIS [recommends](https://workbench.cisecurity.org/files/3773) to disable it, and it just segfaults on SELinux systems. I would never recomend to use $function myself, but I assume it's one of the cases why it is not deprecated yet. The answer is super useful **if the results are required in the next stage of the pipeline**. Otherwise I would strongly recommend to run the function on the client. – Alex Blex Sep 26 '22 at 00:04