Бази даних. Вступний курс

20.3. рекурсивні запити
20.3.1. Визначення, що відносяться до рекурсії
20.3.2. Рекурсивні запити з розділом WITH
розділ SEARCH
розділ CYRCLE
20.3.3. рекурсивні уявлення
20.4. висновок

Наша взаимовыгодная связь https://banwar.org/

2008 р Сергій Кузнецов

назад зміст вперед

20.3. рекурсивні запити

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

20.3.1. Визначення, що відносяться до рекурсії

Обхід дерева в ширину. При цьому способі обходу безпосередні нащадки обходяться зліва направо, до того як проводиться перехід до нащадків наступного рівня спорідненості.

Мал
Мал. 20.5. приклад дерева

При обході в ширину дерева, показаного на Мал. 20.5 , Вузли будуть обходитися в наступному порядку: Корінь-Потомок1-Потомок2-Потомок3-П1.1-П1.2-П1.3-П2.1-П2.3-П3.1-П3.2-п3.3.

Обхід дерева в глибину. При цьому способі обходу на кожному кроці виробляється перехід до самого лівому поточному нащадку. При обході в глибину дерева з Мал. 20.5 порядок обходу вузлів буде наступним: Корінь-Потомок1-П1.1-П1.2-П1.3-Потомок2-П2.1-П2.2-П2.3-Потомок3-П3.1-П3.2-п3.3.

Цикл в орієнтованому графі. В теорії графів орієнтований граф називається циклічним в тому і тільки в тому випадку, коли хоча б один вузол графа одночасно є і предком, і нащадком (т. Е. Для цього вузла є і виходить, і що входить дуги). У SQL: 1999 вузлами графа рекурсії є рядки, що входять в результат рекурсивного запиту, а дуги відповідають способам обробки поточних рядків, які ведуть до додавання до результату нових рядків. на Мал. 20.6 показаний найпростіший приклад орієнтованого графа з циклом.

Мал
Мал. 20.6. Приклад графа з циклом

Пряма рекурсія. За визначенням, певний елемент використовує пряму рекурсію в тому і тільки в тому випадку, коли він звертається сам до себе без посередників. Приклад, наведений на Мал. 20.6 , Демонструє (в графовой формі) пряму рекурсію. на Мал. 20.7 показаний Графова приклад непрямої рекурсії.

Мал
Мал. 20.7. Графова приклад непрямої рекурсії

Лінійна рекурсія. При лінійно рекурсивном виклик елемент прямо рекурсивно звертається сам до себе не більше одного разу. У SQL: 1999 року в визначенні будь віртуальної таблиці з рекурсією допускається не більше одного посилання на саму себе (в розділі FROM і / або в підзапитах). на Мал. 20.8 показаний Графова приклад рекурсії, яка не є лінійної.

Монотонність. Монотонної прогресією називається послідовність неубутних або незростаюча значень. Наприклад, послідовність натуральних чисел {1, 2, ..., n, ...} є монотонною. У SQL: 1999 властивість монотонності підтримується в тому сенсі, що число рядків результату рекурсивного запиту не зменшується на кожному кроці рекурсії.

Взаємна рекурсія. Елементи A і B пов'язані ставленням взаємної рекурсії, якщо A прямо або побічно викликає B, і B прямо або побічно викликає A. На Мал. 20.9 показаний Графова приклад взаємної рекурсії (елемент A викликає елемент B через елемент C, а елемент B викликає елемент A через елемент D).

Мал
Мал. 20.8. Графова приклад нелінійної рекурсії

Мал
Мал. 20.9. Графова приклад взаємної рекурсії

