ОГЛЯД КОНЦЕПЦІЇ тризначні ЛОГІКИ

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

Логічні оператори

Вище вже зазначалося, що результатом операцій порівняння скалярів, в яких хоча б один з операндів є величиною UNK, буде логічне значення unknown, а не значення true або false Тому в таких випадках доводиться мати справу з тризначною

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

логікою Третім логічним значенням тут є значення unknown, на яке ми досить часто, але не постійно, будемо посилатися за допомогою скорочення ІПК Нижче наведені таблиці істинності для операторів AND, OR і NOT в тризначній логіці (в таблицях використовуються такі скорочення: t – true, f-false, і ІПК)

Припустимо, що А = 3, в = 4 і змінна с має значення UNK Тоді наведені нижче вирази матимуть такі результати (які показані праворуч)

А> У AND У> С:false

А> У OR У> С: ІПК

А < У OR В < С: true NOT (A = С): ІПК

, Проте, для реалізації тризначною логіки одних тільки операторів AND, OR і NOT недостатньо [1911] Ще одним важливим оператором є оператор MAYBE (можливо) [195] Таблиця істинності даного оператора показана нижче

Щоб продемонструвати необхідність у використанні оператора MAYBE, розглянемо запит: Отримати відомості про співробітників з річною зарплатою менше 50 тис дол, які можуть бути (але це точно не відомо) програмістами і народилися до 18 січня 1971 . За допомогою оператора MAYBE даний запит можна досить коротко записати в наступному віде3

EMP WHERE MAYBE ( JOB = Programmer AND

DOB &lt DATE (1971-1-18) AND SALARY &lt 5000000 )

(Тут передбачається, що атрибути JOB, DOB і SALARY змінної відносини ОМР мають типи CHAR, DATE і RATIONAL, відповідно) Але без оператора MAYBE ЦЕЙ же запит буде виглядати наступним чином

ОМР WHERE (JOB = Programmer OR IS_UNK (JOB))

AND    ( DOB &lt DATE (1971-1-18) OR IS_UNK ( DOB ) )                                                                                 ( SALARY &lt 5000000

OR IS_UNK ( SALARY ) )

AND NOT ( JOB = Programmer AND

DOB &lt DATE (1971-1-18) AND

SALARY &lt 5000000 )

3 Щоб скласти приклади, наведені в цій главі, необхідно було прийняти допущення, що мова Tutorial D включає засоби підтримки значень UNK і тризначною логіки Фактично така підтримка, зрозуміло, не передбачена

Тут передбачається існування іншого истинностного оператора IS_UNK, який приймає як параметр єдиний скалярний операнд і повертає значення true, якщо цей операнд дорівнює UNK, або значення false – В іншому випадку (До речі, слід зазначити, що певна версія оператора IS_DNK необхідна і для операндів, відмінних від скалярних Але автор не робить спробу визначити тут подібну конструкцію, оскільки рішення цього завдання повязане із занадто великими складнощами, до того ж він взагалі не відчуває довіри до твердження про необхідність підтримки тризначною логіки)

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

може виявитися оператор TRUE_OR_MAYBE (який повертає true, якщо його операнд

дорівнює true або ІПК, а в іншому випадку повертає false), як показано в [195]

Див також анотацію до [1911] в розділі Додаткова література.

Квантори

Всупереч тому безперечного факту, що для представлення більшості прикладів в цій книзі використовується реляційна алгебра, а не обчислення, нам все ж слід розглянути вплив тризначною логіки на обчислення кванторів реляційного числення EXISTS і FORALL Як говорилося в главі 8, квантори EXISTS І FORALL визначаються як ітераційні конструкції з операторів OR і AND, відповідно Інакше кажучи, якщо r – відношення з кортежами tl, t2, .., tm, V – мінлива області значень, яка приймає значення з даного відношення г, а р (V) – логічний вираз, в якому V використовується як вільна змінна, то вираз

EXISTS V (р (V))

за визначенням еквівалентно наступному вираженню false  OR p (tl) OR .. OR p ™ Аналогічним чином, вираз

FORALL V (р (V))

за визначенням еквівалентно наступному вираженню

true AND  p   (   tl   )   AND   ..   AND  p   (   tm   )

Що відбудеться, якщо для деякого i значення p (ti) дорівнюватиме unk Наприклад,

нехай ставлення r містить наступні кортежі

(                                          1,                                        2,                                             3    )

(                                           1 ,    2 ,    U N K )

(   UNK,   UNK,   UNK   )

Припустимо для простоти, що трьома атрибутами в зазначеному вище порядку зліва направо є атрибути А, в і з, відповідно, і кожен з них має тип INTEGER Нижче наведені приклади різних виразів і результати їх обчислення

EXISTS  v  ( vc &gt 1 )                                                                                                                                                                                                          :  true EXISTS V( VB &gt 2 )                                             : unk EXISTS V( MAYBE ( VA &gt 3 ) )  : true EXISTS V( IS_UNK ( VC ) )    : true

FORALL V( VA &gt 1 )                                            : false FORALL V( VB &gt 1 )                                             : unk FORALL V ( MAYBE ( VC &gt 1 ) )  : false

