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

如果 selects &燃气轮机; manipulations Closure -表格法。是的,路径表中的路径爆炸,但它确实可以快速交付结果(与邻接模型相反),并将更新限制在相关部分(与嵌套集的50%更新相反)。

Bill Karwin在网上做了一些很好的演示,介绍了不同型号的优缺点,请参阅 http://www.slideshare.net/billkarwin/models-for-hierarchical-data (幻灯片48是概述)。

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

1. 递归WITH子句。

2. Transitive closure

RDBMS:不存在不是专门用来处理这种数据的。显而易见的选择是使用 graph database 相反,不需要将图形转换为不同的表示形式,您可以一直使用图形API。Marko Rodriguez的一个很好的演示文稿解释了在处理图遍历时底层数据模型的影响,请参阅 The Graph Traversal Programming Pattern 如果你想深入研究的话。

我写了一个简单的例子 handling DAGs with the Neo4j graph database 不久前这可能对你有用。

• 变量节点关系{节点:sometype}密钥{节点};
• 可变边关系{parentNode:sometype子节点:sometype}键{parentNode childNode};

“如何查询所有后代?”

t关闭(边),其中parentNode=somevalue;

“如何插入和删除节点和关系?”

• 插入到边关系{TUPLE{parentNode somevalue chlidNode somevalue};
• 删除删除条件的边;

“你对这些数据做了什么假设?”

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

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

• 父亲
• 祖先

• • O(logn)(找到节点就完成了)
• 所有后代:
• • O(1)代表父亲+祖先
  • 更新父的childs O(|父的childs |)
• :
  • O(1)更新父
  • O(logn)查找新老父亲
  • 更新父的childs两次O(|父的childs |)
  • 更新所有子体的祖先(简单替换):O(|子体|*|深度最大树|)(深度最大:替换并创建最大长度的大字符串(深度最大))

• 树的深度
• 孩子的数量?(平均值,最大值…)

仅用于选择,高效,但难以更新。

在实践中:在公羊大小的树上工作(例如memchaed,把所有的东西都放在公羊里),如果不可能的话,买更多的公羊,把你的树“cur”放在更小的树上。

不管怎样,所有的子代都会花费很多,使用子树,您可以拥有最大深度D的子代,而不必拥有所有的子代。

您可以从一个子树“跳”到另一个子树:请求越多,请求越快,移动节点的速度就越快(只需要更新一个子树)。