SQL中的树(关于SQL树和层次结构的一些问题的答案)

翻译自：Trees in SQL by Joe Celko

这个主题是我的旧主题，但是值得重复的再谈一次，我在新闻讨论组中看到过太多关于SQL树和层次结构的问题。SQL书籍中树结构的常见示例称为邻接列表明细，它如下所示：

CREATE TABLE Personnel (
 emp CHAR(10) NOT NULL PRIMARY KEY,
 boss CHAR(10) DEFAULT NULL REFERENCES Personnel (emp),
 salary DECIMAL (6,2) NOT NULL DEFAULT 100.00
);

复制

另外一种表示树的方法是将他们显示为嵌套集，因为SQL是一种面向集合的语言，所以该模型比你在大多数教科书上看到的常见的邻接表更好。我们像这样定义一个简单的Personal表，暂时忽略左(lft)和右(rgt)列：

CREATE TABLE Personnel (
 emp CHAR(10) NOT NULL PRIMARY KEY,
 lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),
 rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1),
 CONSTRAINT order_okay CHECK (lft < rgt)
);

复制

这个问题总是在教科书书中为员工提供一列，为他的老板提供一列。这个表(表2)没有lft和rgt列--被称为邻接表模型，以同名的图论技术命名；节点对彼此相邻。

组织结构图类似于图1的有向图：

表1以多种方式进行了非规范化。我们在一张表中对人员和组织结构图进行建模。但是为了节省空间，假设名称是职位，并且我们有另一个表格来描述担任这个职位的人员。

邻接表模型的另外一个问题是，boss列和employee列是同一种类型（人员姓名），因此应该只显示在规范化表中的一列上。为了证明这不是规范化的，假设”Chuck“将他的名字改为”Charles“；你必须在两列和其他的地方更改他的名字。规范化表的定义特征是一次在一个地方有一个事实。

最后一个问题是邻接表模型没有对从属进行建模。权利在等级制度中向下流动，但如果我解雇Chuck，我就会断开他所有的下属和Albert的联系。有时(例如水管)确实如此，但在嵌套集中不会出现这种情况。

要将树显示为嵌套集，请将节点替换为椭圆，然后将下级椭圆相互嵌套。根将是最大的椭圆，将包含所有其他的节点。叶节点将是最里面的椭圆，里面没有任何其他东西，嵌套将显示层次关系。rgt列和lft列（不能在SQL中使用保留关键字LEFT和RIGHT）显示嵌套。

如果不理解这个模型，那么想象一条小虫子沿着树逆时针爬行。每次到达节点的左侧或右侧时，虫子都会对其进行编号，当虫子回到顶部时，它就会停止。

此模型是显示子节点的一种自然方式，因为最终装配是由其分解为单独节点的物理嵌套组成的。

此时，boss列既是多余的，又是非规范化的，因此可以将其删除。另外注意，树型结构可以保存在一张表中，有关节点的所有信息可以放在第二张表中，你可以在员工编号上加入两者以进行查询。

要将图形转换为嵌套集模型，请考虑沿着树爬行的小虫子。虫子从顶部(根部)开始，然后绕着树完整的走一圈，当涉及到一个节点时，它就会在它正在访问的一侧单元格中放置一个数字并增加计数器。每个节点将得到两个数字-一个用于右侧(rgt)，一个用于左侧(lft)。（计算机科学专业的学生会认为这是一种经过修改的预排序树的遍历算法），最后删除不需要的”Personnel.boss“列，它表示图的变。

这有一些可预测的结果，我们可以使他们来构建查询。根的形式总是(lft=1,rgt=2 * (SELECT COUNT(*) FROM TreeTable)
)，叶子节点总是有(lft+1=rgt)，between谓词定义了子树等等；以下是一些可用于构建其他查询的常见查询：

1. 找到一个员工的所有主管，无论树有多深。

    SELECT
     P2.*
    FROM
     Personnel AS P1,
     Personnel AS P2
    WHERE
     P1.lft BETWEEN P2.lft
     AND P2.rgt
     AND P1.emp = :myemployee;
   
   复制

2. 找到该员工及其所有下属（此查询与第一个查询具有很好的对称性）。

   SELECT
    P2.*
   FROM
    Personnel AS P1,
    Personnel AS P2
   WHERE
    P1.lft BETWEEN P2.lft
    AND P2.rgt
    AND P2.emp = :myemployee;
   
   复制

