8

假设我有一个无环有向图，例如家庭“树”（不是真正的树，因为孩子有 2 个父母）。我想将此图的表示形式放在关系数据库中，以便快速计算节点的所有祖先和节点的所有后代。你会如何表示这个图表？您将如何查询所有后代？您将如何插入和删除节点和关系？你对数据做了什么假设？

对于您运行查询祖先和后代的语句数量，最佳解决方案将具有最佳大 O，在select/insert/delete总运行时间中，最佳大 O 打破平局，并因空间要求而打破平局。

我的同事向我提出了这个问题。我有一个解决方案，但在最坏的情况下它是指数级的，所以我想看看其他人会如何解决它。

编辑

明确的关系数据库。如果您使用带有内置传递闭包的图形数据库，这个问题是微不足道的（而且很无聊）。

4

5 回答 5

8

如果selects> manipulations，尤其是子树选择（所有祖先，所有后代），我会选择Closure -table 方法。是的，路径表中的路径爆炸式增长，但它确实可以快速提供结果（与邻接模型相反），并将更新限制在相关部分（与嵌套集的 50% 更新相反）。

Bill Karwin 在网上有一些关于不同模型优缺点的精彩介绍，请参阅http://www.slideshare.net/billkarwin/models-for-hierarchical-data（幻灯片 48 是概述）。

于 2010-09-20T21:18:11.163 回答
4

对于 SQL 数据库中的 DAG，似乎只有两种解决方案：

  1. 递归 WITH 子句。

  2. 传递闭包

我不知道任何实用的图形标记方案（如嵌套集、间隔或物化路径）

于 2010-09-23T16:41:38.477 回答
2

“你会如何表示这个图表？”

  • VAR 节点关系{node:sometype} KEY {node};
  • VAR EDGES RELATION{parentNode:sometype childNode:sometype} KEY {parentNode childNode};
  • 约束 NO_CYCLES IS_EMPTY(TCLOSE(EDGES) WHERE parentNode=childNode);

“你将如何查询所有后代？”

TCLOSE(EDGES) WHERE parentNode=somevalue;

“你将如何插入和删除节点和关系？”

  • 插入边缘关系{TUPLE{parentNode somevalue chlidNode somevalue}}；
  • DELETE EDGES WHERE deleteCondition;

“你对数据做了什么假设？”

有什么样的假设？您已经通过说“有向无环图”指定了所有要指定的内容。

于 2010-09-21T11:04:19.313 回答
2

RDBMS:s 并不是真正为处理此类数据而设计的。显而易见的选择是使用图形数据库，然后无需将图形转换为不同的表示形式，您一直使用图形 API。Marko Rodriguez 有一个很好的演示文稿，解释了在处理图遍历时底层数据模型的影响，如果您想更深入地研究它，请参阅图遍历编程模式。

不久前，我写了一个使用 Neo4j 图形数据库处理 DAG的简单示例，这可能对您有用。

于 2010-09-20T22:46:15.793 回答
0

在关系数据库中，我将为每个节点存储：

  • 父亲
  • 孩子们
  • 祖先

对所有内容都有索引，对祖先有完整索引

要求 ：

  • 所有的祖先：
    • O(log n) （找到节点然后你就完成了）
  • 所有后代：
    • O（对祖先的全索引搜索）（取决于数据库）
  • 添加新节点/删除节点（没有子节点）：
    • O(1) 对于父亲+祖先
    • O(log n) 找到父亲
    • 更新父亲的孩子 O(|父亲的孩子|)
  • 移动节点（困难）：
    • O(1) 更新父亲
    • O(log n) 找到新老父亲
    • 更新父亲的孩子两次 O(|父亲的孩子|)
    • 更新所有后代的祖先（简单替换）： O(|descendants|*|depth max tree|) (depth-max : 替换并创建最大长度的大字符串 (depth-max) )

总体复杂性将取决于：

  • 树的深度
  • 平衡树？
  • 孩子的数量？（平均，最大...）
  • 给定关系数据库中的操作复杂度

仅适用于 SELECT，高效，但难以更新。

在实践中：在 RAM 大小的树上工作（例如，使用 memchaed，将所有内容保存在 RAM 中），如果不可能购买更多的 RAM，则“cur”你的树在较小的树中。

无论如何，所有后代都会花费很多，使用子树，您可以拥有最大深度 D 的后代，而无需拥有所有后代。

您从子树“跳”到子树：更多请求但更快，并且更快地移动节点（只需要更新子树）。

于 2010-09-23T14:46:30.407 回答