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

Откуда:
Сообщений: 2
есть таблица хранящая древовидную структуру типа
(
id numeric not null - primary key
parent numeric - foreign key id (cссылка на id из этой же таблицы)
field1 varchar
)

нужно сделать процедуру, которая выбирала бы все записи принадлежащие дереву, вершина которого (первый ID) задается во входных параметрах
13 окт 00, 04:43    [1752]     Ответить | Цитировать Сообщить модератору
 RE:tree  [new]
Vasily
Guest
Схожий вопрос уже обсуждался под рубрикой 'Третья нормальная форма'.
Одной простой процедурой не обойтись. Скорее всего нужны будут рекурсивные вызовы,
временная таблица и курсоры. Если данные условия устраивают, могу поделиться опытом.
13 окт 00, 05:47    [1753]     Ответить | Цитировать Сообщить модератору
 RE:tree  [new]
SergSuper
Guest
Это недавно тут обсуждалось. См. про "третью нормальную форму".
https://www.sql.ru/cgi-bin/UltraBoard/UltraBoard.pl?Action=ShowPost&Board=mssql&Post=108&Idle=365&Sort=0&Order=Descend&Page=0&Session=

Но к сожалению и там ответа не найдешь.
13 окт 00, 05:54    [1754]     Ответить | Цитировать Сообщить модератору
 RE:tree  [new]
Ольга
Guest
Вспомним рекурсию. :) Создаем две процедурки:

