Собственно, сабж... 

Есть некое дерево в БД


Необходимо выбрать всех родителей элемента, например, ITEM-1-3-1, вплоть до самого верхнего уровня, в том числе и ITEM-1.
Как построить простой запрос - нормального ничего не приходит...

Возникла идея просто добавить доп. столбец в БД, в котором будут перечислены все родители через запятую, например, в этом случае будет "1,6".
Ну а потом уже SELECT ... IN (1,6).

Что посоветуете?

Почитать что-нить по хранению и обработке деревьев в базах данных.
Можно - тут, на форуме. Тем предостаточно, в т.ч. и свеженьких.
Посмотри в подвале страницы, раздел "А здесь смотрели?".

@Akina:
По темам "А здесь смотрели?" пробежался ещё перед созданием темы...
Наиболее подходящая - "Выборка из одной таблицы несколько раз одновременно"...
Но не хотелось бы использовать JOIN по несколько раз в запросе, тем более, количество использований напрямую зависит от вложенности дерева.
И я думал об этом ещё до создания темы...

Мог бы почитать и другие темы, но не знаю, как правильней задать вопрос в поиск...

К тому же, хотелось бы найти наиболее рациональное и производительное решение, поэтому родилась идея, которую я описал в 1м посте.


Это сообщение отредактировал(а) fridkaratel - 18.11.2010, 11:18

есть три принципа хранения иерархическихдревовидных данных: materialized path, nested sets и adjacency list(в переводе, соответственно, "материализованный путь", "вложенные множества" и "список смежности"). для вытягивания предков одним запросом подходит первая и вторая структура. для быстрого вытягивания предков(кстати, и потомков) одним запросом подходит вторая структура.
если ты вытягиваешь родителей имеено по имени, как ты показал(т.е. ориентируемся на "item-1-3-1" и должны выбрать "item-1-3" и "item-1"), то у тебя metrialized path и вытянуть всех родителей можно всего одним запросом where "item-1-3-1" like concat(name_item, "-", "%")

@skyboy:
Я неудачно привёл пример  Имена указывал, чтобы легче было понять, что мне надо 

Вообще, названия элементов не зависят от родителей, то есть может быть и "SomeItem", и "ItemOfChild" и т.п. - в имени нет иерархии...

Сейчас у меня такая таблица:


Это сообщение отредактировал(а) fridkaratel - 18.11.2010, 12:09

твой текущий вариант - как раз реализует список смежности. в котором для выбора всех родителей и только родителей можно использовать только рекурсивные запросы.

@skyboy:
А как тебе вариант с доп. столбцом, который я привёл в своём 1м посте?
А то у меня как-то душа к нему лежит - всего одним запросом без JOIN'ов 

materialized path
один запрос, без join'в, без рекурсии. но работа с текстом, что выльется в невозможность использования ключей(никакого IN не получится; конструкция будет использовать like/locate).
так что, если у тебя могут быть офигенно глубокие деревья(раз ты писал про "неопределенную вложенность"), стоит посмотреть на nested sets

fridkaratel, смотря какая таблица и сколько занимает
если 100млн и неограниченное количество ступеней, то может быть с одним parent_id будет сложнова-то

вот тут тут обсуждали

еще варианты:
1) в любом случае можно прокэшировать, например, на 3 минуты, за это время все ветки будут из кеша...
2) или постаивть тип таблицы Memory в этой таблицы хранить только id и parent_id
3) для экономии рекурсии, может быть попробовать как-то так:



посмотреть чему равнятеся t6.id_se, если null значит посмотреть t5.id_se и т.д. остальные и найти начало дерева
если t6.id_se какая-то ветка, то сделать еще раз такой запрос и так далее


========================

в PostgeSQL  есть допоплнение для работы с деревом на уровне хранилица... не на уровне SQL

можно PostgeSQL (правда я там сильно не интересовался деревом, говорят там несколько разных вариантов )
http://www.sai.msu.su/~megera/postgres/gist/ltree/

с одним parent_id: запросы insert и update будет быстрыми, а nested set будет обновлять вдоль и поперек всю ветку... это может быть ресурсоемко (по крайней мере так видно по структуре NestedSet и по тестах так пишут)

лучше всего использовать транзакции, если использовать Nested sets может разваливатся дерево (т.к. INSERT, UPDATE и DETELE ресурсоемкий ) или нужно будет корректировать его

вот тут вот есть самый быстрый и лучший вариант на innodb я это давно еще видел:
http://www.opennet.ru/docs/RUS/hierarchical_data/


MyISAM:

http://habrahabr.ru/blogs/perl/65495/

вот есть на триггерах:
http://habrahabr.ru/blogs/mysql/63883/
http://habrahabr.ru/blogs/postgresql/63416/

не много старые
http://doc.prototypes.ru/database/nestedsets/perl/module/
http://webscript.ru/stories/04/09/01/8197045

PS: я бы попробовал бы PostgeSQL
http://habrahabr.ru/blogs/sql/27965/

PSS: я использую только parent_id + кэширование, для моих решений достаточно




Это сообщение отредактировал(а) gcc - 18.11.2010, 13:41

@skyboy:
Спасибо, буду изучать... если вдруг ещё кому понадобится, то вот ссылка: http://www.getinfo.ru/article610.html

@gcc:
Спасибо за такой развёрнутый ответ  Думаю, пока реализую через несколько JOIN'ов, так как в ближайшее время уровень вложенности не привысит 10... По крайней, думаю, что не превысит...

Посмотрел на структуру nested set - думаю, использовать её мне смысла нет - в ней есть как плюсы, так и минусы...

В дальнейшем, как вариант, думаю всё же иметь доп. столбцы для своего рода кэша... Опять же склоняюсь к той идеи, как написал в 1м посте 

Ну а пока... а пока буду через JOIN'ы и возьму 1й код gcc ;)

покажи мне структуру без "минусов" - ограничений, нюансов, неоднозначностей.

@skyboy:
Э...  Все с минусами 
Но, прочитав и изучив, понял, что она слишком большая для моих задач ;)