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

Откуда: Melbourne
Сообщений: 1344
Имеется желание сделать проверку на правильность ввода данных пользователями в древовидную таблицу tree(parentID,childID). Пока-что додумался до 2-х аномалий - подвисшие ветки и циклы. Вроде как, нет особых проблем в обнаружении подвисших веток - достаточно убедиться, что каждый узел имеет родителя (за исключением корневого узла).
А вот как бороться с циклами ? Например если ввести что-то типа

insert into tree values(1,2)
insert into tree values(2,1)

то получается полная ж. Тем более, что цикл может иметь много уровней вложенности...

Кроме того, может еще какие аномалии существуют ?
16 авг 05, 18:55    [1792081]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
AlexCzech
Member

Откуда:
Сообщений: 729
С учетом того, что дерево суть связный граф без циклов (причем связностью обычно в задачах программистских пренебрегают, называя набор N деревьев одним деревом), никаких именно "деревянных" аномалий кроме циклов быть не может, все остальные аномалии наличием циклов так или иначе выявляются. Подвисшие ветки же - это уже из серии аномалий, связанные не с природой дерева как математического объекта, а нарушение ограничения целостности, т.е. аномалии "уровня СУБД"
16 авг 05, 19:03    [1792102]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
AlexCzech
Member

Откуда:
Сообщений: 729
А циклы надо проверять при вводе, в смысле в триггерах. Это совсем не сложно сделать даже без рекурсии
16 авг 05, 19:04    [1792105]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
ChA
Member

Откуда: Москва
Сообщений: 11377
В случае цикла, при обходе, начиная с текущей вершины, рано или поздно снова придете к ней. Можно оформить функцией, с вызовом в CHECK CONSTRAINT...
16 авг 05, 19:05    [1792107]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
StalkerS
Member

Откуда: Melbourne
Сообщений: 1344
>>А циклы надо проверять при вводе, в смысле в триггерах

в триггере к сожалению нельзя, дерево может вводиться в любой последовательности, главное что-бы результат оказался верным, это должно проверяться потом, когда из этого дерева будет формироваться другая структура...

В общем, если от каждого узла подниматься вверх - то обязательно должен дойти до корня, а если дошел до первоначального узла - значит цикл, если вообще до корня не дошел - подвисшая ветка... Спасибо.

>>это уже из серии аномалий, связанные не с природой дерева как математического объекта, а нарушение ограничения целостности
А почему ? Я думал это как раз аномалия дерева, самой-то СУБД по-сути все-равно, какой узел с каким соединен, и соединен-ли с вершиной...

кстити извиняюсь, что не в тот форум запостил, хотел в Проектирование СУБД, может модераторы перенесут...
16 авг 05, 20:15    [1792258]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
AlexCzech
Member

Откуда:
Сообщений: 729
Ну с точки зрения дерева строк как математического объекта ситуация, когда ребро указывает неведомо куда (а пара ObjectID + ParentID - это по сути ребро графа), просто невозможна.

Насчет "нельзя проверить при вводе" - это не так. Если при проверке в триггере двигаться не только вверх, но и вниз, можно любые некорректные ситуации определить именно при вводе. Даже в случае, когда, как я понимаю, потомок может оказаться в базе раньше предка - да, в этом случае ошибка возникнет не в добавляемом объекте, а в каком-то из его предков, но это не мешает не давать возможности создавать такие строки. Главное, как это говорят в армии, в данном случае - не сделать, а доложить, т.е. не просто обнаружить ошибку, а так сформулировать сообщение об ошибке, чтобы пользователь понял, в чем дело, и мог разобраться либо инициировать разбирательство :)
16 авг 05, 21:41    [1792399]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
alex-ls
Member

Откуда: Иркутская обл - Пенза - Москва
Сообщений: 7078
StalkerS
Имеется желание сделать проверку на правильность ввода данных пользователями в древовидную таблицу tree(parentID,childID). Пока-что додумался до 2-х аномалий - подвисшие ветки и циклы. Вроде как, нет особых проблем в обнаружении подвисших веток - достаточно убедиться, что каждый узел имеет родителя (за исключением корневого узла).
А вот как бороться с циклами ? Например если ввести что-то типа

Сначала надо решить, что у Вас дерево или граф. Не факт, что корень должен быть один...
18 авг 05, 08:44    [1797352]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
gardenman
Member

Откуда: С-Петербург
Сообщений: 2347
очень тяжело делать обработку деревьев когда сервер базы не поддерживает рекурсивные запросы и когда нет триггеров на запись, а только на стэйтмент. Кодирование превращается в сущий кошмар.
18 авг 05, 11:52    [1798057]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
4321
Member [заблокирован]

Откуда:
Сообщений: 3573
gardenman
очень тяжело делать обработку деревьев когда сервер базы не поддерживает рекурсивные запросы и когда нет триггеров на запись, а только на стэйтмент. Кодирование превращается в сущий кошмар.
есть куча методов ведения "SQL-ного" древа (или леса). Например ведение не ссылок на предков, а на "левого/правого по обходу", или же текстового (мемо) поля с полной иерархией узла, или таблицы всех иерархических связей узла. Понятно, что все это избыточно и затратно, но работает с "простыми" SQL конструкциями (и при этом автоматом поддерживает отсутствие колец).
18 авг 05, 12:11    [1798163]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
gardenman
Member

