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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Модель вкладених множин (англ. 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
Skirts 17 18
Блузи 19 20
Вечірні 12 13
Сонячні літні 14 15

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]