将邻接列表层次结构展平为所有路径的列表

4 回答

• 0

  在一个简单的邻接列表中进行多级查询总是涉及自左连接 . 制作一个右对齐的表格很容易：

  SELECT category.category_id,
      ancestor4.category_id AS lvl4,
      ancestor3.category_id AS lvl3,
      ancestor2.category_id AS lvl2,
      ancestor1.category_id AS lvl1
  FROM categories AS category
      LEFT JOIN categories AS ancestor1 ON ancestor1.category_id=category.category_id
      LEFT JOIN categories AS ancestor2 ON ancestor2.category_id=ancestor1.parent
      LEFT JOIN categories AS ancestor3 ON ancestor3.category_id=ancestor2.parent
      LEFT JOIN categories AS ancestor4 ON ancestor4.category_id=ancestor3.parent;
  

  像你的例子一样左对齐它有点棘手 . 想到这一点：

  SELECT category.category_id,
      ancestor1.category_id AS lvl1,
      ancestor2.category_id AS lvl2,
      ancestor3.category_id AS lvl3,
      ancestor4.category_id AS lvl4
  FROM categories AS category
      LEFT JOIN categories AS ancestor1 ON ancestor1.parent IS NULL
      LEFT JOIN categories AS ancestor2 ON ancestor1.category_id<>category.category_id AND ancestor2.parent=ancestor1.category_id
      LEFT JOIN categories AS ancestor3 ON ancestor2.category_id<>category.category_id AND ancestor3.parent=ancestor2.category_id
      LEFT JOIN categories AS ancestor4 ON ancestor3.category_id<>category.category_id AND ancestor4.parent=ancestor3.category_id
  WHERE
      ancestor1.category_id=category.category_id OR
      ancestor2.category_id=category.category_id OR
      ancestor3.category_id=category.category_id OR
      ancestor4.category_id=category.category_id;
  

  适用于n层层次结构 .

  抱歉，在邻接列表模型中无法进行任意深度查询 . 如果您经常进行此类查询，则应将模式更改为other models of storing hierarchical information之一：完全邻接关系（存储所有祖先 - 后代关系），物化路径或嵌套集 .

  如果类别不会移动很多（这通常就像你的例子那样的商店），我倾向于嵌套集 .

  回复于 2024-05-04T19:51:20+08:00
• 1

  如前所述，SQL没有干净的方法来实现具有动态变化的列数的表 . 我之前使用的唯一两个解决方案是：1 . 固定数量的自连接，给出固定数量的列（每个BobInce的AS）2 . 在单个列中将结果生成为字符串

  第二个听起来很怪诞;将ID存储为字符串？！但是当输出格式化为XML或其他东西时，人们似乎并不介意这么多 .

  同样，如果您想要在SQL中加入结果，这几乎没用 . 如果要将结果提供给应用程序，则它可能非常合适 . 但就个人而言，我更喜欢在应用程序而不是SQL中进行展平

  我给出了测试代码，但基本方法是以某种方式利用递归;

  • 递归标量函数可以做到这一点
  • MS SQL可以使用递归WITH语句执行此操作（更高效）

  Scalar Function (something like):

  CREATE FUNCTION getGraphWalk(@child_id INT)
  RETURNS VARCHAR(4000)
  AS
  BEGIN
  
    DECLARE @graph VARCHAR(4000)
  
    -- This step assumes each child only has one parent
    SELECT
      @graph = dbo.getGraphWalk(parent_id)
    FROM
      mapping_table
    WHERE
      category_id = @child_id
      AND parent_id IS NOT NULL
  
    IF (@graph  IS NULL)
      SET @graph = CAST(@child_id AS VARCHAR(16))
    ELSE
      SET @graph = @graph + ',' + CAST(@child_id AS VARCHAR(16))
  
    RETURN @graph
  
  END
  
  
  SELECT
    category_id                         AS [category_id],
    dbo.getGraphWalk(category_id)       AS [graph_path]
  FROM
    mapping_table
  ORDER BY
    category_id
  

  我有一段时间没有使用递归的WITH，但即使我没有SQL来测试任何东西，我也会给出语法 .

  Recursive WITH

  WITH
    result (
      category_id,
      graph_path
    )
  AS
  (
    SELECT
      category_id,
      CAST(category_id AS VARCHAR(4000))
    FROM
      mapping_table
    WHERE
      parent_id IS NULL
  
    UNION ALL
  
    SELECT
      mapping_table.category_id,
      CAST(result.graph_path + ',' + CAST(mapping_table.category_id AS VARCHAR(16)) AS VARCHAR(4000))
    FROM
      result
    INNER JOIN
      mapping_table
        ON result.category_id = mapping_table.parent_id
  )
  
  SELECT
    *
  FROM
    result
  ORDER BY
    category_id
  

  EDIT - OUTPUT for both is the same:

  1   '1'
  2   '1,2'
  3   '1,2,3'
  4   '1,2,4'
  5   '1,2,5'
  6   '1,6'
  7   '1,6,7'
  8   '1,6,7,8'
  9   '1,6,9'
  

  回复于 2024-05-04T19:51:20+08:00
• 8

  遍历任意深度的树通常涉及递归过程代码，除非您使用某些DBMS的特殊功能 .

  在Oracle中，如果使用邻接列表，CONNECT BY子句将允许您以第一顺序遍历树，就像在此处所做的那样 .

  如果使用嵌套集，则左序列号将为您提供访问节点的顺序 .

  回复于 2024-05-04T19:51:20+08:00
• 11

  实际上可以在存储过程中使用动态SQL来完成 . 然后，您将受限于存储过程可以执行的操作 . 显然，将EXEC的结果变成一个临时表而不知道预期有多少列会成为一个挑战 . 但是，如果目标是输出到网页或其他UI，那么可能值得付出努力......

  回复于 2024-05-04T19:51:20+08:00