假设我有一个无圈有向图,例如一个家族“树”(实际上不是一棵树,因为一个孩子有两个父母)。我希望将此图的表示放在关系数据库中,以便快速计算节点的所有祖先和节点的所有后代。你怎么表示这张图?您将如何查询所有的后代?如何插入和删除节点和关系?你对这些数据做了什么假设?
对于查询祖先和后代的select/insert/delete语句的数量,最好的解决方案将有最好的大O,而在总的运行时,领带被最好的大O所打破,而领带被空间需求打破。
我的同事向我提出了这个问题。我有一个解决方案,但在最坏的情况下,它是指数大小的,所以我想看看其他人会如何解决它。
编辑
澄清关系数据库。如果您使用内置在传递闭包中的图形数据库,那么这个问题就很简单(也很无聊)。
发布于 2010-09-20 21:18:11
如果selects > manipulations,特别是子树选择(所有祖先,所有后代),我将选择闭包-table方法。是的,路径表中路径的爆炸式增长,但它确实能快速传递结果(相对于邻接模型),并将更新限制在相关部分(相对于嵌套集更新的50% )。
Bill在网上有一些关于不同型号的优缺点的很好的介绍,参见http://www.slideshare.net/billkarwin/models-for-hierarchical-data (幻灯片48是一个概述)。
发布于 2010-09-23 16:41:38
发布于 2010-09-20 22:46:15
S不是真正设计用来处理这种数据的。最明显的选择是使用图形数据库,然后不需要将图转换成不同的表示,而是一路使用图形API。Marko在处理图遍历时很好地解释了底层数据模型的影响,如果您想深入了解这一点,请参阅图遍历编程模式。
不久前,我编写了一个简单的用Neo4j图形数据库处理DAG示例,它可能对您有用。
https://stackoverflow.com/questions/3755439
复制相似问题