Заперечення. В контексті SQL запереченням називається будь-яка дія, що приводить до зменшення числа рядків в результаті запиту. Властивостями заперечення мають операції над (мульти) множинами EXCEPT і INTERSECT, специфікація DISTINCT, умова NOT EXISTS і т.д. У стандарті SQL не забороняє використання заперечення в рекурсивних запитах. Можливою проблеми порушення монотонності вдається уникнути за рахунок того, що заперечення дозволяється застосовувати тільки до тих таблиць, які є повністю відомими (або обчисленими) до моменту застосування заперечення. У процесі обчислення таблиці застосування до неї заперечення не допускається.

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

Стратифікація. У SQL рекурсивний запит зазвичай складається з «рекурсивної» і «нерекурсивною» частин. В процесі стратифікації ( «розшарування») запиту виконання цих двох частин поділяється. У більш складних рекурсивних запитах може мати декілька рекурсивних частин і більше однієї нерекурсивною частини. В цьому випадку в процесі стратифікації буде виявлено більше число шарів.

Семантика фіксованою точки. В контексті SQL: 1999 семантика фіксованою точки означає, що рішення про завершення рекурсивного запиту приймається тоді, коли стає неможливо додати до результату будь-які додаткові рядки.

20.3.2. Рекурсивні запити з розділом WITH

У попередніх лекціях ми вже говорили про різновиди специфікації посилання на таблицю з використанням розділу WITH. Однак ми навмисне відклали обговорення рекурсивних можливостей. Повний синтаксис розділу WITH виглядає наступним чином:

with_clause :: = WITH [RECURSIVE] with_element_comma_list with_element :: = query_name [(column_name_list)] AS (query_expression) [search_or_cycle_clause] search_or_cycle_clause :: = search_clause | cycle_clause | search_clause cycle_clause search_clause :: = SEARCH recursive_search_order SET sequence_column_name recursive_search_order :: = DEPTH FIRST BY order_item_commalist | BREADTH FIRST BY order_item_commalist cycle_clause :: = CYCLE cycle_column_name_comma_list SET cycle_mark_column_name TO value_expression DEFAULT value_expression USING path_column_name

Для ілюстрації можливостей рекурсивних запитів з розділом WITH і пояснення сенсу конструкцій SEARCH і CYCLE скористаємося класичним прикладом «розборки деталей» (в даному випадку ми будемо розбирати автомобіль). Припустимо, що дані про конструктивні елементи автомобіля зберігаються в таблиці CAR, визначеної в такий спосіб:

CREATE TABLE CAR (CONTAINING_PART VARCHAR (10), CONTAINED_PART VARCHAR (10), NUMBER_OF_PARTS INTEGER, PART_COST DECIMAL (6,2));

У автомобіля є один конструктивний елемент верхнього рівня - повністю зібраний автомобіль. Цей елемент не є складовою частиною будь-якого іншого елемента, і для його рядки значенням стовпця CONTAINING_PART є текстовий рядок довжини 0. В будь-який інший рядку таблиці CAR, що відповідає деякому неатомарному конструктивного елементу e, стовпець CONTAINING_PART містить ідентифікаційний номер елемента e1, в який входить елемент e, стовпець NUMBER_OF_PARTS - число примірників елемента e, що входять в e1, а стовпець CONTAINED_PART - ідентифікаційний номер самого елемента e. У будь-якому рядку таблиці CAR, що відповідає деякому атомарному конструктивного елементу, значенням стовпця CONTAINED_PART є рядок довжини 0, а в стовпці PART_COST зберігається ціна атомарного конструктивного елементу (для неатомарних елементів значення цього стовпця дорівнює нулю).

Припустимо, що нам потрібно розібрати автомобіль, починаючи з елемента самого верхнього рівня, і для кожного конструктивного елементу отримати його номер, загальна кількість використовуваних екземплярів цього елемента, а також, якщо елемент є атомарним, загальну вартість використовуваних екземплярів. Ось можливе формулювання запиту (приклад 20.3):

WITH RECURSIVE PARTS (PART_NUMBER, NUMBER_OF_PARTS, COST) AS (SELECT CONTAINED_PART, 1, 0.00 (a) FROM CAR WHERE CONTAINING_PART = '' UNION ALL SELECT CAR.CONTAINED_PART, CAR.NUMBER_OF_PARTS, CAR.NUMBER_OF_PARTS * CAR.PART_COST FROM CAR, PARTS WHERE PARTS.PART_NUMBER = CAR.CONTAINING_PART) SELECT PART_NUMBER, SUM (NUMBER_OF PARTS), SUM (COST) (b) FROM PARTS GROUP BY PART_NUMBER;

Цей запит буде виконуватися наступним чином. При обчисленні розділу FROM основного запиту (b) почнеться виконання рекурсивного вираження запитів (a), визначеного в розділі WITH. На першому кроці рекурсії буде виконана частина цього виразу, що передує операції UNION ALL і утворює початковий джерело рекурсії. В результаті буде вироблено початковий стан віртуальної таблиці PARTS, в якому, в нашому випадку, з'явиться єдиний рядок, відповідна автомобілю цілком. На наступному кроці до таблиці PARTS будуть додані рядки, відповідні конструктивних елементів другого рівня (для автомобіля це, мабуть, двигун, колеса, шасі і т.д.). Цей процес буде продовжуватися до тих пір, поки ми не дійдемо до атомарних конструктивних елементів і не досягнемо, тим самим, фіксованої точки. Оскільки в рекурсивном запиті міститься операція UNION ALL, в результуючій таблиці можуть з'являтися рядки-дублікати. Наявність рядка-дубліката виду <part_no, number, cost> означає, що елемент з номером part_no входить в одному і тому ж числі примірників в кілька конструктивних елементів більш високого рівня.

розділ SEARCH

У наведеному вище прикладі не визначався порядок, в якому рядки додаються до часткового результату рекурсивного запиту. Однак іноді потрібно, щоб ієрархія обходилася в глибину або в ширину. Відповідна можливість забезпечується конструкцією SEARCH. При вказівці вимоги обходу в глибину гарантується, що кожен елемент-предок з'явиться в результаті раніше своїх нащадків і своїх братів справа. Якщо вказується вимога обходу ієрархії в ширину, в результаті все брати одного рівня з'являються раніше, ніж будь-якої їх нащадок. Нижче показаний варіант запиту, в якому міститься розділ SEARCH з вимогою обходу ієрархії елементів автомобіля в ширину (приклад 20.4).

WITH RECURSIVE PARTS (ASSEMBLY, PART_NUMBER, NUMBER_OF_PARTS, COST) AS (SELECT CONTAINING_PART, CONTAINED_PART, 1, 0.00 FROM CAR WHERE CONTAINING_PART = '' UNION ALL SELECT CAR.CONTAINING_PART, CAR.CONTAINED_PART, CAR.NUMBER_OF_PARTS, CAR.NUMBER_OF_PARTS * CAR. PART_COST FROM CAR, PARTS WHERE PARTS.PART_NUMBER = CAR.CONTAINING_PART) SEARCH BREADTH FIRST BY CONTAINING_PART, CONTAINED_PART SET ORDER_COLUMN SELECT PART_NUMBER, NUMBER_OF PARTS, COST FROM PARTS ORDER BY ORDER_COLUMN;

У списку стовпців сортування розділу SEARCH повинні вказуватися імена стовпців віртуальної таблиці, визначеної в розділі WITH. Оскільки в даному випадку ми хочемо, щоб в результаті спочатку з'являлися все конструктивні елементи одного рівня (CONTAINING_PART), а потім все їх піделементи (CONTAINED_PART), в список вибірки рекурсивного запиту PARTS доданий стовпець CONTAINING_PART, який не використовується ніде, крім розділу SEARCH. У розділі SET до результуючої таблиці рекурсивного запиту доданий стовпець, який ми назвали ORDER_COLUMN. Назва відповідає природі стовпчика, тому що при виконанні рекурсивного запиту в цей стовпець автоматично заносяться значення, що характеризують порядок генеруються рядків відповідно до обраного способу обходу ієрархії. Щоб рядки результату основного запиту з'являлися в належному порядку, в цьому запиті потрібно наявність розділу ORDER BY із зазначенням стовпчика, визначеного в розділі SET.

