Dav*_*ith 8 database algorithm graph family-tree
假设我有一个非循环有向图,例如一个家庭"树"(因为一个孩子有2个父母,所以不是真正的树).我想在关系数据库中放置此图的表示,以便快速计算节点的所有祖先以及节点的所有后代.你会如何表示这张图？你会如何查询所有后代？您将如何插入和删除节点和关系？您对数据做出了哪些假设？
select/insert/delete对于查询祖先和后代运行的语句数量,最佳解决方案将具有最佳的大O,并且在总运行时间中由最佳大O打破,并且由空间要求打破关系.
我的同事向我提出了这个问题.我有一个解决方案,但在最坏的情况下它是指数大小所以我想看看其他人如何解决它.
编辑
阐明了关系数据库.如果您使用具有内置传递闭包的图数据库,这个问题是微不足道的(而且很无聊).
如果selects> manipulations,特别是子树选择(所有祖先,所有后代),我会选择一个Closure -table方法.是的,路径表中的路径爆炸,但它确实快速提供结果(与邻接模型相反),并且将更新限制在相关部分(而不是使用嵌套集进行50%更新).
Bill Karwin在网上有一些关于不同模型的优缺点的精彩演示,请参阅http://www.slideshare.net/billkarwin/models-for-hierarchical-data (幻灯片48是概述).