Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Рекурсивные запросы  [new]
Дед Маздай
Member

Откуда:
Сообщений: 655
Наглядный пример такого запроса (WITH ...) показан Paul Atreidies в https://www.sql.ru/forum/actualthread.aspx?bid=10&tid=29091 (16 апр 03, 14:02). Приведенная DimaR конструкция в Oracle с CONNECT BY (там же, 17 апр 03 13:09), на мой взгляд, ориентирована строго на древовидные иерархии. Это только подмножество из возможной области применения рекурсии в запросе. Исходя из этого, я бы проставил такие значения:
Рекурсивные запросы.
IBM DB2 (v.8?) +
Oracle 9i (release 2?) +/-
MS SQL Server 2000 -
Поправьте, пожалуйста, если я ошибаюсь.

И вопрос к тем, кто использует SQL Server. Насколько необходимо, на ваш взгляд, вводить такую возможность, в след.версии (Yukon)?
18 апр 03, 12:18    [178475]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
AI
Member

Откуда: Москва
Сообщений: 2817
В оракле в любом релизе, начиная с 7.0. Ограничение - работа только с одной таблицей в запросе.
18 апр 03, 12:25    [178488]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Crip
Member

Откуда:
Сообщений: 2490
К вопросу нужно ли это в Yukon

Мое мнение - крайней необходимости нет, но было бы неплохо.

Я пользуюсь структурой данных на основе статьи sqltrees на этом сайте.
ID,Parent,LeftBound,RightBound. Есть некоторая избыточность. Но для того чтобы выбрать к примеру все дочерние записи.
То всего лишь (условно)
SELECT * FROM Tree WHERE LeftBound > @LeftBound and RightBound < @RightBound
При наличии соответствующих индексов думаю этот запрос выполнится быстрее любого рекурсивного, хотя могу и ошибаться. Вообщем пользы от рекурсивного запроса большой не будет.

Но при использовании стандартной схемы
ID,Parent рекурсивные запросы могут оказаться очень полезными и избавят разработчика от написания процедур обработки деревьев ( они как правило основы на поуровневой выборке)
18 апр 03, 12:45    [178530]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Denis Popov
Member

Откуда: Санкт-Петербург
Сообщений: 7862
2Al: Ну почему же, а select .. from (select ...)? Те. в подзапросе подготавливаешь данные, потом в верхнем ставишь CONNECT BY.

2Дед Маздай: а можно сформулировать определение рекурсивного запроса? Paul Atreidies говорил о нем как о "возможности запроса ссылаться на самого себя". Если в DB2 под этим понимается использование оператора WITH, то в Oracle 9.2 он присутствует.
18 апр 03, 12:48    [178538]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Crip
Member

Откуда:
Сообщений: 2490
Маленький добавчик.

Получился частный случай. Я хотел этим показать, что вместо использования рекурсии, часто помогает перепроектирование структуры. Я затрудняюсь привести пример, когда использование рекурсии является наиболее оптимальным решением.
18 апр 03, 12:54    [178555]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Дед Маздай
Member

Откуда:
Сообщений: 655
Ну да, возможность запроса ссылаться на себя. Если это решается с помощью WITH, то мне непонятно, зачем еще иметь CONNECT BY.
По поводу нескольких таблиц в рекурсивном запросе написано: "... a multi-table query cannot contain the CONNECT BY clause. So, unlike the procedure, the SQL statement cannot be modified to do joins".
18 апр 03, 13:05    [178581]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Paul Atreidies
Member

Откуда:
Сообщений: 35
Принцип работы в дб2
Есть некоторый исходный набор данных (таблица, вьюшка, табличное выражение).
Из него выбирается стартовый набор строк. Он соединяется с исходным набором. Полученный результат опять соединяется с исходный набором данных. И так до тех пор пока результат соединения будет не пустым.
Область применения - какое-то подмножество алгоритмов на графах вроде поиска в ширину.
Возможно зацикливание - само собой :)
18 апр 03, 13:11    [178596]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
ziktuw
Member

Откуда:
Сообщений: 3552
Вместо рекурсивного запроса куда ценнее было бы в Yukon'e реализовать:
1) Снять ограничение на глубину рекурсий процедур. Т.е. ограничить только размером стэка.
2) Снять ограничение на вложенное "insert exec" или реализовать select * from (exec proc) без ограничения вложенности.
3) Разрешить использования переменных в OPENQUERY и т.п. вместо констант.

Перечисленное перекрывает рекурсивные запросы и по удобству и по функциональности.
18 апр 03, 13:18    [178612]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
x
Guest
Согласен с Dankov

И вообще побольше ортогональности - ну почему я не могу использоватать оператор OR между select и from, а после where - могу !
Да и вообще надо-бы сделать TSQL более похожим на современные языки - с удобными структурными операторами, обработкой исключений

