Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Сравнение СУБД [игнор отключен] [закрыт для гостей] / Деревянные аномалии / 16 сообщений из 16, страница 1 из 1
16.08.2005, 18:55
    #33219132
StalkerS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
Имеется желание сделать проверку на правильность ввода данных пользователями в древовидную таблицу tree(parentID,childID). Пока-что додумался до 2-х аномалий - подвисшие ветки и циклы. Вроде как, нет особых проблем в обнаружении подвисших веток - достаточно убедиться, что каждый узел имеет родителя (за исключением корневого узла).
А вот как бороться с циклами ? Например если ввести что-то типа

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

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

Кроме того, может еще какие аномалии существуют ?
...
Рейтинг: 0 / 0
16.08.2005, 19:03
    #33219148
AlexCzech
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
С учетом того, что дерево суть связный граф без циклов (причем связностью обычно в задачах программистских пренебрегают, называя набор N деревьев одним деревом), никаких именно "деревянных" аномалий кроме циклов быть не может, все остальные аномалии наличием циклов так или иначе выявляются. Подвисшие ветки же - это уже из серии аномалий, связанные не с природой дерева как математического объекта, а нарушение ограничения целостности, т.е. аномалии "уровня СУБД"
...
Рейтинг: 0 / 0
16.08.2005, 19:04
    #33219150
AlexCzech
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
А циклы надо проверять при вводе, в смысле в триггерах. Это совсем не сложно сделать даже без рекурсии
...
Рейтинг: 0 / 0
16.08.2005, 19:05
    #33219151
ChA
ChA
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
В случае цикла, при обходе, начиная с текущей вершины, рано или поздно снова придете к ней. Можно оформить функцией, с вызовом в CHECK CONSTRAINT...
...
Рейтинг: 0 / 0
16.08.2005, 20:15
    #33219227
StalkerS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
>>А циклы надо проверять при вводе, в смысле в триггерах

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

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

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

кстити извиняюсь, что не в тот форум запостил, хотел в Проектирование СУБД, может модераторы перенесут...
...
Рейтинг: 0 / 0
16.08.2005, 21:41
    #33219298
AlexCzech
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
Ну с точки зрения дерева строк как математического объекта ситуация, когда ребро указывает неведомо куда (а пара ObjectID + ParentID - это по сути ребро графа), просто невозможна.

Насчет "нельзя проверить при вводе" - это не так. Если при проверке в триггере двигаться не только вверх, но и вниз, можно любые некорректные ситуации определить именно при вводе. Даже в случае, когда, как я понимаю, потомок может оказаться в базе раньше предка - да, в этом случае ошибка возникнет не в добавляемом объекте, а в каком-то из его предков, но это не мешает не давать возможности создавать такие строки. Главное, как это говорят в армии, в данном случае - не сделать, а доложить, т.е. не просто обнаружить ошибку, а так сформулировать сообщение об ошибке, чтобы пользователь понял, в чем дело, и мог разобраться либо инициировать разбирательство :)
...
Рейтинг: 0 / 0
18.08.2005, 08:44
    #33222124
alex-ls
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
StalkerSИмеется желание сделать проверку на правильность ввода данных пользователями в древовидную таблицу tree(parentID,childID). Пока-что додумался до 2-х аномалий - подвисшие ветки и циклы. Вроде как, нет особых проблем в обнаружении подвисших веток - достаточно убедиться, что каждый узел имеет родителя (за исключением корневого узла).
А вот как бороться с циклами ? Например если ввести что-то типа

Сначала надо решить, что у Вас дерево или граф. Не факт, что корень должен быть один...
...
Рейтинг: 0 / 0
18.08.2005, 11:52
    #33222627
gardenman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
очень тяжело делать обработку деревьев когда сервер базы не поддерживает рекурсивные запросы и когда нет триггеров на запись, а только на стэйтмент. Кодирование превращается в сущий кошмар.
...
Рейтинг: 0 / 0
18.08.2005, 12:11
    #33222705
