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

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

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