Статья:
Иерархические структуры данных в реляционных БД

Автор(ы): Михаил Голованов
Дата: 28.01.2002

Авторы:
Михаил Голованов

Аннотация:
Архитектура реляционных баз данных ориентирована на хранение внутри таблиц БД информации о сущностях информационной системы и связях между ними. Каждая из записей таблицы содержит информацию об одном экземпляре. Организация хранения информации о независимых друг от друга экземплярах сущностей (т.е. так называемых «плоских» данных) не вызывает никаких затруднений. Однако, наряду с «плоскими» данными, при построении даже простых информационных систем, приходится хранить в БД и информацию о «вложенных» друг в друга сущностях, т.е иерархические данные. Организация хранения такой информации в реляционных БД проста, но не всегда очевидна для тех, кто впервые сталкивается с подобной задачей. В данной статье я попытаюсь поделиться накопленным опытом.

Замечен глюк: время внесения комментария отображается некорректно. Например, в предыдущем комментарии время оображается как 9:3 вместо 9:03.

Во-первых,предлагаемый в начале статье метод идентификации родительских элементов с помощью значения 0 или -1 — это полный бред. Единственно верный способ — использование внешнего ключа и значения NULL для вершины дерева.
Во-вторых, хотелось бы предложить ещё один вариант. Идея такая же, как в системе с поразрядным ключом, но вместо ключа использовать строковое поле, где через запятую перечислить значения. Например, строки элементов первого уровня — "1", "2", ... Для второго уровня — "1,3" — третий потомок первого элемента верхнего уровня. Разбор такой строки не сложнее, чем выделение десятичных знаков числа, но не имеет ограничений на размер дерева.
Крайний вариант — в корневой элемент дерева добавить blob-поле с xml-текстом, в котором будет полная структура дерева (т.е. иерархия значений первиынх ключей).

по-моему, просто детский лепет начинающего.
Поразрядный ключ на практике.... — даже в хиленьком проектике легче от него отказаться, чем возиться с разбором строк при каждом чихе...

Очень рекомендую почитать о множественной модели представления деревьев: http://www.codenet.ru/db/trees/ узнаете много интересного :-)

Согласен с Андреем. На мой взгляд, проверенный более чем трехлетней промышленной эксплуатацией множественной модели, лучшего варианта не найти (мне не удалось).

Здравствуйте, Аноним, Вы писали:

А>Единственно верный способ — использование внешнего ключа и значения NULL для вершины дерева.

Эк Вы загнули
Ведь это всего лишь один из вариантов, хоть и более распространённый.

http://www.akzhan.midi.ru/devcorner/articles/DDP-Representation-of-an-absent-information-rus.html

Здравствуйте, SMike, Вы писали:

SM>Согласен с Андреем. На мой взгляд, проверенный более чем трехлетней промышленной эксплуатацией множественной модели, лучшего варианта не найти (мне не удалось).

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

Здравствуйте, Михаил Голованов, Вы писали:

Привет, Михаил. Отличная статья, буквально пара замечаний:
1. При рассмотрении операций, было бы неплохо прокомментировать их быстродействие.
2. Вариант с правым поразрядным ключом я бы рассматривал только как пример неудачной реализации хорошей идеи. Дело в том, что при левом поразрядном ключе запрос с поиском всех потомков выражается в диапазонном запросе (типа id between 10000 and 19999), который напрямую отображается в seek по B-tree индексу. При правом поразрядном ключе так сделать не выйдет — придется выполнять сканирование индекса с дорогостоящей операцией выделения разряда.
3. Доп. мелочь: левый порязрядный ключ можно сделать не числом, а varchar. Тогда можно выделить под разряд не 10 значений, а 255, увеличив максимальное количество прямых потомков; типичное ограничение длины varchar — тоже 255 (иногда значительно больше), что увеличивает максимальную глубину иерархии (типичное ограничение на количество десятичных разрядов в числовых полях — 18). При этом возможность диапазонных поисков сохраняется (where id like '1%' приводит к очень эффективному index seek). Это примерно то же, о чем говорил Аноним, безжалостно (и напрасно) раскритикованный Андреем Щербина.
3.1. Одним из преимуществ левого поразрядного ключа является возможность одним запросом получить записи в порядке обхода дерева.
4. Автором "структуры с хранением границ ветви" является Joe Celko, на которого неплохо было бы сослаться (см. ссылку, приведенную Андреем). Кстати, учет вышеприведенного п.1. помог бы понять, почему этот крутой способ не применяется до сих пор сплошь и рядом. Сам Джо технично обходит обсуждение быстродействия. Именно потому, что его метод совершенно неприемлем для иерархий с частыми вставками.
5. Статья намеренно обходит методы денормализации структур для повышения быстродействия? Такие технологии, как транзитивное замыкание, ограниченное транзитивное замыкание и модифицированное транзитивное замыкание могут гарантировать квазилогарифммическое быстродействие всех операций, в то время, как рассмотренные структуры как правило оптимизируют одни выды запросов в ущерб другим.
6. Примечание редактора про вставку корневой записи в таблицу с внешним ключом не совсем корректно. Многие СУБД разрешают внешнему ключу принимать значение null (если это не запрещено явно модификатором типа колонки not null)