А рекурсия сама пойдет :)
18 апр 03, 14:51    [178816]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Paul Atreidies
Member

Откуда:
Сообщений: 35
Дело вкуса... :)
Работа с БД - это операции над множествами и мыслить нужно категориями множеств. Лично мне не нравятся процедурные расширения, построчная обработка и т.д.
Это имхо.
18 апр 03, 15:05    [178840]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
DimaR
Member

Откуда:
Сообщений: 1570
to Paul Atreidies:
тогда тебе подойдет APL :))
18 апр 03, 15:12    [178862]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
ziktuw
Member

Откуда:
Сообщений: 3552
построчная обработка - это понятно. а что не нравится в процедурной обработке множества записей - это непонятно.
18 апр 03, 15:54    [178967]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
alexeyvg
Member

Откуда: Moscow
Сообщений: 32174
2Dankov
Вместо (или вместе) всего этого сделали-бы там возможность передачи в процедуру переменной-таблицы (естественно, в виде ссылки) и ещё пользовательский табличный тип (для обеспечения раннего связывания) Это сразу подняло-бы MSSQL на такую высоту...

Ну сколько мы-бы не рассуждали здесь...
18 апр 03, 17:41    [179166]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
с127
Guest
Вопрос был задан так:
Paul Atreidies > Поддерживает ли сервер рекурсию (хоть какую) в операторе SELECT?.

Поэтому для оракла нужно отвечать Да (+), без всяких (+/-)

Вопроc:
Можно ли в MSSQL рекурсивный запрос реализовать с помощью UDF, возвращающих рекорд сет? Более конкретно: позволяют ли такие UDF рекурсивные вызовы?

2 Crip
>Я хотел этим показать, что вместо использования рекурсии, часто помогает перепроектирование структуры.

Перепроектирование структуры всегда помогает. Вопрос только в том, сколько вокруг этого траха ((С) чингиз).

>Я затрудняюсь привести пример, когда использование рекурсии является наиболее оптимальным решением.

Например то же дерево, которое является очень распространенной структурой. Задача: для данных двух вершин выяснить, связаны ли они отношением предок-потомок. Можно написать триггеры и добавлять (удалять) всех потомков в отдельную таблицу вида (z, z_потомки). При этом нужно не забыть все пересчитать при перерносе поддерева на другую вершину. Сильно замедлится время для инсертов, делитов и апдейтов и усилится головная боль от написания триггеров. Еще решение: можно вместо select все считать в SP или UDF, но тут мелькала информация об ограниченной глубине рекурсии (кстати сколько в случае MSSQL2000?). По-моему рекурсивный seleсt в данном случае отимальнее. Но я не берусь доказывать, что он наиболее оптимальный.
19 апр 03, 07:13    [179396]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Crip
Member

Откуда:
Сообщений: 2490
2c127
Задача: для данных двух вершин выяснить, связаны ли они отношением предок-потомок
В приведенной мною структуре эта задаче решается проверкой невходит ли диапозон одного в другой(одна операция сравнения) . Я так понимаю
с этой статьей вы не знакомы...
21 апр 03, 10:30    [179792]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Paul Atreidies
Member

Откуда:
Сообщений: 35
Я читал когда-то. Насколько помню - это решение в определенных случаях, но:
1. работает только для дерева - когда корневых вершин несколько начинаются проблемы.
2. Достаточно недетская процедура вставки новых данных.
3. В запросах выборка выглядит достаточно тяжелой - join на принадлежность множеству. Т.е. производительность :)
21 апр 03, 12:40    [179966]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Crip
Member

Откуда:
Сообщений: 2490
1. работает только для дерева - когда корневых вершин несколько начинаются проблемы.
Хм... Не внимательно значит читали...
2. Достаточно недетская процедура вставки новых данных.
Это вы загнули... Впрочем может быть для кого-то единственный Update границ может оказаться очень критичным.

3. В запросах выборка выглядит достаточно тяжелой - join на принадлежность множеству. Т.е. производительность
Вы так полагаете? При наличии соотвествующих индексов все проходит достаточно быстро и уж я думаю куда быстрее чем рекурсивные вызовы...Хотя это в значительной степени зависит от того как эти вызовы реализованы, к сожалению с DB2 малознаком...
Тем не менее для нескольких тысяч записей у меня проблем никаких. Для небольшего не тестировал...
21 апр 03, 12:58    [179988]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Paul Atreidies
Member

Откуда:
Сообщений: 35
2 Crip
1. Честно говоря не увидел - или ткните пальцем - или просто кратко опишите на случай несвязного графа.
2. Вставка при "традиционном" методе не треьует изменения остальных записей. В случае вложенных множеств потредуется пересчет достаточно "большого" количества записей - я не говорю что это много по времени - это много в сравнении со вставкой одной записи :). Дальше я не уверен (при желании можно посчитать посчитать), но на первый взгляд в среднем что-то около n/2 строк при вставке случайных данных. n-число строк.
Пример в статье со вставкой смежной, крайней правой не очень удачет - он достаточно прост.
То же и при удалении.
3. Она и при работе с такой структурой неявно присутствует - это видно по запросам (для каждой вершины идет поиск в глубину):

SELECT COUNT(P2.emp) AS indentation, P1.emp
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
GROUP BY P1.emp
ORDER BY P1.emp;

Согласитесь что этот join потяжелее чем на равенство :). Я ничего не имею против такого метода хранения. Просто иметь встроенные средства поддержки рекурсии, на мой взгляд, предпочтительнее.
21 апр 03, 14:27    [180082]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Crip
Member

Откуда:
Сообщений: 2490
1. Честно говоря не увидел - или ткните пальцем - или просто кратко опишите на случай несвязного графа.
Честно говоря погорячился... Конечно это работает только для дерева. Решение для множества корней сделано у меня сделано через дополнительную таблицу.
Согласитесь что этот join потяжелее чем на равенство :). Я ничего не имею против такого метода хранения. Просто иметь встроенные средства поддержки рекурсии, на мой взгляд, предпочтительнее
Возможно вы правы. Своим примером я лишь пытался показать, что возможно приемлиемое решение проблемы без использования встроенных механизмов.
Хотя по-поводу графов не так просто что-то придумать на таком высоком уровне как программирование БД.
Вообще лично у меня возникает впечатление, что все-таки глубокой проработкой отдельных деталей, характерной для DB2 и Oracle, разработчики MS не занимаются, в основном сосредотачивая усилия на улучшении стандартных механизмов( оптимизатор etc.) . Это вероятно позволяет привлечь массового потребителя, но в узкоспециализированных задачах SQL server наверняка проигрывает DB2 и Oracle.
21 апр 03, 14:48    [180116]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
c127
Guest
2 Crip

Прочитал статью. Интересно, может когда пригодится. Недостатки такого решения тут уже обсуждались. К тем двум альтернативам (кстати в первй из них задача тоже решается одним запросом), которые я упоминал добавилась третья - Celko. У рекурсивного запроса по-прежнему остается по крайней мере одно преимущество: простота. Ничего вообще менять не надо. Это важно, если необходимость рекурсивных запросов вдруг появилась в середине проекта. Поэтому рекурсивные запросы иметь в своем арсенале было бы очень непохо. Я абслютно согласен, что приведенные тут альтернативные решения в некоторых случаях предпочнительнее (например select будет работать быстрее).

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

Насколько я знаю термина "вложенные множества" в математике нет. Есть подмножества и есть множества, элементы которых в свою очередь есть множества. Автор статьи по-видимому имеет в виду последние.
22 апр 03, 01:30    [180604]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Denis Popov
Member

Откуда: Санкт-Петербург
Сообщений: 7862
Захотелось поднять тему. Скажите, можно ли в различных СУБД только средствами SQL реализовать получение чисел Фибоначчи?

https://www.sql.ru/forum/actualthread.aspx?bid=3&tid=75150#542297
19 фев 04, 11:36    [542859]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Crip
Member

Откуда:
Сообщений: 2490
Давайте лучше дифуры решать с помощью SQL
19 фев 04, 11:55    [542904]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Wadim
Member

Откуда:
Сообщений: 31
2 Дед Маздай
Не то чтобы совсем нас спрашивали о том нужно это или нет в Yukon.
Но это уже включено туда. Вот пример кода из журнала www.sqlmag.com за Ноябрь 2003 года.

Listing 2. Query That Uses a Recursive CTE to Return Andrew's Direct and Indirect Subordinates

With EmpsCTE(empid, mgrid, fname, lname, lvl)
AS
(
SELECT EmployeeID, ReportTo, FirstName, LastName, 0
FROM Employees
WHERE EmployeeID=2
UNION ALL
SELECT EmployeeID, ReportTo, FirstName, LastName, M.lvl+1
FROM Employees AS E JOIN EmpsCTE AS M
ON E.ReportsTo=M.empid
)
SELECT * FROM empsCTE
19 фев 04, 15:13    [543580]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
alexeyvg
Member

Откуда: Moscow
Сообщений: 32174
Наконец-то Дед Маздай узнал! С апреля человек ждал...
19 фев 04, 17:17    [544028]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивные запросы  [new]
Redbor
Member

Откуда: Москва
Сообщений: 289
2 Дед Маздай: К самому началу топика - в этом списке не хватает Sybase ASA
26 фев 04, 21:08    [553591]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Сравнение СУБД Ответить