当前位置: 首页 > 知识库问答 >
问题:

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

佘缪文
2023-03-14

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

通过一个查询中节点的直接子节点及其所有直接和间接子节点的聚合属性检索每个节点的前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

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

共有1个答案

宰父夕
2023-03-14

使用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
            }
          ]
        }
      ]
    }
  ]
}
 类似资料:
  • 我遇到了这个问题,似乎在任何地方都找不到解决办法。 给定一个二叉树,其中每个节点都包含一个数字,表示其子树中剩余节点的数量,编写一个函数,返回第n个按顺序遍历的节点。 查找按序遍历的第n个节点相当简单,但如何使用关于左节点数的信息来改进该过程?

  • 问题内容: 首先,我必须说我发现它是一个非常好的解析器,并且在与其他解析器进行比较时,我认为它非常强大。 给出以下代码: 如果我想找到回合1和门1 的节点,请在此处: 我将这样做: 如果我想要第一回合和第一回合的节点,则: 但如何使用一个循环,因为我不知道多少我做我的,这意味着我怎么能这样使用一个循环,其中每个迭代我取回3(我的意思是,和值)的值更值节点!? 要求这样做的原因是: 我不知道我有多少

  • 我一直在尝试在工作中实现Autosys作业计划的树表示。由于每个作业(流程)可以有一个或多个依赖作业,因此我决定使用n元树实现,以便映射流程。我使用java集合来实现同样的目标。 Q1(已解决):目前的问题是显示功能被挂在一个无限循环中。我尝试寻找现有的线程,但无法遇到使用迭代器进行遍历的示例。 Q2:(打开)显示功能以后序方式遍历树。我希望以一种级别顺序的方式遍历它,其中节点以级别为基础进行打印

  • 问题内容: pyspark中有一个DataFrame,其数据如下: 我期望在每个组中返回2条记录,每条记录具有相同的user_id,它们需要具有最高的得分。因此,结果应如下所示: 我真的是pyspark的新手,有人可以给我一个代码段或门户网站有关此问题的相关文档吗?万分感谢! 问题答案: 我相信您需要使用窗口函数基于和来获得每一行的排名,然后过滤结果以仅保留前两个值。 通常,官方编程指南是开始学习

  • 问题内容: 我正在一个项目中,用户对我们的代客服务的请求在另一端代客接受请求。 我正在使用Firebase作为后端,并应要求将客户uid保存在“ request”子项上。 当代客接受请求时,客户uid应从“请求”节点移至“进行中”节点。 我怎样才能做到这一点? 问题答案: 我建议使用这个: 这来自以下来源:https : //gist.github.com/katowulf/6099042。我在J

  • 我正在做一个项目,以创建一个超过2个子节点的树。我明白在创建二叉树时,我们可以只创建一个左节点和一个右节点来充当子节点,但当我在网上寻找创建树的帮助时,我找到的每一个解决方案都谈到了创建二叉树。我明白创建树的部分意味着您需要创建子节点数组或arraylist,但我不明白如何将数据放入数组,或者如何将子节点数组“连接”到父节点? 这是我目前掌握的代码。我知道这不是很多,但我正在努力刚刚开始这个项目。