Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 5
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
Кафедра "Інформаційні системи та мережі "
Лабораторна робота №3
з курсу «Теорія систем баз даних та знань»
на тему:
Побудова функціональних залежностей для обраної ПО
Виконала
студентка
групи ІСМм-11
Бігун Г.В.
Прийняв
асистент
Завалій Т. І.
Львів-2012
Мета роботи: створення баз даних має дві основні мети: зменшити надлишковість даних і підвищити їх надійність. Будь-яке апріорне знання про різного роду обмеження, що накладаються на сукупність даних, може принести велику користь для досягнення вказаних цілей. Одним із способів формалізації цих знань є встановлення залежностей між даними, а саме побудова множини функціональних залежностей (F-залежність (FD)), що підтримуються в обраній ПО.
Теоретичні відомості
Функціональна залежність є узагальненням поняттям ключа. Не строго кажучи, F-залежність має місце тоді, коли значення кортежу на одній множині атрибутів єдиним чином визначають ці значення на іншій множині атрибутів.
Нехай r – відношення зі схемою R, X та Y – підмножини. Відношення r задовольняє функціональні залежності X Y, якщо має не більше одного кортежу для кожного Х – значення х. Один із способів інтерпретувати ей вираз – розглянути два кортежі та в r. Якщо то . В F-залежності X Y підмножина Х називається лівою частиною, відповідно Y – правою.
Алгоритм SATISFIES. Цей алгоритм перевіряє, чи задовольняє відношення r F-залежності X Y.
Вхід: відношення r та F-залежність X Y. Вихід: істина, якщо r задовольняє X Y, хибність – в іншому випадку.
SATISFIES (r, X Y);
Застосування аксіом виведення. Множина функціональних залежностей, що застосовуються до відношення r(R), кінцева, так як існує тільки кінцеве число підмножин множини R. Таким чином, завжди можна знайти всі F – залежності, яким r задовольняє, перебравши всі можливі з допомогою алгоритма SATISFIES. Проте цей підхід потребує більшої кількості часу. Якщо відомі деякі F-залежності з F, тоді здебільшого можна вивести решта. Множина F-залежностей породжує F-залежність X Y(позначення: F | X Y), якщо кожне відношення, що задовольняє всім залежностям в F, задовольняє також залежності X Y. Аксіома виведення – це правило, яке встановлює, що якщо відношення задовольняє визначеним F – залежностям, тоді воно повинно задовольняти і деяким іншим F – залежностям.
Тепер введемо шість аксіом виведення для F-залежностей. В їх формулюваннях використовуються позначення r для відношення на R і W, X, Y і Z – для підмножин R.
F1. Рефлексивність: X X.
F2: Поповнення: X Y породжує XZ Y.
F3: Адитивність:X Y i X Z породжує X YZ.
F4: Проективність: X YZ породжує X Y.
F5: Транзитивність: X Y i Y Z породжує X Z.
F6: Псевдотранзитивність: X Y i YZ W породжує XZ W.
Аксіоми F1, F2 і F6 складають повну підмножину для F1-F6. Аксіоми F1, F2 i F6також є незалежними: жодна з цих аксіом не може бути отримана з двох інших. Ці три аксіоми називаються іноді аксіомами Армстронга, хоча вони не дуже схожі на вихідну аксіому Армстронга (проте ця назва узвичаєна).
Нехай F – множина F-залежностей для відношення r (R). Замикання F, що позначається, F - це найменша множина, що містить F, така, що при застосуванні до неї аксіом Армстронга не можна одержати жодної F-залежності не приналежної F. Оскільки F повинно бути завжди, то можна обчислити його, починаються з F шляхом застосування F1, F2 і F6 і додавання отриманих Р-залежностей до F доти, поки не перестануть утворюватися нові залежності. Замикання F залежить від схеми R. Якщо R = AB, то F завжди будуть містити B B. Коли R не визначене явно, передбачається, що існує множина всіх символів атрибутів, використовуваних у F – залежностях із F.
З множини F можна вивести F-залежність X Y, якщо X Y належить F, тому що аксіоми виведення породжують тільки функціональні залежності, то F спричиняє за собою X Y, якщо X Y виводиться з F.
Відношення Альбом.
Код виконавця функціонально залежить від назви альбому:
Код виконавця {Назва альбому}.
Назва льбому функціонально залежить від (визначає) рік випуску, загальна тривалість, кількість пісень:
Назва альбому {Рік випуску, загальна тривалість, кількість пісень}.
Загальна тривалість функціонально залежить від кількість пісень:
Загальна тривалість {Кількість пісень}.
Кількість пісень функціонально залежить від назва альбому, загальна тривалість:
Кількість пісень {Назва альбому, Загальна тривалість}.
Таблиця 1. Відношення Альбом
Відношення Склад.
Номер альбому функціонально залежить від наявність:
Номер альбому {Наявність}.
Наявність функціонально залежить від номер складу, номер сектору, номер полиці, номер стелажа:
Наявність {Номер складу, Номер сектору, Номер полиці}.
Номер складу функціонально залежить від вулиця, телефон:
Номер складу {Вулиця, Телефон}.
Таблиця 2. Відношення склад
В таблиці 3 показано результат застосування алгоритму SATISFIES (Альбом, Назва альбому Код виконавця) до відношення Альбом з таблиці 1 (таблиці розбиті на кортежі з рівними значеннями атрибутів Назва альбому, Рік випуску, Кількість пісень, Загальна тривалість).
Таблиця 3. Результат алгоритму SATISFIES (Альбом, Назва альбому Код виконавця)
Значення атрибутів Назва альбому, Рік випуску, Загальна тривалість, Кількість пісень в кожній множині однакові, отже, вказана F-залежність задовольняється.
Нехай F = {ALB_ZTR KST, KST ZTR} – множина F-залежностей на АЛЬБОМ (ALB_ZTR_KST).
F =
{
ALB ALB, ALB_ZTR ALB, ALB_KST ALB, ALB_ZTR_KST ALB,
ZTR ZTR, ALB_ZTR ZTR, ALB_KST ZTR, ALB_ZTR_KST ZTR,
KST KST, ALB_ZTR KST, ALB_KST KST, ALB_ZTR_KST KST,
ALB_ZTR ALB_ZTR, ALB_ZTR_KST ALB_ZTR,
ALB_KST ALB_KST, ALB_ZTR_KST ALB_KST,
ZTR_KST ZTR_KST, ALB_ZTR_KST ZTR_KST,
ALB_ZTR_KST ALB_ZTR_KST,
ALB_ZTR KST, ALB_ZTR ALB_KST, ALB_ZTR ZTR_KST, ALB_ZTR ALB_ZTR_KST,
KST ZTR, KST ZTR_KST,
ALB_KST ZTR, ALB_KST ALB_ZTR
}
Висновок: на цій лабораторній роботі я ознайомилась з побудова множини функціональних залежностей як способом зменшення надлишковості даних і підвищення їх надійності.