Інші скалярні оператори

Розглянемо наступне числове вираження

WEIGHT *  454

Тут атрибут WEIGHT представляє вага деякої деталі Що буде, якщо вага розглянутої деталі є величиною UNK Яким буде значення всього цього виразу Відповідь полягає в тому, що значенням всього виразу також повинна бути величина UNK У загальному випадку, якщо хоча б один з операндів арифметичного виразу є величиною UNK, результатом обчислення всього виразу також буде величина UNK Таким чином, наприклад, якщо атрибут WEIGHT містить величину UNK, результатом обчислення всіх наведених нижче виразів також буде величина UNK

■&nbsp WEIGHT + 454                                         ■ 454 + WEIGHT                                             ■ + WEIGHT

■&nbsp WEIGHT 454                                         ■ 454 WEIGHT                                             ■ WEIGHT

■&nbsp WEIGHT * 454                                        ■ 454 * WEIGHT

■&nbsp WEIGHT / 454     ■ 454 / WEIGHT

Примітка Ймовірно, слід відразу ж зазначити, що подібна трактування числових виразів може призвести до появи деяких аномалій Наприклад, вираз WEIGHT WEIGHT, значенням якого повинен бути нуль, на насправді буде мати значення UNK, а результатом обчислення виразу WEIGHT / 0 буде також величина UNK замість звичайного в даному випадку повідомлення про помилку ділення на нуль (безумовно, в обох виразах передбачається, що атрибут WEIGHT містить величину UNK) Такі аномалії ігноруватимуться до особливого згадки

Аналогічні міркування застосовні до всіх інших скалярним типам і операторам, за винятком логічних операторів (розглянутих у двох попередніх підрозділах), оператора IS_UNK, описаного вище, і розглянутого нижче оператора

IF_UNK Таким чином, для символьних рядків вираз А | | в повертає UNK, якщо

А рівний UNK, або в дорівнює UNK, або обидва рівні UNK (Знову слід відзначити існування аномальних випадків, розгляд яких ми тут опустимо)

Оператор IF_UNK отримує на вході два скалярних операнда і повертає значення першого операнда, якщо це не величина UNK Якщо перший операнд є величиною UNK, то оператор IF_UNK повертає значення другого операнда Іншими словами,

це – оператор перетворення величини UNK в деяке значення, відмінне від UNK

Наприклад, припустимо, що значення UNK дозволено використовувати для приміщення в атрибут CITY змінної відносини постачальників S Розглянемо наступний вираз

EXTEND S ADD IF_UNK ( CITY, City unknown ) AS SCITY

У результаті його обчислення буде отримана мінлива відносини, в якій значення атрибута SCITY одно City unknown для кожного постачальника, місто якого у змінній відносини s визначений як UNK

Слід зазначити, що оператор IF_UNK можна визначити з допомогою оператора

IS_UNK Точніше кажучи, вираз

IF_UNK ( exp1, exp2 )

де параметри expl і ехр2 повинні мати однакові типи, еквівалентно наступному вираженню

IF IS_UNK ( expl ) THEN exp2 ELSE expl END IF

UNK – це не ІПК

Дуже важливо розуміти, що величина UNK (невизначене значення виду значення не відомо) і значення ІПК (Логічне значення unknown) — це НЕ одне і то А4 Дійсно, дане положення справ є прямим наслідком того, що ІПК – Це значення (точніше, істиннісне значення), у той час як величина UNK взагалі не є значенням Сформулюємо сказане вище більш точно Припустимо, що X є змінною логічного типу (BOOLEAN) Тоді вона може приймати одне з наступних значень:true,  false  абоІПКТаким чином, вираз X одноІПК означає в точності те, що значення змінної X відомо і дорівнює ІПК На відміну від цього, вираз X одно UNK означає, що значення змінної х не відомо

Проблема приналежності величини UNK до типу

З того факту, що ШГК НЕ є значенням, прямо випливає висновок, що типи (тобто безлічі значенні) не можуть містити величину UNK Дійсно, якби типи могли містити невизначені значення якого виду, то перевірка обмежень цілісності для них завжди завершувалася б з позитивним результатом Але, оскільки типи фактично не можуть містити величину UNK, відносини, що допускають присутність величини UNK, є чим завгодно, але тільки НЕ реляційними відносинами Причому це вірно як для відносин, визначення яких дано в главі 6, так і для відносин, що відповідають оригінальному визначенням Кодда [61] До обговорення цього важливого питання ми ще повернемося пізніше

Реляційні оператори

Розглянемо вплив величини ШГК на оператори реляційної алгебри Для простоти обмежимося пятьма примітивними операторами: твір, скорочення, проекція, обєднання і різниця (вплив величини UNK на інші оператори можна визначити на основі висновків про її впливі на пять перерахованих операторів)

Насамперед, відзначимо, що на операцію твори величина UNK ніякого влия ня не надає

Далі, операцію скорочення слід кілька переформулювати, зажадавши, щоб поверталися тільки кортежі, для яких умова скорочення має значення true, тобто ця операція не повинна включати в результат кортежі, для яких умова скорочення приймає значення false або ІПК

