Численні предикатів

Тепер перейдемо до опису обчислення предикатів Основна відмінність між обчисленням висловлювань і обчисленням предикатів полягає в тому, що останнє дозволяє включати у формули переменние4 і квантори, завдяки чому ці формули стають набагато більш потужними і знаходять набагато більш широку область застосування Наприклад, наступні твердження не є допустимими формулами обчислення висловлювань, але вони допустимі в численні предикатів: Постачальник S1 поставляє деталь р і Деякий постачальник s поставляє деталь р. Тому обчислення предикатів надає основу для складання приблизно таких запитів: Які деталі постачає постачальник S1″, або Визначити постачальників, які постачають деяку деталь, або навіть Визначити постачальників, які не постачають взагалі ніяких деталей .

Предикати

Як було описано в розділі 3, предикат являє собою логічну функцію, тобто функцію, яка після постановки відповідних фактичних параметрів замість формальних параметрів повертає або TRUE, або FALSE Наприклад, функція > (Х, у) (Яка найчастіше записується як х> у) являє собою предикат з двома формальними параметрами, х і у вона повертає TRUE, якщо її фактичний

4 Точніше, імена змінних Розглянуті змінні є логічними змінними, а не змінними мови програмування Їх можна розглядати як змінні області значень в тому сенсі, який вказаний в розділі 8

параметр, відповідний х, більше фактичного параметра, відповідного у в іншому випадку ця функція повертає FALSE Предикат, який приймає п фактичних параметрів (тобто рівним чином, який визначений в термінах п формальних параметрів) називається n-місцевим або п-арним предикатом Висловлювання (тобто формула в тому сенсі, який визначено у розділі 243) може розглядатися як нульместний, або нуль-арний предикат – вона не має формальних параметрів і недвозначно приймає значення TRUE або FALSE

Приймемо зручне припущення, що предикати, відповідні операторам =, >, > і тд, є вбудованими (тобто що вони входять до складу описуваної нами формальної системи) і що вирази, в яких вони використовуються, дозволено записувати в загальноприйнятій формі Але, безумовно, користувачам має бути також надана можливість визначати свої власні предикати І дійсно, весь зміст розглянутого нами підходу полягає в наступному: справа в тому, що в термінах баз даних визначається користувачем предикат відповідає обумовленою користувачем змінної відносини (як уже було зазначено в попередніх розділах) Наприклад, змінна відносини постачальників S може розглядатися як предикат з чотирма формальними параметрами, S #, SNAME, STATUS І CITY Більш того, вираження S (S1, Smith, 20, London) і S (S 6, White, 45, Rome), сформульовані з використанням наочного скороченого позначення, являють собою екземпляри, варіанти конкретизації або виклики цього предиката, які (при використанні зазвичай прийнятого як приклад безлічі значень) приймають значення, відповідно, TRUE і FALSE Неформально такі предикати (поряд з усіма застосовними обмеженнями цілісності, які також є предикатами) можуть розглядатися як визначення того, що означає ця база даних, як було описано в попередніх частинах цієї книги (особливо в розділі 9)

Правильно побудовані формули

Наступний етап полягає в тому, що можна розширити визначення поняття формули Для того щоб уникнути плутанини з формулами, розглянутими у попередньому розділі (які фактично являють собою окремий випадок), перейдемо до використання терміна правильно побудована формула (Well-Formed Formula – WFF, вимовляється як вефф), або скорочено ППФ, який був визначений в розділі 8 Нижче наведено спрощений синтаксис правильно побудованих формул

&ltwff&gt

::&ltterm&gt

| NOT ( &ltwff&gt )

| ( &ltwff&gt ) AND ( &ltwff&gt )

j ( &ltwff&gt ) OR ( &ltwff&gt )

| ( &ltwff&gt ) ⇒  ( &ltwff&gt )

| EXISTS &ltvar name&gt ( &ltwff&gt )

I FORALL &ltvar name&gt (

&ltwff&gt )

&ltterm&gt

::= [ NOT ] &ltpred name&gt [ ( &ltargument commalist&gt ) ]

З цього визначення випливають наведені нижче висновки

1 В якості терма &ltterm&gt застосовується просто екземпляр предиката або, можли але, його заперечення (якщо предикат розглядається як логічна функція, то екземпляр предиката являє собою виклик цієї функції) Кожен фактіче ський параметр &ltargument&gt повинен являти собою константу, імя змін ної або виклик функції, де кожен фактичний параметр у виклику функції, в свою чергу, є константою, імям змінної або викликом функції Розділений комами список фактичних параметрів &ltargument   commalist&gt і (за бажання) відповідні круглі дужки в разі нуль-місцевого преди ката виключаються

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

2 Як описано в розділі 243, застосовуються звичайні правила пріоритету для логи чеських операторів (NOT, потім AND, потім OR, потім ⇒) для того, щоб можна б

ло скоротити кількість круглих дужок, необхідних для регламентації желае мого порядку обчислення

3 Передбачається, що читач знайомий з кванторами EXISTS і FORALL

Примітка Тут нас цікавить тільки числення предикатів першого порядку, а це по суті означає, по-перше, що немає предикативних змінних (Тобто змінних, допустимими значеннями яких є предикати), і тому, по-друге, самі предикати не можуть ставати обєктом застосування кванторів Див вправу 88 з глави 8

4 Закони де Моргана можуть бути узагальнені стосовно правильно побудований ним формулами, що містить квантори, наступним чином:

NOT ( FORALL X ( f ) ) ≡  EXISTS X ( NOT ( f ) )

NOT ( EXISTS X ( f ) ) ≡  FORALL X ( NOT ( f ) )

Ця тема також обговорювалася в розділі 8

5 Повторимо ще один фрагмент з глави 8: в будь-якої конкретної правильно постро енной формулою кожна посилання на змінну є або вільною, або свя занной Посилання є повязаної тоді і тільки тоді, коли вона, по-перше, знаходиться безпосередньо за ключовим словом EXISTS АБО FORALL (тобто обозна чає змінну, на яку поширюється дія квантора) або, подруге, знаходиться в області дії квантора і позначає відповідну квантифікувати змінну Посилання на змінну є вільної тоді і тільки тоді, коли вона не повязана

6&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp Закритої правильно побудованої формулою називається така формула, яка не містить посилань на вільні змінні (фактично вона є висловлюючи ням) Відкритої правильно побудованої формулою називається така формула, до торая не є замкнутою

Інтерпретації та моделі

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

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

■ По друге, визначимо зміст кожного предиката в термінах обєктів предметної області

■ По-третє, визначимо також зміст кожної функції в термінах обєктів пред предметної області

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

Як приклад припустимо, що предметна область являє собою безліч цілих чисел {0,1,2,3,4,5} припустимо, що такі константи, як 2, відповідають обєктів цієї області очевидним чином, а також приймемо допущення, що предикат х> у визначений як має звичайний сенс (При бажанні ми можемо також визначити такі функції, як +, – і тд) Тепер зявляється можливість привласнювати відповідні істиннісні значення правильно побудованим формулами, як показано нижче

2 &gt 1                                                                                   : TRUE

2> 3: FALSE EXISTS x (х> 2): TRUE FORALL X (x> 2): FALSE

Але слід зазначити, що можливі й інші інтерпретації Наприклад, можна визначити предметну область як безліч ступенів класифікації секретності таким чином

знищити перед прочитанням (рівень 5) знищити після прочитання (рівень 4) цілком таємно (рівень 3) таємно (рівень 2) для службового користування (рівень 1) нетаємно (рівень 0)

Тепер предикат > може означати більш секретний (тобто що має більш високу ступінь секретності), чим.

Після цього читач, мабуть, виявив, що наведені вище дві можливі інтерпретації є ізоморфними Це означає, що між ними можна встановити взаємно-однозначна відповідність і тому на більш глибокому рівні ці дві інтерпретації фактично являють собою одне і те ж Але слід чітко розуміти, що можуть існувати інтерпретації, які спочатку є різними

за своїм характером Наприклад, можна знову взяти в якості предметної області цілі числа від 0 до 5, але визначити предикат > як позначає рівність (Безумовно, це може стати причиною значній плутанини, але, принаймні, ми маємо повне право прийняти подібне рішення) У такому випадку перша правильно побудована формула зі списку (2> 1) буде мати значення FALSE,, а НЕ TRUE

Ще одна ідея, яку слід чітко сформулювати, полягає в тому, що дві інтерпретації можуть бути спочатку різними в зазначеному вище сенсі і, тим не менш, приводити до отримання однакових істиннісних значень для заданої множини правильно побудованих формул Таким був би випадок з двома різними визначеннями оператора > в розглянутому прикладі, якби була виключена правильно побудована формула 2> 1 .

До речі, слід зазначити, що все правильно побудовані формули, які розглядалися до цих пір в цьому підрозділі, були замкнутими ППФ Причина цього полягає в тому, що при наявності деякої інтерпретації завжди можливо привласнити замкнутої ППФ конкретне істиннісне значення, але істиннісне значення відкритої ППФ залежить від значень, присвоєних вільним змінним Наприклад, цілком очевидно, що наведена нижче відкрита ППФ приймає значення TRUE, якщо х більше 3, і FALSE в іншому випадку (при будь трактуванні понять більше ніж і 3 в даній інтерпретації):

х> з

Тепер можна визначити модель безлічі (обовязково замкнутих) правильно побудованих формул як інтерпретацію, при якій всі ППФ в даній безлічі приймають значення TRUE Друга з двох інтерпретацій, які були дані для чотирьох наведених нижче ППФ в термінах цілих чисел від 0 до 5, не була моделлю для цих ППФ, оскільки деякі з ППФ при цій інтерпретації брали значення

FALSE:

2   &gt   1

2   &gt  3

EXISTS x (х> 2)

FORALL x (х> 2)

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

“Належним чином), повинна була бути моделлю для наступного безлічі ППФ:

2 &gt 1

3 &gt 2

EXISTS х (х> 2)

FORALL x {х> 2 OR NOT (x> 2))

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

Клаузальная форма

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

Процес перетворення здійснюється наступним чином (тут він описаний схематично додаткові відомості наведені в [246]) Етапи перетворення будуть показані на прикладі застосування їх до наступної ППФ:,

FORALL X (р (X) AND EXISTS у (FORALL z (q (у, z))))

Тут р і g – предикати, а х, у і z – змінні

1 Видалити символи ⇒ , як показано в розділі 243 У даному прикладі цей пров

вий етап перетворення не потрібно

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

3 Перетворити правильно побудовану формулу в попереджання (Або пренексную) нормальну форму, переміщаючи всі квантори вперед (і в разі необхідності систематично перейменовуючи змінні), як показано нижче

FORALL х (EXISTS у (FORALL z (р (х) AND q (у, z))))

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

EXISTS  v  (  r  (  v   )   )

еквівалентна наступній правильно побудованої формулі для деякої невідомої константи а:

r (а)

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

FORALL u ( EXISTS v ( s ( u, v ) ) )

еквівалентна наведеної нижче правильно побудованої формулі для деякої невідомої функції f від універсально квантифікованій змінної і

FORALL і (s (і, f (і)))

Константа а і функція f в цих прикладах відомі, відповідно, під назвою скулемовской константи і скулемовской функції,які названі на честь логіка ТАСкулема (TASkolem) {Примітка Скулемовская константа насправді являє собою просто скулемовскую функцію без параметрів) Тому наступний етап полягає в усуненні кванторів існування шляхом

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

FORALL х (FORALL z (р (X) AND q (f (х), 2)))

5 Тепер всі змінні квантифікувати універсально, тому може бути прийнято угоду, відповідно до якого всі змінні неявно вважаються квантифікувати універсально, що дозволяє видалити явно задані кван тори таким чином

р (х) AND q (f (X), z)

6 Перетворити цю правильно побудовану формулу в конюнктівную нормаль ную форму, тобто в безліч виразів (званих також Клаузена або діз юнктамі), зєднаних операторами AND, в якому кожен вираз може включати оператори NOT і OR, але не AND У даному прикладі правильно побудований ная формула вже знаходиться в такій формі

7 Записати кожен вираз на окремому рядку і видалити оператори AND, сле дме чином

Р (X) q (f (X), Z)

Це і є клаузальная форма, еквівалентна первісної правильно побудованої формулі

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

NOT Al OR NOT А2 OR .. OR NOT Am OR Bl OR B2 OR .. OR Bn

Тут все терми А і В не містять операторів заперечення При бажанні, такий вираз можна записати наступним чином

Al AND A2 AND AND Am =&gt Bl OR B2 OR .. OR Bn

Якщо кількість термів в не перевищує одного (п = 0 або 1), такий вираз називають хорновскім виразом на честь логіка Альфреда Хорна (Alfred Horn)

Використання правила резолюції

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

1&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp MOTHER_OF ( Anne, Betty )

