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

Откуда: Южное Тушино
Сообщений: 232
Уважаемые господа
Имеет ли кто-нибудь опыт реализации модели вложенных множеств Джо Целко (Joe Celсo) для деревьев?http://oralib.h1.ru/articles/1810.html
Из всех известных моделей эта показалась мне наиболее "sql-ной". Отзыв на нее я обнаружил только один http://www.pwr.ru/items/?id=3. К числу недостатков автором отнесено то, что
автор
практически при любом изменении требуется пройтись, в общем случае, по большей части дерева и перегенерировать значения левой и правой границ множества
На мой взгляд здесь требуется уточнить, что в некоторых случаях изменение требуется только для правой границы (а для корня всегда).
Почитав топики про деревья данного форума пришел к выводу, что наиболее популярной схемой хранения деревьев является таблица с рекурсивной связью id, parent_id причем в таблице хранятся записи для всех предков узла, что дает возможность, например, легко получать суммы по любому поддереву.
Что касается трудоемкости обновления, то из общих соображений полагаю, что для данной схемы и схемы Целко она примерно одинакова.
Так стоит ли связываться со схемой Целко или нет?
Как считаете?
Спасибо
26 мар 04, 09:31    [598318]     Ответить | Цитировать Сообщить модератору
 Re: А кто-нибудь пробовал реализовать модель вложенных множеств Целко для деревьев?  [new]
Mike Neck
Member

Откуда:
Сообщений: 56
Я исполнял такую схему. Очень ничего для деревьев которые редко (у меня раз в год) модифицируются. Делал правда на SQL Anywhere. Только аккуратно пиши триггера которые считают веса. И напиши процедуру полного пересчёта весов в дереве. Иначе отладка мучительна и ужасна. Самое неприятное с чём столкнулся - дерево у меня направленное и порядок детей для родителя имеет значение. Когда надо поменять местами поддеревья внутри дерева - можно фимоз головного мозга нажить(ну да у меня и опыта не было). Зато запросы на выборку - конфетка - быстро удобно и прямо. Хочешь детей, хочешь родителей, хочешь поддерево с листьями выбранными по опредёленному признаку.

Но если модификации нужны частые и дерево большое - ищи другой метод.
26 мар 04, 10:02    [598391]     Ответить | Цитировать Сообщить модератору
 Re: А кто-нибудь пробовал реализовать модель вложенных множеств Целко для деревьев?  [new]
SergSuper
Member

Откуда: SPb
Сообщений: 5488
когда то давно я писал
вот тут снизу
по идее должно поддерживать и удаления и перенос и нескольких записей и т.д.
26 мар 04, 10:34    [598451]     Ответить | Цитировать Сообщить модератору
 Re: А кто-нибудь пробовал реализовать модель вложенных множеств Целко для деревьев?  [new]
ChA
Member

Откуда: Москва
Сообщений: 11137
> Дмитрий Валуев
> Что касается трудоемкости обновления, то из общих соображений полагаю, что для данной схемы и схемы Целко она примерно одинакова.

В случае добавление листа в модели по Celko может понадобиться
перенумеровать практически все узлы, что при индексах на обе границы
тяжеловато. Кроме того, в таком случае произойдет блокировка практически
всей таблицы.
В случае хранения дополнительной таблицы со всеми предками та же самая операция сводится к добавлению записей только для этого листа, т.е.
идентификатор листа плюс предков для предка, что, IMHO, значительно
легче.
После знакомства с моделью Celko, была попытка ее использовать,
но это привело к тому, что в некоторых случаях появились запросы,
в которых понадобилось самослияние таблицы, тогда как во второй
модели обходилось одним прямым запросом. Короче, вернулись обратно
ко второй модели...

P.S. Это только IMHO. Другие мнения не исключаются...
26 мар 04, 11:57    [598700]     Ответить | Цитировать Сообщить модератору
 Re: А кто-нибудь пробовал реализовать модель вложенных множеств Целко для деревьев?  [new]
RatTail
Member [заблокирован]

Откуда: Z
Сообщений: 4517
целко-манделко.. манделко-целко.. всё это детский лепет..
Вот задача на порядок "по-проще":
дан плоский неориентированный связный граф (короче, "нормальный"
такой граф, без всяких там "мостов", "ручек" и т.п.). Каждая вершина
этого графа имеет степень >= 3, т.е., из каждой его вершины выходят
не менее 3-х ребер.
Надо найти вершины этого графа через которые проходит его внешняя
граница.
==============
Не будем мегаломанами и возьмем совершенно конкретный граф с 10
вершинами и 17 ребрами. Это таблица с его ребрами (edges):

create table #edges(v1 int, v2 int)
insert into #edges
select 1, 2 union all
select 1, 3 union all
select 1, 7 union all
select 2, 3 union all
select 2, 10 union all
select 3, 4 union all
select 3, 5 union all
select 4, 5 union all
select 4, 6 union all
select 5, 8 union all
select 5, 10 union all
select 6, 7 union all
select 6, 8 union all
select 7, 9 union all
select 8, 9 union all
select 8, 10 union all
select 9, 10


