Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
 Проверка на циклы в иерархической таблице(Головоломка)  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 89
Навеяно другой темой, про constraints и проверку данных на вшивость.

Задана таблица EMPLOYEES с полями employee_id и manager_id типа integer.
Таблица описывает строгую древовидную иерархию, с одним гендиректором наверху.

Как в SQL (или в PL/SQL, чтоб легче) подтвердить правильность древовидной структуры?
Критерии правильности древовидности довольно очевидна но на всякий случай в вики есть определение:

https://ru.wikipedia.org/wiki/Дерево_(структура_данных)

Сообщение было отредактировано: 15 сен 20, 19:24
15 сен 20, 02:41    [22196993]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
Relic Hunter
Member

Откуда: AB
Сообщений: 7374
select count(*) from employees where manager_id is null
15 сен 20, 03:34    [22196994]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
xtender
Member

Откуда: Мск
Сообщений: 5618
НеофитSQL,

На форуме ужн многократно обсуждалось, решения элементарные, а на современных версиях ещё легче. Но ты пиши, посмотрим...
15 сен 20, 03:57    [22196995]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 89
Relic Hunter
select count(*) from employees where manager_id is null


Лаконично. Похоже, что производится подсчет гендиректоров, из предположения что гендиректор помечен null.
Это не единственный способ отметить гендиректора, но вполне рабочий. Для этого manager_id придется сделать nullable, расслабив одно из ограничений.

Этот тест отловит таблицы где нет гендиректоров, или более одного гендиректора. Некоторые вещи он пропустит.

Контрпример: следующие таблицы обе вернут (1), но вторая из них не отвечает определению дерева.

EMPLOYEES_GOOD EMPLOYEES_BAD
emp_id mgr_id emp_id mgr_id
===============================================
5 0 5 0
8 5 8 8

У меня пока тоже не получается записать эту задачу на SQL, т.к. мое решение полагается на цикл, а с циклами в SQL туго.
15 сен 20, 06:08    [22197000]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2557
НеофитSQL,

проверить что все "узлы" employee_id в дереве и нет циклов?

ps
connect by, with ...

....
stax
15 сен 20, 10:13    [22197061]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 9950
НеофитSQL
Некоторые вещи он пропустит.

Контрпример: следующие таблицы обе вернут (1), но вторая из них не отвечает определению дерева.

EMPLOYEES_GOOD EMPLOYEES_BAD
emp_id mgr_id emp_id mgr_id
===============================================
5 0 5 0
8 5 8 8


Пропустит, но не это. Это предотвращается а не проверяется. Например через FBI на EMPLOYEES(1 / (EMPNO - MGR)) или через calculated column X = EMPNO - MGR плюс check constraint CANT_SELFREPORT на X != 0.

SY.
15 сен 20, 13:25    [22197359]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
кит северных морей
Member

Откуда: krsk / nyc / krsk
Сообщений: 785
SY
НеофитSQL
Некоторые вещи он пропустит.

Контрпример: следующие таблицы обе вернут (1), но вторая из них не отвечает определению дерева.

EMPLOYEES_GOOD EMPLOYEES_BAD
emp_id mgr_id emp_id mgr_id
===============================================
5 0 5 0
8 5 8 8


Пропустит, но не это. Это предотвращается а не проверяется. Например через FBI на EMPLOYEES(1 / (EMPNO - MGR)) или через calculated column X = EMPNO - MGR плюс check constraint CANT_SELFREPORT на X != 0.

SY.
а просто чек на empno != mgr?
15 сен 20, 13:39    [22197371]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 89
Мне приятно, что есть желающие размять мозги и возможно, блеснуть кодом.

Действительно, можно ввести проверку на eid != mid (давайте сократим эти поля employee_id и manager_id).
Такая проверка исключит тривиальные циклы. Но пропустит более длинные.

Контрпример: цикл из двух, не ловится вышеописанной проверкой.

EMPLOYEES_GOOD       EMPLOYEES_BAD
emp_id mgr_id emp_id mgr_id
===============================================
5 0 5 0
8 5 8 3
3 5 3 8

