Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
 Хранение деревьев  [new]
bernex
Member

Откуда:
Сообщений: 14
Нужна быстрая база или подход, какой выбрать?

1. Выбирать дерево, целиком или от родителя со всеми детьми.. или с одним ребенком.
2. Причем по выбранной ноде надо сумму столбца с поднодами...

Какую базу выбрать или подход?
Postgres?
14 мар 14, 14:36    [15724252]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54792

bernex
Какую базу выбрать или подход?

Да любую выбирай, как и любой подход. Эти условия ничего не ограничивают.

Posted via ActualForum NNTP Server 1.5

14 мар 14, 14:59    [15724509]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
Yo.!
Guest
bernex,

выбрать реляционную и имеющую иерархические запросы, в postgres вроде рекурсивные CTE уже есть.
14 мар 14, 15:39    [15724946]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
ARTURV
Member

Откуда: Санкт-Петербург
Сообщений: 314
bernex,

На Postgres вполне прилично работает рекурсия, но Вы определитесь какой метод Вам больше подходит
Adjacency List или Nested Sets. Почитайте литературу
14 мар 14, 15:56    [15725128]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54792

Yo.!
выбрать реляционную и имеющую иерархические запросы

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

Posted via ActualForum NNTP Server 1.5

14 мар 14, 15:58    [15725145]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
AlexKB
Member

Откуда: Запорожье
Сообщений: 856
bernex,
Лучше всего хранить деревья в древовидной базе!!!
14 мар 14, 16:03    [15725192]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
dma_caviar
Member

Откуда: https://itproduct.ru
Сообщений: 2362
Yo.!
bernex,

выбрать реляционную и имеющую иерархические запросы, в postgres вроде рекурсивные CTE уже есть.

походу в postgres уже все есть, пока кидать mssql)
14 мар 14, 16:07    [15725226]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
ScareCrow
Member

Откуда: Белый город
Сообщений: 17472
Dimitry Sibiryakov
Yo.!
выбрать реляционную и имеющую иерархические запросы

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

а что за способы?
14 мар 14, 17:19    [15725881]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54792

ScareCrow
а что за способы?

1) включение в ключ ноды полного пути до неё
2) хранение полного списка связей
Оба имеют свои ограничения, но позволяют быстрые выборки без использования рекурсии.

Posted via ActualForum NNTP Server 1.5

14 мар 14, 17:26    [15725926]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
Зайцев Фёдор
Member

Откуда: Лужки
Сообщений: 5308
Dimitry Sibiryakov
ScareCrow
а что за способы?

1) включение в ключ ноды полного пути до неё
2) хранение полного списка связей
Оба имеют свои ограничения, но позволяют быстрые выборки без использования рекурсии.

первый способ - нарушение 1НФ
14 мар 14, 19:34    [15726661]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54792

Зайцев Фёдор
первый способ - нарушение 1НФ

А второй - третьей (или второй?..). Денормализация - обычный способ увеличения быстродействия.

Posted via ActualForum NNTP Server 1.5

14 мар 14, 20:07    [15726812]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
Ы
Guest
Зайцев Фёдор,

вы имеет в виду, что пересечение строки и столбца должно содержать единственное значение из некоторого домена? Так там и будет не несколько значений идентификаторов узлов, а единое значение (напр., из специально созданного домена), интепретируемое как путь на графе. В PostgreSQL для этого есть тип данных ltree.
14 мар 14, 20:18    [15726856]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
Зайцев Фёдор
Member

Откуда: Лужки
Сообщений: 5308
Dimitry Sibiryakov
А второй - третьей (или второй?..). Денормализация - обычный способ увеличения быстродействия.

второй - вообще не денормализация, по-моему )
14 мар 14, 20:21    [15726871]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54792

Зайцев Фёдор
второй - вообще не денормализация, по-моему )

Избыточность налицо, так что это по-любому денормализация. Осталось только придумать номер
нарушаемой НФ.

Posted via ActualForum NNTP Server 1.5

14 мар 14, 20:24    [15726883]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
Зайцев Фёдор
Member

Откуда: Лужки
Сообщений: 5308
Ы
вы имеет в виду, что пересечение строки и столбца должно содержать единственное значение из некоторого домена? Так там и будет не несколько значений идентификаторов узлов, а единое значение (напр., из специально созданного домена), интепретируемое как путь на графе. В PostgreSQL для этого есть тип данных ltree.

Я имею ввиду возможные проблемы с сохранением ссылочной целостности при таких полях. Можно повесить внешний ключ на ltree (пардон, не знаю PostgreSQL)
14 мар 14, 20:24    [15726886]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
Зайцев Фёдор
Member

Откуда: Лужки
Сообщений: 5308
Dimitry Sibiryakov
Зайцев Фёдор
второй - вообще не денормализация, по-моему )

Избыточность налицо, так что это по-любому денормализация. Осталось только придумать номер
нарушаемой НФ.

Избыточность лечится очень просто - изменением имени таблицы
В том смысле, что тип отношения не "близкий родственник" а "родственник" ^^
14 мар 14, 20:26    [15726899]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
Зайцев Фёдор
Member

Откуда: Лужки
Сообщений: 5308
На самом деле, избыточность, конечно, присутствует. Но для 3НФ это по барабану, ей вообще не нужно знать про деревья, достижимость и т.д. Не нарушается, короче)
14 мар 14, 20:32    [15726929]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
Yo.!
Guest
Dimitry Sibiryakov
Или хранить деревья способом, отличным от самого примитивного, и обойтись без рекурсии.

вам товарищ можно все, это не лечится
14 мар 14, 20:50    [15726997]     Ответить | Цитировать Сообщить модератору
 Re: Хранение деревьев  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54792

Yo.!
вам товарищ можно все

Да, я всё могу. И даже использовать index range scan вместо nested loop.

Posted via ActualForum NNTP Server 1.5

14 мар 14, 21:02    [15727043]     Ответить | Цитировать Сообщить модератору
Все форумы / Сравнение СУБД Ответить