ТОРА (9) - Семинар №4 - Синтез хорошей БД: различия между версиями

Материал из Кафедра ИУ5 МГТУ им. Н.Э.Баумана, студенческое сообщество
Перейти к навигации Перейти к поиску
(Новая страница: «__TOC__ == Синтез хорошей схемы БД == Из [[ТОРА (9) - Семинар №2 - Функциональные зависимости#Зад...»)
 
 
(не показано 5 промежуточных версий 1 участника)
Строка 11: Строка 11:


1)
1)
 
: [[ТОРА (9) - Лекция №3 - Хорошая схема БД - Соединение без потерь#Алгоритм построения условно-неизбыточного покрытия|строим условно-неизбыточное покрытие:]]
: {{Формула|f=УНП = B\rightarrow D, D\rightarrow B, BC\rightarrow AD}}
: {{Формула|f=УНП = B\rightarrow D, D\rightarrow B, BC\rightarrow AD}}


Строка 20: Строка 20:
3)
3)


: {{Формула|f=B\rightarrow^? AD}} !!нет!!
: {{Формула|f=B\rightarrow^? AD}} <span style="color:red">нет</span>
: {{Формула|f=B:+ = BD}}, {{Формула|f=AD\nsubseteq B^+}}
: {{Формула|f=B:+ = BD}}, {{Формула|f=AD\nsubseteq B^+}}


: {{Формула|f=C\rightarrow^? AD}} !!нет!!
: {{Формула|f=C\rightarrow^? AD}} <span style="color:red">нет</span>
: {{Формула|f=C:+ = C}}, {{Формула|f=AD\nsubseteq C^+}}
: {{Формула|f=C:+ = C}}, {{Формула|f=AD\nsubseteq C^+}}


Строка 58: Строка 58:
10)
10)


* смотрим сохранение без потерь:
* смотрим соединение без потерь:


{| class="wikitable"
{| class="wikitable"
Строка 92: Строка 92:
Таким образом, {{Формула|f=\rho}} обладает соединением без потерь, сохранением ФЗ и находится в 3НФ.
Таким образом, {{Формула|f=\rho}} обладает соединением без потерь, сохранением ФЗ и находится в 3НФ.


== ДЗ 1 ==
== ДЗ ==


Сделать к следующему (пятому) семинару.
<u>Задание:</u>


Проверить, находятся ли получившиеся {{Формула|f=R_1}} и {{Формула|f=R_2}} в НФБК?
Проверить, находятся ли получившиеся {{Формула|f=R_1}} и {{Формула|f=R_2}} в НФБК?


== ДЗ 2 ==
<u>Решение:</u>
 
Сделать к послеследующему (шестому) семинару.


=== Первая задача ===
{{Формула|f=\rho = (BD, ABC) = (R_1, R_2)}}


Задана та же предметная область (про пилотов), но ФЗ другие:
{{Формула|f=F = (B\rightarrow D, BC\rightarrow A)}}


{{Формула|f=F = (B\rightarrow D, D\rightarrow B, AB\rightarrow D, AD\rightarrow B, BC\rightarrow A, BC\rightarrow D, CD\rightarrow A, CD\rightarrow B, ABC\rightarrow D, ACD\rightarrow B, BCD\rightarrow A)}}
Отношение находится в НФБК, если для каждой нетривиальной и неприводимой ФЗ {{Формула|f=X\rightarrow Y}} {{Формула|f=X}} - ключ.


Синтезировать БД с помощью алгоритма.
1. Выбираем ключи:


=== Вторая задача ===
:{{Формула|f=R_1}}:
::1)
:::{{Формула|f=i = 0}}, {{Формула|f=X_0 = BD}}
:::{{Формула|f=(X_0 - D)^+ = B^+ = BD = R}}, {{Формула|f=i = 1}}, {{Формула|f=X_1 = B}}
:::{{Формула|f=(X_0 - B)^+ = D^+ = D\neq R}}
:::{{Формула|f=i}} возросло.
::2)
:::{{Формула|f=i = 1}}, {{Формула|f=X_1 = B}}
:::{{Формула|f=(X_1 - B)^+ = \varnothing^+ = \varnothing}}
:::{{Формула|f=i}} не возросло, значит {{Формула|f=B}} - ключ.