4 Проте, в стандарті SQL вони розглядаються як еквівалентні поняття (див розділ 197)

Примітка Використання саме цього формулювання неявно передбачалося в прикладі з оператором MAYBE, наведеному вище, в підрозділі Логічні оператори даного розділу

Тепер розглянемо операцію проекції Для отримання проекції відносини потрібно, крім усього іншого, виключити дублікати кортежів У двухзначной логіці два кортежу tl і t2 вважаються дублікатами тоді і тільки тоді, коли вони мають однакові атрибути А1, А2, , An і для всіх i (i = 1, 2, .., п) значення Ai в кортежі tl дорівнює значенню Ai в кортежі t2 Однак в тризначній логіці деякі з цих значень атрибутів можуть містити величину UNK, а величина UNK (як було сказано вище) не дорівнює ніякої другий величиною, навіть самій собі Чи випливає з цього висновок, що кортеж, який містить величину UNK, не може бути дублікатом іншого кортежу і навіть самого себе

Згідно Кодд, відповідь на це питання відємний: дві величини UNK, навіть якщо вони не рівні між собою, вважаються дублікатами одна інший в цілях виключення дублікатів кортежів [147] 5 Це очевидне протиріччя пояснюється наступним чином:

“… Перевірка на рівність у процесі виключення дублікатів кортежів .. виконується на більш низькому рівні деталізації в порівнянні з перевіркою на рівність при оцінці умов вибірки Тому тут можна застосувати інше правило .

Автор надає читачеві право вирішувати, чи є таке обгрунтування прийнятним У кожному разі, давайте погодимося зараз з цим обгрунтуванням, а заодно приймемо наведене нижче визначення

■ Кортежі tl і t2 є дублікатами один іншого тоді і тільки тоді, коли вони мають однакові атрибути А1, А2, , An і для всіх i (i = 1, 2,

. , П), або значення Ai в кортежі tl дорівнює значенню Ai в кортежі t2, або обидва значення Ai в кортежі tl і t2 рівні UNK

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

■&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp tl  =  t2

■ tl і t2 є дублікатами один одного

Обєднання також на увазі виключення надлишкових дублікатів кортежів, і для цієї операції також може бути застосоване наведене вище визначення дублікатів кортежів Таким чином, обєднання відносин r1 і r2 одного і того ж типу можна визначити як відношення r того ж типу, тіло якого складається з усіх можливих кортежів t, таких що кортеж t є дублікатом деякого кортежу відносно rl або щодо r2 (Або в них обох одночасно)

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

5 Робота [147] була першою роботою Кодда, в якій проблема відсутності інформації розглядалася досить докладно, хоча опис цієї проблеми не було основною задачею статті (див главу 14) Крім усього іншого, в статті пропонуються версії можливого 9-зєднання, 8-вибірки (тобто скорочення), оператори ділення (див упр 194), а також зовнішні версії операцій зєднання, перетину, віднімання, 8-зєднання і природного зєднання (див розділ 195)

операції r1 MINUS r2 тоді і тільки тоді, коли цей кортеж є дублікатом-якого кортежу відносно rl, але не є дублікатом жодного з кортежів у відношенні r2 (Для повноти картини зазначимо, що операція перетину визначається аналогічно, хоча вона, безумовно не відноситься до типу примітивних Це означає, що кортеж t потрапляє в результат операції rl INTERSECT r2 тоді і тільки тоді, коли цей кортеж є дублікатом -якого кортежу відносно rl і одночасно дублікатом-якого кортежу відносно r2)

Операції поновлення

Тут слід згадати два описаних нижче основні моменти

1 Якщо атрибут А відносини R може містити величину UNK і якщо вставляється у відношення R за допомогою оператора INSERT кортеж не містить значення для ат рібута А, то система автоматично помістить величину UNK на місце неприсутній ного значення (безумовно, тут передбачається, що для А не визначено заданий ве за замовчуванням значення, відмінне від UNK) Якщо атрибут А у змінній відносини R не допускає присутності величини UNK, то спроба помістити в R кортеж (за допомогою операції INSERT або UPDATE), в якому в атрибут А поме щено значення UNK, призведе до помилки

2 Спроба помістити у відношенні R дублікат кортежу (за допомогою операції INSERT або UPDATE) зазвичай є помилкою У даному випадку визначення дублікатів кортежів взято з попереднього підрозділу

Обмеження цілісності

Як вказувалося в розділі 9, обмеження цілісності неформально можна розглядати як логічне вираження, результат обчислення якого не повинен бути рівний false Отже, обмеження цілісності не буде порушено, якщо результат його обчислення буде дорівнює значенню ІПК (Насправді, це неявно передбачалося в зауваженнях, наведених вище в цьому розділі щодо обмежень типів) Безумовно, в цьому випадку точніше було б сказати, що нам нічого що не відомо про те, чи буде порушено дане обмеження цілісності Але з відомою часткою наближення цілком можна стверджувати, що якщо в конструкції WHERE значення ІПК розглядається як false, то в обмеженнях цілісності воно розглядається як true (І тут в обох випадках застосовуються кілька неформальні затвердження)

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

*

*