在数据库中表示无根树/图表/层次结构

Question

在数据库中表示无根树/图表/层次结构

sqlms-accessdatabase-designrelational-database

4

在数据库中表示分层数据似乎有几个很好的选项，其中最流行的显然是树遍历算法。

在我的情况下，另一个可能起作用的选项是递归。这可能涉及保存父ID并从那里开始——虽然这也需要某种方向。

现在我有一个问题，我有一组可以由连接图表来描述连接的项目，但没有根和不一定有起点。例如，可能会发生项目彼此环绕，因此排序仅为元素而不完整。无论排序是“父”还是“子”取决于您从哪个方向开始，这是一种说法。此外，每个连接应该通过多个属性进行特征化，因此需要以某种方式识别连接。以下是一个示例，尽管请注意它只是一个小示例，但您已经可以看到简单的遍历算法可能从254开始，然后从203到162，然后254实际上是162的子代-这可能是个问题（我远非计算机科学专业）所以我真的不知道） example

另一件事是我限制在Access中，这意味着我几乎只能使用标准SQL命令，而没有递归或SQL函数。例如，在SQL中许多算法在飞行中将其转换为左/右遍历树的算法不适用于Access SQL。我对解决这个问题没有太多依赖于VBA也有很大兴趣。

就性能而言，我预计少于5000个项目，虽然涉及元素属性和它们的连接的查询可能有数十个元素。首先只有不到10个用户同时使用数据库，但如果它们工作良好，这些事情往往会迅速扩展。

那么，您将如何实现此结构？

- IMA

我承认我没有详细查看您的问题。不过，您是否阅读过Joe Celko关于嵌套集的文章？这可能会给您一些启示。 http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html - Vinny Roe

1

我已经阅读了那个特定的网站。我知道他有一本书，但我没有。也许我完全错了，但我相信由于元素顺序未定义，我的交易会遇到麻烦。 - IMA

如何将图表（通过算法）分成可以通过树遍历呈现的部分？一定有一种方法可以保存这些信息。我的意思是，我可以创建一个常规的n:n类型关系表，但我仍然需要一个算法来输出任何一个元素的相关连接。 - IMA

如果物品A连接到物品B，这是否总是意味着物品B连接到物品A？此外，A->B的连接是否可能具有与B->A不同的属性？我试图确定这个图形是定向的，以及属性是否具有方向特定性。另外，属性是否预先定义（因此可以用一堆字段表示），或者您需要能够动态添加它们？ - Branko Dimitrijevic

2

... 排序是“父级”或“子级”，取决于您从哪个方向开始 ... 因此它不是有向图；因此不是树形结构或层次结构。从这里开始，http://techportal.inviqa.com/2009/09/07/graphs-in-the-database-sql-meets-social-networks/ - Damir Sudarevic

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mwolfe02 · Accepted Answer

我使用了Joe Celko的嵌套集方法。它在正确的情况下运作得非常好。但这不是那种情况。

一个更加灵活的方法，也是我推荐您使用的方法，是Bill Karwin所谓的闭包表。

基本思路是为每条路径都有一条记录。Bill建议使用两个字段：祖先ID和后代ID。从您的图中不清楚祖先/后代范例是否真的适用于您的情况。

我还发现增加至少一个字段来记录节点之间跳数很有用。我会通过创建一个具有三个字段的表来调整Bill的方法：

1. NodeA 2. NodeB 3. Hops

以下是您的图表的一些示例数据：

NodeA   NodeB  Hops
------  ------ ----
tog171  tog171  0
tog171  abb521  1
abb521  tog171  1
tog171  tog226  2
tog226  tog171  2
tog171  tog218  3
tog218  tog171  3

如果不同颜色的线和实线与虚线有一些语义意义，那么您的表格还可以添加一个捕获该语义意义的附加字段。您最终会在表格中得到很多条目，但是灵活性几乎是无限的。从您的图表中看，灵活性似乎是您最需要的。编辑：在我的示例数据中，具有0个跳数的第一行实际上是我从PJ Eby的博客文章中学到的技巧The simplest(?) way to do tree-based queries in SQL。这些节点的目的是使节点的插入和删除更简单。我强烈推荐该页面，以获取有关实现闭包表的详细概述。我认为PJ Eby的页面实际上是编写闭包表的更好资源，而Bill Karwin的答案则提供了一些从表格中读取的好例子。