Дедуктивного СИСТЕМИ БАЗ ДАНИХ

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

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

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

Примітка У наведеному нижче описі для зручності читання застосовуються по суті такі ж угоди про представлення значень, як і на рис 38 (див стор 119) і в інших розділах даної книги Таким чином, в якості зручного скорочення для QTY (300) використовується 3 0 0 і тд

S# ( SI ) NAME ( Smith)   INTEGER ( 5 )     CHAR ( London )

S # (S2) NAME (Jones) INTEGER (10) CHAR (Paris) S # (S3) NAME (Blake) INTEGER (15) CHAR (Rome) S # (S4) NAME (Clark) і тд CHAR (Athens) S # (S5) NAME (Adams) і тд

S# ( S6 ) NAME( White ) S# ( S7 ) NAME( Nut )

і тд NAME (Bolt)

NAME ( Scre)

і тд

7 Це також передбачено в стандарті SQL [423] Див упр 46 з глави 4

8 У цьому звязку слід зазначити, що Кодд ще в 1974 році заявив, що одне із завдань впровадження реля ційної моделі полягає саме в тому, щоб домогтися інтеграції засобів вибірки фактів і управ ня файлами для підготовки до введення в подальшому коштів логічного висновку, застосовних в програмних продуктах виробничого призначення [122], [2612]

Потім повинні бути введені основні аксіоми для кортежів в базових відносинах такий спосіб

S ( SI, Smith, 20, London ) S ( S2, Jones, 10, Paris )

і тд

P     (     P i,     Nut,  Re d,     12,  Lon don  )

і т д :

SP   (   SI,   PI,   300   )

і т д

Примітка Безумовно, на підставі цього прикладу не слід робити висновок про те, що екстенсіональная база даних створюється шляхом явного перерахування всіх основних аксіом, як показано в цьому прикладі скоріше, для цього повинні застосовуватися традиційні методи визначення даних і введення даних Іншими словами, дедуктивні СУБД, як правило, повинні застосовувати свої дедуктивні засоби до звичайних баз даних, які вже існують, і були сформовані звичайним чином Але слід зазначити, що тепер стає ще більш важливим вимога, щоб в екстенсіональной базі даних не порушувалося жодне з оголошених обмежень цілісності Це повязано з тим, що база даних, в якій порушується хоча б одне з таких обмежень, являє собою (з точки зору логіки) несумісне безліч аксіом, але широко відомо, що, виходячи з такої початкової позиції, можна довести, що істинним, взагалі кажучи, є абсолютно будь-яке висловлювання (іншими словами, як описано в анотації [916], з несумісного безлічі аксіом можуть бути виведені взаємно суперечливі твердження) Саме по тієї ж причини важливо також, щоб було сумісним заданий безліч обмежень цілісності

Тепер перейдемо до визначення інтенсіональні бази даних Нижче наведені обмеження атрибутів

S ( S, sn, St, SC ) ⇒ S# ( S ) AND

NAME ( sn ) AND

INTEGER { st ) AND CHAR ( sc )

P ( p, pn, p1, pw, pc ) ⇒ P# ( p ) AND NAME ( pn ) AND COLOR ( p1 ) AND WEIGHT ( pw )

AND CHAR ( pc )

Розглянемо обмеження потенційного ключа

S ( s, sn1, st1, sc1 ) AND S ( s, sn2, st2, sc2 )

⇒ snl = sn2 AND

stl = St2 AND

scl =

sc2 і тд

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

SP  (  s,  p,  q  )   ⇒ S   (  s,   sn,   st,   sc  ) AND P   (   p,   pn,   pi,   pw,   pc   )

Інша частина бази даних визначається аналогічно

Примітка Для більш повної демонстрації розглянутого підходу припустимо, що змінні, що зявляються праворуч, а не ліворуч від символу імплікації (у даному прикладі sn, st і тд), квантифікувати екзистенційно (Як було описано в розділі 244, всі інші змінні квантифікувати універсально) Тому, говорячи формально, буде потрібно застосування певних скулемовскіх функцій наприклад, змінна sn фактично повинна бути замінена (скажімо) термом SN (s), де SN – скулемовская функція

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

