Отправляет email-рассылки с помощью сервиса Sendsay

Клуб профессиональных программистов

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Килограмм килобайтов" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Декабрь 2011   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
RXL

Статистика

1.297 подписчиков
-1 за неделю
←   Все выпуски   →

Клуб профессиональных программистов :: Выпуск #131


Клуб профессиональных программистов «Весельчак У»
Информационная рассылка сайта и форума.  Выпуск 131.  24 декабря 2011 г.

Здравствуйте, уважаемые читатели!



Сегодня предлагаем вам прочесть фрагмент статьи «SQLite. Деревья. Добавление материализованного пути к паре id—parent_id».



Приятного чтения! Прощаемся с Вами до следующего выпуска.


С уважением, команда Клуба.


SQLite. Деревья. Добавление материализованного пути к паре id—parent_id.

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

  • список смежности (adjacency list) — классическая пара id и parent_id;
  • вложенные множества (nested sets);
  • материализованный путь (materialized path — в различных вариантах).

Иногда применяют сразу две структуры. Это позволяет воспользоваться плюсами обеих структур, правда, заплатив и за минусы обеих, и за необходимость синхронно поддерживать целостность обеих структур. Я расскажу, как в SQLite дополнить список смежности материализованным путем, автоматизировать поддержание целостности обеих структур и организовать автоматическую генерацию материализованного пути.


Идея


Таблица предполагается такая:


Код: (sql)
CREATE TABLE tree

(

    id INTEGER NOT NULL PRIMARY KEY AUTOINCREMENT,

    parent_id INTEGER REFERENCES tree (id),

    path TEXT NOT NULL UNIQUE DEFAULT '',

    content TEXT NOT NULL DEFAULT ''

);

Внешний ключ поможет поддерживать целостность связки parent_id — id. В принципе, его наличие не принципиально, но в триггерах проверку наличия предка я не делал и внешний ключ здесь будет не лишним. Узел с parent_id равным NULL является корнем дерева. Причем, значений NULL может быть несколько, а значит в одной таблице можно хранить несколько деревьев. Материализованный путь в данной таблице нужен только для выборки поддерева по заданному узлу. Поддержанием целостности материализованного пути будут заниматься триггеры.

Вычислять материализованный путь будет следующее выражение:


Код: (sql)
CASE

    WHEN parent_id IS NULL THEN '/' || NEW.id || '/'

    ELSE (

        SELECT path || NEW.id || '/'

            FROM tree

            WHERE id = NEW.parent_id

    )

END

Логика простая: если parent_id равен NULL, то узел является корневым; в противном случае достаточно найти предка, взять его путь и дополнить нужной информацией. Данная реализация выдает материализованный путь следующего формата:


/id1/id2/id3/id4/


Здесь: id1 — корень, id2 и id3 — предки, id4 — сам узел.

Особенность данной реализации материализованного пути — не предусмотрена возможность хранить сортировку смежных узлов одного уровня. Зато есть возможности хранения нескольких деревьев и перемещения узлов между ними.

Для добавления и перемещения узлов используется пара полей — id и parent_id. Для удаления узлов, изменения их полезной нагрузки и выборки (одиночного узла или по списку) используется поле id. Для выборки поддерева используется поле path в выражении LIKE. Для перемещения узла и всех его потомков в другую ветку достаточно изменить только parent_id этого узла, все остальные необходимые изменения сделают триггеры.


Реализация.


...



Полностью прочитать статью можно на нашем сайте, в разделе «Базы данных».
В избранное