如何在一个查询中检索树中每个节点的前 n 个子节点

Question

我最近正在评估图形数据库或任何其他数据库的一个特定要求：

通过一个查询中节点的直接子节点及其所有直接和间接子节点的聚合属性检索每个节点的前n个子节点的能力。结果应返回正确的层次结构。

实例

root + 11
          ++ 111
             ++ 1111
          ++ 112
             ++ 1121
             ++ 1122
             ++ 1123
          ++ 113
     + 12
          ++ 121
          ++ 122
             ++ 1221
             ++ 1222
             ++ 1223
          ++ 123
     + 13
         ++ 131
         ++ 132
         ++ 133
         ++ 134
     + 14

< code >每个节点都有一个属性，即它有多少个直接子节点。并且该树不超过8层。假设我想运行整个树的查询，通过每个级别的所有节点，它的前2个子节点有最多的直接和间接子节点。它将为我们提供以下信息:

root + 11
          ++ 111
             ++ 1111
          ++ 112
             ++ 1121
             ++ 1122
     + 12
          ++ 121
          ++ 122
             ++ 1221
             ++ 1222

我想知道是否有任何图形数据库或任何其他数据库有效地支持这种查询，如果是，如何？

Answer 1

使用Neo4j

你可以用Neo4j来实现，但是你需要确保你使用的是APOC程序插件来访问一些地图和采集功能和程序。

首先要注意一点。当子节点的后代节点数量相等时，您没有定义在子节点之间进行选择时要使用的任何标准。因此，下面的结果可能与您的不完全匹配，因为可能已经选择了备用节点(具有相同的计数)。如果您确实需要订购和选择的附加标准，您必须将它添加到您的描述中，以便我可以相应地修改查询。

创建测试图

首先，让我们创建测试数据集。我们可以通过Neo4j浏览器做到这一点。

首先，让我们设置创建图表所需的参数:

:param data => [{id:11, children:[111, 112, 113]}, {id:12, children:[121, 122, 123]}, {id:13, children:[131,132,133,134]}, {id:14, children:[]}, {id:111, children:[1111]}, {id:112, children:[1121, 1122, 1123]}, {id:122, children:[1221,1222,1223]}]

现在我们可以使用这个查询来使用这些参数来创建图形：

UNWIND $data as row
MERGE (n:Node{id:row.id})
FOREACH (x in row.children |
 MERGE (c:Node{id:x})
 MERGE (n)-[:CHILD]->(c))

我们正在处理类型为：Node的节点，通过：CHILD关系相互连接，向叶节点传出。

我们还可以在顶层添加一个：Root:节点，以使后面的一些查询变得更简单：

MERGE (r:Node:Root{id:0})
WITH r
MATCH (n:Node)
WHERE NOT ()-[:CHILD]->(n)
MERGE (r)-[:CHILD]->(n)

：Root 节点现在已连接到顶部节点（11、12、13、14），我们的测试图已准备就绪。

实际的查询

因为您想要的聚合需要节点的所有后代的计数，而不仅仅是它的直接子节点，所以我们不能使用节点有多少直接子节点的子节点计数属性。或者更确切地说，我们可以对节点的所有后代的计数求和，但由于这需要我们无论如何都要遍历到所有后代，因此更容易只获取所有后代的计数并完全避免属性访问。

下面是整个查询，您应该能够对测试图运行完整查询。我用换行符和注释将其分成几个部分，以更好地显示每个部分正在做什么。

// for each node and its direct children, 
// order by the child's descendant count
MATCH (n:Node)-[:CHILD]->(child)
WITH n, child, size((child)-[:CHILD*]->()) as childDescCount
ORDER BY childDescCount DESC
// now collect the ordered children and take the top 2 per node
WITH n, collect(child)[..2] as topChildren

// from the above, per row, we have a node and a list of its top 2 children.
// we want to gather all of these children into a single list, not nested
// so we collect the lists (to get a list of lists of nodes), then flatten it with APOC
WITH apoc.coll.flatten(collect(topChildren)) as topChildren

// we now have a list of the nodes that can possibly be in our path
// although some will not be in the path, as their parents (or ancestors) are not in the list
// to get the full tree we need to match down from the :Root node and ensure
// that for each path, the only nodes in the path are the :Root node or one of the topChildren
MATCH path=(:Root)-[:CHILD*]->()
WHERE all(node in nodes(path) WHERE node:Root OR node in topChildren)

RETURN path

没有注释，这只是一个8行查询。

现在，如果您查看图形结果，这实际上返回多条路径，每行一条路径，所有路径的全部一起创建您想要的可视化树。

在JSON中以树的形式获取结果

但是，如果不使用可视化工具以图形方式查看结果，则可能需要树的 JSON 表示形式。我们可以通过收集所有结果路径并使用 APOC 中的过程来生成 JSON 树结构来获得这一点。下面是一个稍作修改的查询，其中包含这些更改：

MATCH (n:Node)-[:CHILD]->(child)
WITH n, child, size((child)-[:CHILD*]->()) as childDescCount
ORDER BY childDescCount DESC
WITH n, collect(child)[..2] as topChildren
WITH apoc.coll.flatten(collect(topChildren)) as topChildren
MATCH path=(:Root)-[:CHILD*]->()
WHERE all(node in nodes(path) WHERE node:Root OR node in topChildren)
// below is the new stuff to get the JSON tree
WITH collect(path) as paths
CALL apoc.convert.toTree(paths) YIELD value as map
RETURN map

结果将如下所示：

{
  "_type": "Node:Root",
  "_id": 52,
  "id": 0,
  "child": [
    {
      "_type": "Node",
      "_id": 1,
      "id": 12,
      "child": [
        {
          "_type": "Node",
          "_id": 6,
          "id": 122,
          "child": [
            {
              "_type": "Node",
              "_id": 32,
              "id": 1223
            },
            {
              "_type": "Node",
              "_id": 31,
              "id": 1222
            }
          ]
        },
        {
          "_type": "Node",
          "_id": 21,
          "id": 123
        }
      ]
    },
    {
      "_type": "Node",
      "_id": 0,
      "id": 11,
      "child": [
        {
          "_type": "Node",
          "_id": 4,
          "id": 111,
          "child": [
            {
              "_type": "Node",
              "_id": 26,
              "id": 1111
            }
          ]
        },
        {
          "_type": "Node",
          "_id": 5,
          "id": 112,
          "child": [
            {
              "_type": "Node",
              "_id": 27,
              "id": 1121
            },
            {
              "_type": "Node",
              "_id": 29,
              "id": 1123
            }
          ]
        }
      ]
    }
  ]
}