SQL - 如何存储和导航层次结构？

Question

您在数据库中建模和检索分层信息的方式有哪些？

Answer 1

我喜欢Modified Preorder Tree Traversal算法.这种技术使查询树变得非常容易.

但是这里有一个关于这个主题的链接列表,我从Zend Framework(PHP)贡献者网页上复制了这个主题(由Laurent Melmoux发布于2007年6月5日15:52).

许多链接都是语言无关的:

有两种主要的表示和算法来表示具有数据库的层次结构:

• 嵌套集也称为修改前序树遍历算法
• 邻接表模型

这里有很好的解释:

• http://www.sitepoint.com/article/hierarchical-data-database
• 在MySQL中管理分层数据
• http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html

以下是我收集的一些链接:

• http://en.wikipedia.org/wiki/Tree_%28data_structure%29
• http://en.wikipedia.org/wiki/Category:Trees_%28structure%29

邻接表模型

• http://www.sqlteam.com/item.asp?ItemID=8866

嵌套集

• http://www.sqlsummit.com/AdjacencyList.htm
• http://www.edutech.ch/contribution/nstrees/index.php
• http://www.phpriot.com/d/articles/php/application-design/nested-trees-1/
• http://www.dbmsmag.com/9604d06.html
• http://en.wikipedia.org/wiki/Tree_traversal
• http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html(applet java montrant le fonctionnement)

Graphes

• http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html

课程:

嵌套集DB树Adodb

• http://www.phpclasses.org/browse/package/2547.html

访问模型ADOdb

• http://www.phpclasses.org/browse/package/2919.html

PEAR :: DB_NestedSet

• http://pear.php.net/package/DB_NestedSet
• 利用率:https://www.entwickler.com/itr/kolumnen/psecom,id,26,nodeid,207.html

梨树

• http://pear.php.net/package/Tree/download/0.3.0/
• http://www.phpkitchen.com/index.php?/archives/337-PEARTree-Tutorial.html

nstrees

• http://www.edutech.ch/contribution/nstrees/index.php

Answer 2

关于这个主题的权威部分是由Joe Celko编写的,他已经将其中的一些作品编写成了一本名为Joe Celko的树和层次结构的SQL for Smarties.

他赞成一种称为有向图的技术.可在此处找到他关于此主题的工作介绍

Answer 3

在SQL数据库中表示层次结构的最佳方法是什么？一种通用的便携式技术？

我们假设层次结构主要是读取的,但不是完全静态的.让我们说这是一棵家谱.

这是不怎么做:

create table person (
person_id integer autoincrement primary key,
name      varchar(255) not null,
dob       date,
mother    integer,
father    integer
);

并插入如下数据:

person_id   name      dob       mother father  
1           Pops      1900/1/1   null   null  
2           Grandma   1903/2/4   null   null  
3           Dad       1925/4/2   2      1  
4           Uncle Kev 1927/3/3   2      1
5           Cuz Dave  1953/7/8   null   4
6           Billy     1954/8/1   null   3

相反,将节点和关系拆分为两个表.

create table person (
person_id integer autoincrement primary key,
name      varchar(255) not null,
dob       date
);

create table ancestor (
ancestor_id   integer,
descendant_id integer,
distance      integer
);

数据创建如下:

person_id   name      dob       
1           Pops      1900/1/1  
2           Grandma   1903/2/4   
3           Dad       1925/4/2   
4           Uncle Kev 1927/3/3
5           Cuz Dave  1953/7/8   
6           Billy     1954/8/1   

ancestor_id  descendant_id  distance
1            1              0
2            2              0
3            3              0
4            4              0
5            5              0
6            6              0
1            3              1
2            3              1
1            4              1
2            4              1
1            5              2
2            5              2
4            5              1
1            6              2
2            6              2
3            6              1

现在,您可以运行不涉及将表连接回自身的仲裁查询,如果您在与节点相同的行中具有heirachy关系,则会发生这种情况.

谁有祖父母？

select * from person where person_id in 
    (select descendant_id from ancestor where distance=2);

你所有的后代:

select * from person where person_id in 
    (select descendant_id from ancestor 
    where ancestor_id=1 and distance>0);

谁是叔叔？

select decendant_id uncle from ancestor 
    where distance=1 and ancestor_id in 
    (select ancestor_id from ancestor 
        where distance=2 and not exists
        (select ancestor_id from ancestor 
        where distance=1 and ancestor_id=uncle)
    )

您可以避免通过子查询将表连接到自身的所有问题,常见的限制是16个子查询.

麻烦的是,维护祖先表有点难 - 最好用存储过程完成.

Answer 4

我不得不同意乔希.如果您使用像公司组织这样的庞大层级结构会发生什么.人们可以加入/离开公司,更改报告行等...维持"距离"将是一个大问题,您将不得不维护两个数据表.

此查询(SQL Server 2005及更高版本)将允许您查看任何人的完整行并计算它们在层次结构中的位置,并且它只需要一个用户信息表.可以修改它以查找任何子关系.

--Create table of dummy data
create table #person (
personID integer IDENTITY(1,1) NOT NULL,
name      varchar(255) not null,
dob       date,
father    integer
);

INSERT INTO #person(name,dob,father)Values('Pops','1900/1/1',NULL);  
INSERT INTO #person(name,dob,father)Values('Grandma','1903/2/4',null);
INSERT INTO #person(name,dob,father)Values('Dad','1925/4/2',1);
INSERT INTO #person(name,dob,father)Values('Uncle Kev','1927/3/3',1);
INSERT INTO #person(name,dob,father)Values('Cuz Dave','1953/7/8',4);
INSERT INTO #person(name,dob,father)Values('Billy','1954/8/1',3);

DECLARE @OldestPerson INT; 
SET @OldestPerson = 1; -- Set this value to the ID of the oldest person in the family

WITH PersonHierarchy (personID,Name,dob,father, HierarchyLevel) AS
(
   SELECT
      personID
      ,Name
      ,dob
      ,father,
      1 as HierarchyLevel
   FROM #person
   WHERE personID = @OldestPerson

   UNION ALL

   SELECT
    e.personID,
      e.Name,
      e.dob,
      e.father,
      eh.HierarchyLevel + 1 AS HierarchyLevel
   FROM #person e
      INNER JOIN PersonHierarchy eh ON
         e.father = eh.personID
)

SELECT *
FROM PersonHierarchy
ORDER BY HierarchyLevel, father;

DROP TABLE #person;