首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >无圈有向图上祖先的高效数据库查询

问无圈有向图上祖先的高效数据库查询
EN

Stack Overflow用户
提问于 2010-09-20 20:56:39
回答 5查看 3.3K关注 0票数 8

假设我有一个无圈有向图,例如一个家族“树”(实际上不是一棵树,因为一个孩子有两个父母)。我希望将此图的表示放在关系数据库中,以便快速计算节点的所有祖先和节点的所有后代。你怎么表示这张图?您将如何查询所有的后代?如何插入和删除节点和关系?你对这些数据做了什么假设?

对于查询祖先和后代的select/insert/delete语句的数量,最好的解决方案将有最好的大O,而在总的运行时,领带被最好的大O所打破,而领带被空间需求打破。

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

编辑

澄清关系数据库。如果您使用内置在传递闭包中的图形数据库,那么这个问题就很简单(也很无聊)。

EN

回答 5

Stack Overflow用户

回答已采纳

发布于 2010-09-20 21:18:11

如果selects > manipulations,特别是子树选择(所有祖先,所有后代),我将选择闭包-table方法。是的,路径表中路径的爆炸式增长,但它确实能快速传递结果(相对于邻接模型),并将更新限制在相关部分(相对于嵌套集更新的50% )。

Bill在网上有一些关于不同型号的优缺点的很好的介绍,参见http://www.slideshare.net/billkarwin/models-for-hierarchical-data (幻灯片48是一个概述)。

票数 8
EN

Stack Overflow用户

发布于 2010-09-23 16:41:38

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

  1. 递归WITH子句
  2. 传递闭包

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

票数 4
EN

Stack Overflow用户

发布于 2010-09-20 22:46:15

S不是真正设计用来处理这种数据的。最明显的选择是使用图形数据库,然后不需要将图转换成不同的表示,而是一路使用图形API。Marko在处理图遍历时很好地解释了底层数据模型的影响,如果您想深入了解这一点,请参阅图遍历编程模式。

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

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/3755439

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档