Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Как избежать обхода всех ветвей дерева  [new]
alcrux
Member

Откуда:
Сообщений: 39
Добрый день!

Используется MSSQL 2008 R2. Есть таблица tree описывающая элементы дерева

table tree( id int, parent int, name varchar( 100 ), flag bit)


Элементы с parent равен null назовем корневыми. Надо найти все корневые элементы у которых хотя бы один из дочерних элементов имеет flag равным 1. Это можно сделать с помощью рекурсивного запроса(предполагается, что зацикленных ссылок нет):

with cte( id, r, ok ) as (
  select id, id, f from tree where parent is null
  union all
  select tr.id, r, f from tree tr join cte t on parent = t.id
) 
select distinct r from cte where ok = 1

Но есть один недостаток. Даже если для данного корневого элемента ответ будет ясен при проходе первой ветви, то, тем не менее, все остальные его ветви будут также пройдены.

Существует ли запрос/способ позволяющий устранить этот недостаток?

Не знаю могут ли помочь в этом курсоры, но такой вариант не рассматривается.
25 ноя 15, 12:37    [18470241]     Ответить | Цитировать Сообщить модератору
 Re: Как избежать обхода всех ветвей дерева  [new]
Glory
Member

Откуда:
Сообщений: 104760
alcrux
Существует ли запрос/способ позволяющий устранить этот недостаток?

Найдите все записи с flag равным 1.
И к ним найдите всех родителей до корня.
25 ноя 15, 12:40    [18470267]     Ответить | Цитировать Сообщить модератору
 Re: Как избежать обхода всех ветвей дерева  [new]
iap
Member

Откуда: Москва
Сообщений: 46999
Не исключено, что как раз курсор здесь был бы эффективен.
25 ноя 15, 12:52    [18470364]     Ответить | Цитировать Сообщить модератору
 Re: Как избежать обхода всех ветвей дерева  [new]
invm
Member

Откуда: Москва
Сообщений: 9396
alcrux
Существует ли запрос/способ позволяющий устранить этот недостаток?
with cte( id, r, ok ) as (
  select id, id, f from tree where parent is null
  union all
  select tr.id, r, f from tree tr join cte t on parent = t.id and t.ok = 0
) 
select distinct r from cte where ok = 1
25 ноя 15, 13:06    [18470439]     Ответить | Цитировать Сообщить модератору
 Re: Как избежать обхода всех ветвей дерева  [new]
alcrux
Member

Откуда:
Сообщений: 39
Это ничего не дает, если много элементов с полем f равным 1, у которых один корень.
25 ноя 15, 14:45    [18471117]     Ответить | Цитировать Сообщить модератору
 Re: Как избежать обхода всех ветвей дерева  [new]
alcrux
Member

Откуда:
Сообщений: 39
Второе предложение решает проблему частично. Прохождение данной ветви действительно прерывается, но прохождение остальных ветвей с данным корнем все равно продолжиться.

Может можно решить более простую задачу. Протестировать с теми же требованиями данный корень на наличие ветви с f равным 1. Можно было бы избежать ненужных проходов если бы разрешалось устанавливать значения локальных переменных

set @found = 0 ;
select top( 1)  @root = id from tree where parent is null ;
with cte( id ) as (
  select @root
  union all
  select tr.id, @found = case when f = 1 then @found else  @found end from tree tr join cte t on parent = t.id and @found = 0
) 
select id from cte ;


К сожалению код приведенный выше выдает ошибку в @found = case....
A SELECT statement that assigns a value to a variable must not be combined with data-retrieval operations.

Может существует какой-нибудь трюк, который позволяет обойти это ограничение?
25 ноя 15, 15:14    [18471365]     Ответить | Цитировать Сообщить модератору
 Re: Как избежать обхода всех ветвей дерева  [new]
invm
Member

Откуда: Москва
Сообщений: 9396
alcrux
Это ничего не дает, если много элементов с полем f равным 1, у которых один корень.
Т.е. вы попробовали предложенный вариант запроса и пришли к такому выводу?
Было бы интересно узнать на основании чего?
25 ноя 15, 15:16    [18471378]     Ответить | Цитировать Сообщить модератору
 Re: Как избежать обхода всех ветвей дерева  [new]
