Организация хранения иерархических данных

[Keeper89]

Доброго времени суток!

Столкнулся с вопросом хранения в БД иерархической информации. Информация представляет собой бухгалтерский отчет, типа:

Номер	Наименование	1 кв. 2010 г.	...	Сумма
1.	Расходы на персонал - всего	500	...	1500
1.1.	Повременные расходы	500	...	1500
1.1.1.	Больничные листы	500	...	1500

И т.д.

Все суммируется в группах, по строкам и столбцам. Как организовать хранение такой штуки?
Заранее спасибо.

Сообщение отредактировано: Keeper89 - 11.05.14, 18:04

[AVA12]

Насколько я понимаю, структура дерева счетов меняется крайне редко, зато нужно очень часто искать потомков узла (всех или один уровень) и собирать по ним статистику. Также для оптимизации (кэширования) подсчетов пригодится поиск всех узлов-предков.

В этом случае идеально подходят вложенные множества (nested sets). Вкратце: для каждой записи хранятся два числа - левый (il) и правый (ir) индекс - которые отражают положение записи в иерархии. Назначаются они так: счетчик инициализируется единицей, затем дерево обходится в глубину слева направо; при каждом заходе в узел/лист "сверху" в его il пишется текущее значение счетчика и счетчик увеличивается; при каждом выходе из узла/листа "наверх" в его ir записывается текущее значение счетчика и счетчик увеличивается. В результате получается, что для каждой записи ее il больше il любого предка, а ее ir меньше ir любого предка.

Также можно хранить в записи уровень ее вложенности и флаг, показывающий, является ли запись листом (а значит, хранит реальное число) или промежуточным узлом (а значит, нужно считать).

В прстейшем случае суммы по строке и по столбцу не хранятся в БД, а высчитываются "на лету", но тогда требуется лишний SQL-запрос, и БД выполняет не очень-то нужную работу. Лучше кэшировать эти суммы в узлах. Если какое-либо число в листе изменилось, то пересчитываем сумму строки и для всех узлов-предков выставляем флаг "кэш невалиден". Если видим, что кэшированные данные в узле невалидны, то в транзакции считаем суммы потомков-листьев, пишем результат в узел и помечаем данные как валидные.

[Bas]

> Сохранение дерева в файл (в БД), а также связанных с ним записей

[Akina]

Думаю, в данном конкретном случае (бух. отчёт) использование nested set избыточно. Вполне достаточно хранить материализованный путь узла (в примере структуры - поле Номер).

[Bas]

Цитата Akina @ 12.05.14, 06:19

хранить материализованный путь узла

Могут быть варианты.Например, узел содержит несколько балансовых или внебалансовых (забалансовых) счетов.

Сообщение отредактировано: Bas - 12.05.14, 08:10

[Akina]

Для меня всё, что ты сказал - китайская грамота... но не вижу сложностей, если у какого-то узла несколько потомков. Лишь бы не было сетки.

[Bas]

Цитата Akina @ 12.05.14, 08:13

но не вижу сложностей, если у какого-то узла несколько потомков.

Классическое дерево.

Цитата Akina @ 12.05.14, 08:13

Для меня всё, что ты сказал - китайская грамота...

Если это отчет и его надо хранить то нет проблем, но если надо вычислять - то ой. Например в пункте 1.1.1 сумма может складываться из 1000 счетов по которым прошли 1 000 000 транзакций за квартал (по каждому).
Добавлено 12.05.14, 09:14

Цитата AVA12 @ 11.05.14, 23:21

В этом случае идеально подходят вложенные множества (nested sets).

Достаточно ввести поле parent которое хранит выше стоящий id если есть, если нет то он сам по себе (1).

Сообщение отредактировано: Bas - 12.05.14, 09:17

[Akina]

Цитата Bas @ 12.05.14, 09:10

Например в пункте 1.1.1 сумма может складываться из 1000 счетов по которым прошли 1 000 000 транзакций за квартал (по каждому).

Ну и что? какая разница, в сете оно хранится или на материализации? один хрен миллион сумм плюсить. Конечно, в сете группить попроще, но тоже не сахар - тут скорее всего наибольший эффект даст сегментация или кластеризация по путям. А ещё лучше - предрасчёты по минимальной (или даже не минимальной - но это усложнит хранимую логику) единице дискретизации по времени.

[Bas]

Akina, мы залезли глубоко.
Keeper89, надо просто сохранить отчет, он не просил помощи в расчете

[Akina]

Ну и что? ТС ответ получил. Во всяком случае не возмущается и в оффтопе нас не обвиняет - чё не потрындеть-то?

[Павел Калугин]

Цитата Bas @ 12.05.14, 09:10

Достаточно ввести поле parent которое хранит выше стоящий id если есть, если нет то он сам по себе (1).

Для удобства еще "ПОЛНЫЙ НОМЕР СЧЕТА" в дереве счетов хранить неплохо.

[Akina]

Павел Калугин
А смысл? материализованный путь это покрывает. Главное - не вешать абстрактные выравнивающие хвосты из нулей.
А нестедсету это так и вовсе сиренево...

[Keeper89]

Всем спасибо, ответы поизучаю!

[Павел Калугин]

Akina чтобы при необходимости просто показать полный номер счета не "разматывая" все дерево вверх

Отчеты "подпрыгивают и взлетают"

[Akina]

Павел Калугин
Так полный номер и есть материализованный путь...