Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Составление SQL-запросов > Получить всех родителей элемента в дереве

Автор: zammar 18.9.2009, 17:43

Как можно получить всех родителей для каждого элемента.

Например, для 4 получить идентификаторы 2-ки и 1-ы
для 2-ки идентификатор 1

id    name    left    right       level
1     eee       0         11          1
2     sss        1         6            2
3     www     7        10           2
4    ggg        2         3            3
5    jjj           4         5            3
6    ooo        8         9            3

Автор: Gluttton 18.9.2009, 17:57

Не совсем понятно (мне), а точнее совсем не понятно smile

, на основании каких данных? Что храниться в left и right?
СУБД?

Автор: Zloxa 18.9.2009, 19:57

Цитата(Gluttton @ 18.9.2009, 17:57

)

Что храниться в left и right?

Судя по всему дерево представлено в виде http://www.woweb.ru/publ/41-1-0-464

Автор: Gluttton 18.9.2009, 20:09

Цитата(Zloxa @ 18.9.2009, 19:57

)

Судя по всему дерево представлено в виде nested sets

Здорово, открыл для себя nested sets smile

...

Автор: Zloxa 18.9.2009, 20:24

Цитата(Gluttton @ 18.9.2009, 20:09

)

Здорово, открыл для себя nested sets smile ...

в FB есть рекурсивные запросы, этот анонизгемморой тебе врядли там понадобится. Получается сейчас наверное только MySQL не умеет рабоать с деревьфми. Однако ключевые слова для поиска, навсяк, запомнить желательно бы, ну и ключевой принцип тоже ;)

Автор: Gluttton 18.9.2009, 22:37

Ну теперь, когда я теоретически подкован smile

, приведу свои варианты (если в этом ещё остался смысл smile

)...
Таблица:
user posted image

Первый вариант я списанал адаптировал smile

из приведенного Zloxой источника:

Код


select id
from nt
    where left<=2 AND right>=3 order by left

Результат:
user posted image

Второй вариант, я написал, вдохновлённый реализацией рекурсивных запросов в Firebird:

Код


with recursive
    sub as
    (
        select cast(nt.id as varchar(10)) as id, nt.left, nt.right, nt.level
        from nt
        union all
        select cast(sub.id as varchar(10))||'-'||cast(nt.id as varchar(10)) as id, nt.left, nt.right, nt.level
        from sub, nt
            where sub.level=nt.level+1
            and
            (
                nt.left=sub.left-1
                or
                nt.right=sub.right+1
            )
    )
select
    max(sub.id)
from sub
    where substring(sub.id from 1 for 1)='4'

Результат:
user posted image

*
- запросы выполнялись на Firebird 2.1;
- left, right, level - зарезервированные слова Firebird 2.1, и для использования необходимо помещать их в двойные кавычки (и что меня очень удевило приводить к верхнему регистру smile

?).

Zloxa,

Цитата(Zloxa @ 18.9.2009, 20:24

)

в FB есть рекурсивные запросы, этот анонизгемморой тебе врядли там понадобится. Получается сейчас наверное только MySQL не умеет рабоать с деревьфми.

Т.е. nested sets необходимы только в том случае если нет рекурсии? А если есть (в смысле реализована) рекурсия, то деревья можно строить используя parent_id?

Автор: Zloxa 19.9.2009, 02:27

Цитата(Gluttton @ 18.9.2009, 22:37

)

тип того.
nested sets безумно дорогие на модификацию. Фактически этот способ хранения применим только для весьма статичных данных с очень невеликим объемом./*О конкурентной модификации я, если честно, пока даже не размышлял ибо мысль об обдумывании стратегии конкурентной модификации меня заведомо ввергает в ужос. Хотя, может, там все просто и думать придется лишь самую малость. Но буде мне пришлось бы реализовывать такую модель, я таки бы смалодушничал и впопервой, пока не подумал, проводил бы модификации в режиме монопольного доступа.*/
Однако, стоит заметить, этот метод хранения, таки дает существенные преимущества на выборке.

Автор: zammar 19.9.2009, 08:57

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

Ну а метод который предложил Gluttton лежит конечно на поверхности. Но все равно спасибо.

Код


select id
from nt
    where left<=2 AND right>=3 order by left

Автор: Gluttton 19.9.2009, 22:29

Цитата(zammar @ 19.9.2009, 08:57

)

Мне нужно достать все элементы и для каждого всех его родителей.

Для указанных выше исходных данных, приведенный ниже запрос

Код


select
    nta.id as children,
    ntb.id as parent
from nt as nta, nt as ntb
    where ntb.left<nta.left
    and ntb.right>nta.right
    order by nta.id

Вернет следующие данные:
user posted image

Цитата(zammar @ 19.9.2009, 08:57

)

Это можно сделать только запросом в цикле как мне думается или все таки как-то можно это сделать одним запросом?

Что за императивные взгляды в декларативном мировозрении smile

Цитата(zammar @ 19.9.2009, 08:57

)

Ну а метод который предложил Gluttton лежит конечно на поверхности. Но все равно спасибо.

Всё равно пожалуйста...

Подумал тут на досуге...
Правильнее будет так:

Код


select
    nta.id as children,
    ntb.id as parent
from nt as nta
    left join nt as ntb
    on
    (
        ntb.left<nta.left
        and 
        ntb.right>nta.right
    )
    order by nta.id

И тогда результат буде таким:
user posted image

Автор: Zloxa 19.9.2009, 22:30

Цитата(zammar @ 19.9.2009, 08:57

)

Мне нужно достать все элементы и для каждого всех его родителей.

приведите ожидаемый Вами результат запроса.

Автор: gcc 21.9.2009, 04:21

все дерево в низ:

Код


SELECT id_se
                              FROM section
                            WHERE
                    parent_se_id = 55
                      
                    UNION
                      
                    SELECT t1.id_se
                    FROM
                    section t1 JOIN section t2
             ON t1.parent_se_id = t2.id_se
                    WHERE
              t2.parent_se_id = 55

смотря какое дерево все таки, в большинстве случаев достаточно просто parent

была статья opennet.ru nestedset на innodb с дополнительной таблицей и внешними ключами, транззакцией в 6 раз быстре обычного nestedset при UPDATE INSERT

но innodb наверное будет грузить сервер больше чем MyISAM

Автор: zammar 21.9.2009, 13:00

Gluttton, спасибо. То что нужно.
Всем спасибо!