drop table #edges
26 мар 04, 17:02    [599852]     Ответить | Цитировать Сообщить модератору
 Re: А кто-нибудь пробовал реализовать модель вложенных множеств Целко для деревьев?  [new]
RatTail
Member [заблокирован]

Откуда: Z
Сообщений: 4517
Находит все восемь минимальные петли (циклы) этого графа.
Плюс, его внешнюю границу - №8 - (1 7)(7 9)(9 10)(10 2)(2 1).
Для "большинства" графов код внизу работает чудесно, но есть
один восхитительно-коварный случай ког..............

nl ce
----------- ------------------------------------

1 (1 2)(2 3)(3 1)
2 (3 4)(4 5)(5 3)
3 (5 8)(8 10)(10 5)
4 (8 9)(9 10)(10 8)
5 (2 10)(10 5)(5 3)(3 2)
6 (4 6)(6 8)(8 5)(5 4)
7 (6 7)(7 9)(9 8)(8 6)
8 (1 7)(7 9)(9 10)(10 2)(2 1)
9 (1 3)(3 4)(4 6)(6 7)(7 1)


if object_id('g3')>0 drop table g3
if object_id('g3x')>0 drop table g3x
if object_id('g3y')>0 drop table g3y
if object_id('g3l')>0 drop table g3l
GO
create table g3y(n int, v1 int, v2 int)
GO
create table g3x(n int, ne int, v1 int, v2 int)
GO
create table g3l(nl int, ne int, v1 int, v2 int, ce varchar(80))
GO
create table g3(ne int, v1 int, v2 int)
GO
insert into g3 (v1, v2)
select 1, 2 union all
select 1, 3 union all
select 1, 7 union all
select 2, 3 union all
select 2, 10 union all
select 3, 4 union all
select 3, 5 union all
select 4, 5 union all
select 4, 6 union all
select 5, 8 union all
select 5, 10 union all
select 6, 7 union all
select 6, 8 union all
select 7, 9 union all
select 8, 9 union all
select 8, 10 union all
select 9, 10
GO
update g3 set ne=(select count(*) from g3 g
where (g.v1=g3.v1 and g.v2<=g3.v2) or g.v1<g3.v1)
insert into g3 select ne, v2, v1 from g3
declare @i int, @n int, @nemax int, @ne int, @ns int,
@v1 int, @v2 int, @ce varchar(80), @f int
set @nemax=(select max(ne) from g3)
set @ns=2 set @i=1

while 0=0
begin
set @f=0 set @ns=@ns+1 set @ne=0

while @ne<@nemax
begin
set @ne=@ne+1
select @v1=v1, @v2=v2 from g3 where ne=@ne and v1<v2 and
not exists (select 0 from g3l where ne=@ne)

if @@rowcount>0
begin
set @f=1 set @n=1
truncate table g3x truncate table g3y
insert into g3x select @n, @ne, @v1, @v2

while 0=0
begin
set @n=@n+1
insert into g3x select top 1 @n, ne, v1, v2 from g3 where
v2 not in (select v1 from g3x union all select v2 from g3x) and
v1=(select top 1 v2 from g3x order by n desc) and not exists
(select 0 from g3y where g3y.v1=g3.v1 and g3y.v2=g3.v2)
if @@rowcount=0
if @n>2
begin
insert into g3y select n, v1, v2 from g3x where n=@n-1
delete from g3x where n=@n-1 delete from g3y where n>@n-1
set @n=@n-2
end
else break
else
if @n=@ns-1
begin
insert into g3x select top 1 @n, ne, v1, v2 from g3 where v2=@v1
and v1<>@v2 and v1=(select top 1 v2 from g3x order by n desc)
if @@rowcount=0
begin
insert into g3y select n, v1, v2 from g3x where n=@n
delete from g3x where n=@n
set @n=@n-1
end
else
begin
insert into g3l select @i, ne, v1, v2, '' from g3x
set @i=@i+1 break
end
end
end
end
end
if @f=0 break
end

delete from g3 where ne in
(select ne from g3l group by ne having count(*)>1)

while 0=0
begin
set @n=1 truncate table g3x
insert into g3x select top 1 @n, ne, v1, v2 from g3 where v1<v2
if @@rowcount=0 break
delete from g3 where ne=(select ne from g3x)

while 0=0
begin
set @n=@n+1
insert into g3x select top 1 @n, ne, v1, v2 from g3
where v1=(select v2 from g3x where n=@n-1)
delete from g3 where ne=(select ne from g3x where n=@n)
set @f=0
set @f=
(select n from g3x where v1=(select v2 from g3x where n=@n))
if @f>0
begin
insert into g3l select @i, ne, v1, v2, '' from g3x
where n>=@f set @i=@i+1
delete from g3x where n>=@f set @n=@f-1
if @n=0 break
end
end
end

set @n=0
while @n<(select max(nl) from g3l)
begin
set @ce='' set @n=@n+1
select
@ce=@ce+'('+cast(v1 as varchar(8))+' '+cast(v2 as varchar(8))+')'
from g3l where nl=@n
update g3l set ce=@ce where nl=@n
end
select distinct nl, ce from g3l order by nl
27 мар 04, 22:43    [600762]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить