Arangodb AQL递归图遍历

Question

我有一个包含三个集合的图表，其中的项目可以通过边连接。 ItemA 是 itemB 的父级，而 itemB 又是 itemC 的父级。元素只能通过

方向的边连接

"_from : child, _to : parent"

目前我只能通过此 AQL 查询获得 "linear" 结果：

LET contains = (FOR v IN 1..? INBOUND 'collectionA/itemA' GRAPH 'myGraph' RETURN v)

     RETURN {
        "root": {
            "id": "ItemA",
            "contains": contains
       }
   }

结果如下所示：

"root": {
    "id": "itemA",
    "contains": [
        {
            "id": "itemB"
        },
        {
            "id": "itemC"
        }
    ]
}

但我需要得到一个 "hierarchical" 这样的图遍历结果：

"root": {
    "id": "itemA",
    "contains": [
        {
            "id": "itemB",
            "contains": [
                {
                    "id": "itemC"
                }
            }
        ]
    }

那么，我可以通过 aql 查询得到这个 "hierarchical" 结果运行吗？

还有一件事：遍历应该运行直到遇到叶节点。所以遍历的深度事先是未知的。

Answer 1

我还需要知道这个问题的答案，所以这是一个有效的解决方案。

我确定代码需要为您定制，并且可以做一些改进，如果适合此示例答案，请相应地发表评论。

解决方案是使用支持递归并构建树的 Foxx 微服务。我遇到的问题是循环路径，但我实施了最大深度限制来阻止这种情况，在下面的示例中硬编码为 10。

创建 Foxx 微服务：

创建一个新文件夹（例如recursive-tree）
创建目录脚本
将文件manifest.json和index.js放入根目录
将文件 setup.js 放入脚本目录
然后用这三个文件创建一个新的 zip 文件（例如 Foxx.zip）
导航到 ArangoDB 管理控制台
点击服务 |添加服务
输入合适的挂载点，例如/my/tree
单击“压缩”选项卡
将您创建的 Foxx.zip 文件拖入，它应该可以正常创建
如果出现错误，请确保集合 myItems 和 myConnections 不存在，并且名为 myGraph 的图不存在，因为它将尝试创建它们带有示例数据。
然后导航到 ArangoDB 管理控制台，服务 | /my/tree
点击API
展开/tree/{rootId}
提供ItemA的rootId参数，点击'Try It Out'
您应该从提供的根 ID 中看到结果。

如果 rootId 不存在，它return什么都不是如果 rootId 没有 children，它 return 是 'contains' 的空数组如果 rootId 有循环 'contains' 值，它会 return 嵌套到深度限制，我希望有更简洁的方法来阻止它。

这是三个文件： setup.js（位于脚本文件夹中）：

'use strict';
const db = require('@arangodb').db;
const graph_module =  require("org/arangodb/general-graph");

const itemCollectionName = 'myItems';
const edgeCollectionName = 'myConnections';
const graphName = 'myGraph';

if (!db._collection(itemCollectionName)) {
  const itemCollection = db._createDocumentCollection(itemCollectionName);
  itemCollection.save({_key: "ItemA" });
  itemCollection.save({_key: "ItemB" });
  itemCollection.save({_key: "ItemC" });
  itemCollection.save({_key: "ItemD" });
  itemCollection.save({_key: "ItemE" });

  if (!db._collection(edgeCollectionName)) {
    const edgeCollection = db._createEdgeCollection(edgeCollectionName);
    edgeCollection.save({_from: itemCollectionName + '/ItemA', _to: itemCollectionName + '/ItemB'});
    edgeCollection.save({_from: itemCollectionName + '/ItemB', _to: itemCollectionName + '/ItemC'});
    edgeCollection.save({_from: itemCollectionName + '/ItemB', _to: itemCollectionName + '/ItemD'});
    edgeCollection.save({_from: itemCollectionName + '/ItemD', _to: itemCollectionName + '/ItemE'});
  }

  const graphDefinition = [ 
    { 
      "collection": edgeCollectionName, 
      "from":[itemCollectionName], 
      "to":[itemCollectionName]
    }
  ];

  const graph = graph_module._create(graphName, graphDefinition);
}

mainfest.json（位于根文件夹）：

{
  "engines": {
    "arangodb": "^3.0.0"
  },
  "main": "index.js",
  "scripts": {
    "setup": "scripts/setup.js"
  }
}

index.js（位于根文件夹）：

'use strict';
const createRouter = require('@arangodb/foxx/router');
const router = createRouter();
const joi = require('joi');

const db = require('@arangodb').db;
const aql = require('@arangodb').aql;

const recursionQuery = function(itemId, tree, depth) {
  const result = db._query(aql`
    FOR d IN myItems
    FILTER d._id == ${itemId}
    LET contains = (
      FOR c IN 1..1 OUTBOUND ${itemId} GRAPH 'myGraph' RETURN { "_id": c._id }
    )
    RETURN MERGE({"_id": d._id}, {"contains": contains})
  `);

  tree = result._documents[0];

  if (depth < 10) {
    if ((result._documents[0]) && (result._documents[0].contains) && (result._documents[0].contains.length > 0)) {
        for (var i = 0; i < result._documents[0].contains.length; i++) {
        tree.contains[i] = recursionQuery(result._documents[0].contains[i]._id, tree.contains[i], depth + 1);
        }
    }
  }
  return tree;
}

router.get('/tree/:rootId', function(req, res) {
  let myResult = recursionQuery('myItems/' + req.pathParams.rootId, {}, 0);
  res.send(myResult);
})
  .response(joi.object().required(), 'Tree of child nodes.')
  .summary('Tree of child nodes')
  .description('Tree of child nodes underneath the provided node.');

module.context.use(router);

现在您可以调用 Foxx 微服务 API 端点，提供 rootId 它将 return 完整的树。很快。

ItemA 的示例输出是：

{
  "_id": "myItems/ItemA",
  "contains": [
    {
      "_id": "myItems/ItemB",
      "contains": [
        {
          "_id": "myItems/ItemC",
          "contains": []
        },
        {
          "_id": "myItems/ItemD",
          "contains": [
            {
              "_id": "myItems/ItemE",
              "contains": []
            }
          ]
        }
      ]
    }
  ]
}

可以看到Item B包含两个children，ItemC和ItemD，然后ItemD也包含ItemE。

我等不及 ArangoDB AQL 改进 FOR v, e, p IN 1..100 OUTBOUND 'abc/def' GRAPH 'someGraph' 样式查询中可变深度路径的处理。不建议在 3.x 中使用自定义访问者，但并没有真正被替换为处理路径中顶点深度的通配符查询或处理 prune 或 [=24] 的强大功能=] 路径遍历样式命令。

如果这可以简化，我很想 comments/feedback。

Answer 2

我找到了解决办法。我们决定使用 UDF (user defined functions).

以下是构建适当层次结构的几个步骤：

在arango db中注册函数。
运行你的 aql 查询，它构建了一个平面结构（顶点和该顶点的对应路径）。并将结果作为 UDF 函数的输入参数传递。这里我的函数只是将每个元素附加到它的父元素

以我为例： 1）在arango db中注册函数。

db.createFunction(
        'GO::LOCATED_IN::APPENT_CHILD_STRUCTURE',
            String(function (root, flatStructure) {
                if (root && root.id) {
                    var elsById = {};
                    elsById[root.id] = root;

                    flatStructure.forEach(function (element) {
                        elsById[element.id] = element;
                        var parentElId = element.path[element.path.length - 2];
                        var parentEl = elsById[parentElId];

                        if (!parentEl.contains)
                            parentEl.contains = new Array();

                        parentEl.contains.push(element);
                        delete element.path;
                    });
                }
                return root;
            })
        );

2) 运行带 udf 的 AQL:

    LET flatStructure = (FOR v,e,p IN 1..? INBOUND 'collectionA/itemA' GRAPH 'myGraph' 
       LET childPath = (FOR pv IN p.vertices RETURN pv.id_source)
    RETURN MERGE(v, childPath))

    LET root = {"id": "ItemA"} 

    RETURN GO::LOCATED_IN::APPENT_CHILD_STRUCTURE(root, flatStructure)

注意：实现功能时请不要忘记the naming convention。

Arangodb AQL递归图遍历

Arangodb AQL recursive graph traversal

recursion

graph-traversal

arangodb

aql