Откуда: С-Петербург
Сообщений: 2347
4321
[quot gardenman]или же текстового (мемо) поля с полной иерархией узла.


А ну-ка перепоlчините одну ветку - другой... :)) Любопытно взглянуть на количество кода, которое придется нарисовать при этом, а так же на производительность этого чуда :)
18 авг 05, 12:37    [1798338]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
4321
Member [заблокирован]

Откуда:
Сообщений: 3573
gardenman
4321
[quot gardenman]или же текстового (мемо) поля с полной иерархией узла.


А ну-ка перепоlчините одну ветку - другой... :)) Любопытно взглянуть на количество кода, которое придется нарисовать при этом, а так же на производительность этого чуда :)
Я делал несколько другой случай - триггера для заполнения "полной таблицы связей" в постгресе (т.е. "на каждую запись". Делал без использования касадного срабатывания триггеров (т.е. запись в таблице дерева отрабатывала свой триггер, правя ВСЕ порождаемые этим изменения таблицы связей SQL конструкциями (на основе той же самой таблицы связей)). При вставке/редактировании отдельных записей пользователями работает приемлемо. Наиболее критичны массовые вливы/апдейты данных какой-нть приладой. Кода "изрядно" (по полстранички на адд -2 инсерта, и 3/4 - на апп - несколько дилетов и инсертов). Но "полчаса потерять" - а дальше можно код просто юзать для других деревьев..


Для текстовой иерархии в поле очевидно порождение каскадного срабатывания триггеров (если поле в той же таблице) "на запись". От этого мне хотелось уйти. Можно наверное иерархию держать в таблице связанной 1-1. Но мне не улыбалось писать Лайки (они у постгреса как-то криво работают со стандартными индексами, а я был "не в теме").
18 авг 05, 13:11    [1798556]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
SergSuper
Member

Откуда: SPb
Сообщений: 5488
gardenman
4321
[quot gardenman]или же текстового (мемо) поля с полной иерархией узла.


А ну-ка перепоlчините одну ветку - другой... :)) Любопытно взглянуть на количество кода, которое придется нарисовать при этом, а так же на производительность этого чуда :)

Дык это один раз написать, зато потом выборки будет несравнимо проще и быстрее чем с рекурсивными запросами
18 авг 05, 14:05    [1798796]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
StalkerS
Member

Откуда: Melbourne
Сообщений: 1344
Собственно, не зря метод Джо Селко является популярным, очень сильно увеличивает скорость запросов...
18 авг 05, 15:45    [1799289]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
gardenman
Member

Откуда: С-Петербург
Сообщений: 2347
автор
Дык это один раз написать, зато потом выборки будет несравнимо проще и быстрее чем с рекурсивными запросами

а вы в курсе, что такое переключение контекстов?
И, интересно где на каких серверах и на таблицах какого объема вы сравнивали рекурсивные запросы с хранимками? :))
Может вы хотябы в курсе как формируется план запроса у хранимки?
И что такое расщепление ХП и зачем оно нужно?
18 авг 05, 16:00    [1799377]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
SergSuper
Member

Откуда: SPb
Сообщений: 5488
gardenman
автор
Дык это один раз написать, зато потом выборки будет несравнимо проще и быстрее чем с рекурсивными запросами

а вы в курсе, что такое переключение контекстов?
И, интересно где на каких серверах и на таблицах какого объема вы сравнивали рекурсивные запросы с хранимками? :))
Может вы хотябы в курсе как формируется план запроса у хранимки?
И что такое расщепление ХП и зачем оно нужно?

Что такое переключение контекстов и расщепление ХП не в курсе, тем более зачем оно нужно. Но если вы считаете что можно как-то быстрее найти записи чем выбрав их стандартным запросом непосредственно по индексу - расскажите как это может быть.
И причем тут хранимки? Я про них ни слова не писал, хотя как примерно формируется план запроса в курсе(в очень общих чертах).
18 авг 05, 18:56    [1800340]     Ответить | Цитировать Сообщить модератору
 Re: Деревянные аномалии  [new]
StalkerS
Member

Откуда: Melbourne
Сообщений: 1344
gardenman

а вы в курсе, что такое переключение контекстов?
...
Может вы хотябы в курсе как формируется план запроса у хранимки?
И что такое расщепление ХП и зачем оно нужно?

а какие еще умные слова вы знаете ?
Никогда не слышал о таком понятии в mssql как расшепление ХП, обьясните скорее, а то все это выглядит распальцовкой типа "Вы знаете что такое ковергенция корреляции скалярного поля ? Нет ? Ну и тупые же вы все, не то, что я"
22 авг 05, 10:33    [1805969]     Ответить | Цитировать Сообщить модератору
Все форумы / Сравнение СУБД Ответить