Glory
Member

Откуда:
Сообщений: 104760
alcrux
Может существует какой-нибудь трюк, который позволяет обойти это ограничение?

А вы поняли хоть, что это за ограничение ?
25 ноя 15, 15:22    [18471420]     Ответить | Цитировать Сообщить модератору
 Re: Как избежать обхода всех ветвей дерева  [new]
Serg_77m
Member

Откуда: Донецк
Сообщений: 237
alcrux
Даже если для данного корневого элемента ответ будет ясен при проходе первой ветви, то, тем не менее, все остальные его ветви будут также пройдены.

Существует ли запрос/способ позволяющий устранить этот недостаток?
Если проход от элементов с f=1 к корню неэффективен, то остаётся разве что триггер написать, который будет для каждого элемента с f=1 ставить этот (или другой) флаг также всем родителям вплоть до корня.

При проходе от корня просмотра побочных ветвей не избежать никак. В каком порядке ни ищи, нужный элемент может оказаться самым последним.
25 ноя 15, 16:02    [18471695]     Ответить | Цитировать Сообщить модератору
 Re: Как избежать обхода всех ветвей дерева  [new]
Сид
Member

Откуда: Москва
Сообщений: 305
alcrux,

Оптимально, если данная логика должна использоваться постоянно:
1) добавить поле - id корня (чтобы он светился на всех уровнях);
2) если флаг где-то выставляется в 1, то обновлять также корневой элемент (вместо предложенного Serg_77m выставления всем родителям вплоть до корня);
3) если флаг выставляется в 0, то делаем прямой обход дерева до корня и ищем 1; если не нашли, выставляем 0 у корня.

В этом случае запрос будет тривиальным:
select id
from tree
where parent is null
and flag=1
25 ноя 15, 16:47    [18471947]     Ответить | Цитировать Сообщить модератору
 Re: Как избежать обхода всех ветвей дерева  [new]
Сид
Member

Откуда: Москва
Сообщений: 305
Сид
прямой обход дерева до корня

очепяточка: должно быть ОТ корня
25 ноя 15, 17:05    [18472072]     Ответить | Цитировать Сообщить модератору
 Re: Как избежать обхода всех ветвей дерева  [new]
alcrux
Member

Откуда:
Сообщений: 39
invm
alcrux
Это ничего не дает, если много элементов с полем f равным 1, у которых один корень.
Т.е. вы попробовали предложенный вариант запроса и пришли к такому выводу?
Было бы интересно узнать на основании чего?


Это был комментарий на предложение:
Glory
Найдите все записи с flag равным 1.
И к ним найдите всех родителей до корня.


Invm, как я писал, ваше предложение частично решает проблему, но обход всех ветвей избежать нельзя, я проверял.

Serg_77m, Сид, ваши варианты решают проблему, но мне хотелось их избежать выбрав промежуточный компромисс: делать обход ветвей, но не всех.
25 ноя 15, 22:17    [18473389]     Ответить | Цитировать Сообщить модератору
 Re: Как избежать обхода всех ветвей дерева  [new]
alcrux
Member

Откуда:
Сообщений: 39
Glory
alcrux
Может существует какой-нибудь трюк, который позволяет обойти это ограничение?

А вы поняли хоть, что это за ограничение ?


Нет. Я не вижу серьезных причин для невозможности конструкции

select filed1, @var1= field2 from ...


Более того, я где-то видел подобный код(но не для MSSQL). Поэтому и спросил о трюке.
25 ноя 15, 22:30    [18473444]     Ответить | Цитировать Сообщить модератору
 Re: Как избежать обхода всех ветвей дерева  [new]
invm
Member

Откуда: Москва
Сообщений: 9396
alcrux
делать обход ветвей, но не всех.
Так, как вы хотите - только курсор или цикл.
С помощью рекурсивного CTE не получится.
25 ноя 15, 22:32    [18473454]     Ответить | Цитировать Сообщить модератору
 Re: Как избежать обхода всех ветвей дерева  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 7868
alcrux,

найдите дочек, создайте по ним курсор и рекурсией найдите корни.
CTE внутри курсора.
26 ноя 15, 01:04    [18473864]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить