Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Модель вкладених множин (англ. Nested Set Model) - техніка для представлення дерев в реляційних базах даних.
Мотивація
Техніка є відповіддю на проблему того, що стандартна реляційна алгебра та побудовані на ній SQL операції не можуть бути застосовані для всіх потрібних маніпуляцій з деревами (ієрархіями). Якщо дерево має довільну глибину, це не дозволяє використовувати 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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Model vkladenih mnozhin angl Nested Set Model tehnika dlya predstavlennya derev v relyacijnih bazah danih MotivaciyaTehnika ye vidpoviddyu na problemu togo sho standartna relyacijna algebra ta pobudovani na nij SQL operaciyi ne mozhut buti zastosovani dlya vsih potribnih manipulyacij z derevami iyerarhiyami Yaksho derevo maye dovilnu glibinu ce ne dozvolyaye vikoristovuvati SQL virazi dlya takih operacij yak porivnyannya miscya v iyerarhiyi dlya dvoh elementiv abo viznachennya nalezhnosti elementa do pevnogo pid dereva Isnuye dekilka pidhodiv dlya virishennya problemi i deyaki ye dostupnimi v sistemah keruvannya bazami danih pidtrimka iyerarhichnih tipiv danih rozshirennya SQL dlya manipulyacij z derevami SQL zapiti mozhut buti virazheni movoyu programuvannya yaka pidtrimuye iteraciyi ta dozvolyaye vikonuvati relyacijni operaciyi yak ot PL SQL T SQL abo majzhe bud yakoyu suchasnoyu movoyu programuvannya TehnikaTehnika modeli vkladenih mnozhin polyagaye v numeraciyi vuzliv vidpovidno do obhodu dereva Kozhen vuzol obroblyuyetsya dvichi kozhnomu vuzlu nadayetsya nomer vidpovidnij do poryadkovogo nomera zgidno z obhodom Kozhen vuzol nabuvaye dvoh nomeriv yaki zberigayutsya yak dva atributi Vibirka staye shvidkoyu nalezhnist do dereva abo pevnoyi gilki dereva mozhe buti viznachena cherez porivnyannya cih nomeriv Onovlennya dereva vimagaye povtornoyi numeraciyi i tomu ye povilnoyu PrikladU katalozi odyag mozhe buti kategorizovano vidpovidno do iyerarhiyi Obhid dereva z nadannyam nomeriv atributivVuzol Live PraveOdyag 1 22Chol 2 9Zhin 10 21Kostyumi 3 8Shtani 4 5Zhaketi 6 7Sukni 11 16Spidnici 17 18Bluzi 19 20Vechirni 12 13Sonyachni litni 14 15Atributi Kategoriya Odyag yaka maye najvishu poziciyu v iyerarhiyi vklyuchaye v sebe vsi pidkategoriyi Atributi mayut znachennya 1 ta 22 ostannye znachennya dorivnyuye chislu vuzliv pomnozhenomu na 2 Nastupnij riven iyerarhiyi vklyuchaye kategoriyi Chol ta Zhin obidva vklyuchayut piddereva Na kozhnomu rivni vuzlu priznacheno prave ta live znachennya vidpovidno do kilkosti vkladenih vuzliv Takim chinom shob virahuvati chi nalezhit napriklad kategoriya Bluzi do zhinochogo odyagu treba porivnyati vidpovidni atributi Live ta Prave Div takozhMnozhina teoriya mnozhin Obhid dereva Derevo struktura danih PosilannyaIyerarhichna model vkladenih mnozhin u relyacijnih bazah danih B Golub nedostupne posilannya z lipnya 2019 Troels links to Hierarchical data in RDBMSs angl 3 bereznya 2010 u Wayback Machine Managing hierarchical data in relational databases angl 1 chervnya 2013 u Wayback Machine PHP PEAR Implementation for Nested Sets angl 17 zhovtnya 2012 u Wayback Machine by Daniel Khan