Рекурсивних ОБРОБКА ЗАПИТІВ

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

Як приклад ще раз розглянемо наведене в розділі 246 рекурсивне визначення предиката COMPONENT_OF в термінах відносини PART_STRUCTURE (але для стислості тут замість PART_STRUCTURE застосовується імя PS, а замість COMPONENT_OF – імя СОМР) Відповідне визначення на мові Datalog виглядає наступним чином

СОМР (рх, ру) ⇐ PS (рх, ру)

СОМР (рх, ру) ⇐ PS (рх, pz) AND СОМР (pz, ру)

Нижче наведено типовий рекурсивний запит до цієї бази даних (Показати компоненти деталі Р1)

? ⇐ СОМР (Р1, ру)

Ще раз коротко розглянемо зазначену ухвалу У цьому визначенні друге правило (тобто рекурсивне правило) називається лінійно рекурсивним, оскільки предикат, що знаходиться в голові правила, зявляється в тілі правила тільки один раз Нижче для порівняння наведено таке визначення предиката СОМР, в якому другий (рекурсивне) правило не є лінійно рекурсивним у вказаному вище сенсі

СОМР (рх, ру) ⇐ PS (рх, ру)

СОМР (рх, ру) ⇐ СОМР (рх, pz) AND СОМР {pz, ру)

Але в цілому в літературі найчастіше висловлюється думка про те, що лінійна рекурсія являє собою найбільш цікавий випадок. Під цим мається на увазі, що основна частина рекурсивних алгоритмів, застосовуваних на практиці, за своїм характером є лінійними Крім того, відомі ефективні методи, призначені для використання саме у випадку лінійної рекурсії [2411] Тому до кінця цього розділу обмежимося вивченням лінійної рекурсії

Примітка Для повноти викладу слід зазначити, що необхідно узагальнити визначення рекурсивного правила (І лінійної рекурсії), щоб мати можливість розглядати більш складні випадки на зразок таких .

Р (х, у) ⇐ Q (х, z) AND R (z, у)

Q (х, у) ⇐ Р (х, z) AND S (z, у)

Але для скорочення обсягу викладу тут такі уточнення ігноруються Більш докладні відомості на цю тему наведені в [2411]

Як і у випадку обробки класичних (тобто нерекурсивних) запитів, загальна проблема реалізації якогось конкретного рекурсивного запиту може бути розділена на дві підпроблеми: по-перше, перетворення первісного запиту в деяку еквівалентну, але більш ефективну форму, а потім, по-друге, фактичне виконання програмної конструкції, отриманої в результаті цього перетворення У літературі можна зустріти опис всіляких підходів до вирішення обох зазначених проблем А в цьому розділі коротко розглядаються деякі з найбільш простих методів на прикладі їх застосування для виконання запиту: Показати компоненти деталі Р1 стосовно до наведеним нижче даними

Уніфікація і резолюція

Один з можливих підходів полягає у використанні стандартних методів уніфікації і резолюції мови Prolog, як описано в розділі 244 У даному прикладі цей підхід здійснюється наступним чином Першими передумовами є дедуктивні аксіоми, які виглядають, як показано нижче (у конюнктівной нормальній формі)

1 NOT PS (рх, ру) OR COMP (рх, ру)

2 NOT PS (рх, pz) OR NOT COMP (pz, py) OR COMP (px, py)

З використанням необхідного висновку формується ще одна передумова, показана нижче

3&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp NOT  COMP   (   P1,   py   )   OR  RESULT   (   py   )

Основні аксіоми утворюють залишилися передумови Наприклад, розглянемо наведену нижче основну аксіому

4 PS (Р1, Р2)

Після підстановки Р1 замість рх і Р2 замість ру в рядку 1 можна застосувати правило резолюції до рядків 1 і 4, отримавши наступний результат

5 СОМР (PI, P2)

Тепер після підстановки Р2 замість ру в рядку 3 та застосування правила резолюції до рядків 3 і 5 буде отриманий наступний результат

6 RESULT (Р2)

Отже, деталь Р2 є компонентом деталі Р1 Точно такий же хід докази показує, що деталь РЗ також є компонентом деталі Р1 Таким чином, отримано дві додаткові аксіоми (або, швидше, теореми), СОМР (Р1, Р2) і СОМР (Р1, РЗ) тепер можна рекурсивно застосувати описаний вище процес для визначення всього складу компонентів Виконання цих дій залишаємо читачеві як вправи

Але на практиці використання процедур уніфікації та резолюції може призвести до дуже значного зниження продуктивності Тому зазвичай потрібно знайти деяку більш ефективну стратегію В інших підрозділах даного розділу розглядаються деякі можливі підходи до вирішення цієї проблеми

