Рекурсивные SQL запросы

    Рекурсивны SQL запросы являются одним из способов решения проблемы дерева и других проблем, требующих рекурсивную обработку. Они были добавлены в стандарт SQL 99. До этого они уже существовали в Oracle. Несмотря на то, что стандарт вышел так давно, реализации запоздали. Например, в MS SQL они появились только в 2005-ом сервере.

    Рекурсивные запросы используют довольно редко, прежде всего, из-за их сложного и непонятного синтаксиса:
    with [recursive] <имя_алиаса_запроса> [ (<список столбцов>) ]
    as (<запрос>)
    <основной запрос>

    В MS SQL нет ключевого слова recursive, а в остальном все тоже самое. Такой синтаксис поддерживается в DB2, Sybase iAnywhere, MS SQL и во всех базах данных, которые поддерживают стандарт SQL 99.

    Проще разобрать на примере. Предположим, есть таблица:
    create table tree_sample (
      id integer not null primary key,
      id_parent integer foreign key references tree_sample (id),
      nm varchar(31) )


    id – идентификатор
    id_parent – ссылка на родитель
    nm – название.

    Для вывода дерева:
    with recursive tree (nm, id, level, pathstr)
    as (select nm, id, 0, cast('' as text)
       from tree_sample
       where id_parent is null
    union all
       select tree_sample.nm, tree_sample.id, t.level + 1, tree.pathstr + tree_sample.nm
       from tree_sample
         inner join tree on tree.id = tree_sample.id_parent)
    select id, space( level ) + nm as nm
    from tree
    order by pathstr


    Этот пример выведет дерево по таблице с отступами. Первый запрос из tree_sample этот запрос выдаст все корни дерева. Второй запрос соединяет между собой таблицу tree_sample и tree, которая определяется этим же запросом. Этот запрос дополняет таблицу узлами дерева.

    Сначала выполняется первый запрос. Потом к его результатам добавляются результаты второго запроса, где данные таблица tree – это результат первого запроса. Затем снова выполняется второй запрос, но данные таблицы tree – это уже результат предыдущего выполнения второго запроса. И так далее. На самом деле база данных работает не совсем так, но результат будет таким же, как результат работы описанного алгоритма.

    После этого данные этой таблицы можно использовать в основном запросе как обычно.

    Хочу заметить, что я не говорю о применимости конкретно этого примера, а лишь пишу его для демонстрации возможностей рекурсивных запросов. Этот запрос реально будет работать достаточно медленно из-за order by.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 51

      +1
      Вопрос к аудитории: как вы решаете задачу вывода дерева в MySQL? Встроенные процедуры? Внесение избыточности в таблицы?
        0
        сортировкой по идентификатору родителя =))
        а остальное уже сделает клиент.
          +1
          Библиотеку DBSimple юзаем.
            0
            организовываем хранение дерева другими методами, в зависимости от условий ;)
            • UFO just landed and posted this here
                +4
                Nested Sets
                  0
                  * можно какую-нить статью об етой технике?

                  если на базе РНР - буду вдвое рад. если на другом языке - тоже рад. но больше разбиратся будет. главное - по SQL нужно понять как ето нормально делать.
                0
                nested sets + немного хранимых процедур по управлению деревом.
                рекурсия, имхо плохо, по скрости чтения, ns самый быстрый метод хранение (про вставку узлом промолчим(: )
                  0
                  * вставку узов, опечатка, извините
                  0
                  Я храню данные в подобной же таблице (id - идентификатор элемента, id_parent - идентификатор родителя, data - какие нибудь доп. данные элемента дерева). Затем делаю выборку всей таблицы в массив (arrData). По полям id и id_parent функцией рекурсивного обхода выстраиваю ещё один вложенный многомерый массив (т.е. массив масивов, в которых могут быть элементы массивов), который представляет собой структуру дерева (arrStructure). И потом по этим двум массивам, масиву труктуры и массиву данных, делаю вывод. Т.е. обхожу полностью массив структуры определяю положение и расставляю данные.

                  Наверняка лучше сделать такое хранимой процедурой на сервере СУБД.

                  Был так же вариант без рекурсии, он быстрее работает чем с рекурсией, но настолько незначительно (проводились тесты с несколькими тысячами записей), что сложность его реализации проигрывает перед легкостью реализации с рекурсией. Поэтому решено было всё таки рекурсией реализовывать построение структуры дерева.

                  А вот насчёт сортировки по идентификатору родителя, простите, но это бред, так правильной структуры дерева не достичь, т.к. вложенность может быть бесконечно большой.
                    0
                    имхо, хранимая процедура, быть может, и проще в использовании, но она создаёт большую нагрузку на сервере СУБД.
                    во всяком случае, у нас тут не рекомендуется даже "ORDER BY" использовать, а сортировать на сервере приложения. но это всё имхо и частные случаи, у вас может быть всё иначе
                      0
                      Я отписал лишь по поводу того, что возможно было лучше. На данный момент у нас реализована сортировка и оброаботка массивов данных именно на сервере приложения.
                    0
                    Юзаю materialized path. Конечно, Nested Sets часто побыстрее работает, но зато matpath удобней, легко ручками править дерево. Особенно удобно, когда в БД храниться структура сайта и применяется mod_rewrite. в этом случае, берем url и простеньким запросом находим нужную нам ветвь (в этом случае в качестве пути применяю латинские имена узлов, а не id)
                      0
                      Не всегда NS быстрее работает :), да и измененный (замечу измененный, жаль мало реализаций, но на коммерческих есть что посмотреть) mp не только удобней, но целостней NS + возможно перенести почти под любую СУБД без сильных изменений.
                      0
                      Могу кинуть create proc, но оно не влазит в коммент.
                      Подскажите, как сделать - кину...
                        0
                          0
                          Ну собственно вот... hттp://pastebin.com/f58ed1208
                          Только не бейте ногами за динамич. SQL.
                          работает достаточно быстро.
                          Главное для меня - мегауниверсальность...
                      –1
                      до этого я думал что знаю mysql
                        0
                        Это MS SQL.
                          0
                          не совсем, дело в том, что приведенный пример парсится с ошибкой
                          почему это так я написал ниже
                            +3
                            Это не MS SQL. На самом деле это стандарт SQL 99. Эту конструкцию поддерживают: DB2, Sybase iAnywhere, MS SQL. Не знаю как Oracle, но там точно есть другая конструкция типа:
                            select ...
                            from tree_sample
                            start with id = ....
                            connect by prior id = id_parent


                            * This source code was highlighted with Source Code Highlighter.
                              0
                              См. ниже — я уже писал об этом.
                                0
                                Пардон, не досмотрел.
                          +1
                          Хммм. Честно в описаниях по PL/SQL не встречал такой конструкции, обычно везде приводят «родную» конструкцию вида start with ... connect by ... . В очередной раз убеждаюсь, что оракл всегда бежал впереди паравоза=)
                          Спецы по PostgreSQL поделитесь, как у вас с этим?
                            +1
                            Автору стоит указать, что в MS SQL (даже в 2008) нет ключевого слова recursive, в этой СУБД его следует опускать
                              +1
                              Спасибо, исправил.
                              0
                              Автору спасибо. Теперь подумаю, чтобы вернуться к нормальным деревьям, вместо этих Nested Sets... хотя и к ним уже привык.
                                +2
                                Я думаю, что Nested Sets будут побыстрее работать, хотя не сравнивал. Конечно, Nested Sets гораздо сложнее реализуются. Надо будет попробывать провести эксперимент по сравнении скорости для разных способов реализации дерева.
                                  0
                                  Действительно, nested set при выборке из него будет работать быстрее. Сложности в нем нет по одной причине - его уже столько раз обмусолили и сделали столько реализаций... что думать уже даже ненадо :) При необходимости и в nested set можно столбец parent_id добавить(иногда бывает полезно).
                                    0
                                    Я был бы рад если бы вы поэкспериментировали с новым типом hierarchyid для MS SQL 2008 и сообщили нам о своих результатах. Этот тип как раз и придуман для реализации иерархий.
                                      0
                                      Я попытаюсь попробывать, правда MS SQL 2008 у меня нет, но думаю найду.
                                  +3
                                  В PostgreSQL есть библиотека ltree. Позволяет получать дерево простым селектом и очень быстро. Дерево хранится в своем типе, и не очень удобно в манипуляциях (перенос веток). Для манипуляций писал свои функции, но процесс получения самого дерева или ветки - песня.
                                    0
                                    можно не использовать ключевое слово recursive - а просто 'with' - создаётся временное представление. Жаль что в MySQL нельзя в таком же духе строить рекурсию. На днях пришлось использовать старый дедовский способ - рекурсию делать на клиенте.
                                      0
                                      А через хранимые процедуры не получалось реализовать(для MySQL)?
                                        0
                                        хотелось бы использовать но хостер не позволяет использовать хранимые процедуры - на мой запрос - посоветовали перейти на vps.
                                      +1
                                      Автору следовало бы указать, что это называется Common Table Expressions (CTE) и, очевидно, ничего общего с рекурсивными запросами в Oracle не имеет. Кроме того, CTE используются не только не только для рекурсии.

                                      P.S.
                                      Возможно, следует перенести топик в блог по SQL.
                                        0
                                        Топик я перенес. У меня просто кармы не было, чтобы туда написать.
                                        Я писал просто про рекурсивные запросы, а не про Common Table Expressions (CTE), поэтому решил, что это лишнее.
                                        Oracle я никогда не использовал и так и не смог найти поддерживает ли он этот синтаксис, поэтому решил просто указать, что это часть стандарта SQL 99 и каждая база, которая полностью поддерживает этот стандарт должна поддерживать и эту конструкцию. Oracle, как я понял, не поддерживает ни эту конструкцию ни SQL 99, а придерживается своих стандартов.
                                          0
                                          Я писал просто про рекурсивные запросы, а не про Common Table Expressions (CTE), поэтому решил, что это лишнее.

                                          Как раз наооборот, ибо надо показать откуда ноги растут и в каком направлении копать, в случае углубленного изучения.
                                        –3
                                        Стандарт для крупных промышленных разработок - Oracle. Там конструкция "connect by prior" уже давно и работает неплохо. В других случаях и базы, и нагрузки поменьше.
                                          +1
                                          Oracle стандартом не является. Он очень популярен у нас в стране, так как часто его получали бесплатно.
                                          Например, в США DB2 не сильно отстает от Oracle по использованию.
                                            0
                                            Ну да, забыл добавить, у нас в стране.

                                            Насчет "бесплатно" не знаю, но некоторым предприятиям уже надоедает платить за эту СУБД и посматривают в сторону MySql. Только не вижу в этом смысла, у них всё повалится моментально от перегруза.
                                              0
                                              Зря вы так думаете про MySQL, им даже Гугл пользуется. Там другая проблема — хранимые процедуры. Их придется заново реализовывать на чём-то отдельном от мускула.
                                                0
                                                postgres им в помощь
                                            0
                                            Был у меня случай, когда нужно было построить дерево из однонаправленного графа, т.е. переходы происходят строго в одном направлении, но ветки могут как расходиться, так и сходиться.
                                            На Оракле я решил это хранимой процедурой, которая помещала в локальную таблицу (ту, то из type объявить можно) корневые элементы, проставляла им айдишники и начинала вычитывать для каждой позиции из локальной таблицы её потомков, добавлять их в конец списка и проставлять им парентом айдишник элемента, по которому они вычитывались. До и после вычитки потомков элемента запоминалась количество элементов (локальные счетчики, просто инкрементились при добавлении). Если мы приходили в конец списка и для последнего элемента потомков больше не обнаруживалось — построение дерева останавливалось.
                                            В случае неоднонаправленного графа пришлось бы плясать с проверкой на вхождение добавляемого элемента в список уже существующих, что невероятно затормозило бы алгоритм, но, к счастью, обошлось.
                                              0
                                              а сколько родителей у одного узла?
                                                0
                                                А вот в том-то и была проблема, что у узла могло быть более одного родителя. Т.е. у меня получилось дерево с повторяющимися фрагментами.
                                                  0
                                                  чем "connect by" не устроил?
                                                    0
                                                    В принципе ничем, просто не получилось когда пытался. Подозреваю, что набыдлокодил, да только переделывать я это уже не буду. :)

                                            Only users with full accounts can post comments. Log in, please.