在无环有向图上祖先的高效数据库查询

Question

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

最好的解决方案将拥有最好的大o select/insert/delete 您跑到查询祖先和后代的陈述，最佳Big O打破了整个运行时的联系，并因空间要求而打破了联系。

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

编辑

澄清的关系数据库。如果您使用内置及时封闭的图形数据库，则此问题是微不足道的（和无聊）。

Answer 1

如果 selects > manipulations, ，尤其是子树选择（所有祖先，所有后代）我会去 关闭- 表。是的，您的路径表中的路径爆炸式增长，但确实可以快速提供结果（与邻接模型相反），并将更新仅限于相关部分（而不是使用嵌套集的50％更新）。

比尔·卡尔文（Bill Karwin http://www.slideshare.net/billkarwin/models-for-hierarchical-data （幻灯片48是一个概述）。

Answer 2

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

1. 递归条款。

2. 传递闭合

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

Answer 3

“你如何表示这张图？”

• var nodes关系{node：lye stype} key {node};
• var Edges Reliation {parentnode：fory stype childNode：lye stye} key {parentnode childnode};
• 约束no_cycles is_empty（tclose（edges），parentnode = childNode）;

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

tclose（edges）其中parentnode = someValue;

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

• 插入边缘关系{tuple {parentnode somevalue chlidnode somevalue}}}};
• 删除删除的边缘；

“您对数据有什么假设？”

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

Answer 4

RDBMS：S并非真正设计用于处理此类数据的设计。明显的选择是使用 图数据库 取而代之的是，无需将图形转换为不同的表示形式，您可以一直使用图形API。 Marko Rodriguez有一个很好的演讲，解释了在处理图形遍历时基础数据模型的影响，请参阅 图形遍历编程模式 如果您想更深入地研究。

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

Answer 5

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

• 父亲
• 孩子
• 祖先

在所有内容上都有索引和祖先的全索引

要求 ：

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

总体复杂性将取决于：

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

仅选择，高效，但很难更新。

实际上：在Ram大小的树上工作（例如，将所有内容都放在RAM中），如果不符合可能的话，请购买更多的RAM，在较小的树上树上“ Cur”您的树。

无论如何，所有居民的成本都会很大，而子树则可以拥有最大深度D的后代，而无需所有这些后树。

您“跳”表格子树向子树：更多请求，但更快的速度并更快地移动节点（只需要更新子树）。