Примітивний алгоритм обчислення

Мабуть, найбільш простий підхід з усіх можливих полягає у використанні примітивного алгоритму обчислення (Naive evaluation) [2420] Як показує його назва, цей алгоритм є досить спрощеним найлегше його можна описати (стосовно запиту, він розглядався як приклад) за допомогою наступного псевдокоду

СОМР: = PS

do until СОМР <Не досягне "усталеного стану">

СОМР: = СОМР UNION (СОМР PS) ‘

end DISPLAY: = СОМР WHERE РХ =

Р # (Р1)

Кожна із змінних відносини СОМР І DISPLAY (як і змінна відносини PS) мають два атрибути, РХ і PY Неформально висловлюючись, цей алгоритм діє шляхом повторного формування проміжного результату, що складається з результатів зєднання змінної відносини PS з попереднім проміжним результатом, до тих пір, поки цей проміжний результат не досягне усталеного стану f ixpoint (тобто поки він не перестане рости)

Примітка Вираз СОМР a PS є скороченням від вираження, яке можна описати таким чином: отримати зєднання СОМР і PS no COMPPY і PSPX, а потім проекцію результату по СОМРРХ і PSPY; для скорочення обсягу викладу тут ігноруються операції перейменування атрибутів, які потрібні у використовуваному діалекті алгебри для забезпечення можливості застосування такої операції (див розділ 7)

Тепер поетапно виконаємо цей алгоритм з використанням даних, що розглядаються в якості прикладу Після першої ітерації циклу вираз СОМРPS приймає значення, показане нижче (ліворуч), а змінна відносини СОМР приймає результуюче значення, показане справа (кортежі, додані в цій ітерації, позначені зірочками)

Слід звернути особливу увагу на те, що при обчисленні виразу СОМР

Після другої ітерації зазначені результати виглядають наступним чином

PS на другому етапі повторюється весь процес обчислення виразу СОМР »PS на першому етапі, а також додатково обчислюються деякі додаткові кортежі У розглянутому випадку фактично формуються ще два кортежу, (Р 1, Р 6) І (Р 2, Р 6) У цьому полягає одна з причин, по якій даний примітивний алгоритм обчислення є не дуже ефективним

Після третьої ітерації (при якій ще раз повторно виконуються ті ж обчислення) виявляється, що значення виразу СОМРPS залишається таким же, як і після попередньої ітерації Таким чином, змінна відносини СОМР досягла усталеного стану і відбувається вихід з циклу Потім обчислюється наступний остаточний результат як скорочення змінної отношеніясОМР

Тепер стає очевидною інша важлива причина низької ефективності: фактично при використанні даного алгоритму обчислюється склад компонентів кожної деталі (насправді, в ньому обчислюється всі Транзитивне замикання відносини PS), а потім знову відкидаються всі результати, крім фактично необхідних кортежів Іншими словами, ще раз зазначимо, що при використанні цього алгоритму виконується великий обсяг непотрібної роботи

На завершення цього підрозділу слід зазначити, що описаний тут метод, заснований на застосуванні примітивного алгоритму, може розглядатися як реалізація процедури прямого логічного висновку: він починає свою роботу з вихідною екстенсіональной бази даних (тобто виходячи з фактичних значень даних), після цього повторно застосовуються передумови даного визначення (тобто тіло правила) до тих пір, поки не буде отриманий необхідний результат Насправді, цей алгоритм обчислює фактично мінімальну модель для програми Datalog (див розділи 245 і 246)

Полупрімітівний алгоритм обчислення

Перше очевидне удосконалення примітивного алгоритму обчислення складу компонентів полягає в запобіганні повторного виконання на наступному етапі тих обчислень, які були виконані на попередньому етапі, тому він називається полупрімітівним алгоритмом обчислення (seminaive evaluation) [2423] Іншими словами, тепер на кожному етапі обчислюються тільки нові кортежі, які повинні бути додані в даній конкретній ітерації Основну ідею цього алгоритму знову розглянемо на прикладі запиту Визначити компоненти деталі Р1. Відповідний псевдокод показаний нижче

NEW := PS

СОМР: = NEW

do until NEW <Не порожня>

NEW := ( NEW PS ) MINUS COMP COMP := COMP UNION NEW end

DISPLAY := COMP WHERE PX = P# (PI)

Знову розглянемо поетапно процес виконання цього алгоритму При первісному входження в цикл обидві змінні відносини, NEW і СОМР, ідентичні PS, як показано нижче

Мінлива відносини СОМР є такою ж, якою вона була на аналогічному

Наприкінці першої ітерації вони виглядають таким чином

