Навеяно другой темой, про constraints и проверку данных на вшивость.

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

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

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

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

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


У меня пока тоже не получается записать эту задачу на SQL, т.к. мое решение полагается на цикл, а с циклами в SQL туго.

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

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

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


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

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

Дополнение к первому сообщению, более конкретные условия задачи:
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, будет невозможно испортить дерево при добавлении сотрудников.

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

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

Кстати, я не знал про существование connect by до этого момента, сейчас читаю как эта конструкция обрабатывает циклы.

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

А вот connect-by/noloop - очень полезная штука, я о ней до этого не знал.
С этим оператором задача упрощается в разы.

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


Идея понятна, но уровень иерархии не определен для циклов.

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

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


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

Ваше предложенное решение начинается с "предположим, что это правильное дерево, где определен уровень иерархии.." :)