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

Question

假设我有一个无环有向图，例如家庭“树”(不是真正的树，因为 child 有 2 个 parent )。我想将此图的表示形式放入关系 数据库中，以便快速计算节点的所有祖先和节点的所有后代。你会如何表示这个图表？您将如何查询所有后代？您将如何插入和删除节点和关系？您对数据做出了哪些假设？

最佳解决方案将拥有最佳的大 O，用于查询祖先和后代的 select/insert/delete 语句的数量，与总运行时间的最佳大 O 打破了联系，有联系因空间要求而中断。

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

编辑

阐明了关系数据库。如果您使用带有内置传递闭包的图形数据库，这个问题很简单(而且很无聊)。

Answer 1

如果选择 > 操作，尤其是子树选择(所有祖先，所有后代)我会选择Closure -表方法。是的，路径表中的路径呈爆炸式增长，但它确实可以快速提供结果(与邻接模型相反)，并将更新限制在相关部分(与嵌套集的 50% 更新相反)。

Bill Karwin 在网上有一些关于不同模型优缺点的精彩演讲，请参阅 http://www.slideshare.net/billkarwin/models-for-hierarchical-data (幻灯片 48 是概述)。