如何在 SQL 中进行广度优先搜索? [英] How can I do a breadth-first search in SQL?

问题描述

给定一个存储为关系的树:

Given a tree stored as a relation:

++++++++++++++++++
| Parent | Child |
++++++++++++++++++
|   1    |   2   |
++++++++++++++++++
|   1    |   3   |
++++++++++++++++++
|   3    |   4   |
++++++++++++++++++
|   3    |   5   |
++++++++++++++++++
|   2    |   6   |
++++++++++++++++++
|   7    |   8   |
++++++++++++++++++
|   7    |   9   |
++++++++++++++++++

如何获取给定节点的所有后代?例如，对于1, 我想要 (1, 2, 3, 4, 5, 6) 并且对于 3 我想要 (3, 4, 5), 对于 7 I想要 (7, 8, 9).

How can I get all the descendants of a given node? For example, for 1, I want (1, 2, 3, 4, 5, 6) and for 3 I want (3, 4, 5), and for 7 I want (7, 8, 9).

我是通过脚本(Python，但这无关紧要)执行此操作，所以我可以执行以下操作:

I'm doing this from a script (Python, but that doesn't matter) so I can do something like:

children(p):
   nodes = SELECT child FROM relation WHERE parent=p
   for each node in nodes
        nodes += children(node)
   return nodes

nodes = children(root)

但是如果有一些时髦的 SQL 可以让我在一个查询中做到这一点，那会很棒.

But if there's some funky SQL that lets me do that in one query, that would be awesome.

推荐答案

如果您有能力更改表定义，请使用 嵌套集 而不是直接的父链接使这个问题更容易解决.Joe Celko 的 SQL for Smarties 详细介绍了这一点.

If you have the ability to change the table definition then using a nested set rather than a direct parent link makes this problem much easier to solve. Joe Celko's SQL for Smarties covers this in some detail.

这篇关于如何在 SQL 中进行广度优先搜索?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！