3. 将group by和其他的聚合函数添加到这些基本查询中，你就有了分层的报告。例如，每个员工控制的总工资。

   SELECT
    P2.emp,
    SUM(S1.salary)
   FROM
    Personnel AS P1,
    Personnel AS P2,
    Salaries AS S1
   WHERE
    P1.lft BETWEEN P2.lft
    AND P2.rgt
    AND P1.emp = S1.emp
   GROUP BY
    P2.emp;
   
   复制

   在邻接表模型中，你必须使用游标来完成这个功能。

4. 找到每个节点的级别，以便你可以将树打印为缩进列表。

   SELECT
    COUNT(P2.emp) AS indentation,
    P1.emp
   FROM
    Personnel AS P1,
    Personnel AS P2
   WHERE
    P1.lft BETWEEN P2.lft
    AND P2.rgt
   GROUP BY
    P1.emp
   ORDER BY
    P1.lft;
   
   复制

5. 嵌套集模型具有邻接表模型没有的兄弟姐妹的隐含排序。插入一个新的节点作为最右边节点的兄弟节点。

   BEGIN
   DECLARE
    right_most_sibling INTEGER;
    SET right_most_sibling = (
    SELECT
     rgt
    FROM
     Personnel
    WHERE
     emp = :your_boss);
    UPDATE
     Personnel
    SET
     lft = CASE WHEN lft > right_most_sibling THEN
      lft + 2
     ELSE
      lft
     END,
     rgt = CASE WHEN rgt >= right_most_sibling THEN
      rgt + 2
     ELSE
      rgt
     END
    WHERE
     rgt >= right_most_sibling;
    INSERT INTO Personnel (emp, lft, rgt)
     VALUES('New Guy', right_most_sibling, (right_most_sibling + 1))
   END;
   
   复制

6. 要将邻接表模型转换为嵌套集模型，请使用下推堆栈算法。假设我们有这些表：

   树持有邻接表模型。

   CREATE TABLE Tree
   (emp CHAR(10) NOT NULL,
   boss CHAR(10));
   
   INSERT INTO Tree
   SELECT emp, boss FROM Personnel;
   
   -- Stack starts empty, will holds the nested set model
   CREATE TABLE Stack
   (stack_top INTEGER NOT NULL,
   emp CHAR(10) NOT NULL,
   lft INTEGER,
   rgt INTEGER);
   
   BEGIN
    ATOMIC
   DECLARE
    counter INTEGER;
   DECLARE
    max_counter INTEGER;
   DECLARE
    current_top INTEGER;
    SET counter = 2;
    SET max_counter = 2 * (
    SELECT
     COUNT(*)
     FROM
      Tree);
    SET current_top = 1;
    INSERT INTO Stack
    SELECT
     1,
     emp,
     1,
     NULL
    FROM
     Tree
    WHERE
     boss IS NULL;
    DELETE FROM Tree
    WHERE boss IS NULL;
    WHILE counter <= (max_counter - 2)
    LOOP
     IF EXISTS (
      SELECT
       *
      FROM
       Stack AS S1,
       Tree AS T1
      WHERE
       S1.emp = T1.boss
       AND S1.stack_top = current_top) THEN
   BEGIN
    -- push when top has subordinates, set lft value
    INSERT INTO Stack
    SELECT
     (current_top + 1), MIN(T1.emp), counter, NULL
    FROM
     Stack AS S1,
     Tree AS T1
    WHERE
     S1.emp = T1.boss
     AND S1.stack_top = current_top;
    DELETE FROM Tree
    WHERE emp = (
      SELECT
       emp
      FROM
       Stack
      WHERE
       stack_top = current_top + 1);
    SET counter = counter + 1;
    SET current_top = current_top + 1;
   END
   ELSE
    BEGIN
     -- pop the stack and set rgt value
     UPDATE
      Stack
     SET
      rgt = counter,
      stack_top = - stack_top -- pops the stack
     WHERE
      stack_top = current_top
     SET
      counter = counter + 1;
    SET current_top = current_top - 1;
   END IF;
   END LOOP;
   END;
   
   
   复制

   尽管此过程有效，但是你可能希望使用一种包含数组的语言，而不是坚持使用SQL。