2&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp MOTHER_OF ( Betty, Celia )

Крім того, дана наведена нижче правильно побудована формула (Дедуктивна аксіома)

3 MOTHER_OF (X, у) AND MOTHER_OF (у, z) ⇒ GRANDMOTHER_OF (X, z) Зверніть увагу на те, що це – хорновское вираз) Для того щоб спростити застосування правила резолюції, перепишемо цей вираз для видалення

символу ⇒ , як показано нижче

4 NOT MOTHER_OF (X, у) OR NOT MOTHER_OF (у, z) OR GRANDMOTHER_OF (x, z)

Тепер ми можемо перейти до доказу того, що Анна – бабуся Селії Таким чином, буде показано, як відповісти на запит: Чи є Анна бабусею Селії” Почнемо з заперечення того укладення, яке має бути доведено, та прийняття його в якості додаткової передумови, як показано нижче

5&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp NOT GRANDMOTHER_OF ( Anne, Celia )

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

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

Для того щоб розглянути, як описаний вище процес діє в даному конкретному випадку, спочатку слід відзначити, що рядки 4 і 5 містять, відповідно, терми GRANDMOTHER_OF (x, z) І NOT GRANDMOTHER_OF (Anne, Celia) Тому виконаємо підстановку в рядку 4 значення Anne замість х і Celia замість z і застосуємо правило резолюції для отримання наведеного нижче вираження

6 NOT MOTHER_OF (Anne, у) OR NOT MOTHER_OF (у, Celia)

Рядок 2 містить терм MOTHER_OF (Betty, Celia), тому можна виконати підстановку значення Betty замість у в рядку 6 і застосувати правило резолюції для отримання наведеного нижче вирази

7&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp NOT MOTHER_OF ( Anne, Betty )

Застосувавши правило резолюції до рядків 7 і 1, отримуємо порожній безліч виразів, [] Це означає, що виявлено протиріччя Тому відповідь на початковий запит полягає в наступному: Так, Анна – Бабуся Селії .

А тепер знайдемо відповідь на запит: Хто є онукою Анни” Спочатку відзначимо, що системі нічого не відомо про онуках вона має інформацію тільки про бабусь Тому, щоб вийти з положення, можна ввести ще одну дедуктивну аксіому, яка свідчить про те, що z є онукою х тоді і тільки тоді, коли х – бабуся z (у цій базі даних немає інформації про чоловіків) Ще один варіант полягає в тому, що початковий питання може бути перефразувавши наступним чином: Чиєю бабусею є Ганна” Розглянемо останню формулювання Застосовувані передумови (ще раз) показані нижче

1&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp MOTHER_OF ( Anne, Betty ) ,

2&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp MOTHER_OF ( Betty, Celia )

3 NOT MOTHER_OF (X, у) OR NOT MOTHER_OF (y, z) OR GRANDMOTHER_OF (x, z)

Введемо четверту передумову, як показано нижче

4&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp NOT GRANDMOTHER_OF ( Anne, r ) OR RESULT ( r )

На інтуїтивному рівні ясно, що в цій новій передумові міститься твердження, що або Анна не є бабусею когось, або існує деяка особа r, дані про якого входять до складу бажаного результату (оскільки Анна є бабусею цієї особи r) Нам потрібно визначити імена всіх таких осіб r Подальші дії виконуються таким чином Спочатку виконаємо підстановку значення Anne замість х і змінної r замість z і застосуємо правило резолюції до рядків 4 і 3 для отримання наведеного нижче вирази

5 NOT MOTHER_OF (Anne, у) OR NOT MOTHER_OF (у, z) OR RESULT (z)

Потім виконаємо підстановку значення Betty замість у і застосуємо правило резолюції до рядків 5 і 1 для отримання виразу, яке показано нижче

6&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp NOT MOTHER_OF ( Betty, z ) OR RESULT ( z )

Тепер виконаємо підстановку значення Celia замість z і застосуємо правило резолюції до рядків 6 і 2, отримавши показане нижче вираз;

7&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp RESULT   (   Celia   )

Отже, Анна – бабуся Селії

Примітка Якби був введений додатковий терм таким чином, що

MOTHER_OF ( Betty, Delia )

то на останньому етапі (замість значення Celia) можна було б підставити в якості z значення Delia і отримати наступний результат

RESULT ( Delia )

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

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

*

*