Сколько запросов SQL мне нужно?

Question

У меня есть таблица базы данных (sqlite), содержащая элементы, которые образуют древовидную иерархию. Каждый элемент имеет поле id (для себя) и parentId для своего родителя. Теперь, получив предмет, я должен получить всю цепочку от корня до предмета.

В основном алгоритм в псевдокоде выглядит так:

1. курсор это элемент
2. получение parentItem для курсора по parentId
3. если parentItem не является rootItem, то курсор = parentItem и переход к 2.

Поэтому мне нужно выполнить запрос SQL SELECT для каждого элемента.

Можно ли получить элемент rootItem -> ... -> всей цепочки, выполнив только один SQL-запрос?

Answer 1

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

Общее количество усилий: 1 запрос + 1 программный проход через ваш набор данных для создания иерархии.

---

Альтернативный подход:

Я использовал этот метод в прошлом с ограниченным успехом. Вы можете сохранить путь каждого элемента в вашем дереве, используя столбец varchar (max) следующим образом:

ID    ParentID    Path
--    --------    ----
1     null        1/
2     1           1/2/
3     null        3/
4     2           1/2/4/
5     4           1/2/4/5/
6     null        6/
7     5           1/2/4/5/7/
9     5           1/2/4/5/9/

С этого момента получить все узлы с ID = 5 очень просто:

SELECT *
FROM table
WHERE Path like (SELECT Path FROM Table WHERE ID = 5) + '%'

Answer 2

Вы можете изменить структуру таблицы? Похоже, что с сохранением левого и правого узлов будет проще работать, чем с сохранением только родительского узла, поскольку тогда возможен единственный выбор. Смотрите следующие ссылки:

http://www.mail-archive.com/sqlite-users@sqlite.org/msg23867.html

http://weblogs.asp.net/aghausman/archive/2009/03/16/storing-retrieving-hierarchical-data-in-sql-server-database.aspx (это SQLServer, но у них есть диаграмма, которая может помочь.)

Answer 3

Нет, для стандарта ANSI SQL это не так, нет. Ну, это не совсем так. Вы можете сделать левые внешние соединения и вставить достаточно, чтобы покрыть вероятную максимальную глубину, но если вы не ограничите максимальную глубину и не включите столько соединений, это не всегда будет работать.

Если ваш набор строк достаточно мал (скажем, меньше 1000), просто извлеките их все, а затем выясните это. По всей вероятности, это будет быстрее, чем одиночный обход.

Вы можете пакетировать родительский обход. Есть запрос как:

SELECT t1.id id1, t1.parent parent1,
       t2.id id2, t2.parent parent2,
       t3.id id3, t3.parent parent3,
       t4.id id4, t4.parent parent4,
       t5.id id5, t5.parent parent5
FROM mytable t1
LEFT OUTER JOIN mytable t2 ON t1.parent = t2.id
LEFT OUTER JOIN mytable t3 ON t2.parent = t3.id
LEFT OUTER JOIN mytable t4 ON t3.parent = t4.id
LEFT OUTER JOIN mytable t5 ON t4.parent = t5.id
WHERE t1.id = 1234

и добавьте его к любому номеру, который вы хотите. Если последний найденный родитель не равен нулю, вы еще не находитесь на вершине дерева, поэтому повторите запрос еще раз. Таким образом, вы должны уменьшить его до 1-2 круговых поездок.

Кроме этого, вы можете посмотреть на способы кодирования этих данных в ID. Это не рекомендуется, но если вы ограничите, скажем, каждый узел 100 дочерними узлами, вы можете сказать, что у узла с идентификатором 10030711 есть путь 10 -> 03 -> 07 -> 11. У этого, конечно, есть другие проблемы (например, max ID длина) и, конечно, это взломать.

Стоит также отметить, что в SQL существует две основные модели иерархических данных. Списки смежности и вложенные множества. Ваш путь (который довольно распространен) - это набор смежности. Вложенные наборы не очень помогут в этой ситуации, и они сложны для выполнения вставок.