Третья нормальная форма

Рекурсивная связь в таблице нарушает третью нормальную форму или нет?

Наверное, имееются в виду иерархические цепочки?
По идее, поля входящие в рекурсивную ссылку должны выделяться в отдельную сущность. Иначе, определение 3 н.ф. нарушается (зависимость от ключа).

Как это, интересно, нарушается зависимость от ключа??? Как раз-таки если одним из атрибутов будет рекурсивная ссылка, то значение этого атрибута в случае бинарного дерева будет зависеть только от ключа этой записи. Так что в случае иерархической цепочки с нормализацией все будет нормально. А вот если есть произвольный граф, то уже надо выделять отдельную сущность для всех связок. Так что говорить абстрактно о том, нарушает ли рекурсия третью нормальную форму, нельзя.

А если дан произвольный граф, который хранится в двух таблицах: в одной хранятся номера узлов, а во второй описаны связи между ними (2 поля, первое хранит номер узла, второе, номер узла предка), как составить запрос, чтобы
он возвращал список всех узлов предков для заданного узла (не только родителей, а вообще всех узлов предков, стоющих по иерархии выше заданного?
(предположительно в графе нет циклов и ссылок узлов самих на себя)

Я долго думал над этой проблеммой и пришел к выводу, что это теоритически невозможно. Но доказать не могу. Руссуждения у меня примерно такие: чтобы вывести дерево, мы должны установить переменное число связей, чего в селекте сделать нельзя.

Но как хочется здесь ошибиться! :)

Разве что через while с занесением во временную таблицу...

На самом деле, такая задачка не решается одним select-ом и для иерархического дерева. Если стоит такая задача, то получается, что нормализация - только помеха. Один из способов - плюнуть на теорию и хранить ссылки в виде 12.34.45.58. Тогда операции "сборки предков" будут производиться достаточно быстро и одним select-ом (например, динамически формируемым на клиенте). И вопросы целостности будут целиком зависеть от клиента.

Подобная ссылка, внутри одной таблицы, называется "свинное ухо" (отображение на графиках похоже) и не противоречит третьему уровню нормализации уж точно. По-моему оно не противоречит ни одному из уровней нормализации (5 их или 6 не помню). В Oracle есть специальное расширение PL/SQL для подобных штук. B MS SQL лучше писать хранимую процедуру.

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