етапі реалізації примітивного алгоритму, a NEW містить тільки нові кортежі, які були додані до СОМР в цій ітерації тут заслуговує на увагу те, що NEW не включає кортеж (Р 1, РЗ) (на відміну від аналога цієї змінної відносини, застосовуваного в примітивному алгоритмі) Наприкінці наступного ітерації будуть отримані наведені нижче результати

Після наступної ітерації NEW залишається порожньою, тому здійснюється вихід з циклу

Алгоритм статичної фільтрації

Алгоритм статичної фільтрації являє собою удосконалення основної ідеї класичної теорії оптимізації, згідно з якою операції скорочення повинні застосовуватися якомога раніше Він може розглядатися як практичне застосування підходу, заснованого на зворотному логічному висновку, оскільки в цьому алгоритмі, по суті, використовується інформація із запиту (висновок) для модифікації правил (передумов) Цей алгоритм називають також алгоритмом скорочення безлічі релевантних (що відносяться до справи) фактів, оскільки в ньому (ще раз підкреслимо) використовується інформація із запиту для видалення з самого початку непотрібних кортежів з екстенсіональной бази даних [2424] Відповідні дії можна описати на розглянутому прикладі за допомогою наступного псевдокоду

NEW: = PS WHERE PX = Р # (P1)

СОМР: = NEW

do until NEW «не порожня>

NEW := ( NEW PS ) MINUS COMP COMP := COMP UNION NEW

; end DISPLAY := COMP

Ще раз виконаємо цей алгоритм поетапно При первісному входження в цикл обидві змінні відносини, NEW і СОМР, виглядають наступним чином

Наприкінці першої ітерації вони представлені таким чином

Наприкінці наступного ітерації буде отриманий наступний результат

Після наступної ітерації змінна відносини NEW залишається порожньою, тому відбувається вихід з циклу

На цьому коротке вступне опис стратегій обробки рекурсивних запитів завершується Безумовно, в літературі було запропоновано багато інших підходів, причому більшість з них є набагато більш розвиненими в порівнянні з тими простими

алгоритмами, які були описані в даному розділі Але обсяг книги такого характеру, як ця, не дозволяє привести весь методичний матеріал, необхідний для повного розуміння цих підходів Додаткові відомості з цієї теми можна знайти, наприклад, в [2411] – [2425]

241 РЕЗЮМЕ

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

Тепер коротко повторимо основні теми наведеного в цій главі матеріалу Спочатку були представлені короткі навчальні розділи по обчисленню висловлювань і обчисленню предикатів, а також введені, крім усього іншого, описані нижче поняття

■&nbsp&nbsp&nbsp&nbsp Інтерпретація безлічі правильно побудованих формул являє собою зі четаніе, по-перше, предметної області, по-друге, перетворення, яке повязує окремі константи, застосовувані в правильно побудованих форму лах цієї множини з обєктами зазначеної предметної області, і, по-третє, безлічі певних смислових значень для предикатів і функцій, при міняних в цих правильно побудованих формулах

■&nbsp&nbsp&nbsp&nbsp Моделлю для безлічі правильно побудованих формул є інтерпретація, при якій все правильно побудовані формули цієї множини беруть істинні значення Кожне конкретне безліч правильно побудованих фор мул (взагалі кажучи) може мати будь-яку кількість моделей

■&nbsp&nbsp&nbsp&nbsp Доказ – Це процес демонстрації того, що деяка конкретна пра вільно побудована формула g (Висновок) є логічним наслідком з

■ деякого конкретного безлічі правильно побудованих формул fl, f2,

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

уніфікацією

Потім було описано доказово-теоретичне уявлення баз даних У такому поданні база даних розглядається як складається з комбінаціїекстенсіональной бази даних і інтенсіональні бази даних Екстенсіональная база даних містить основні аксіоми (Тобто, кажучи неформально, базові дані) інтенсиональная база даних містить обмеження цілісності та дедуктивні аксіоми (Тобто, знову неформально кажучи, подання) У такому випадку смислове значення бази даних складається з безлічі теорем, які можна дедуктивно вивести з аксіом процес виконання запиту стає (принаймні, концептуально) процесомдоведення теореми Дедуктивна СУБД – Це така СУБД, яка підтримує доказово-теоретичне уявлення Крім того, коротко описаний Datalog – Мову користувача для подібної СУБД

Одним з безпосередньо очевидних відмінностей між мовою Datalog і класичними реляційними мовами є те, що Datalog підтримує рекурсивні аксіоми і тому – рекурсивні запити, хоча немає жодних причин, по яких не можна було б розширити класичну реляционную алгебру та обчислення для виконання такої ж задачі9 (див опис оператора TCLOSE в розділі 7) У цьому розділі описані деякі прості методи виконання таких запитів