CREATE PROCEDURE sp_InsertItems
AS
begin
insert #ttt
(ID)
select ID
from Table1 t1
where Parent in
(select ID from #ttt) and
not exists(select * from #ttt t2 where t1.ID=t2.ID)

if @@rowcount<>0
exec sp_InsertItems


return
end
GO

CREATE PROCEDURE sp_SelectTreeItems
@ID int
AS
begin
select ID=@ID into #ttt
exec sp_InsertItems

select * from #ttt

return
end
GO

Чтобы построить список узлов, вызываем вторую процедуру с параметром - корень узла.
Работает до уровня "Maximum stored procedure nesting level", равного 32. Если у вас глубина дерева не больше 32, то такое решение подойдет.
13 окт 00, 07:11    [1755]     Ответить | Цитировать Сообщить модератору
 RE:tree  [new]
judge
Администратор

Откуда: SQL.ru
Сообщений: 6005
Блог
Я тут подумал и написал процедурку которая без рекурсии и курсоров выполняет требуемую задачу. Правда я ее не отлаживал, так что если что не работает - не особо пинайте :)
Таблица tree - имеет такую же структуру, как и в примере A_pol.


\nCREATE PROCEDURE get_tree @node_id int
AS
BEGIN
DECLARE @id int,
@node int

/* Creating temporary table for tree storage*/
CREATE TABLE #temp_tree
(
surrogate_id INT NOT NULL IDENTITY,
id int not null primary key,
parent int,
field1 varchar(32)
)

/* Inserting starting node into the temp table*/
INSERT #temp_tree (id, parent, field1)
SELECT id, parent, field1
FROM tree
WHERE id = @node_id

SELECT @id = -1

/* Cycling through the temp table and inserting branches for each node*/
WHILE 1 = 1
BEGIN
SET ROWCOUNT 1

/* Getting next ID and Node*/
SELECT @id = surrogate_id,
@node = id
FROM #temp_tree
WHERE surrogate_id > @id
ORDER BY surrogate_id

IF @@rowcount = 0
BEGIN
SET ROWCOUNT 0
BREAK
END

SET ROWCOUNT 0

/* Inserting all branches into temp table for selected node*/
INSERT #temp_tree (id, parent, field1)
SELECT id, parent, field1
FROM tree
WHERE parent = @node

END

/* Selecting results*/
SELECT id, parent, field1
FROM #temp_tree

DROP TABLE #temp_Tree
END



Должна работать быстро, единственное не забудьте создать нужные индексы на табличке tree.

Успехов, Александр.
13 окт 00, 10:17    [1756]     Ответить | Цитировать Сообщить модератору
 RE:tree  [new]
SergSuper
Guest
Вот тут мне пришла такая мысль. А что если несколько не так хранить данные. Вернее хранить так же, но еще дополнительно вести таблицу, которая будет управляться триггерами основной таблицы. А в этой дополнительной записывать все связи между эдементом и всеми его предками, и уровень их "предкости" - т.е. для родителей - 1, для будушек - 2 и т.д.
Тогда легко решается задача выбора всех записей для одной вершины. Но по-моему одними запросом построить дерево всё-равно не получиться.

Т.е. если у нас есть дерево, которое храниться в таблице:
1 2
1 4
2 3
3 5

Вести также и таблицу:
1 2 1
1 4 1
2 3 1
3 5 1
1 3 2
1 5 3
2 5 2
Последний столбик - это и есть "предкость". Если нарисовать будет понятно.

Не знаю, может кому мысль покажется полезной.
13 окт 00, 10:52    [1757]     Ответить | Цитировать Сообщить модератору
 RE:tree  [new]
alexeyvg
Guest
Предлагается простое и быстрое решение для предлагаемой структуры данных - одна итеррация на один уровень дерева:

CREATE PROCEDURE get_tree @node_id int
AS

DECLARE @level int

/* Creating temporary table for tree storage*/
CREATE TABLE #temp_tree
(
level int,
id int not null primary key,
parent int,
field1 varchar(32)
)

INSERT #temp_tree (level, id, parent, field1)
SELECT 0, id, parent, field1
FROM tree
WHERE id = @node_id

select @level = 0

WHILE 1 = 1
BEGIN

INSERT #temp_tree (level, id, parent, field1)
SELECT @level + 1, t.id, t.parent, t.field1
FROM tree t, #temp_tree tt
WHERE t.parent = tt.id
and tt.level = @level

IF @@rowcount = 0 BREAK

select @level = @level + 1

END

SELECT id, parent, field1
FROM #temp_tree

DROP TABLE #temp_Tree
GO
16 окт 00, 08:00    [1758]     Ответить | Цитировать Сообщить модератору
 RE:tree  [new]
Павел
Guest
К сожалению все предложенные варианты не гарантируют быстрого выполнения операции. Я эту прорблему (как и многие сопутствующие, возникающие при работе с деревьями) решил следующим образом:
Помимо основной таблицы Nodes (node_id, parent_node_id, node_name) существует вторая таблица Nodes2Parent(id, Node_id, parent_node_id)где для КАЖДОГО элеменита дерева перечисляются ВСЕ его дочерние элементы + сам элемент. Nodes.Node_id связаны нечетким отношением один-ко-многим с Nodes2Parent.parent_node_id и Nodes2Parent.Node_id (специфичный для MSSQL тип связи). Такая связь используется потому, что данные в таблице Nodes2Parent пасутся триггерами из таблицы Nodes. Надеюсь что обьяснил понятно. Таким образом запрос на удалении всей ветки очевиден. Кажущаяся сложность и неоптимальность слихвой компенсируется скоростью работы и дополенительными возможностями.
23 окт 00, 06:50    [1759]     Ответить | Цитировать Сообщить модератору
 RE:tree-в догонку  [new]
Павел
Guest
Сразу не увидел практически тот же вариант что и предложенный мной. Так что пардон за повтор.
23 окт 00, 06:55    [1760]     Ответить | Цитировать Сообщить модератору
 RE:tree  [new]
alexeyvg
Guest
В варианте, предложенном SergSuper и Павлом есть недостаток: объёмные обновления второй таблицы при перестроении дерева (например, при перемещении ветки в 1000 элементов и несколькими уровнями вложенности). Т.е. этот алгоритм хорош, если дерево редко меняется и нужны частые выборки ветвей.
23 окт 00, 10:25    [1761]     Ответить | Цитировать Сообщить модератору
 RE:tree  [new]
Павел
Guest
Все верно. Но подобного рода операции производятся одним запросом на обновление или изменение, и даже при очень большом количестве записей выполняются быстро. Приведу еще один пример. Организован древовидный справочник категорий продукции. Категория спецодежда включает в себя средства защиты рук, спецобувь, средства защиты от аониженных температур и.т.д, каждая подкатегория содержит еще кучу других. Юзерам захотелось, чтобы при выборе главной категории отображалась прордукция не только из нее самой, но и из всех дочерних категорий всех уровней вложенности. В предложенном мной и SergSuper это делается без проблем.
24 окт 00, 04:04    [1762]     Ответить | Цитировать Сообщить модератору
 RE:tree  [new]
VadimB
Member

Откуда: Москва
Сообщений: 22
Иногда программа из 10 строк будет работать быстрее, чем один Update па несколько милионов записей.
Поясняю.

Переположим дерево имеет 10 уровней и у каждого узла есть 10 потомков
Тогда:
на втором уровне 10 узлов
на третьем 10*10=100 узлов
на четвертом 10*10*10=1000 узлов
...
на десятом уровне 10*10*10*10*10*10*10*10*10*10=10 000 000 узлов (10 милионов)

Таблица, которая содержит описание деоева (узел и его один предок)
будет содержать 10+100+1000+...+10 000 000 (более 10 милионов) записей

10 узлов первого уровня имеют по 1 000 000 (1 милион) потомков, всего 10 милинов
100 узлов второго уровня имеют по 100 000 потомков, всего 10 милинов
...
1 милион узлов девятого уровня имеют по 10 потомков, всего 10 милинов

Таблица, которая содержит все потомки для каждого узла (предложение Павла)
будет содержать 10 милионов * 9 = 90 милионов записей

Любые операции (select,update,delet,insert) для узлов из верхних уровней будет обрабатывать несколько милионов записей.

Мне кажется лучше иметь программу из 10 строк, чем таблицу из 90 милионов записей.
24 окт 00, 12:46    [1763]     Ответить | Цитировать Сообщить модератору
 RE:tree  [new]
Павел
Guest
VadimB сделал вполне резонное замечание. Вот только с количеством элементов я с ходу разобраться не смог, тем боле что на правоту я не претендую. Да и тяжелый день сегодня был, я как мог снял стресс, да видно перестарался. Но одну IMHO достойную мысль напоследок из себя выдавлю: все познается в сравнении. Давайте потестируем разные варианты. Ведь в споре рождается истина.

Павел Жидков
orton@kemnet.ru
24 окт 00, 16:53    [1764]     Ответить | Цитировать Сообщить модератору
 RE:tree  [new]
petr13
Guest
Рекомендую почитать статейку на sdm.viptop.ru/articles/sqltrees.html

Там предлагается несколько другой способ организации дерева, который позволяет
довольно быстро и изящно выполнять операции типа выборки поддеревьев, листьев,
ну там еще кое что. Правда за это приходитиься платить дополнительными усилиями
при вставке и удалении узлов в существующее дерево. Но сам подход весьма интересен.
26 окт 00, 02:10    [1765]     Ответить | Цитировать Сообщить модератору
Между сообщениями интервал более 1 года.
 Re: tree  [new]
StarGale
Member

Откуда: С-Пб
Сообщений: 35
Нахрен нужна рекурсия и иже с нею!
Мы с другом написали так, работает.
Найдете глюки или ситуации какие хитрые - будем рады.

Дерево tre: tr_id-первичн.ключ, tr_prev-ключ папы (ссылается на tr_id)
Вызов EXEC cascade_del_proc @i_id (это id того, кого удаляем)


CREATE PROCEDURE cascade_del_proc (@top_id int) AS
DECLARE @item_id int
BEGIN
CREATE TABLE #Results(tr_id int NOT NULL)
INSERT INTO #Results(tr_id) SELECT tr_id FROM tre WHERE tr_id = @top_id
WHILE EXISTS(SELECT * FROM #Results)
BEGIN
SELECT top 1 @item_id = tr_id FROM #Results
INSERT INTO #Results(tr_id) SELECT tr_id FROM tre WHERE tr_prev=@item_id
DELETE FROM #Results WHERE tr_id = @item_id
DELETE FROM tre WHERE tr_id = @item_id
END
DROP TABLE #Results
END
1 июл 03, 13:31    [247158]     Ответить | Цитировать Сообщить модератору
 Re: tree  [new]
StarGale
Member

Откуда: С-Пб
Сообщений: 35
На всякий случай:
Таблица создавалась

CREATE TABLE tre (tr_id int IDENTITY, tr_name varchar(100) PRIMARY KEY, tr_prev int DEFAULT 0)

Удаление ветки по имени элемента:

CREATE PROCEDURE del_tree (@t_name varchar(100)) AS
DECLARE @i_id int
BEGIN
IF (SELECT COUNT(*) FROM tre WHERE tr_name=@t_name)>0
BEGIN
SELECT TOP 1 @i_id = tr_id FROM tre WHERE tr_name=@t_name
EXEC cascade_del_proc @i_id
END
END
1 июл 03, 13:38    [247167]     Ответить | Цитировать Сообщить модератору
 Re: tree  [new]
alexeyvg
Member

Откуда: Moscow
Сообщений: 31949
Ваш метод неэффективен - он требует 4 стэйтмента на каждый элемент дерева + 3 стэйтмента на всё.
Поищите с вашим другом в форуме - можно делать 2-я стэйтментами на всё + 1 стэйтмент на каждый уровень (не элемент) дерева.
1 июл 03, 13:56    [247211]     Ответить | Цитировать Сообщить модератору
 Re: tree  [new]
SergSuper
Member

Откуда: SPb
Сообщений: 5488
2 StarGale
Вы бы смотрели на дату обсуждения - это ж было почти 3 года назад.
Я думаю Вам с другом полезно будет посмотреть и более поздние сообщения.
1 июл 03, 14:07    [247234]     Ответить | Цитировать Сообщить модератору
 Re: tree  [new]
StarGale
Member

Откуда: С-Пб
Сообщений: 35
Где такое? Киньте ссылку pls, кто видел, если не трудно.
1 июл 03, 14:09    [247238]     Ответить | Цитировать Сообщить модератору
 Re: tree  [new]
alexeyvg
Member

Откуда: Moscow
Сообщений: 31949
Да, по деревьям надо-бы в фак засунуть...

Например, такая ф-ция есть, в ней ещё есть поле для сортировки, например, чтобы в сайте сразу выводить:

CREATE FUNCTION dbo.CT_GetTreeSort(@root int)
RETURNS @tree TABLE (id int, parent_id int, [level] int, [order] varchar(2000))
AS
BEGIN
declare @level int set @level = 0
insert @tree (id, parent_id, [level], [order])
select @root, null, @level, ''
while 1 = 1
begin
insert @tree (id, parent_id, [level], [order])
selecttr.ID, tr.ParentID, @level + 1, t.[order] + '::' + tr.Name + convert(varchar, tr.ID)
from tblTree as tr
join @tree as t on t.id = tr.ParentID and t.level = @level
if @@rowcount = 0 break
select @level = @level + 1
end
return
END
GO
1 июл 03, 14:35    [247293]     Ответить | Цитировать Сообщить модератору
 Re: tree  [new]
StarGale
Member

Откуда: С-Пб
Сообщений: 35
Спасибо!
Обновляемый FAQ по деревьям - да, пожалуй это было бы здорово. ;)
1 июл 03, 15:13    [247382]     Ответить | Цитировать Сообщить модератору
 Re: tree  [new]
AlexeyV
Member

Откуда: Москва
Сообщений: 40
А вот как делают в Microsoft: (BOL)

Expanding Hierarchies

Databases often store hierarchical information. For example, the following data is a hierarchical representation of regions of the world. 

This representation does not clearly show the structure implied by the data.

Parent Child
---------------------------------- ----------------------------------

World Europe
World North America
Europe France
France Paris
North America United States
North America Canada
United States New York
United States Washington
New York New York City
Washington Redmond

This example is easier to interpret:

World
North America
Canada
United States
Washington
Redmond
New York
New York City
Europe
France
Paris

The following Transact-SQL procedure expands an encoded hierarchy to any arbitrary depth. Although Transact-SQL supports recursion,
it is more efficient to use a temporary table as a stack to keep track of all of the items for which processing has begun but is not complete.
When processing is complete for a particular item, it is removed from the stack. New items are added to the stack as they are identified.

CREATE PROCEDURE expand (@current char(20)) as
SET NOCOUNT ON
DECLARE @level int, @line char(20)
CREATE TABLE #stack (item char(20), level int)
INSERT INTO #stack VALUES (@current, 1)
SELECT @level = 1

WHILE @level > 0
BEGIN
IF EXISTS (SELECT * FROM #stack WHERE level = @level)
BEGIN
SELECT @current = item
FROM #stack
WHERE level = @level
SELECT @line = space(@level - 1) + @current
PRINT @line
DELETE FROM #stack
WHERE level = @level
AND item = @current
INSERT #stack
SELECT child, @level + 1
FROM hierarchy
WHERE parent = @current
IF @@ROWCOUNT > 0
SELECT @level = @level + 1
END
ELSE
SELECT @level = @level - 1
END -- WHILE


The input parameter (@current) indicates the place in the hierarchy to start.
It also keeps track of the current item in the main loop.

The local variables used are @level, which keeps track of the current level in the hierarchy,
and @line, which is a work area used to construct the indented line.

The SET NOCOUNT ON statement avoids cluttering the output with ROWCOUNT messages from each SELECT.

The temporary table, #stack, is created and primed with the item identifier of the starting point in the hierarchy, and @level is set to match.
The level column in #stack allows the same item to appear at multiple levels in the database.
Although this situation does not apply to the geographic data in the example, it can apply in other examples.

In this example, when @level is greater than 0, the procedure follows these steps:

If there are any items in the stack at the current level (@level), the procedure chooses one and calls it @current.


Indents the item @level spaces, and then prints the item.


Deletes the item from the stack so it will not be processed again, and then adds all its child items to the stack at the next level (@level + 1).
This is the only place where the hierarchy table (#stack) is used.
With a conventional programming language, you would have to find each child item and add it to the stack individually.
With Transact-SQL, you can find all child items and add them with a single statement, avoiding another nested loop.

If there are child items (IF @@ROWCOUNT > 0), descends one level to process them (@level = @level + 1); otherwise, continues processing at the current level.


If there are no items on the stack awaiting processing at the current level,
goes back one level to see if there are any awaiting processing at the previous level (@level = @level - 1). When there is no previous level,
the expansion is complete.
11 июл 03, 11:44    [258439]     Ответить | Цитировать Сообщить модератору
 Re: tree  [new]
alexeyvg
Member

Откуда: Moscow
Сообщений: 31949
2AlexeyV
Да, алгоритм у них хреновый... На больших деревьях тормозить будет.
11 июл 03, 15:24    [258968]     Ответить | Цитировать Сообщить модератору
 Re: tree  [new]
AlexeyV
Member

Откуда: Москва
Сообщений: 40
Я то лично использую сейчас подход Павла со служебной таблицей со всеми потомками. Этот путь оказался наиболее эффективным по производительности и минимизации блокировок. Перед этим был пройден путь от классического представления (id - parent_id) через модель вложенных множеств(очень сильно тормозит при вставках/удалениях, да еще и блокирует таблицу). У нас сейчас в каталоге около 100000 объектов, вложенность достигает где-то 7-8, объекты хитрым образом типизированы, да еще связаны отношениями много-ко-многим друг с другом. В общем запросы к дереву нетривиальные, а тормозов практически никаких. Плата за это - каких-то 20Мб диска (на служебную таблицу) - что, согласитесь, ничто!

Так что настоятельно рекомендую.
11 июл 03, 16:04    [259071]     Ответить | Цитировать Сообщить модератору
 Re: tree  [new]
ChA
Member

Откуда: Москва
Сообщений: 11314
2 alexeyvg

tr.name может отсутствовать, да оно собственно и не надо,
если [order] сделать varbinary(8000) и конкатенацию делать
по CAST(tr.id AS varbinary(4)), а если посмотреть на цикл
WHILE 1 = 1, то это ужасно, если аккуратно, то его можно
превратить
WHILE @@ROWCOUNT > 0 BEGIN
...
INSERT ...
END

/**********/
Уже больше 3 лет пользую дополнительную таблицу, где
для каждого потомка указаны все предки, была попытка
сделать по Joe Celko, но на практике ужасно в сравнении
с дополнительной таблицей.
14 июл 03, 19:49    [261337]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Microsoft SQL Server Ответить