Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ПОБУДОВА ФУНКЦІОНАЛЬНИХ ЗАЛЕЖНОСТЕЙ ДЛЯ ОБРАНОЇ ПО
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
РТ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2013
Тип роботи:
Лабораторна робота
Предмет:
Бази даних та знань
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ, НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ІСМ
Лабораторна робота №3
на тему:
ПОБУДОВА ФУНКЦІОНАЛЬНИХ ЗАЛЕЖНОСТЕЙ ДЛЯ ОБРАНОЇ ПО
З курсу:
«Теорія систем баз даних та знань»
Мета роботи
Вивчення застосування звичайних булевих операцій над множинами до відношень. Визначення трьох спеціальних операторів над відношеннями: вибору, проекції і з’єднання. Оператори об’єднання, перетину, різниці, активного доповнення, вибірки, натурального зєднання, ділення, перейменування і -з’єднання разом з постійними і регулярниим відношеннями відносяться до реляційної алгебри. Нарешті, аналізуються дві операції, що не належать алгебрі, але іноді корисні при реалізації бази даних, а саме: оператор розщеплення та оператор фактор.
Теоретичні відомості
Функціональна залежність є узагальненням поняттям ключа. Не строго кажучи, 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.
/=
Рис. 1. Відношення «Змагання»
Для цього використаю написану програму, текст якої:
Клас Cortege (кортеж):
package first;
public class Cortege {
public int id;
public String name;
public String date;
public String situated;
public Cortege(int id, String name,String date, String situated) {
this.id = id;
this.name = name;
this.date = date;
this.situated = situated;
}
}
Клас Main:
package first;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<Cortege> al = new ArrayList<Cortege>();
al.add(new Cortege(1," Loeb ","29/12/86"," Citroen C4"));
al.add(new Cortege(1,"Solberg ","29/12/89"," Subaru Impreza"));
int n = al.size();
boolean result = true;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(i!=j) {
if(al.get(i).name.equals(al.get(j).name)) {
if(!al.get(i).situated.equals(al.get(j).situated) ) {
result = false;
}
}
}
}
}
System.out.println("Func. dependence - " + result);
}
}
Результат виконання програми :
Func. dependence – true
Висновок
На даній лабораторній роботі я ознайомився з побудовою множини функціональних залежностей як способом зменшення надлишковості даних і підвищення їх надійності, також я склав програму для перевірки функціональної залежності для конкретного прикладу, та побудував замикання.
20.05.2013 22:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора