ЗБЕРІГАННЯ ІЄРАРХІЧИХ СТРУКТУР В РЕЛЯЦІЙНИХ БАЗАХ ДАНИХ
DOI:
https://doi.org/10.28925/2663-4023.2022.16.8597Ключові слова:
база даних; ієрархічні структури даних; дерево; модель суміжних списків; модель таблиці зв’язківАнотація
Системи управління реляційними базами даних і сама мова SQL не мають жодних вбудованих механізмів для зберігання та управління ієрархічними структурами. Існує кілька різних способів представлення дерев в реляційних базах даних. В роботі розглянуто метод моделювання ієрархічних структур даних у вигляді списків суміжності (Adjacency List) та таблиці зв’язків (Closure Table). Для кожного методу, подано приклади написання запитів для розв’язання типових завдань, які зустрічаються під час роботи з деревовидними структурами: пошук всіх дочірніх вузлів, всіх нащадків та предків заданого вузла, переміщення вузла до іншого батьківського вузла, видалення вузлів з усіма його нащадками. Розглянуто можливість використання рекурсивних запитів при відображення всього дерева в моделі списків суміжності. У випадку, якщо глибина дерева не відома, або не відомо на якому рівні знаходиться заданий елемент, то запит не може бути побудований стандартними засобами оператора SELECT, тоді потрібно створювати рекурсивну процедуру, або писати рекурсивний запит. Для того, щоб уникнути рекурсії при виведенні всього дерева, всіх вузлів піддерева та пошук шляху від певного місця до кореня, моделювання ієрархічних структур даних виконують у вигляді таблиці зв’язків (Closure Table). При цьому ускладнюється процес додавання нового вузла, переміщення вузла до іншого батьківського вузла. В такому випадку для спрощення написання запитів пропонується створювати тригери, які будуть будувати, або перебудовувати зв’язки. Враховуючи те, що іноді виникає потреба збереження залежних, зокрема ієрархічних структур в реляційній базі даних, потрібно вміти орати модель збереження таких даних. На вибір методу, для розв’язання конкретної задачі, впливає швидкість виконання основних операцій з деревами. Дослідження різних варіантів організації деревоподібних структур SQL дозволить зрозуміти та обрати самий оптимальний спосіб побудови такої структури в реляційній базі даних для конкретної задачі. Усі, наведені в даній роботі SQL запити, створювалися та тестувалися для реляційних баз даних Oracle.
Завантаження
Посилання
Wirth, N. (1986). Algorithms and data structures. Prentice-Hall.
Narasimha Karumanchi. (2017). Data Structures And Algorithms Made Easy. CareerMonk.
Joe Celko's Trees and Hierarchies in SQL for Smarties. (2004). Elsevier. https://doi.org/10.1016/b978-1-55860-920-4.x5000-4
Bui D., & Poliakov S. (2010). Rekursyvni zapyty v SQL-podibnykh movakh: pryklady, zmistova i formalna semantyka. Problemy prohramuvannia. 2010. (2-3).
Bui D., & Poliakov S. (2010). Kompozytsiina semantyka rekursyvnykh vyraziv ta yikhnikh uzahalnen v SQL-podibnykh movakh. Naukovi zapysky NaUKMA. Kompiuterni nauky. 112. 21–26.
Reznychenko V. (2010) Rekursyvnyi SQL. Inzheneriia prohramnoho zabezpechennia, (4), 63–81.
Sarmiento, E. (2008, June 16). Recursive Queries using Common Table Expressions (CTE) in SQL Server. SQL Server Tips, Techniques and Articles. https://www.mssqltips.com/sqlservertip/1520/recursive-queries-using-common-table-expressions-cte-in-sql-server/
Trees in SQL. Joe Celko. (n.d.). Firebird, InterBase, HQbird: replication, monitoring, technical support. http://www.ibase.ru/files/articles/programming/dbmstrees/sqltrees.html.
Shramchenko B. L., & Akhmatov V. V. (2021). Obrobka iierarkhichnykh danykh u reliatsiinii bazi danykh. Informatsiini tekhnolohii v nautsi, vyrobnytstvi ta pidpryiemnytstvi (pp. 152–155). Osvita Ukrainy.
Holub V. (2010). Iierarkhichna model vkladenykh mnozhyn u reliatsiinykh bazakh danykh. VISNYK LVIV. UN-TU. Seriia prykl. matem. inform. (16), 106–113.
Hazel, D. (2008). Using rational numbers to key nested sets. Article DocSetID-311997. https://doi.org/10.48550/arXiv.0806.3115
