以有效和简单的方式实现等级,父/子关系

Question

我有一张桌子

create table site
(
site_Id int(5),
parent_Id int(5),
site_desc varchar2(100)
);

领域的意义:

• site_Id:网站的ID
• parent_Id:站点的父ID
• site_desc:虽然与问题无关,但它有网站的描述

要求是,如果我有一个site_id作为输入,我需要在网站下面标记所有ID.例如:

                    A
                   / \
                  B   C
                / | \ /\
               D  E F G H
              /\
             I  J

所有节点都是site_Id.

该表包含如下数据:

Site_id  | Parent_ID  |  site_desc
_________|____________|___________
 A       |   -1       |   
 B       |    A       |
 C       |    A       |
 D       |    B       |
 E       |    B       |
 F       |    B       |
 I       |    D       |
 J       |    D       |

......

A是B和C的父级,依此类推.

如果B是给定的输入,那么查询需要获取D,E,I,F,J

它目前通过循环中的多个查询来实现,但我想在最少数量的查询中实现这一点.

我目前正在做的是::

投票

算法如下:

Initially create a data set object which you will populate, by fetching data from the data base. 
Create a method which takes the parent id as parameter and returns its child nodes if present, and returns -1, if it doesnt have a child. 
Step1: Fetch all the rows, which doesn't have a parent(root) node. 
Step2: Iterate through this result. For example if prod1 and prod2 are the initial returned nodes, in the resultset. 
Iterating this RS we get prod1, and we insert a row in our DataSET obj. 
Then we send the id of prod1 to getCHILD method, to get its child, and then again we iterate the returned resultset, and again call the getCHILD method, till we dont get the lowest node.

我需要在数据模型约束中使用最佳优化技术.如果您有任何建议,请随时回答.
请提出建议.提前致谢.

Answer 1

不幸的是,如果您无法更改数据模型,并且您正在使用MySQL,那么您将陷入需要递归查询并且您使用不支持递归查询的DBMS的情况.

Quassnoi写了一系列有趣的博客文章,展示了查询分层数据的技巧.他的解决方案非常聪明,但非常复杂. http://explainextended.com/2009/03/17/hierarchical-queries-in-mysql/

PostgreSQL是另一个开源RDBMS,它支持递归查询,因此您可以获取以您显示的方式存储的整个树.但是如果你不能改变数据模型,我假设你不能切换到不同的RDBMS.

有几种替代数据模型可以更容易地获取任意深度的树:

• 关闭表
• 嵌套集又名修改预订树遍历
• 路径枚举又称物化路径

我在我的演示文稿中介绍了使用SQL和PHP的分层数据模型,以及我的书" SQL反模式:避免数据库编程的缺陷".

最后,还有我在Slashdot代码中看到的另一个解决方案,用于它们的注释层次结构:它们像在Adjacency List中一样存储"parent_id",但它们也存储了一个"root_id"列.给定树的每个成员对于root_id具有相同的值,root_id是其树中最高的祖先节点.然后在一个查询中很容易获取整个树:

SELECT * FROM site WHERE root_id = 123;

然后,您的应用程序将所有节点从数据库中取回到数组中,您必须编写代码以循环此数组,将节点插入内存中的树数据结构.如果您有许多单独的树,并且每个树的条目相对较少,这是一个很好的解决方案.对Slashdot来说这很好.

Answer 2

昨天,我已经回答了这个问题,这恰好与你的问题你所描述:出给定的邻接表的,你想获得一个特定父的所有子节点 -也许在一维数组,你可以很容易地迭代.

您只需对数据库进行一次调用即可完成此操作,但有一些问题:您必须从表中返回所有行.MySQL不支持递归查询,因此您必须SELECT在应用程序代码中执行此操作.

我只是重申我上面链接的答案,但基本上如果你返回一个结果集(可能来自PDOStatement->fetchAll(PDO::FETCH_ASSOC)或其他方法),格式如下:

Array
(
    [0] => Array
    (
        [site_id] => A
        [parent_id] => -1
        [site_desc] => testtext
    )
    [1] => Array
    (
        [site_id] => B
        [parent_id] => A
        [site_desc] => testtext
    )
    [2] => Array
    (
        [site_id] => C
        [parent_id] => A
        [site_desc] => testtext
    )
    [3] => Array
    (
        [site_id] => D
        [parent_id] => B
        [site_desc] => testtext
    )
    [4] => Array
    (
        [site_id] => E
        [parent_id] => B
        [site_desc] => testtext
    )
    [5] => Array
    (
        [site_id] => F
        [parent_id] => B
        [site_desc] => testtext
    )
    [6] => Array
    (
        [site_id] => I
        [parent_id] => D
        [site_desc] => testtext
    )
    [7] => Array
    (
        [site_id] => J
        [parent_id] => D
        [site_desc] => testtext
    )
)

您可以site_id使用此递归函数检索所有子/孙子/曾祖父/等等(如果您知道id):

function fetch_recursive($src_arr, $id, $parentfound = false, $cats = array())
{
    foreach($src_arr as $row)
    {
        if((!$parentfound && $row['site_id'] == $id) || $row['parent_id'] == $id)
        {
            $rowdata = array();
            foreach($row as $k => $v)
                $rowdata[$k] = $v;
            $cats[] = $rowdata;
            if($row['parent_id'] == $id)
                $cats = array_merge($cats, fetch_recursive($src_arr, $row['site_id'], true));
        }
    }
    return $cats;
}

例如,假设您想要检索所有子项site_id D,您将使用如下函数:

$nodelist = fetch_recursive($pdostmt->fetchAll(PDO::FETCH_ASSOC), 'D');
print_r($nodelist);

输出:

[0] => Array
(
    [site_id] => D
    [parent_id] => B
    [site_desc] => testtext
)
[1] => Array
(
    [site_id] => I
    [parent_id] => D
    [site_desc] => testtext
)
[2] => Array
(
    [site_id] => J
    [parent_id] => D
    [site_desc] => testtext
)

请注意,我们保留父母及其子女,孙子等的信息(无论嵌套深度如何).

Answer 3

如果您希望能够在单个查询中执行此操作,请查看嵌套集模型:http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

另一种方法是在链接表中包含所有关系.因此,每个站点都会有一个指向其父级,祖父级等的链接.每个关系都是明确的.然后,您只需查询该链接表以获取所有后代.