Dimitry SibiryakovScareCrowа что за способы?
1) включение в ключ ноды полного пути до неё
2) хранение полного списка связей
Оба имеют свои ограничения, но позволяют быстрые выборки без использования рекурсии.

первый способ - нарушение 1НФ

Dimitry SibiryakovА второй - третьей (или второй?..). Денормализация - обычный способ увеличения быстродействия.
второй - вообще не денормализация, по-моему )

Ывы имеет в виду, что пересечение строки и столбца должно содержать единственное значение из некоторого домена? Так там и будет не несколько значений идентификаторов узлов, а единое значение (напр., из специально созданного домена), интепретируемое как путь на графе. В PostgreSQL для этого есть тип данных ltree.
Я имею ввиду возможные проблемы с сохранением ссылочной целостности при таких полях. Можно повесить внешний ключ на ltree (пардон, не знаю PostgreSQL)

Dimitry SibiryakovЗайцев Фёдорвторой - вообще не денормализация, по-моему )
Избыточность налицо, так что это по-любому денормализация. Осталось только придумать номер
нарушаемой НФ.

Избыточность лечится очень просто - изменением имени таблицы
В том смысле, что тип отношения не "близкий родственник" а "родственник" ^^

На самом деле, избыточность, конечно, присутствует. Но для 3НФ это по барабану, ей вообще не нужно знать про деревья, достижимость и т.д. Не нарушается, короче)