Модель вкладених множин
Модель вкладених множин (англ. 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. Наступний рівень ієрархії включає категорії "Чол." та "Жін.", обидва включають піддерева. На кожному рівні вузлу призначено "праве" та "ліве" значення відповідно до кількості вкладених вузлів. Таким чином, щоб вирахувати чи належить, наприклад, категорія "Блузи" до жіночого одягу треба порівняти відповідні атрибути "Ліве" та "Праве".
Див. також[ред. | ред. код]
Посилання[ред. | ред. код]
- Ієрархічна модель вкладених множин у реляційних базах даних - Б. Голуб[недоступне посилання з липня 2019]
- Troels' links to Hierarchical data in RDBMSs (англ.) [Архівовано 3 березня 2010 у Wayback Machine.]
- Managing hierarchical data in relational databases (англ.) [Архівовано 1 червня 2013 у Wayback Machine.]
- PHP PEAR Implementation for Nested Sets (англ.) [Архівовано 17 жовтня 2012 у Wayback Machine.] - by Daniel Khan
- Interpreting Nested Sets in PHP (англ.)
- Understanding Nested Sets (англ.)