розділ CYRCLE

Нарешті, обговоримо, для чого потрібен розділ CYRCLE. Справа в тому, що іноді самі дані, що зберігаються в таблицях бази даних, можуть мати циклічну природу. Уявімо собі, наприклад, компанію, в якій існує рада директорів, що є вищим органом управління компанією. Звичайним випадком є той, коли принаймні один з членів ради директорів є простим службовцям цієї ж компанії (наприклад, він може входити до ради директорів як представник профспілки). Назвемо даного члена ради директорів EMP_DIR. Як член ради директорів, EMP_DIR «управляє» діяльністю президента компанії. З іншого боку, як службовець компанії, EMP_DIR знаходиться в прямому чи непрямому підпорядкуванні у президента компанії. Такий стан може призвести до зациклення виконання рекурсивних запитів. Розділ CYRCLE забезпечує деяку можливість розпізнавати подібні ситуації. Якщо у користувача є повна впевненість у відсутності циклів в даних, до яких адресується рекурсивний запит, то використання розділу CYRCLE не потрібно.

Підхід до розпізнавання зациклених запитів, прийнятий в SQL, полягає в тому, що розпізнаються дані, які вже брали участь раніше в формуванні результату рекурсивного запиту. При наявності розділу CYRCLE при додаванні до результату рядків, які відповідають умові запиту, такі рядки позначаються зазначеним значенням, яке означає, що ці рядки вже увійшли в результат. При спробі додавання до результату кожної нової рядки перевіряється, чи не знаходиться вона вже в результаті, т. Е. Позначена вона цим зазначеним в розділі CYRCLE значенням. Якщо це дійсно так, то вважається, що має місце цикл, і подальше виконання рекурсивного запиту припиняється.

Обговоримо все це більш формально. Для зручності відтворимо ще раз синтаксис розділу CYRCLE.

cycle_clause :: = CYCLE cycle_column_name_comma_list SET cycle_mark_column_name TO value_expression_1 DEFAULT value_expression_2 USING path_column_name

У списку cycle_column_name_comma_list вказуються імена одного або декількох стовпців, які використовуються для ідентифікації нових рядків результату на основі рядків, вже входять в результат. Наприклад, в прикладах 16.3 і 16.4 стовпець CONTAINED_PART пов'язує конструктивний елемент автомобіля з вхідними в його склад піделементи (через значення його шпальт CONTAINING_PART). Розділ SET призводить до утворення нового стовпця результуючої таблиці. Для рядків, які потрапляють в результат перший раз, в стовпець cycle_mark_column_name заноситься значення виразу value_expression_2. У повторно заносяться рядках значення стовпця - value_expression_1. Типом даних цього стовпця є тип символьних рядків довжини один, так що в якості value_expression_1 і value_expression_2 розумно використовувати константи '0' і '1' або 'Y' і 'N'.

Розділ USING призводить до утворення ще одного додаткового стовпця результату з ім'ям path_column_name. Типом даних стовпця є ARRAY, причому кардинальність цього типу передбачається досить великий, щоб зберегти інформацію про всі рядках, які потрапили в результат. Елементи масиву мають «рядковий тип» (row type), що містить стільки стовпців, скільки їх зазначено в списку розділу CYRCLE. Кожен елемент масиву відповідає рядку результату, і в його шпальтах міститься копія значень відповідних стовпців цього рядка. Ось приклад запиту, що містить розділ CYRCLE (приклад 20.5):

