Может кто знает,
какой-нибудь стандартный алгоритм суммирования по деревьям. Например есть
дерево с n уровнями, сколько ветвей и сколько уровней я незнаю. Фактическое
значения имеют только самые нижние уровни ветвей. Причем у каждой ветви
может быть разное колличество уровней вложенности. Как скажем собрать сумму
на кокой-нибудь средний уровень. Ну например если взять реестр Windows и
значение каких-либо параметров сложить и получить сумму этих параметров для
узла HKEY_CURRENT_USER.
Warcat (17.05.01 10:38)
Вопрос на сколько я понял
все таки про SQL :)
Вот здесь есть интересная статья про множественное
представление деревьев.
http://sdm.viptop.ru/articles/sqltrees.html
В
такой модели операции выборки, нахождения суммы выполняются не сложно, но
очень сложно выполняются операции добавления и удаления.
SergVlad (17.05.01 10:43)
Нужно использовать
рекурсивные механизмы спуска по дереву и иметь метод определения наличия
child узлов у текущего узла.
На примере TTreeView(
идея)
GetResultForNode(node)) - ваша функция определения значения
чего-либо для текущего узла.
function TDBTreeView.RecurseChilds(node: TTreeNode): double;
begin
while node <> nil do begin
if node.HasChildren then
Result := RecurseChilds(node.GetFirstChild);
Result := Result + GetResultForNode(node));
node := node.GetNextSibling;
end;
end;
function TDBTreeView.GetResult(curnode: TTreeNode;): double;
begin
Result := 0;
if curnode = nil then Exit;
Result := RecurseChilds(curnode.GetFirstChild);
end;
Эту
идею можно распространить и на БД, естественно с написанием своих методов
поиска child и навигации по ним.
Более широкие возможности здесь в случае
применения SQL-запросов.
Но нужны специальные способы организации
структуры, т.к. простейший, с использованием ID и PARENT не слишком
функционален.
Warcat (17.05.01 10:56)
Если реализовывать алгоритм
на Delphi, то согласен с SergVlad'ом.
При использовании матрицы
смежности, надо учитывать, что для нее наиболее оптимальными алгоритмами
являются рекурсии. А вот если использовать рекурсию в SQL, то следует
узнать, какая степень вложенности рекурсии допускается используемым
сервером. К примеру, у MS существует ограничение в 32 вложенные рекурсии.Это
надо учитывать при разработке алгоритма. Я лично при написании кода на SQL
стараюсь не использовать рекурсии. В большинстве случаев без них можно
обойтись.
Но в любом случае на операциях выборки матрица смежности будет
работать медленнее, чем множественная модель. Зато остальные операции
гораздо быстрее. Выбор за Вами.
SergSuper (17.05.01 12:25)
Если это SQL и есть
определённое количество уровней, то всё делается просто:
Допустим есть
таблица tree с полями
id - идентификатор записи
parent - идентификатор
родителя
var - некое нужное значение
тогда делается так(если 3
уровня):
select sum(var)
from tree t1,tree t2,tree t3
where t2.parent=t1.id and t3.parent=t2.id
В
остальном - см. выше
Алексей (17.05.01 12:50)
В том то и смыл, что
сколько уровней неизвестно.
Выбока может собирается на любой из них,
вопрос-то в том что бы можно было обеспечить приемлемую скорость
работы.
Объем записей порядка миллиона. Что касается статьи по ссылке
http://sdm.viptop.ru/articles/sqltrees.html
то я ее прочитал, но там
все кратенько и не совсем понятно как формирутся столбцы left и right.
Если кто знает так просветите поподробнее.
Wild_V (17.05.01 18:21)
Вот я прочитал статью... Я
чего-то не понимаю...
Есть у нас табличка Документы (Папки документов и
сами документы).
Компания у нас крупная, записей в табичке ~ 500000. И
тут я добавляю один документик(а это происходит сотни(тысячи) раз в день) и
идёт апдейт чуть не на всю базу... Вау...
Или у меня буйная фантазия? А
каким образом пересчёт на тригерах? Для удаления - пускай, но для вставки мы
должны определить сами, куда мы вставляем вершинку... короче -
геморой...
Народ, а вот файловые системы... Ведь их разрабатывают не
идиоты...
FAT - более медленная, но меньше объёмом, NTFS - быстрее, но
объёмнее.
Лично я готов жертвовать объёмом ради
быстродействия.
Проблема в том, что там ничем реляционным и не пахнет, но
всё-таки может какие-то идейки можно оттуда украсть?
Если я намолол
ерунды - не принимайте близко к сердцу(конец рабочего дня всё-таки...
:)
Warcat (17.05.01 18:35)
To Wild_V
Множественная
модель отлично подходит к РЕДКООБНОВЛЯЕМЫМ данным.
Конечно, для 500000
постоянно изменяемых записей множественная модель не подойдет. А вот если
разбить документы и группы документов на разные таблицы, то думаю в самый
раз :). Ведь согласитесь, новая группа документов появляется не часто, а
удаляется и того реже. (Я понимаю, что для Вашей конкретной задачи это может
быть не вариант).
А принципы построения файловых систем к сожалению вряд
ли подойдут к решению реляционных задач. Очень уж разные области. Очень
разные объемы данных. Разные средства разработки для решения.
Wild_V (17.05.01 18:52)
Угу , таблица Папкок,
таблица Документов...
Согласен, но у меня вот какая бяка...
Все
дочерние вершины (и папки и документы) должны зачитываться одним запросом
... Выходит, либо кривой Union(слишком велика разница в структуре таблицы
папок и таблицы документов, либо... 2 запроса...
Грустно... :(
nikkie (17.05.01 20:57)
вообще-то очень просто
написать не рекурсивный обход
дерева. я на MS SQL для рекурсивного
удаления такую процедуру писал
(Function - таблица со ссылкой на
себя):
create procedure cascade_del_function (@func_id int)
as
declare @item_id int
declare @child_id int
declare cur_child cursor for
select Function_Id from Function
where Function_Id_Above = @item_id
declare cur_parent cursor for
select Function_Id_Above from Function
where Function_Id = @child_id
begin
select @item_id = @func_id
while 1 = 1
begin
while 1 = 1
begin
open cur_child
fetch cur_child into @child_id
close cur_child
if @@fetch_status <> 0
break
select @item_id = @child_id
end
select @child_id = @item_id
open cur_parent
fetch cur_parent into @item_id
close cur_parent
delete from Function where Function_Id = @child_id
if @child_id = @func_id
break
end
deallocate cur_child
deallocate cur_parent
end
go
извините,
если в смысле использования возможностей MS SQL не здорово - я вообще-то им
не занимаюсь... но идея, надеюсь понятна: берем первого чайлда до тех пор,
пока можно, удаляем, берем папу, у него опять-таки самого первого чайлда
пока можно и т.д. останавливаемся, когда удалили переданный элемент.
если
вопрос про суммирование - немножко сложнее, поскольку ничего не удаляется и
нельзя все время брать первого чайлда. надо добавить в select сортировку по
id и условие where > id и брать "следующего" чайлда.
---
Из конференции сайта МАСТЕРА DELPHI (delphi.mastak.ru)
|
| Copyright ©
"Мастера DELPHI" E-mail:
delphi@mastak.com
http://www.delphimaster.ru |
| Источник получения информации: http://www.delphimaster.ru
|
Конвертация DBF в DB