Тепер введемо ще кілька дедуктивних аксіом, як показано нижче

S    (   s,    sn,   st,    sc  )  AND   st   &gt  15

⇒ GOOD_SUPPLIER   (  s,   st,   SC  )

Рекомендуємо порівняти цю аксіому з визначенням уявлення GOOD_SUPPLIER (Сумлінний постачальник), яке наведене в розділі 101 глави 10)

S ( sx, sxn, sxt, sc ) AND S ( sy, syn, syt, sc )

⇒ SS_COLOCATED ( SX, sy

) S (s, sn, st, с) AND P (p, pn, p1, pw,

с)

⇒ SP_COLOCATED ( s, p )

Можуть бути також додатково введені інші дедуктивні аксіоми

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

PART_STRUCTURE (рх, ру) ⇒ Р (рх, xn, xl, xw, xc) AND

Р (ру, yn, yl, yw, ус)

Нижче наведені деякі значення даних

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

Тепер введемо наступну пару дедуктивних аксіом, що дозволяють описати, що мається на увазі під твердженням, що деталь рх містить деталь ру в якості компонента (на будь-якому рівні)

PART_STRUCTURE (рх, ру) ⇒ COMPONENT_OF (рх,

ру) PART_STRUCTURE (рх, pz) AND COMPONENT_OF (

pz, py )

⇒ COMPONENT_OF (рх, ру)

Іншими словами, деталь ру є компонентом деталі рх (на деякому рівні), якщо вона є або безпосереднім компонентом деталі рх, або безпосереднім компонентом деякої деталі pz, яка, в свою чергу, є компонентом (на деякому рівні) деталі рх Заслуговує на особливу увагу те, що тут другий аксіома рекурсивно – вона визначає предикат COMPONENT_OF в термінах самого цього предиката Відзначимо, що спочатку в реляційних системах не допускалось використання визначень таких уявлень (або запитів, або обмежень цілісності, або інших конструкцій), які були б задані як рекурсивні у зазначеній формі Тому розглянута тут здатність підтримувати рекурсию є одним з найбільш очевидних безпосередніх відмінностей між дедуктивним СУБД та їх класичними реляційними аналогами Хоча, як було зазначено в розділі 245 (і описано в главі 7, при обговоренні оператора TCLOSE), фактично не існує таких причин, по яких не можна було б розширити класичні реляційні системи для підтримки такої рекурсії, і в деяких системах зазначена задача вже була вирішена Додаткові відомості, що стосуються рекурсії, наведені в розділі 247

Мова Datalog

З наведеного вище опису має бути очевидно, що однією з частин дедуктивної СУБД, найбільшою мірою безпосередньо доступних користувачеві, можна вважати мова, яка дозволяє формулювати дедуктивні аксіоми (зазвичай звані правилами) Широко відомим прикладом такої мови є Datalog [245], що отримав таку назву за аналогією з мовою Prolog У даному підрозділі наведено короткий опис мови Datalog

Примітка Основна увага при розробці мови Datalog було приділено розширенню його описових можливостей, а не обчислювальних засобів (насправді, справа йшла так само і при реалізації первісної реляційної моделі [61])

Мета його створення полягала в тому, що ця мова в кінцевому підсумку повинен був володіти більш широкими виразними можливостями, ніж звичайні реляційні мови [245] У результаті цього мова Datalog (А фактично всі логічні системи баз даних в цілому) придбав чітко виражену спрямованість на підтримку запитів, а не оновлень Проте, можливо і бажано розширити цю мову, щоб він підтримував також поновлення (як описано нижче)

У своїй найпростішої формі мова Datalog забезпечує формулювання правил у вигляді простих хорновскіх виразів, без функцій У розділі 244 хорновское вираз визначено як правильно побудована формула, що має одну з наступних двох форм

Al AND A2 AND AND An

Al AND A2 AND .. AND An ⇒ В

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

У ⇐ A1 AND A2 AND AND An

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

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

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

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

який в наші дні передбачений у звичайних реляційних СУБД