В этом контрпримере, в "хорошей" таблице строчки 2-3 подчинены гендиректору, а в "плохой" таблице - друг другу (цикл).
Цикл может быть из трех и более - нужно ловить все.
15 сен 20, 13:48    [22197394]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 9950
кит северных морей
а просто чек на empno != mgr?


Brain fart

SY.
15 сен 20, 13:51    [22197401]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 9950
НеофитSQL


В этом контрпримере, в "хорошей" таблице строчки 2-3 подчинены гендиректору, а в "плохой" таблице - друг другу (цикл).
Цикл может быть из трех и более - нужно ловить все.


А это без сериализации не предотвращается а проверить можно только полным проходом по дереву.

SY.

Сообщение было отредактировано: 15 сен 20, 13:56
15 сен 20, 13:58    [22197409]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 89
Stax
НеофитSQL,

проверить что все "узлы" employee_id в дереве и нет циклов?

ps
connect by, with ...

....
stax


Чувствуется человек с опытом работы - первым делом уточнил условия задачи.

Дополнение к первому сообщению, более конкретные условия задачи:
1) гендиректор обозначается manager_id (mid) = null
2) пустая таблица не считается деревом
3) таблица из одного и более элементов может быть деревом (только гендиректор - считать деревом)
3) в дереве ровно один ген директор
4) циклы в графе запрещены - у дерева не бывает циклов
5) каждый сотрудник должен быть напрямик или через других подчинен гендиректору
6) результат функции или запроса должен говорить "дерево" или "не дерево" (true/false, 1/0, на усмотрение)
7) код должен отрабатывать за конечное время, быстрее - лучше

Я заметил что в коммерческих решениях зачастую вершина дерева помечается как mid=eid, а не как mid=null.
Думаю, что это делается с целью усиления constraints, тогда mid можно определить non-nullable внешний ключ.
Если к этому добавить запрет на mid=eid для INSERT, будет невозможно испортить дерево при добавлении сотрудников.
15 сен 20, 14:06    [22197419]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2557
НеофитSQL

Цикл может быть из трех и более - нужно ловить все.

connect by нельзя пльзоваться?

....
stax
15 сен 20, 14:09    [22197426]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18150
Тривиально: пройтись по всем записям, выстраивая иерархию от подчиненного к менеджеру.
Обработать exception "connect-by loop in user data" либо проконтролировать соответствующий флаг.
Отобрать листья.
Сгруппировать листья и убедиться, что результатом группировки является единственная запись и эта запись соответствует корню иерархии.
Фсьо.
15 сен 20, 14:19    [22197442]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 89
Можно пользоваться connect by, и любыми другими встроенными средствами Оракл.

Если там есть встроенная команда проверки всего дерева, то это было бы самым правильным решением.

Кстати, я не знал про существование connect by до этого момента, сейчас читаю как эта конструкция обрабатывает циклы.
15 сен 20, 14:39    [22197474]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18150
Уважаемый, уже несколько дней наблюдаю за Вашим творчеством.
Не скрою,увлекательно.
Продолжайте пожалуйста.
Только огромная просьба: пожалуйста, ни в коем случае не изучайте выбранный технологический стек, не читайте документацию - от этого Ваши сообщения могут существенно потерять в лулзах.
15 сен 20, 14:44    [22197483]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
env
Member

Откуда: Россия, Москва
Сообщений: 6153
НеофитSQL
Если там есть встроенная команда проверки всего дерева,

В множестве типа "куча" нет деревьев, но можно хранить записи, имеющие логические ссылки на соседние. На этом всё.
15 сен 20, 14:54    [22197499]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 89
andrey_anonymous
Тривиально: пройтись по всем записям, выстраивая иерархию от подчиненного к менеджеру.
Обработать exception "connect-by loop in user data" либо проконтролировать соответствующий флаг.
Отобрать листья.
Сгруппировать листья и убедиться, что результатом группировки является единственная запись и эта запись соответствует корню иерархии.
Фсьо.


