KOT MATPOCKuHexpla
Прикольно будет, когда в дереве образуется петля...

"ОНО" перестанет быть деревом!
Кстати, определяется эта проблема легко, правда не на уровне констрейнтов (в большенстве СУБД, в некоторых можно, но таких мало)



На уровне декларативных ограничений целостности это правило легко описать за счёт усложнения операций обновления дерева. Достаточно, чтобы выполнялось ограничение PARENT_ID < ID.

АнатоЛойусложнение операций обновления дерева - это смена идентификаторов при смене родителя у узла? нафикнафик

Сам придумал плохое решение, и сам же от него отказался. Придумай хорошее решение и пользуйся.
К стати для правильного изменения родителя всё равно как минимум может потребоваться блокировка всех его потомков, так что замена ID узлов не будет выглядеть такой уж жудкой процедурой. Да и часто ли приходится вносить такие изменения в деревья?

KOT MATPOCKuHexlpaВетки между узлами описываем внешним ключём PARENT_ID
Это не совсем верно, т.к. PARENT_ID все-таки ссылается на ключ узла, поэтому, чтобы описать ветку нужна как минимум пара, например, [NODE_ID, PARENT_ID].
В общем случае, структура NODE_ID, SOME_FIELDS, PARENT_ID является денормализованной. Правильнее было бы разбить ее на две таблицы: "собственно узлы" и "ребра" (или ветки - кому как приятнее). Правда я сам так никогда не делаю - всегда одна таблица :)
Т.е. в стандартном случае в одной таблице лежат две разные сущности: узлы (ключ NODE_ID) и ребра (ключ: [NODE_ID, PARENT_ID]).


Плевать на сущности. Нормализация сосредоточена только на ключевых, неключевых атрибутах и функциональным зависимостям между ними. Если отношение удовлетворят требованиям той или иной НФ, то сколько в нём сущностей храниться не имеет значения. Как я понял, речь только о том, что в единой таблице узлов/рёбер нельзя создать ребро без двух узлов (если это не корень дерева). Но по моему это вполне нормально, потому как рёбра без узлов не живут.

KOT MATPOCKuH
В "дерево", которое называется моя файловая система я вношу изменения ежедневно по многу раз. А на нашем файл-сервере изменения происходят каждые несколько минут.
Так что...

Вам часто приходится переносить папки с места на место? А если в папке есть открытый файл? В любом случае - не нравится не ешь. Проверяй целостность как нибудь иначе.

KOT MATPOCKuH

exlpaНо нередко мы имеем дело с локальной идентивикацией веток узла (например в двоичном дереве все ветки могут быть правыми или левыми), (поскольку узел в дереве имеет 0..1 ветку связанную с предком, то LOCAL_ID ветки и LOCAL_ID узла можно отождествить, кроме случая корневого узла). Т.е. ключ ветки узла, не является уникальным для всего дерева. Здесь мы не можем описать отдельную ветку записью в реляционном отношении, поскольку это будет нарушением 1НФ (запись не идентифицируема). Добавление сурогатного ключа решает только проблему идентификации записи в физической БД. Чтобы реконструировать логиченский первичный ключ произвольного узла нужно соеденить все записи между этим узлом и корнем дерева. Согласитесь, это неудобно и неэффективно.

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



Имеем бинарное дерево. Каждый узел этого дерева (кроме корневого) имеет одно ребро на входе, и два ребра (правое и левое) на выходе (у листовых узлов есть только ребро на входе). Узел потомок находящийся на конце правого/левого ребра узла предка называем правым/левым. Т.е. отдельно взятый узел будет иметь LOCAL_ID - "правый" (0) или "левый" (1). Таким образом LOCAL_ID не может быть первичным ключём отношения "узлы_бинарного_дерева".

Что делать?... Можно ввести сурогатный ключ, но тогда всплывает куча проблем с поиском и модификацией записей. Но можно сконструировать реальный первичный ключ - перечислить LOCAL_ID всех узлов на пути от корня к данному узлу включительно. В бинарном дереве, это может быть последовательность нулей (для "правых" узлов) и единиц (для "левых" узлов).

MasterZivНо вот работать если с элементами этого полного пути будете в БД ---
уже получится нарушение 1НФ - у вас таких элементов будет много.
Т.е. у вас будет неатомарный атрибут.


Полное имя файла - атрибут атомарный. Какое либо деление этого атрибута лишает его смысла. Если Вас послушать, то можно сказать, что строка, это массив символов, а массив атрибут тоже вроде как не атомарный - состоит из элементов (в случае строки - букв). Однако атомарность, это скорее вопрос системы типов СУБД. Вот стал оракл поддерживать вложенные таблицы и коллекции, и теперь никто не мешает нам хранить атрибуты со сложной структурой в их естественном виде, не прибегая к декомпозиции только из-за того, что в СУБД не было подходящего типа данных.

При таком подходе, для логически неделимых иерархических структур можно XML использовать. Оракл ими хорошо рулит.

MasterZiv
> Второе определение, ИМХО, ближе к делу. Если у вас есть тип данных для
> хранения целого объекта, то независимо от сложности его внутренней
> структуры он с точки зрения реляционной БД (но не с точки зрения
> приложений БД) будет атомарным.

да. Ключевой момент тут - что БД не должа его пытаться разобрать
на части или изменить по частям.



БД по своей сути ничего не может изменить в себе. Изменения в БД вносит СУБД, т.е. некий исполняемый код, но никак не данные. Физическая БД, это всего лишь двоичные файлы на дисках. Семантику типа в эти данные вносит сначала СУБД, а затем приложение. СУБД вполне может разбирать атрибуты на составные части, например выделать из строк слова и создавать инвертированные файлы для контекстного поиска.

Логическая БД это другое дело. Математические типы атрибутов и отношений определяются как множества значений. В свою очередь значения могут быть скалярами, векторами, кортежами, множествами и т.д. некоторых констант.

В процессе проектирования БД мы выбираем такие типы атрибутов, которые поддерживает СУБД и приложения. В этом смысле можно атомарность атрибута рассматривать в привязке к контексту - типа в таком приложении он атомарный, а в другом приложении - нет. Но, ИМХО, этот подход имеет внутреннее противоречие, которое приводит к ошибочным заключениям. Прикол в том, что если СУБД или приложение не поддерживает некий абстрактный тип данных, то и нет смысла говорить о нём с связи с этой СУБД. Если мы дербаним данные на составные части, которые имеют поддерживаемый тип, и создаём из них множество отношений, то это не значит, что исходный тип не был атомарным, это значит, что в БД для данной СУБД нужно хранить атомарные данные в дискретном виде.

Так, счёт - объект по сути атомарный. Позиция счёта или счёт продавца сами по себе не имеет смысла. Однако в обычной реляционной БД нам нужно разложить шапку и позиции счёта в разные таблицы, а потом с помощью всяких ограничений и проверок следить, чтобы эти части не рассыпались.