WITH RECURSIVE PARTS (PART_NUMBER, NUMBER_OF_PARTS, COST) AS (SELECT CONTAINED_PART, 1, 0.00 FROM CAR WHERE CONTAINING_PART = '' UNION ALL SELECT CAR.CONTAINED_PART, CAR.NUMBER_OF_PARTS, CAR.NUMBER_OF_PARTS * CAR.PART_COST FROM CAR, PARTS WHERE PARTS. PART_NUMBER = CAR.CONTAINING_PART) CYRCLE CONTAINED_PART SET CYCLEMARK TO 'Y' DEFAULT 'N' USING CYRCLEPATH SELECT PART_NUMBER, SUM (NUMBER_OF PARTS), SUM (COST) FROM PARTS ORDER BY PART_NUMBER;

Імена стовпців CYCLEMARK і CYRCLEPATH обрані довільним чином - потрібно тільки, щоб імена цих стовпців відрізнялися від імен стовпців рекурсивного запиту. При виконанні запиту рядки, що задовольняють його умові, накопичуються в результуючій таблиці. Але, крім того, ці рядки «кешуються» в стовпці CYRCLEPATH. При спробі додавання до результату нового рядка на основі поточного вмісту стовпця CYRCLEPATH перевіряється, чи не міститься вона вже в результаті. Якщо не міститься, то дані про цю рядку додаються до колонку CYRCLEPATH (до масиву додається новий елемент), в стовпець CYCLEMARK цього рядка заноситься значення 'N', і рядок додається до результату. Інакше в стовпець CYCLEMARK відповідного рядка результату заноситься значення 'Y', що означає, що від цього рядка починається цикл.

20.3.3. рекурсивні уявлення

Рекурсивним називається вистава, у визначальному вираженні запиту якого використовується ім'я цього ж уявлення. В уявленнях може використовуватися і пряма, і взаємна рекурсія. Синтаксис оператора визначення рекурсивного запиту виглядає наступним чином:

CREATE RECURSIVE VIEW table_name [column_name_comma_list] AS query_expression

Хоча для того, щоб вистава була рекурсивним, потрібно рекурсивность визначає вираження запиту (тобто в ньому має бути присутня специфікація RECURSIVE); наявність надлишкового ключового RECURSIVE у визначенні рекурсивного подання є обов'язковим. Як кажуть автори стандарту, це зроблено для того, щоб уникнути випадкового появи непередбачених рекурсивних уявлень. Нарешті, зверніть увагу на те, що ще не обговорювався нами необов'язковий розділ WITH CHECK OPTION не може бути присутнім у визначенні рекурсивного подання (з тієї причини, що розробники стандарту не змогли знайти розумної інтерпретації для комбінації RECURSIVE і WITH CHECK OPTION).

На закінчення цього розділу можу сказати, що особисто мені механізм рекурсії, пропонований в стандарті SQL, представляється громіздким і обмеженим. Крім того, наскільки мені відомо, компанії, які постачають SQL-орієнтовані СУБД, не поспішають впроваджувати в свої продукти кошти рекурсії відповідно до стандарту SQL: 1 999 (або, принаймні, не дуже їх афішують).

20.4. висновок

Якщо повернутися до синтаксичним визначень підрозділу 17.2.1. «Загальні синтаксичні правила побудови скалярних виразів» лекції 17, то можна переконатися, що в останніх чотирьох лекціях ми розглянули всі варіанти організації оператора SELECT мови SQL (за винятком конструкцій collection_derived_table і ONLY (table_or_query_name), що відносяться до об'єктним розширень мови SQL).

Для загального розуміння мови на модельному рівні більш важливими є попередні три лекції. Дана лекція включена в курс, скоріше, з метою загального ознайомлення читачів з новими можливостями оператора вибірки, ніж з метою їх детального опису. З великою ймовірністю кошти формулювання аналітичних і рекурсивних запитів мови SQL будуть переглядатися при підготовці наступних варіантів стандарту мови.