На закінчення необхідно відзначити, що ця глава почалася з згадки цілого ряду термінів, які часто зустрічаються в науковій літературі (і навіть певною сте пені в рекламних оголошеннях постачальників) До них відносяться такі терміни, як логи чна база даних СУБД, заснована на логічному висновку дедуктивна СУБД і тд За цим в кінці даного резюме наведено визначення деяких з цих термінів Але слід попередити читача, що з цих питань не завжди досягнута згода і тому в літературі цілком можна також знайти інші визначення А наведені нижче визначення автор цієї книги вважає найбільш прийнятними

■&nbsp&nbsp&nbsp&nbsp Рекурсивна обробка запитів З приводу цього терміна розбіжності зазвичай не виникають Рекурсивної обробкою запитів називається аналіз і, зокрема, оптимізація запитів, які за визначенням є рекурсивними (Див розділ 247)

■&nbsp&nbsp&nbsp&nbsp База знань Цей термін іноді використовується для позначення того поняття, ко торое в розділі 246 було визначено як інтенсиональная база даних Іншими словами, база знань складається з правил (обмежень цілісності і дедуктивних аксіоми), на відміну від власне бази даних, яка складає екстенсіо нальную базу даних Однак багато авторів використовують термін база знань для позначення комбінації екстенсіональной і інтенсіональні баз даних, якщо не рахувати того, що деякі фахівці стверджують (як, наприклад в [246]), що база знань часто містить складні обєкти, [а також] класичні від носіння (Опис складних обєктів приведено у частині VI цієї книги) Нарешті, в системах обробки природних мов цей термін має інше, більш спеціалізоване значення, тому, мабуть, краще взагалі уникати його використання

9 У цьому звязку цікаво відзначити, що реляційні СУБД так чи інакше повинні бути здатні ми (непомітно для користувача) виконувати рекурсивную обробку, оскільки каталог містить неко торую інформацію, структуровану рекурсивно (справа в тому, що визначення уявлень часто бувають виражені в термінах інших визначень подань)

■&nbsp&nbsp&nbsp&nbsp Знання Ще один термін, практично не викликає розбіжностей Знаннями називають те, що міститься в базі знань .. На жаль, при використанні цього формулювання проблема визначення поняття знання зводиться до описаної вище невирішеної проблеми остаточного визначення понятіябазя знань

■&nbsp&nbsp&nbsp&nbsp&nbsp Система управління базою знань (СУБЗ) Програмне забезпечення, яке управляє базою знань Цей термін зазвичай використовується як синонім для дедуктивної СУБД (див наступний абзац)

■&nbsp&nbsp&nbsp&nbsp Дедуктивна СУБДСУБД, яка підтримує доказово-теоретичне уявлення баз даних і, зокрема, має здатність дедуктивно ви водити додаткову інформацію з екстенсіональной бази даних, примі няя правила виведення (тобто дедуктивні правила), які зберігаються в інтенсив нальної базі даних Фактично обовязковою вимогою до дедуктивної СУБД є підтримка рекурсивних правил і тому здійснення обра лення рекурсивних запитів

■&nbsp&nbsp&nbsp&nbsp Дедуктивна база даних (Чи не рекомендовані термін) База даних, керована дедуктивної СУБД

■&nbsp&nbsp&nbsp&nbsp Експертна СУБД Синонім дедуктивної СУБД

■&nbsp&nbsp&nbsp&nbsp Експертна база даних (Чи не рекомендовані термін) База даних, керована експертної СУБД

■&nbsp&nbsp&nbsp&nbsp СУБД, що підтримує логічний висновок Синонім для дедуктивної СУБД

■&nbsp&nbsp&nbsp&nbsp&nbsp Система, заснована на логіці Синонім для дедуктивної СУБД

■&nbsp&nbsp&nbsp&nbsp Логічна база даних (Чи не рекомендовані термін) Синонім длядедуктивної бази даних

■&nbsp&nbsp&nbsp&nbsp Логіка як модель даних Будь-яка модель даних складається (щонайменше) з обєктів, правил підтримки цілісності та операторів У дедуктивної СУБД всі ці компоненти (обєкти, правила підтримки цілісності та оператори) представлені в деякій однаковій формі (а саме, як аксіоми в такій мові, заснованому на логіці, як Datalog) в дійсності, як було описано в розділі 246, база даних в такій системі може розглядатися саме як логічна програма, що складається з аксіом цих трьох типів Тому цілком обгрунтованим є твердження, що абстрактної моделлю даних для такої системи служить сама логіка

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*