如何为树结构开发数据库模式(定向非循环图)

Question

我正在使用下面的树结构并计划为下面的开发数据库模式.

我到目前为止的发展如下,

我遇到的问题是如果我搜索Y,应该生成树下面.

我正在使用的逻辑是,Y有两个交叉引用X,Z,这两个节点应该在图中,父节点一直到起始父节点.

鉴于我正在使用PHP使用mysql db表生成此树,如上所示.DB结构可以改变.我在谷歌搜索了类似的树结构,但我找不到任何帮助.

注意

我不是要求你为我编写代码.所有我要问的是如何做到这一点的指导.

我发现下面有帮助,但仍然与我的情况不同

将平台解析成树的最有效/优雅的方法是什么？

如何在db中表示树状结构

如果有人可以请告诉我应该使用什么PHP库来生成树,以及使用什么是合适的数据库结构？

Answer 1

您的数据库结构似乎不是树,它只是图形.

我建议你抛弃这个结构的关系数据库,看一下像Neo4j,OrientDB和Infinite Graph这样的图形数据库.

但是如果你被迫使用MySQL,你可以使用FlockDB,它可以用来遍历MySQL节点(参见行作为节点),但有一些限制.或者您可以测试另一个像OQGRAPH这样的MySQL引擎,它为MySQL和MariaDB提供图形引擎.

Answer 2

让我重申一下这个问题,以确保我理解正确.你有节点和两种关系 - 箭头和垂直线.然后给定节点N,您希望生成具有以下递归规则的节点的子集S(N):

• 规则0:N在S(N)中.
• 规则1:如果节点M通过垂直关系与N连接,则它也在S(N)中.
• 规则2:如果节点M在S(N)中,则具有指向M的箭头的任何节点也在S(N)中.

集合S(N)是满足那些规则的最小节点集合.

你给N的例子是Y,似乎证实了这些规则.

然而,还有另一种不同但(至少对我而言)更自然的规则集,其中上面的规则1被替换为

• 规则1':如果节点M在S(N)中,则通过垂直关系与M连接的任何节点也在S(N)中.

在续集中,我将假设您的示例确认规则0,1,2,但类似的方法可用于规则0,1',2或任何修改.

另外我知道第7行的表中有一个错误,它应该是:

7    B2    B    B1,B3 (not B2,B3)

现在提出解决方案.

我首先稍微修改一下你的表结构:由于"id"是你的主键,外键的规则是指向相关条目的主键.也就是说,在你的情况下,我会将"node_id"替换为"node_name"或类似的东西,以免与"id"混淆,并用"id"替换"node_parent_id"和"cross_ref"的条目.例如,行号15看起来像这样:

15    'Y'    [13]    [14,16]

或者,如果您希望出于可读性的原因,您可以使用A,B,X,Y等作为主键,前提是它们是唯一的,那么您的表格将保持不变,但"id"字段除外不需要.我将假设第一种情况,但您可以通过简单的替换将其调整到第二种情况.

就表而言,这就是你所需要的一切.

现在你需要一个递归函数来为每个给定的Node N生成子图S(N).

我将实现集合S作为其节点的所有'id'的数组$ set.然后我将定义两个函数 - 一个用于最初基于规则1,2扩展集合,另一个用于仅基于规则2扩展集合.

为简单起见,我假设您的表作为关联数组$行导入内存,这样$ rows [$ id]表示'id'等于$ id的行,再次表示关联数组.所以

$rows[15] = array('id'=>15, 
                  'node_name'=>'Y', 
                  'node_parent_id'=>array(13), 
                  'cross_ref'=>array(14,16)
);

这是函数的代码:

function initial_expand_set ($node_id) {
    global($rows); // to access the array from outside
    $set = array($node_id);    // Rule 0
    $row = $rows[$node_id];    // Get current Node

    $parents = $row['node_parent_id'];  // Get parents of the Node
    $set = $parents ? array_merge ($set, $parents) : $set;   // Join parents to the set

    $vert_brothers = $row['cross_ref'];  // Get vertical relations
    $set = $vert_brothers ? array_merge ($set, $vert_brothers) : $set;

    $set = expand_set($set);  // Recursive function defined below
    return $set;
}

和递归函数:

// iterate over nodes inside the set, expand each node, and merge all together
function expand_set (array $set) {
    global($rows);
    $expansion = $set;  //  Initially $expansion is the same as $set
    foreach ($set as $node_id) {
        $row = $rows[$node_id];    // Get Node 

        // Get the set of parents of the Node - this is our new set
        $parents = $row['node_parent_id'];  // Get parents of the Node

        // apply the recursion
        $parents_expanded = expand_set($parents);

        // merge with previous expansion
        $expansion = array_merge($expansion, $parents_expanded);
    }
    // after the loop is finished getting rid of redundant entries
    // array_unique generates associative array, for which I only collect values
    $expansion = array_values( array_unique($expansion) );
    return $expansion;
}

希望对你有效.:)

如果需要任何进一步的细节或解释,我将很乐意提供帮助.

PS.对于读者中的小学生,请注意我在'('用于函数定义之前使用空格,而没有用于函数调用的空间,正如Douglas Crokford所推荐的那样.

Answer 3

您的数据库结构未标准化，因为 和 中都有多个node_parent_idid cross_refer。您应该将此信息分离到单独的表中。

因此，您将拥有一个nodes表，再加上第二个表来描述父子关系；该表将有一个子节点 id 和一个父节点 id。

交叉引用应该位于第三个表中，该表同样有两个节点 id 列，但有两种方法可以做到这一点，因为交叉引用是双向的。一种方法是仅存储每个交叉引用一次，这意味着当您查询表时，必须检查两种可能性（X 和 Y 之间的交叉引用可以存储为 X 在第一列，Y 在第二列，或相反，因此要找到 X，您必须检查两列）。另一种方法是将每个交叉引用存储两次，每个方向一次。这使得查询更简单，但它存储了冗余数据，并且可能导致不一致，例如，如果由于某种原因删除了一个引用而另一个没有删除。

使用这种结构查找路径变得更加简单，因为您不必另外解析逗号分隔的字符串，这既更复杂又效率更低。

您还可以使用它来确保引用完整性，例如，节点不会具有数据库中实际不存在的父 ID。

有关更多信息，请研究“数据库规范化”。（或者如果你愿意的话，你可以用“z”来拼写它；-P）