Как я могу сделать поиск в ширину в SQL?

Question

Учитывая дерево, хранящееся как отношение:

++++++++++++++++++
| 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 я хочу (7, 8, 9).

Я делаю это из скрипта (Python, но это не имеет значения), поэтому я может сделать что-то вроде:

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

nodes = children(root)

Но если есть какой-нибудь интересный SQL, который позволяет мне сделать это в одном запросе, это было бы здорово.

Answer 1

Если у вас есть возможность изменить определение таблицы, то использование вложенного набора вместо прямой родительской ссылки значительно облегчает решение этой проблемы. SQL для умников Джо Селко раскрывает некоторые детали.

Answer 2

Я закончил с:

# Parents is a list of strings
def _children(parents):
    if len(parents) == 0:
        return []

    db = self.env.get_db_cnx()
    cursor = db.cursor()
    cursor.execute("SELECT t.id "
                   "FROM ticket AS t "
                   "LEFT OUTER JOIN ticket_custom AS p ON "
                   "    (t.id=p.ticket AND p.name='%s') "
                   "WHERE p.value IN (%s)" % 
                   (self.fields['parent'],
                    "'" + "','".join(parents) + "'"))
    children = ['%s'%row[0] for row in cursor] 
    return parents + _children(children)

Хотя я думаю, что имя функции немного слабое.Я могу изменить его на _tree или что-то в этом роде.

Это работает в Trac 0.11 с PostgreSQL 8 (?).

Answer 3

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

nodes = children(root)

OR

выполняет две функции, что-то вроде:

имеет детей (р)

получить массив детей (p)

Answer 4

Вот подробный пример: Отчет об иерархическом диапазоне управления в SQL без синтаксиса Oracle CONNECT BY? .Чтобы получить потомков (или в моем примере косвенные отчеты), вам сначала нужно сплющить дерево в путь.

Answer 5

Вы можете использовать рекурсивный СО.Я сделал это с помощью Oracle 12c.Синтаксис может немного отличаться от другой СУБД.Я построил таблицу и заполнил ее данными с помощью следующего сценария:

create table parent_child (
  parent integer,
  child integer,
  constraint parent_child_pk primary key (parent, child)
);

insert all
  into parent_child values (1, 2)
  into parent_child values (1, 3)
  into parent_child values (3, 4)
  into parent_child values (3, 5)
  into parent_child values (2, 6)
  into parent_child values (7, 8)
  into parent_child values (7, 9)
  select 1 from dual;

commit;

Затем я использую рекурсивный оператор WITH:

with descendants (node) as (
  select 1 from dual -- root
  union all
  select child from descendants inner join parent_child on parent = node
)
select node from descendants order by node;

select 1 from dual - это элемент привязки (базовый случайрекурсии).Он ставит 1 в таблицу descendants.Вы можете использовать 3 или 7 вместо этого, как в вашем примере.Затем идет рекурсивный случай с select child from descendants inner join parent_child on parent = node рекурсивным членом.Это означает, что мы берем новые узлы в потомках (что означает 1) и получаем все их дочерние элементы (что означает 2 и 3) и добавляем их в таблицу descendants.Итак, теперь у нас есть 1, 2 и 3 в таблице.Мы снова начинаем использовать 2 и 3 в качестве новых узлов и получаем их дочерние элементы, которые равны 4 и 5. Затем мы получаем полный результат, который, вероятно, является тем, что вы хотите.

Мы можем использовать listagg, если нам нужна строкано тогда нам нужен способ упорядочить вещи или хотя бы способ идентифицировать корневой узел.Обратите внимание, что не очень хорошая идея объединять кортежи в таблице как одну большую строку.

with descendants (node, is_root) as (
  select 1, 'Y' from dual -- root
  union all
  select child, 'N' from descendants inner join parent_child on parent = node
)
select '(' || listagg(node, ', ') within group (order by case is_root when 'Y' then 0 else 1 end, node) || ')' list
from descendants;

, что дает (1, 2, 3, 4, 5, 6).