Здравствуйте, Михаил Голованов, Вы писали:

МГ>Статья:
МГ>Иерархические структуры данных в реляционных БД

Автор(ы): Михаил Голованов
Дата: 28.01.2002

ТАм пример на InterBase, а вот я, например, работаю с SQLServer. Почему-то SQLServer не дает в разделе Check использовать запросы, то есть CHECK(PID in (SELECT ID FROM Tree))

Как это обойти в SQL?

Здравствуйте, <Аноним>, Вы писали:

А>Как это обойти в SQL?
Использовать foreign key.

Привет, Sinclair!
Вы пишешь 24 марта 2005:

А>> Как это обойти в SQL?
S> Использовать foreign key.

Как этот топик вообще всплыл?
Статья бредовая, однозначно.

--
With best regards, Alex Cherednichenko.

Здравствуйте, Alex.Che, Вы писали:

AC>Как этот топик вообще всплыл?
AC>Статья бредовая, однозначно.

Почему? Стать-то как раз не бредовая. НУ вы предложите тогда механизмы хранения иерархических данных. Другое дело, что при разных подходах все равно в разных дргих вещах пробелмы будут. Либо при поиске либо при редактировании, либо при кодирвоании.

Здравствуйте, DeniZNET, Вы писали:

DZN>Здравствуйте, Alex.Che, Вы писали:

AC>>Как этот топик вообще всплыл?
AC>>Статья бредовая, однозначно.

DZN>Почему? Стать-то как раз не бредовая. НУ вы предложите тогда механизмы хранения иерархических данных. Другое дело, что при разных подходах все равно в разных дргих вещах пробелмы будут. Либо при поиске либо при редактировании, либо при кодирвоании.

Вот я как раз согласен с товарисчем Че и упоминал в другом топике по поводу статьи — она содержит много способов удаления гланд через жэ. А вот с тобой я не соглашусь, не поверишь, есть способы, при которых проблем нет никаких, и они (способы) здесь упоминались неоднократно. Просто надоело уже жевать эту жвачку. Причем, эти самые способы проверены личной практикой, а не так: "я тут подумал 10 мин и решил, наверное могут быть проблемы при поиске, редактировании или каком-то "кодировании" — какие проблемы могут образоваться при написании кода

Здравствуйте, _d_m_, Вы писали:

AC>>>Как этот топик вообще всплыл?
AC>>>Статья бредовая, однозначно.

DZN>>Почему? Стать-то как раз не бредовая. НУ вы предложите тогда механизмы хранения иерархических данных. Другое дело, что при разных подходах все равно в разных дргих вещах пробелмы будут. Либо при поиске либо при редактировании, либо при кодирвоании.

___>Вот я как раз согласен с товарисчем Че и упоминал в другом топике по поводу статьи — она содержит много способов удаления гланд через жэ. А вот с тобой я не соглашусь, не поверишь, есть способы, при которых проблем нет никаких, и они (способы) здесь упоминались неоднократно. Просто надоело уже жевать эту жвачку. Причем, эти самые способы проверены личной практикой, а не так: "я тут подумал 10 мин и решил, наверное могут быть проблемы при поиске, редактировании или каком-то "кодировании" — какие проблемы могут образоваться при написании кода
И где эти волшебные способы? Сссылки, описания, комментарии. Где?

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, _d_m_, Вы писали:

AC>>>>Как этот топик вообще всплыл?
AC>>>>Статья бредовая, однозначно.

DZN>>>Почему? Стать-то как раз не бредовая. НУ вы предложите тогда механизмы хранения иерархических данных. Другое дело, что при разных подходах все равно в разных дргих вещах пробелмы будут. Либо при поиске либо при редактировании, либо при кодирвоании.

___>>Вот я как раз согласен с товарисчем Че и упоминал в другом топике по поводу статьи — она содержит много способов удаления гланд через жэ. А вот с тобой я не соглашусь, не поверишь, есть способы, при которых проблем нет никаких, и они (способы) здесь упоминались неоднократно. Просто надоело уже жевать эту жвачку. Причем, эти самые способы проверены личной практикой, а не так: "я тут подумал 10 мин и решил, наверное могут быть проблемы при поиске, редактировании или каком-то "кодировании" — какие проблемы могут образоваться при написании кода
А>И где эти волшебные способы? Сссылки, описания, комментарии. Где?

Э... поиск рулит