Предметная область: курсы иностранных языков.
:{{Формула|f=R_2}}:
::1)
:::{{Формула|f=i = 0}}, {{Формула|f=X_0 = ABC}}
:::{{Формула|f=(X_0 - A)^+ = (BC)^+ = ABC = R}}, {{Формула|f=i = 1}}, {{Формула|f=X_1 = BC}}
:::{{Формула|f=(X_0 - B)^+ = (AC)^+ = AC\neq R}}
:::{{Формула|f=(X_0 - C)^+ = (AB)^+ = AB\neq R}}
:::{{Формула|f=i}} возросло.


{{Формула|f=U =}} (код курса, код филиала, условия обучения, номер группы (состоит из номера филиала и номера группы, номер уровня обучения, ФИО слушателя, число оплаченных слушателем занятий (оплачиваются все занятия курса сразу, стоимость обучения для студентов и школьников, стоимость обучения для взрослых, адрес филиала, заведующий филиалом, телефон филиала, часы работы преподавателя с группой слушателей (количество часов), зарплата преподавателя, ФИО преподавателя))) = {{Формула|f=(A, B, C, D, E, K, L, N, O, P, R, S, T, V, X)}}
::2)
:::{{Формула|f=i = 1}}, {{Формула|f=X_1 = BC}}
:::{{Формула|f=(X_1 - B)^+ = C^+ = C\neq R}}
:::{{Формула|f=(X_1 - C)^+ = B^+ = B\neq R}}
:::{{Формула|f=i}} не возросло,значит {{Формула|f=BC}} - ключ.


ФЗ:
2. Проверяем:


{{Формула|f=F = (A\rightarrow CNO, B\rightarrow PRS, ADE\rightarrow X, K\rightarrow DEL, L\rightarrow T, X\rightarrow VT, ET\rightarrow V, D\rightarrow XBE)}}
:{{Формула|f=R_1}}:
::{{Формула|f=B\rightarrow D}} - нетривиальная;
::{{Формула|f=\varnothing\subset B}}, значит {{Формула|f=B\rightarrow D}} - неприводимая;
::{{Формула|f=B}} - ключ, значит {{Формула|f=R_1}} находится в НФБК.


Синтезировать схему БД по алгоритму. Со следующими свойствами:
:{{Формула|f=R_2}}:
* соединение без потерь;
::{{Формула|f=BC\rightarrow A}} - нетривиальная;
* каждая схема в 3НФ;
::{{Формула|f=B\subset BC}}, но {{Формула|f=B\nrightarrow A}};
** каждую проверить ещё и на НФБК;
::{{Формула|f=C\subset BC}}, но {{Формула|f=C\nrightarrow A}};
* наименьшее число схем отношений;
:: выходит, {{Формула|f=BC\rightarrow A}} ещё и неприводимая;
* сохранение ФЗ (если не обладает, то новых схемы отношений добавлять не надо).
::{{Формула|f=BC}} - ключ, значит {{Формула|f=R_2}} тоже находится в НФБК.


[[Категория:Теоретические основы реляционной алгебры (9 семестр)|С]]
[[Категория:Теоретические основы реляционной алгебры (9 семестр)|С]]
[[Категория:Конспекты лекций и семинаров]]
[[Категория:Конспекты лекций и семинаров]]

Текущая версия от 20:40, 26 октября 2017

Синтез хорошей схемы БД

Из семинара 2: предметную область зададим следующую: "график полётов".

График = (пилот, рейс, дата, время), сокращённо: $$\rho=(A,B,C,D)$$

Итоговая $$F = (B\rightarrow D, D\rightarrow B, BC\rightarrow A)$$

Идём по алгоритму:

1)

строим условно-неизбыточное покрытие:
$$УНП = B\rightarrow D, D\rightarrow B, BC\rightarrow AD$$

2)

пропускаем, потому что есть $$BC\rightarrow AD$$

3)