4321
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
gardenmanочень тяжело делать обработку деревьев когда сервер базы не поддерживает рекурсивные запросы и когда нет триггеров на запись, а только на стэйтмент. Кодирование превращается в сущий кошмар.есть куча методов ведения "SQL-ного" древа (или леса). Например ведение не ссылок на предков, а на "левого/правого по обходу", или же текстового (мемо) поля с полной иерархией узла, или таблицы всех иерархических связей узла. Понятно, что все это избыточно и затратно, но работает с "простыми" SQL конструкциями (и при этом автоматом поддерживает отсутствие колец).
...
Рейтинг: 0 / 0
18.08.2005, 12:37
    #33222819
gardenman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
4321[quot gardenman]или же текстового (мемо) поля с полной иерархией узла.

А ну-ка перепоlчините одну ветку - другой... :)) Любопытно взглянуть на количество кода, которое придется нарисовать при этом, а так же на производительность этого чуда :)
...
Рейтинг: 0 / 0
18.08.2005, 13:11
    #33222969
4321
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
gardenman 4321[quot gardenman]или же текстового (мемо) поля с полной иерархией узла.

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


Для текстовой иерархии в поле очевидно порождение каскадного срабатывания триггеров (если поле в той же таблице) "на запись". От этого мне хотелось уйти. Можно наверное иерархию держать в таблице связанной 1-1. Но мне не улыбалось писать Лайки (они у постгреса как-то криво работают со стандартными индексами, а я был "не в теме").
...
Рейтинг: 0 / 0
18.08.2005, 14:05
    #33223114
SergSuper
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
gardenman 4321[quot gardenman]или же текстового (мемо) поля с полной иерархией узла.

А ну-ка перепоlчините одну ветку - другой... :)) Любопытно взглянуть на количество кода, которое придется нарисовать при этом, а так же на производительность этого чуда :)
Дык это один раз написать, зато потом выборки будет несравнимо проще и быстрее чем с рекурсивными запросами
...
Рейтинг: 0 / 0
18.08.2005, 15:45
    #33223428
StalkerS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
Собственно, не зря метод Джо Селко является популярным, очень сильно увеличивает скорость запросов...
...
Рейтинг: 0 / 0
18.08.2005, 16:00
    #33223480
gardenman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
авторДык это один раз написать, зато потом выборки будет несравнимо проще и быстрее чем с рекурсивными запросами
а вы в курсе, что такое переключение контекстов ?
И, интересно где на каких серверах и на таблицах какого объема вы сравнивали рекурсивные запросы с хранимками? :))
Может вы хотябы в курсе как формируется план запроса у хранимки?
И что такое расщепление ХП и зачем оно нужно?
...
Рейтинг: 0 / 0
18.08.2005, 18:56
    #33224006
SergSuper
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
gardenman авторДык это один раз написать, зато потом выборки будет несравнимо проще и быстрее чем с рекурсивными запросами
а вы в курсе, что такое переключение контекстов ?
И, интересно где на каких серверах и на таблицах какого объема вы сравнивали рекурсивные запросы с хранимками? :))
Может вы хотябы в курсе как формируется план запроса у хранимки?
И что такое расщепление ХП и зачем оно нужно?
Что такое переключение контекстов и расщепление ХП не в курсе, тем более зачем оно нужно. Но если вы считаете что можно как-то быстрее найти записи чем выбрав их стандартным запросом непосредственно по индексу - расскажите как это может быть.
И причем тут хранимки? Я про них ни слова не писал, хотя как примерно формируется план запроса в курсе(в очень общих чертах).
...
Рейтинг: 0 / 0
22.08.2005, 10:33
    #33227266
StalkerS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Деревянные аномалии
gardenman
а вы в курсе, что такое переключение контекстов?
...
Может вы хотябы в курсе как формируется план запроса у хранимки?
И что такое расщепление ХП и зачем оно нужно?

а какие еще умные слова вы знаете ?
Никогда не слышал о таком понятии в mssql как расшепление ХП, обьясните скорее, а то все это выглядит распальцовкой типа "Вы знаете что такое ковергенция корреляции скалярного поля ? Нет ? Ну и тупые же вы все, не то, что я"
...
Рейтинг: 0 / 0
Форумы / Сравнение СУБД [игнор отключен] [закрыт для гостей] / Деревянные аномалии / 16 сообщений из 16, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]