Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ФУНКЦІОНАЛЬНІ ЗАЛЕЖНОСТІ

Нехай R - відношення зі схемою 7Z } і Х у У - підмножини 7Z. Ставлення R задовольняє функціональної залежності (F-залежності) X -? Y, якщо пу (має не більше ніж один кортеж для кожного ^ -Значення х. Іншими словами, фіксація значень стовпців з X однозначно визначає значення стовпців з У. У F-залежності X -> У підмножина X називається лівою частиною , а У - правою частиною.

Якщо відношення R зі схемою 71 задовольняє функціональної залежності X -> 71, то безліч X називається суперключ. Тобто суперключ однозначно визначає кортеж. Поняття суперключ в точності відповідає поняттю тесту таблиці. Нагадаємо, що тестом таблиці називається така безліч стовпців, що проекція таблиці на ці стовпчики не має однакових рядків. Суперключ відносини називається ключем, якщо будь-який його підмножина не є суперключ. Поняття ключа повністю відповідає поняттю тупикового тесту таблиці.

Якщо 71 - деяка схема відносин, то через М (71) позначимо множину всіх відносин над схемою 71. Якщо М З М {71 ), то скажемо що безліч М задовольняє функціональної залежності X -? У, якщо кожне відношення з А / задовольняє X -> У.

Часто надходять навпаки і описують безліч М допустимих відносин описується за допомогою безлічі F- залежностей, яким має задовольняти кожне відношення. Це безліч F-залежностей фактично описує наші семантичні знання про ставлення. Тому в подальшому ми будемо вважати, що разом зі схемою 71 задано безліч Т F-залежностей, яким повинні задовольняти всі допустимі відносини.

Якщо відомі деякі F-залежності з F, то часто можна вивести інші. Безліч F-залежностей Т тягне F-залежність X -> У (позначення: F = X - * У), якщо кожне відношення, яке задовольняє F-залежностей з F, задовольняє також F-залежності X -> У. У цьому випадку також кажуть , що X - * Y є логічним наслідком Т, або що X - »У випливає з Т.

Аксіома виведення - це правило, яке встановлює, що якщо відношення задовольняє певним F-залежностей, то воно повинно задовольняти і деяким іншим F-залежностей.

Тепер введемо шість аксіом виведення для ^ -залежних. В їх формулюваннях використовується позначення R для відносини зі схемою 1Z і IV, X, У і Z - для підмножин R.

F1. Рефлексивність. Ставлення irx (& x = x {R)) завжди має не більше одного кортежу, отже, X -> X завжди має місце в R.

F2. Поповнення. Це аксіома має справу з розширенням лівої частини F-залежності. Якщо R задовольняє X -> Y, то ny (crx = x (R)) має не більше одного кортежу для будь-якого Х-значення х. Якщо Z є будь-яким підмножиною 7 ?, то 0 Xuz = xz (R) Я (? X = x (R) і, отже, TTy (axuZ = xz (R)) Я пу (ох = x (R)). Таким чином пу (аxuZ = xz (R)) має найбільше один кортеж, і R має задовольняти F-залежності Xu Z -> Y.

F3. Адитивність. Ця дозволяє об'єднати дві F-залеж- ності з однаковими лівими частинами. Якщо відношення R задовольняє X -> Y і X - * Z, то обидві проекції 'у ((Тх = х (Щ) і nz (мають не більше одного кортежу для будь-якого -Значення х. Якби ставлення тсуіг {0Х = ж {Щ) мало більш одного кортежу, то принаймні одне з відносин я ш у {& х = х (Щ) АБО 7Tz (o'x = x (R)) мало б більше одного кортежу . Таким чином, R задовольняє F-залежності X - * Y U Z.

F4. Проективної. Ця аксіома в деякій мірі протилежна аксіомі аддитивности. Якщо R задовольняє X YuZ, то TTyuz (^ x = x (R)) має не більше одного кортежу для будь-якого Х-значення х. Так як Яу (* Уіг {рх = х {Щ)) - 7ry (aY = x (F)), то 7Ty ((rx = x (R)) також може мати не більше одного кортежу. Отже, R задовольняє X - » Y.

F5. Транзитивність. Ця і наступна аксіома є найбільш потужними з аксіом виведення. Нехай відношення R задовольняє F-залежностей X - * Y і Y -> Z. Розглянемо кортежі Г] і г 2 в R. Якщо г (Х) = г 2 (Х), то ri (T) = г 2 (У) , а з r (Y) = г 2 (У), випливає, що ri (Z) = r 2 (Z). Таким чином, якщо ri (A ') = г 2 (Х), то ri (Z) = r 2 (Z), тобто R задовольняє X -? Z.

F6. Псевдотранзітівность. Нехай відношення R задовольняє F-залежностей X - * Y і Y U Z - * W, а г і г 2 є кортежами в R. За умовою якщо ri (X) = г 2 (Х), то ri (F) = г 2 (Т), і, аналогічно, якщо T {Y U Z) = r 2 (TU Z),

Отже, якщо Х у У , Z, W є підмножинами 71 у те для будь-якого відношення R справедливі наступні аксіоми виведення:

Використовуючи аксіоми F1-F6, можна отримати інші правила виведення для ^ -залежних. Більш того аксіоми F1-F6 не є незалежними, тобто одні з них можуть бути отримані з інших. Так якщо дані аксіоми FI, F2 і F6, то з них можна вивести інші. Якщо дані X -> У і X -> Z, то використовуємо F1, щоб отримати YUZ -> У UZ, і двічі застосовуємо F6, отримуючи спочатку XuZ -? YnZ, а потім X -> YuZ. Тому F3 випливає з FI, F2 і F6. Щоб довести F4, припустимо, що X -> Y U Z. З F1 маємо У - * У, а з F2 отримуємо У U Z -> У. Застосування F6 дає X - * У. F5 є частим випадком F6 при Z = 0 . В якості самостійного вправи можна показати, що аксіоми FI, F2 і F6 є незалежними, тобто жодна з них не може бути виведена з двох інших.

 
<<   ЗМІСТ   >>