$$B\rightarrow^? AD$$ нет
$$B:+ = BD$$, $$AD\nsubseteq B^+$$
$$C\rightarrow^? AD$$ нет
$$C:+ = C$$, $$AD\nsubseteq C^+$$
УНП остаётся без изменений.

4)

разбиваем на классы:
$$B\rightarrow D$$, $$D\rightarrow B$$, $$K_1 = BD$$
$$BC\rightarrow AD$$, $$K_2 = BCAD$$

5)

построить граф:

6)

7)

8)

пропускаем, потому что нет ФЗ с пустой правой частью.

9)

$$\rho = (BD, ABC) = (R_1, R_2)$$

10)

  • смотрим соединение без потерь:
$$A$$ $$B$$ $$C$$ $$D$$
$$R_1$$ $$b$$ $$a$$ $$b$$ $$a$$
$$R_1$$ $$a$$ $$a$$ $$a$$ $$b$$
$$A$$ $$B$$ $$C$$ $$D$$
$$R_1$$ $$b$$ $$a$$ $$b$$ $$a$$
$$R_1$$ $$a$$ $$a$$ $$a$$ $$a$$
Есть строка сплошь из $$a$$, значит схема обладает соединением без потерь.
  • смотрим сохранение ФЗ:
1-4) $$H = \varnothing$$, $$УНП = (B\rightarrow B\rightarrow D, BC\rightarrow AD, D\rightarrow B)$$
5) $$H$$ не пусто.
6)
$$BC\rightarrow^? D\in(B\rightarrow D, BC\rightarrow A, D\rightarrow B)^+$$
$$(BC)^+ = BCAD$$, $$D\in (BC)^+$$, значит, схема обладает сохранением ФЗ.

Таким образом, $$\rho$$ обладает соединением без потерь, сохранением ФЗ и находится в 3НФ.

ДЗ

Задание:

Проверить, находятся ли получившиеся $$R_1$$ и $$R_2$$ в НФБК?

Решение:

$$\rho = (BD, ABC) = (R_1, R_2)$$

$$F = (B\rightarrow D, BC\rightarrow A)$$

Отношение находится в НФБК, если для каждой нетривиальной и неприводимой ФЗ $$X\rightarrow Y$$ $$X$$ - ключ.

1. Выбираем ключи:

$$R_1$$:
1)
$$i = 0$$, $$X_0 = BD$$
$$(X_0 - D)^+ = B^+ = BD = R$$, $$i = 1$$, $$X_1 = B$$
$$(X_0 - B)^+ = D^+ = D\neq R$$
$$i$$ возросло.
2)
$$i = 1$$, $$X_1 = B$$
$$(X_1 - B)^+ = \varnothing^+ = \varnothing$$
$$i$$ не возросло, значит $$B$$ - ключ.
$$R_2$$:
1)
$$i = 0$$, $$X_0 = ABC$$
$$(X_0 - A)^+ = (BC)^+ = ABC = R$$, $$i = 1$$, $$X_1 = BC$$
$$(X_0 - B)^+ = (AC)^+ = AC\neq R$$
$$(X_0 - C)^+ = (AB)^+ = AB\neq R$$
$$i$$ возросло.
2)
$$i = 1$$, $$X_1 = BC$$
$$(X_1 - B)^+ = C^+ = C\neq R$$
$$(X_1 - C)^+ = B^+ = B\neq R$$
$$i$$ не возросло,значит $$BC$$ - ключ.

2. Проверяем:

$$R_1$$:
$$B\rightarrow D$$ - нетривиальная;
$$\varnothing\subset B$$, значит $$B\rightarrow D$$ - неприводимая;
$$B$$ - ключ, значит $$R_1$$ находится в НФБК.
$$R_2$$:
$$BC\rightarrow A$$ - нетривиальная;
$$B\subset BC$$, но $$B\nrightarrow A$$;
$$C\subset BC$$, но $$C\nrightarrow A$$;
выходит, $$BC\rightarrow A$$ ещё и неприводимая;
$$BC$$ - ключ, значит $$R_2$$ тоже находится в НФБК.
Источник — https://iu5bmstu.ru/index.php?title=ТОРА_(9)_-_Семинар_№4_-_Синтез_хорошей_БД&oldid=5602