Это звучит как решение. Вряд ли я такое сегодня смогу написать на SQL.

А вот connect-by/noloop - очень полезная штука, я о ней до этого не знал.
С этим оператором задача упрощается в разы.
15 сен 20, 15:04    [22197512]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
SY
Member

Откуда: Middlebury, CT USA
Сообщений: 9950
НеофитSQL

С этим оператором задача упрощается в разы.


Не упрощается. В многопользовательском режиме (что есть стандарт) такая проверка (CONNECT BY) ничего не гарантирует. Без сериализации тут не обойтись.

SY.
15 сен 20, 15:14    [22197521]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
Dimitry Sibiryakov
Member

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

НеофитSQL
Как в SQL (или в PL/SQL, чтоб легче) подтвердить правильность древовидной структуры?

Составной ключ id+уровень иерархии, соответствующий FK и сверху chеck, проверяющий уровень
иерархии менеджера выше, чем у работника.

Posted via ActualForum NNTP Server 1.5

15 сен 20, 15:21    [22197528]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
xtender
Member

Откуда: Мск
Сообщений: 5618
SY,

Да что ж вы делаете-то... Остановитесь! Сейчас ещё одна же тема появится, теперь про уровни изоляции транзакций и мини-откаты... Прямо галопом по европам...
15 сен 20, 15:23    [22197530]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 89
Dimitry Sibiryakov

НеофитSQL
Как в SQL (или в PL/SQL, чтоб легче) подтвердить правильность древовидной структуры?

Составной ключ id+уровень иерархии, соответствующий FK и сверху chеck, проверяющий уровень
иерархии менеджера выше, чем у работника.


Идея понятна, но уровень иерархии не определен для циклов.
15 сен 20, 15:29    [22197534]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
Dimitry Sibiryakov
Member

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

НеофитSQL
уровень иерархии не определен для циклов.

В дереве не существует циклов.

Posted via ActualForum NNTP Server 1.5

15 сен 20, 15:32    [22197537]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 89
SY

В многопользовательском режиме (что есть стандарт) такая проверка (CONNECT BY) ничего не гарантирует. Без сериализации тут не обойтись.
SY.


В многопользовательском режиме CONNECT BY исполняется по-другому, и ему нельзя доверять?
Я написал следующее условие, которое true если дерево, и false если не дерево.
Оно использует connect by, оно сломается и даст неверные данные в многопользовательском режиме?
Или вы говорите о ситуации, когда таблица меняется во время исполнения проверок?
Если так, то добавим условие что таблицу считать статической на время проверки (напр., копия)

(select  count(*)
   from  EMPLOYEES
   start with mid is null
 connect by
 nocycle
   prior eid = mid)
 =(select count(*) from EMPLOYEES) 
and 
(select count(*) from EMPLOYEES where mid is null) = 1
15 сен 20, 15:51    [22197550]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 89
Dimitry Sibiryakov

НеофитSQL
уровень иерархии не определен для циклов.

В дереве не существует циклов.


Действительно. У дерева нет циклов, и ровно один корень.
Условие этой головоломки - определить представляет ли таблица правильное дерево.

Ваше предложенное решение начинается с "предположим, что это правильное дерево, где определен уровень иерархии.." :)
15 сен 20, 15:56    [22197554]     Ответить | Цитировать Сообщить модератору
 Re: Головоломка  [new]
dmdmdm
Member

Откуда: Нижний Новгород
Сообщений: 1552
НеофитSQL

В многопользовательском режиме CONNECT BY исполняется по-другому, и ему нельзя доверять?


Поскольку в однопользовательском вы будете работать исчезающе редко, лучше сразу прочитать Oracle Database Concepts, о чем вам уже несколько дней повторяют, и выкинуть свой устав, придя в этот монастырь.

и не выдумывать фантастических ситуаций

таблицу считать статической на время проверки (напр., копия)
15 сен 20, 15:59    [22197558]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
Все форумы / Oracle Ответить