Модель вкладених множин

Модель вкладених множин (англ. Nested Set Model) - техніка для представлення дерев в реляційних базах даних.

Мотивація

Техніка є відповіддю на проблему того, що стандартна реляційна алгебра та побудовані на ній SQL операції не можуть бути застосовані для всіх потрібних маніпуляцій з деревами (ієрархіями). Якщо дерево має довільну глибину, це не дозволяє використовувати SQL вирази для таких операцій, як порівняння місця в ієрархії для двох елементів або визначення належності елемента до певного під-дерева.

Існує декілька підходів для вирішення проблеми і деякі є доступними в системах керування базами даних:

  • підтримка ієрархічних типів даних;
  • розширення SQL для маніпуляцій з деревами;
  • SQL запити можуть бути виражені мовою програмування, яка підтримує ітерації та дозволяє виконувати реляційні операції, як от PL/SQL, T-SQL, або майже будь-якою сучасною мовою програмування;

Техніка

Техніка моделі вкладених множин полягає в нумерації вузлів відповідно до обходу дерева. Кожен вузол оброблюється двічі, кожному вузлу надається номер, відповідний до порядкового номера згідно з обходом. Кожен вузол набуває двох номерів, які зберігаються як два атрибути. Вибірка стає швидкою: належність до дерева (або певної гілки дерева) може бути визначена через порівняння цих номерів. Оновлення дерева вимагає повторної нумерації і тому є повільною.

Приклад

У каталозі одяг може бути категоризовано відповідно до ієрархії:

Обхід дерева з наданням номерів-атрибутів
Вузол Ліве Праве
Одяг 1 22
Чол. 2 9
Жін. 10 21
Костюми 3 8
Штани 4 5
Жакети 6 7
Сукні 11 16
Спідниці 17 18
Блузи 19 20
Вечірні 12 13
Сонячні літні 14 15
Атрибути

Категорія "Одяг", яка має найвищу позицію в ієрархії, включає в себе всі підкатегорії. Атрибути мають значення 1 та 22, останнє значення дорівнює числу вузлів помноженому на 2. Наступний рівень ієрархії включає категорії "Чол." та "Жін.", обидва включають піддерева. На кожному рівні вузлу призначено "праве" та "ліве" значення відповідно до кількості вкладених вузлів. Таким чином, щоб вирахувати чи належить, наприклад, категорія "Блузи" до жіночого одягу треба порівняти відповідні атрибути "Ліве" та "Праве".

Див. також

Посилання