Выберите из таблицы, которая использует материализованный путь для кодирования дерева, упорядоченного по глубине (без рекурсивного/ltree)

У меня есть таблица в реляционной базе данных, в которой я кодирую дерево, используя технику, известную как Материализованный путь (также известный как столбец Lineage). То есть для каждого узла в моем дереве у меня есть строка в таблице, и для каждой строки у меня есть строковый столбец с именем ancestry, где я храню путь от корневого узла к узлу, представленному этой строкой.

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

Например, дерево, его стол и выбранные по предзаказу:

 1        SELECT * FROM nodes   SELECT * FROM nodes ORDER BY ?depth_first_visit_order?
| \       id | ancestry         id | ancestry
2   3     -------------         -------------
|  | \    1  | NULL             1  | NULL           NOTE: I don't care about the
4  5  6   2  | 1                2  | 1                    order of siblings!
   |      3  | 1                4  | 1/2
   7      4  | 1/2              3  | 1
          5  | 1/3              5  | 1/3
          6  | 1/3              7  | 1/3/5
          7  | 1/3/5            6  | 1/3

Примечание. Я явно заинтересован в том, чтобы сделать это с кодировкой материализованного пути!
Связано: -data-in-a-relational-database">Какие существуют варианты хранения иерархических данных в реляционной базе данных?


mysql sql relational-database hierarchy tree
person clyfe    schedule 01.02.2012    source источник
comment
Аналогично stackoverflow.com/questions/2797720/< /а>   -  person clyfe    schedule 01.02.2012

Ответы (2)


arrow_upward
1
arrow_downward

Я считаю, что вы хотите, это алфавитный вид.

SELECT id, ancestry, ancestry + '/' + CAST(id as nvarchar(10)) AS PathEnumeration
FROM nodes
ORDER BY 3 ASC;

Я действительно не помню, как MySQL объединяется, но я уверен, что мой смысл ясен.

1
1/2
1/2/4
1/3
1/3/5
1/3/5/7
1/3/6

Обратите внимание, что это алфавитная сортировка, поэтому 11 будет отображаться перед 2. Но вы сказали, что вас не волнует порядок братьев и сестер. Я бы, конечно, переписал его как вложенный набор ;)

person Ion Freeman    schedule 14.02.2012
comment
Я, вероятно, перепишу его как вложенный набор, так как у меня много коротких деревьев. Дело в том, что мои данные уже представляют собой материализованный путь, закодированный естественным образом (точнее, доменные имена a.b.c). Мне придется подумать об этом некоторое время, потому что я не совсем уверен, что это работает в общем случае. - person clyfe; 14.02.2012

arrow_upward
0
arrow_downward

это будет упорядочено по последнему номеру вашей "родословной"

select *, 
Substring(ancestry,LEN(ancestry) - Charindex('/',Reverse(ancestry))+2, LEN(ancestry)) as END_CHAR
from nodes
order by END_CHAR desc

Я не пробовал с числами больше 9, возможно, вам придется привести к int

person Diego    schedule 01.02.2012
comment
Извините, только что понял, что это не ответ на ваш вопрос, я неправильно его понял. Я оставлю запрос, он может дать вам некоторое представление. - person Diego; 01.02.2012