Datalog може також використовуватися як мова запитів (знову-таки, в чому аналогічно мови Prolog) Наприклад, припустимо, що дано таке олределеніе предиката GOOD_SUPPLIER на мові Datalog

GOOD_SUPPLIER   (   s,    st,    sc   )   ⇐  S   (   s,   sn,    st,    sc   ) AND st  &gt  15

Нижче наведено кілька типових запитів до пpeдікaтy GOOD_SUPPLlER

1 Визначити всіх сумлінних постачальників

?   ⇐ GOOD_SUPPLIER  (  s,   st,   sc  )

2 Визначити всіх сумлінних постачальників з Парижа

?   ⇐  GOOD_SUPPLIER   (   s,    st,    Paris   )

3 Чи є постачальник si сумлінним

?   ⇐  GOOD_SUPPLIER  (  S1,   st,   sc  )

Іншими словами, запит на мові Datalog являє собою спеціальне правило з головою, що складається з знаку питання ?”, І тілом, що складається з одного терма, який позначає результат запиту голова ?” означає (відповідно до прийнятого угодою) Показати.

Слід зазначити, що мова Datalog, в тому вигляді, в якому він був визначений спочатку, не підтримує вельми багатьох засобів звичайних реляційних мов: прості обчислювальні оператори (+, * і тд), оператори агрегування (COUNT, SUM і тд), операцію різниці множин (оскільки не можна застосовувати операцію заперечення до виразів), групування і розгрупування і тд (Хоча ця мова підтримує рекурсію) Крім того, в мові Datalog не передбачена підтримка іменування атрибутів (призначення фактичного параметра предиката залежить від його порядкової позиції), а також не передбачена повна підтримка доменів (тобто визначаються користувачем типів, в тому сенсі, який вказаний в розділі 5) До того ж як було зазначено вище в даному розділі, в цій мові не передбачені будь-які операції оновлення, а також (як наслідок з даного факту) в ньому не підтримуються декларативні специфікації правил видалення і оновлення зовнішніх ключів (ON DELETE CASCADE і тд)

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

■&nbsp&nbsp&nbsp&nbsp Заперечує передумови Відповідний приклад наведено нижче

SS_COLOCATED ( sx, sy ) ⇐  S ( sx, sxn, sxt, sc ) AND

S ( sy, syn, syt, sc )

AND NOT ( sx = sy )

■&nbsp&nbsp&nbsp&nbsp Обчислювальні оператори (Як вбудовані, так і оппелеляемие користувачем)

Відповідний приклад наведено нижче

P_WT_IN_GRAMS (р, pn, pl, РG, рс) <=

Р (р, pn, pl, pw, рс) AND рд = pw * 454

У цьому прикладі передбачається, що знак вбудованої функції * можна записувати з використанням звичайної інфіксной системи позначень Більш суворим логічним поданням терма, наступного за оператором AND, була б рядок = (рд, * (pw, 454))

■&nbsp&nbsp&nbsp&nbsp Оператори групування і агрегування (Багато в чому відповідні требовани ям до звичайного реляційному оператору SUMMARIZE, який описаний в главі 7) Такі оператори необхідні для рішення (наприклад) завдань, іноді званих завданнями визначення необхідної кількості (gross requirements problem) Для вирішення цих завдань потрібно не тільки дізнатися, які деталі ру є ком компонентом деякої деталі рх на будь-якому рівні, але також визначити, яка кількість різних деталей ру (на всіх рівнях) буде потрібно для изготовле ня деталі рх (Безумовно, при цьому передбачається, що змінна отноше ня PART_STRUCTURE включає атрибут QTY)

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

“Вставляється в результат Тому можливе розширення мови може полягати в тому, щоб було дозволено використовувати заперечуються предикати в голові правила і розглядати заперечення як запит на видалення (відповідних кортежів)

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

Короткий огляд описаних вище доповнень з прикладами можна знайти в книзі Гардара (Gardarin) і Валдуріса (Valduriez) [246], де також розглядається цілий ряд методів реалізації мови Datalog

Джерело: Дейт К Дж, Введення в системи баз даних, 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>

*

*