ТОРА (9) - Семинар №3 - Соединение без потерь: различия между версиями
ILobster (обсуждение | вклад) (→ДЗ: вторая и третья задачи) |
|||
(не показано 19 промежуточных версий 9 участников) | |||
Строка 73: | Строка 73: | ||
=== Задача 3 === | === Задача 3 === | ||
Обладает ли схема свойством созранения ФЗ? | |||
1-4) | 1-4) | ||
Строка 97: | Строка 99: | ||
=== Задача 4 === | === Задача 4 === | ||
Находится ли отношение в 3НФ? | |||
По каждой таблице. | По каждой таблице. | ||
Строка 126: | Строка 130: | ||
:и так далее, "рутинная тупая работа". | :и так далее, "рутинная тупая работа". | ||
:А можно было, оказывается, так: {{Формула|f=Y^+ = Y}}, а по условию {{Формула|f=H\notin Y}}, значит {{Формула|f=Y\nrightarrow H}}, так что таблица {{Формула|f=S}} находится в 3НФ. | :А можно было, оказывается, так: | ||
:Если для какого-либо {{Формула|f=Y}} {{Формула|f=H\notin Y}}, то {{Формула|f=Y\nrightarrow H}} | |||
:Доказательство: {{Формула|f=Y^+ = Y}}, а по условию {{Формула|f=H\notin (Y^+)}}, значит {{Формула|f=Y\nrightarrow H}}, так что таблица {{Формула|f=S}} находится в 3НФ. | |||
==== Таблица P ==== | ==== Таблица P ==== | ||
Строка 192: | Строка 198: | ||
FROM R1, R2, R3, R4, R5 | FROM R1, R2, R3, R4, R5 | ||
WHERE R1.A = R3.A | WHERE R1.A = R3.A | ||
AND R3.B = R2.B | |||
AND R1.C = R4.C | |||
AND R4.C = R5.C | |||
</syntaxhighlight> | </syntaxhighlight> | ||
Строка 250: | Строка 256: | ||
! !! C !! F | ! !! C !! F | ||
|- align="center" | |- align="center" | ||
! | ! {{Формула|f=r_4}} | ||
| {{Формула|f=c_1}} || {{Формула|f=f_1}} | | {{Формула|f=c_1}} || {{Формула|f=f_1}} | ||
|} | |} | ||
Строка 323: | Строка 329: | ||
=== Задача №1 === | === Задача №1 === | ||
[[#Пример 1 | Находятся ли]] {{Формула|f=P}} и {{Формула|f=SP}} в 3НФ? | |||
==== Таблица P ==== | ==== Таблица P ==== | ||
Ищем тройку: | |||
: 1) {{Формула|f=X = PN}}, {{Формула|f=PN}} - ключ. | |||
: 2) {{Формула|f=Y(Y\nrightarrow X)}}: {{Формула|f=PF, PC, PFPC}} | |||
: 3) рассматриваем: | |||
:: а) {{Формула|f=Y = PF}}, {{Формула|f=H\notin Y}}: {{Формула|f=PC}} | |||
::: {{Формула|f=PF\rightarrow^? PC}} <span style="color:red">нет</span> | |||
::: {{Формула|f=(PF)^+ = PF}}, {{Формула|f=PC\notin (PF)^+}} | |||
:: б) {{Формула|f=Y = PC}}, {{Формула|f=H\notin Y}}: {{Формула|f=PF}} | |||
::: {{Формула|f=PC\rightarrow^? PF}} <span style="color:red">нет</span> | |||
::: {{Формула|f=(PC)^+ = PC}}, {{Формула|f=PF\notin (PC)^+}} | |||
Таким образом, не удалось подобрать необходимую тройку, значит таблица находится в 3НФ. | |||
==== Таблица SP ==== | ==== Таблица SP ==== | ||
Ищем тройку: | |||
: 1) {{Формула|f=X = PN SN}}, так как {{Формула|f=SN PN\rightarrow kol}} | |||
: 2) подберём {{Формула|f=Y}}, для которого {{Формула|f=X\rightarrow Y}}, {{Формула|f=Y\rightarrow X}}, {{Формула|f=Y(Y\nrightarrow X)}}: {{Формула|f=kol}} | |||
:: {{Формула|f=(kol)^+ = kol}}, {{Формула|f=PNSN\nsubseteq kol}}, {{Формула|f=kol\nrightarrow SN}} | |||
: 3) {{Формула|f=Y = kol}} - нельзя подобрать непервичный атрибут {{Формула|f=H}}: {{Формула|f=H\notin Y}} | |||
Таким образом, не удалось подобрать необходимую тройку, значит таблица находится в 3НФ. | |||
=== Задача №2 === | === Задача №2 === | ||
Доказать, что эти две подсхемы {{Формула|f=(R_1, R_2, R_3, R_4)}} и {{Формула|f=(R_4, R_5)}} | Доказать, что эти две подсхемы {{Формула|f=(R_1, R_2, R_3, R_4)}} и {{Формула|f=(R_4, R_5)}} обладают соединением без потерь, и запрос на соединение выполнится правильно. | ||
Ещё раз ФЗ: {{Формула|f=F = (A\rightarrow C, B\rightarrow E, C\rightarrow F, D\rightarrow C)}} | Ещё раз ФЗ: {{Формула|f=F = (A\rightarrow C, B\rightarrow E, C\rightarrow F, D\rightarrow C)}} | ||
==== Первая подсхема ==== | |||
Подсхема {{Формула|f=(R_1, R_2, R_3, R_4)}}: | Подсхема {{Формула|f=(R_1, R_2, R_3, R_4)}}: | ||
Строка 340: | Строка 368: | ||
! !! A !! B !! C !! E !! F | ! !! A !! B !! C !! E !! F | ||
|- align="center" | |- align="center" | ||
! R_1 | ! {{Формула|f=R_1}} | ||
| {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} | | {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} | ||
|- align="center" | |- align="center" | ||
! R_2 | ! {{Формула|f=R_2}} | ||
| {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} | | {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} | ||
|- align="center" | |- align="center" | ||
! R_3 | ! {{Формула|f=R_3}} | ||
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} | | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} | ||
|- align="center" | |- align="center" | ||
! R_4 | ! {{Формула|f=R_4}} | ||
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=a}} | | {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=a}} | ||
|} | |} | ||
Строка 356: | Строка 384: | ||
! !! A !! B !! C !! E !! F | ! !! A !! B !! C !! E !! F | ||
|- align="center" | |- align="center" | ||
! R_1 | ! {{Формула|f=R_1}} | ||
| {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=a}} || {{Формула|f=b_1}} || bgcolor="lime" | {{Формула|f=a}} | | {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=a}} || {{Формула|f=b_1}} || bgcolor="lime" | {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! R_2 | ! {{Формула|f=R_2}} | ||
| {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} | | {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} | ||
|- align="center" | |- align="center" | ||
! R_3 | ! {{Формула|f=R_3}} | ||
| {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}}|| bgcolor="lime" | {{Формула|f=a}} | | {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}}|| bgcolor="lime" | {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! R_4 | ! {{Формула|f=R_4}} | ||
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=a}} | | {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=a}} | ||
|} | |} | ||
Получили строку, сплошь состоящую из {{Формула|f=a}}, значит подсхема {{Формула|f=(R_1, R_2, R_3, R_4)}} обладает свойством соединения без потерь. | Получили строку, сплошь состоящую из {{Формула|f=a}}, значит подсхема {{Формула|f=(R_1, R_2, R_3, R_4)}} обладает свойством соединения без потерь. | ||
<syntaxhighlight lang="sql"> | |||
SELECT * | |||
FROM R1, R2, R3, R4 | |||
WHERE R1.A = R2.A | |||
AND R3.B = R2.B | |||
AND R1.C = R4.C | |||
</syntaxhighlight> | |||
Строим проекции: | |||
{{Формула|f=r_1 = \Pi_{R_1}(r)}} | |||
{| class="wikitable" | |||
! !! A !! C | |||
|- align="center" | |||
! rowspan="2" | {{Формула|f=r_1}} | |||
| {{Формула|f=a_1}} || {{Формула|f=c_1}} | |||
|- align="center" | |||
| {{Формула|f=a_2}} || {{Формула|f=c_1}} | |||
|} | |||
{{Формула|f=r_2 = \Pi_{R_2}(r)}} | |||
{| class="wikitable" | |||
! !! B !! E | |||
|- align="center" | |||
! rowspan="2" | {{Формула|f=r_2}} | |||
| {{Формула|f=b_1}} || {{Формула|f=e_1}} | |||
|- align="center" | |||
| {{Формула|f=b_2}} || {{Формула|f=e_2}} | |||
|} | |||
{{Формула|f=r_3 = \Pi_{R_3}(r)}} | |||
{| class="wikitable" | |||
! !! A !! B | |||
|- align="center" | |||
! rowspan="2" | {{Формула|f=r_3}} | |||
| {{Формула|f=a_1}} || {{Формула|f=b_1}} | |||
|- align="center" | |||
| {{Формула|f=a_2}} || {{Формула|f=b_2}} | |||
|} | |||
{{Формула|f=r_4 = \Pi_{R_4}(r)}} | |||
{| class="wikitable" | |||
! !! C !! F | |||
|- align="center" | |||
! {{Формула|f=r_4}} | |||
| {{Формула|f=c_1}} || {{Формула|f=f_1}} | |||
|} | |||
Теперь соединения: | |||
{{Формула|f=t_1 = r_1 \bowtie_A r_3}} | |||
{| class="wikitable" | |||
! !! A !! B !! C | |||
|- align="center" | |||
! rowspan="2" | {{Формула|f=t_1}} | |||
| {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}} | |||
|- align="center" | |||
| {{Формула|f=a_2}} || {{Формула|f=b_2}} || {{Формула|f=c_1}} | |||
|} | |||
{{Формула|f=t_2 = t_1 \bowtie_B r_2}} | |||
{| class="wikitable" | |||
! !! A !! B !! C !! E | |||
|- align="center" | |||
! rowspan="2" | {{Формула|f=t_2}} | |||
| {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}} || {{Формула|f=e_1}} | |||
|- align="center" | |||
| {{Формула|f=a_2}} || {{Формула|f=b_2}} || {{Формула|f=c_1}} || {{Формула|f=e_2}} | |||
|} | |||
{{Формула|f=t_3 = t_2 \bowtie_C r_4}} | |||
{| class="wikitable" | |||
! !! A !! B !! C !! E !! F | |||
|- align="center" | |||
! rowspan="2" | {{Формула|f=t_3}} | |||
| {{Формула|f=a_1}} || {{Формула|f=b_1}} || {{Формула|f=c_1}} || {{Формула|f=e_1}} || {{Формула|f=f_1}} | |||
|- align="center" | |||
| {{Формула|f=a_2}} || {{Формула|f=b_2}} || {{Формула|f=c_1}} || {{Формула|f=e_2}} || {{Формула|f=f_1}} | |||
|} | |||
Соединение выполнилось верно. | |||
==== Вторая подсхема ==== | |||
Подсхема {{Формула|f=(R_4, R_5)}}: | Подсхема {{Формула|f=(R_4, R_5)}}: | ||
Строка 376: | Строка 495: | ||
! !! C !! D !! F | ! !! C !! D !! F | ||
|- align="center" | |- align="center" | ||
! | ! {{Формула|f=R_4}} | ||
| {{Формула|f=a}} || {{Формула|f= | | {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! | ! {{Формула|f=R_5}} | ||
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f= | | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_5}} | ||
|} | |} | ||
Строка 386: | Строка 505: | ||
! !! C !! D !! F | ! !! C !! D !! F | ||
|- align="center" | |- align="center" | ||
! | ! {{Формула|f=R_4}} | ||
| {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} | | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! | ! {{Формула|f=R_5}} | ||
| {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} | | {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} | ||
|} | |} | ||
Получили строку, сплошь состоящую из {{Формула|f=a}}, значит подсхема {{Формула|f=(R_4, R_5)}} обладает свойством соединения без потерь. | Получили строку, сплошь состоящую из {{Формула|f=a}}, значит подсхема {{Формула|f=(R_4, R_5)}} обладает свойством соединения без потерь. | ||
<syntaxhighlight lang="sql"> | |||
SELECT * | |||
FROM R4, R5 | |||
WHERE R4.C = R5.C | |||
</syntaxhighlight> | |||
Строим проекции: | |||
{{Формула|f=r_4 = \Pi_{R_4}(r)}} | |||
{| class="wikitable" | |||
! !! C !! F | |||
|- align="center" | |||
! {{Формула|f=r_4}} | |||
| {{Формула|f=c_1}} || {{Формула|f=f_1}} | |||
|} | |||
{{Формула|f=r_5 = \Pi_{R_5}(r)}} | |||
{| class="wikitable" | |||
! !! D !! C | |||
|- align="center" | |||
! rowspan="2" | {{Формула|f=r_5}} | |||
| {{Формула|f=d_1}} || {{Формула|f=c_1}} | |||
|- align="center" | |||
| {{Формула|f=d_2}} || {{Формула|f=c_1}} | |||
|} | |||
Теперь соединение: | |||
{{Формула|f=t_1 = r_4 \bowtie_C r_5}} | |||
{| class="wikitable" | |||
! !! C !! D !! F | |||
|- align="center" | |||
! rowspan="2" | {{Формула|f=t_1}} | |||
| {{Формула|f=c_1}} || {{Формула|f=d_1}} || {{Формула|f=f_1}} | |||
|- align="center" | |||
| {{Формула|f=c_1}} || {{Формула|f=d_2}} || {{Формула|f=f_1}} | |||
|} | |||
Соединение выполнилось верно. | |||
=== Задача №3 === | === Задача №3 === | ||
Строка 401: | Строка 563: | ||
Изменяем схему: | Изменяем схему: | ||
[[Файл:9sTORAs3pic2.png|link=9sTORAs3pic2.svg]] | [[Файл:9sTORAs3pic2.png|link=Файл:9sTORAs3pic2.svg]] | ||
Однако, это не самый минимальный способ, потому что мы ввели новую ФЗ. Можно было {{Формула|f=D}} добавить в ключ, тогда связь была бы идентифицирующая. | |||
Но так тоже можно. | |||
Теперь: | Теперь: | ||
Строка 408: | Строка 574: | ||
! !! A !! B !! C !! D !! E !! F | ! !! A !! B !! C !! D !! E !! F | ||
|- align="center" | |- align="center" | ||
! R_1 | ! {{Формула|f=R_1}} | ||
| {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} | | {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} | ||
|- align="center" | |- align="center" | ||
! R_2 | ! {{Формула|f=R_2}} | ||
| {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} | | {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} | ||
|- align="center" | |- align="center" | ||
! R_3 | ! {{Формула|f=R_3}} | ||
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} | | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} | ||
|- align="center" | |- align="center" | ||
! R_4 | ! {{Формула|f=R_4}} | ||
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} | | {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! R_5 | ! {{Формула|f=R_5}} | ||
| {{Формула|f=b_5}} || {{Формула|f=b_5}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_5}} || {{Формула|f=b_5}} | | {{Формула|f=b_5}} || {{Формула|f=b_5}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_5}} || {{Формула|f=b_5}} | ||
|} | |} | ||
Строка 427: | Строка 593: | ||
! !! A !! B !! C !! D !! E !! F | ! !! A !! B !! C !! D !! E !! F | ||
|- align="center" | |- align="center" | ||
! R_1 | ! {{Формула|f=R_1}} | ||
| {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || bgcolor="lime" | {{Формула|f=a}} | | {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || bgcolor="lime" | {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! R_2 | ! {{Формула|f=R_2}} | ||
| {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} | | {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} | ||
|- align="center" | |- align="center" | ||
! R_3 | ! {{Формула|f=R_3}} | ||
| {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} | | {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! R_4 | ! {{Формула|f=R_4}} | ||
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} | | {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} | ||
|- align="center" | |- align="center" | ||
! R_5 | ! {{Формула|f=R_5}} | ||
| {{Формула|f=b_5}} || {{Формула|f=b_5}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_5}} || bgcolor="lime" | {{Формула|f=a}} | | {{Формула|f=b_5}} || {{Формула|f=b_5}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_5}} || bgcolor="lime" | {{Формула|f=a}} | ||
|} | |} | ||
Строка 453: | Строка 619: | ||
Задано множество ФЗ: | Задано множество ФЗ: | ||
{{Формула|f=F = (A\rightarrow BCDV, K\rightarrow D, V\rightarrow SX, V\rightarrow G, XG\rightarrow KEV, VX\rightarrow | {{Формула|f=F = (A\rightarrow BCDV, K\rightarrow D, V\rightarrow SX, V\rightarrow G, XG\rightarrow KEV, VX\rightarrow G)}} | ||
Задана схема БД: | Задана схема БД: | ||
Строка 460: | Строка 626: | ||
Обладает ли эта схема БД свойством соединения без потерь и свойством сохранения ФЗ. | Обладает ли эта схема БД свойством соединения без потерь и свойством сохранения ФЗ. | ||
==== Соединение без потерь ==== | |||
{{Формула|f=\rho = (AKE, ABCX, AVGX, VSDG)}} | |||
{{Формула|f=F = (A\rightarrow BCDV, K\rightarrow D, V\rightarrow SX, V\rightarrow G, XG\rightarrow KEV, VX\rightarrow D)}} | |||
{| class="wikitable" | |||
! !! {{Формула|f=A}} !! {{Формула|f=B}} !! {{Формула|f=C}} !! {{Формула|f=D}} !! {{Формула|f=E}} !! {{Формула|f=K}} !! {{Формула|f=V}} !! {{Формула|f=S}} !! {{Формула|f=X}} !! {{Формула|f=G}} | |||
|- align="center" | |||
! {{Формула|f=AKE}} | |||
| {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} || {{Формула|f=b_1}} | |||
|- align="center" | |||
! {{Формула|f=ABCX}} | |||
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=b_2}} || {{Формула|f=b_2}} || {{Формула|f=b_2}} || {{Формула|f=b_2}} || {{Формула|f=a}} || {{Формула|f=b_2}} | |||
|- align="center" | |||
! {{Формула|f=AVGX}} | |||
| {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=a}} || {{Формула|f=a}} | |||
|- align="center" | |||
! {{Формула|f=VSDG}} | |||
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=a}} | |||
|} | |||
{| class="wikitable" | |||
! !! {{Формула|f=A}} !! {{Формула|f=B}} !! {{Формула|f=C}} !! {{Формула|f=D}} !! {{Формула|f=E}} !! {{Формула|f=K}} !! {{Формула|f=V}} !! {{Формула|f=S}} !! {{Формула|f=X}} !! {{Формула|f=G}} | |||
|- align="center" | |||
! {{Формула|f=AKE}} | |||
| {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} | |||
|- align="center" | |||
! {{Формула|f=ABCX}} | |||
| {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=b_2}} || {{Формула|f=b_2}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} | |||
|- align="center" | |||
! {{Формула|f=AVGX}} | |||
| {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=b_3}} || {{Формула|f=b_3}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} || {{Формула|f=a}} | |||
|- align="center" | |||
! {{Формула|f=VSDG}} | |||
| {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=b_4}} || {{Формула|f=b_4}} || {{Формула|f=a}} || {{Формула|f=a}} || bgcolor="lime" | {{Формула|f=a}} || {{Формула|f=a}} | |||
|} | |||
Получили строку, сплошь состоящую из {{Формула|f=a}}, значит {{Формула|f=\rho}} обладает соединением без потерь. | |||
==== Сохранение ФЗ ==== | |||
1-4) | |||
: {{Формула|f=H = \varnothing}} | |||
: {{Формула|f=УНП = A\rightarrow ABCDVSXGKE, K\rightarrow KD, V\rightarrow VSXGKED, XG\rightarrow XGKEVDS, VX\rightarrow VXDSGEK)}} | |||
: {{Формула|f=H = (A\rightarrow S, K\rightarrow D, V\rightarrow KE, XG\rightarrow KEDS, VX\rightarrow DSEK)}} | |||
5) | |||
: {{Формула|f=H\neq\varnothing}} | |||
6) | |||
: {{Формула|f=H\in^? (A\rightarrow BCV, V\rightarrow SXG)}} <span style="color:red">нет</span> | |||
{{Формула|f=A\rightarrow DS}}, {{Формула|f=A^+ = ABCVSXG}} | |||
{{Формула|f=DS\notin ABCVSXG}}, значит {{Формула|f=\rho}} не обладает сохранением ФЗ. | |||
[[Категория:Теоретические основы реляционной алгебры (9 семестр)|С]] | |||
[[Категория:Конспекты лекций и семинаров]] |
Текущая версия от 23:56, 27 ноября 2017
Свойства хорошей БД:
- соединение без потерь;
- сохранение ФЗ;
- нормализация схемы отношений (3НФ).
По этому семинару надо выполнить домашнее задание. В письменном виде в тетради.
Пример 1
Таблицы $$\rho=(S,P,SP)$$
- $$S$$ - поставщики.
- SN - номер поставщика;
- SF - фамилия;
- SS - статус;
- SG - город.
- $$P$$ - деталь.
- PN - номер детали, ключ;
- PF - название детали;
- PC - цена за единицу.
- $$SP$$ - поставка.
- SN - номер поставщика;
- PN - номер детали;
- kol - количество поставляемых деталей.
$$\rho = (S, P, SP)$$
Задачи:
- выписать ФЗ на основе знания предметной области;
- проверить, обладает ли $$\rho$$ соединением без потерь;
- проверить, обладает ли $$\rho$$ сохранением ФЗ;
- проверить, находится ли $$\rho$$ в 3НФ.
Задача 1
$$SN\rightarrow SF$$, $$SN\rightarrow SS$$, $$SN\rightarrow SG$$
$$PN\rightarrow PF$$, $$PN\rightarrow PC$$
$$SNPN\rightarrow kol$$
Задача 2
SN | SF | SS | SG | PN | PF | PC | kol | |
---|---|---|---|---|---|---|---|---|
$$S$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ |
$$P$$ | $$b_2$$ | $$b_2$$ | $$b_2$$ | $$b_2$$ | $$a$$ | $$a$$ | $$a$$ | $$b_2$$ |
$$SP$$ | $$a$$ | $$b_3$$ | $$b_3$$ | $$b_3$$ | $$a$$ | $$b_3$$ | $$b_3$$ | $$a$$ |
SN | SF | SS | SG | PN | PF | PC | kol | |
---|---|---|---|---|---|---|---|---|
$$S$$ | $$a$$ | $$a$$ | $$a$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ |
$$P$$ | $$b_2$$ | $$b_2$$ | $$b_2$$ | $$b_2$$ | $$a$$ | $$a$$ | $$a$$ | $$b_2$$ |
$$SP$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ |
Получили строку, сплошь состоящую из $$a$$, значит $$\rho$$ обладает соединением без потерь - если мы соединим все три исходные таблицы, то получим правильный результат.
Задача 3
Обладает ли схема свойством созранения ФЗ?
1-4)
- $$H=\varnothing$$
- $$УНП = (SN\rightarrow SFSSSG, PN\rightarrow PFPC, SNPN\rightarrow kolSFSSSGPFPC)$$
- смотрим, кто принадлежит, получается:
- $$УНП = (SN\rightarrow SFSSSG, PN\rightarrow PFPC, SNPN\rightarrow kol)$$
- $$H = (SNPN\rightarrow SFSSSGPFPC)$$
5)
- $$H\neq\varnothing$$
6)
- выполняется ли $$SNPN\rightarrow SFSSSGPFPC\in (SN\rightarrow SFSSSG, PN\rightarrow PFPC, SNPN\rightarrow kol)^+$$?
- $$(SNPN)^+ = SNPNSFSSSGPFPCkol$$, значит выполняется, значит $$\rho$$ обладает сохранением ФЗ.
Задача 4
Находится ли отношение в 3НФ?
По каждой таблице.
Таблица S
Смотрим таблицу $$S$$:
1)
- $$X = SN$$ - ключ.
2)
- $$Y(Y\nrightarrow X)$$: $$SF, SS, SG, SFSS, SFSG, SSSG, SFSSSG$$
3)
- рассматриваем $$Y = SF$$, ищем такие $$H$$, которые не принадлежат $$Y$$: $$SS, SG$$
- а)
- $$SF\rightarrow SS$$?
- $$SF^+=SF$$, значит $$SS\notin SF^+$$
- б)
- $$SF\rightarrow SG$$?
- $$SF^+=SF$$, значит $$SG\notin SF^+$$
- и так далее, "рутинная тупая работа".
- А можно было, оказывается, так:
- Если для какого-либо $$Y$$ $$H\notin Y$$, то $$Y\nrightarrow H$$
- Доказательство: $$Y^+ = Y$$, а по условию $$H\notin (Y^+)$$, значит $$Y\nrightarrow H$$, так что таблица $$S$$ находится в 3НФ.
Таблица P
Таблица SP
Пример 2
Выписать все ФЗ.
$$\rho = (R_1, R_2, R_3, R_4, R_5)$$
$$F = (A\rightarrow C, B\rightarrow E, C\rightarrow F, D\rightarrow C)$$
A | B | C | D | E | F | |
---|---|---|---|---|---|---|
$$R_1$$ | $$a$$ | $$b_1$$ | $$a$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ |
$$R_2$$ | $$b_2$$ | $$a$$ | $$b_2$$ | $$b_2$$ | $$a$$ | $$b_2$$ |
$$R_3$$ | $$a$$ | $$a$$ | $$b_3$$ | $$b_3$$ | $$b_3$$ | $$b_3$$ |
$$R_4$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$b_4$$ | $$b_4$$ | $$a$$ |
$$R_5$$ | $$b_5$$ | $$b_5$$ | $$a$$ | $$a$$ | $$b_5$$ | $$b_5$$ |
A | B | C | D | E | F | |
---|---|---|---|---|---|---|
$$R_1$$ | $$a$$ | $$b_1$$ | $$a$$ | $$b_1$$ | $$b_1$$ | $$a$$ |
$$R_2$$ | $$b_2$$ | $$a$$ | $$b_2$$ | $$b_2$$ | $$a$$ | $$b_2$$ |
$$R_3$$ | $$a$$ | $$a$$ | $$a$$ | $$b_3$$ | $$a$$ | $$a$$ |
$$R_4$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$b_4$$ | $$b_4$$ | $$a$$ |
$$R_5$$ | $$b_5$$ | $$b_5$$ | $$a$$ | $$a$$ | $$b_5$$ | $$a$$ |
Нет строчки, сплошь состоящей из $$a$$, значит $$\rho$$ не обладает соединением из потерь - запрос на соединение пяти таблицы может выполняться неправильно.
Смотрим:
SELECT *
FROM R1, R2, R3, R4, R5
WHERE R1.A = R3.A
AND R3.B = R2.B
AND R1.C = R4.C
AND R4.C = R5.C
и предположим, что задан следуюшие экземпляр универсальной схемы отношения:
A | B | C | D | E | F | |
---|---|---|---|---|---|---|
$$r$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ | $$d_1$$ | $$e_1$$ | $$f_1$$ |
$$a_2$$ | $$b_2$$ | $$c_1$$ | $$d_2$$ | $$e_2$$ | $$f_1$$ |
Найти проекции и выполнить их соединение по запросу выше.
Строим проекции:
$$r_1 = \Pi_{R_1}(r)$$
A | C | |
---|---|---|
$$r_1$$ | $$a_1$$ | $$c_1$$ |
$$a_2$$ | $$c_1$$ |
$$r_2 = \Pi_{R_2}(r)$$
B | E | |
---|---|---|
$$r_2$$ | $$b_1$$ | $$e_1$$ |
$$b_2$$ | $$e_2$$ |
$$r_3 = \Pi_{R_3}(r)$$
A | B | |
---|---|---|
$$r_3$$ | $$a_1$$ | $$b_1$$ |
$$a_2$$ | $$b_2$$ |
$$r_4 = \Pi_{R_4}(r)$$
C | F | |
---|---|---|
$$r_4$$ | $$c_1$$ | $$f_1$$ |
$$r_5 = \Pi_{R_5}(r)$$
D | C | |
---|---|---|
$$r_5$$ | $$d_1$$ | $$c_1$$ |
$$d_2$$ | $$c_1$$ |
Теперь соединения:
$$t_1 = r_1 \bowtie_A r_3$$
A | B | C | |
---|---|---|---|
$$t_1$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ |
$$a_2$$ | $$b_2$$ | $$c_1$$ |
$$t_2 = t_1 \bowtie_B r_2$$
A | B | C | E | |
---|---|---|---|---|
$$t_2$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ | $$e_1$$ |
$$a_2$$ | $$b_2$$ | $$c_1$$ | $$e_2$$ |
$$t_3 = t_2 \bowtie_C r_4$$
A | B | C | E | F | |
---|---|---|---|---|---|
$$t_3$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ | $$e_1$$ | $$f_1$$ |
$$a_2$$ | $$b_2$$ | $$c_1$$ | $$e_2$$ | $$f_1$$ |
$$t_4 = t_3 \bowtie_C r_5$$
A | B | C | D | E | F | |
---|---|---|---|---|---|---|
$$t_4$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ | $$d_1$$ | $$e_1$$ | $$f_1$$ |
$$a_2$$ | $$b_2$$ | $$c_1$$ | $$d_1$$ | $$e_2$$ | $$f_1$$ | |
$$a_1$$ | $$b_1$$ | $$c_1$$ | $$d_2$$ | $$e_1$$ | $$f_1$$ | |
$$a_2$$ | $$b_2$$ | $$c_1$$ | $$d_2$$ | $$e_2$$ | $$f_1$$ |
Получившееся не совпадает с исходной. Вот и проявилось отсутствие сохранения без потерь.
Но подсхемы $$(R_1, R_2, R_3, R_4)$$ и $$(R_4, R_5)$$, при этом, обладают соединением без потерь.
ДЗ
Задача №1
Находятся ли $$P$$ и $$SP$$ в 3НФ?
Таблица P
Ищем тройку:
- 1) $$X = PN$$, $$PN$$ - ключ.
- 2) $$Y(Y\nrightarrow X)$$: $$PF, PC, PFPC$$
- 3) рассматриваем:
- а) $$Y = PF$$, $$H\notin Y$$: $$PC$$
- $$PF\rightarrow^? PC$$ нет
- $$(PF)^+ = PF$$, $$PC\notin (PF)^+$$
- б) $$Y = PC$$, $$H\notin Y$$: $$PF$$
- $$PC\rightarrow^? PF$$ нет
- $$(PC)^+ = PC$$, $$PF\notin (PC)^+$$
- а) $$Y = PF$$, $$H\notin Y$$: $$PC$$
Таким образом, не удалось подобрать необходимую тройку, значит таблица находится в 3НФ.
Таблица SP
Ищем тройку:
- 1) $$X = PN SN$$, так как $$SN PN\rightarrow kol$$
- 2) подберём $$Y$$, для которого $$X\rightarrow Y$$, $$Y\rightarrow X$$, $$Y(Y\nrightarrow X)$$: $$kol$$
- $$(kol)^+ = kol$$, $$PNSN\nsubseteq kol$$, $$kol\nrightarrow SN$$
- 3) $$Y = kol$$ - нельзя подобрать непервичный атрибут $$H$$: $$H\notin Y$$
Таким образом, не удалось подобрать необходимую тройку, значит таблица находится в 3НФ.
Задача №2
Доказать, что эти две подсхемы $$(R_1, R_2, R_3, R_4)$$ и $$(R_4, R_5)$$ обладают соединением без потерь, и запрос на соединение выполнится правильно.
Ещё раз ФЗ: $$F = (A\rightarrow C, B\rightarrow E, C\rightarrow F, D\rightarrow C)$$
Первая подсхема
Подсхема $$(R_1, R_2, R_3, R_4)$$:
A | B | C | E | F | |
---|---|---|---|---|---|
$$R_1$$ | $$a$$ | $$b_1$$ | $$a$$ | $$b_1$$ | $$b_1$$ |
$$R_2$$ | $$b_2$$ | $$a$$ | $$b_2$$ | $$a$$ | $$b_2$$ |
$$R_3$$ | $$a$$ | $$a$$ | $$b_3$$ | $$b_3$$ | $$b_3$$ |
$$R_4$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$b_4$$ | $$a$$ |
A | B | C | E | F | |
---|---|---|---|---|---|
$$R_1$$ | $$a$$ | $$b_1$$ | $$a$$ | $$b_1$$ | $$a$$ |
$$R_2$$ | $$b_2$$ | $$a$$ | $$b_2$$ | $$a$$ | $$b_2$$ |
$$R_3$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ |
$$R_4$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$b_4$$ | $$a$$ |
Получили строку, сплошь состоящую из $$a$$, значит подсхема $$(R_1, R_2, R_3, R_4)$$ обладает свойством соединения без потерь.
SELECT *
FROM R1, R2, R3, R4
WHERE R1.A = R2.A
AND R3.B = R2.B
AND R1.C = R4.C
Строим проекции:
$$r_1 = \Pi_{R_1}(r)$$
A | C | |
---|---|---|
$$r_1$$ | $$a_1$$ | $$c_1$$ |
$$a_2$$ | $$c_1$$ |
$$r_2 = \Pi_{R_2}(r)$$
B | E | |
---|---|---|
$$r_2$$ | $$b_1$$ | $$e_1$$ |
$$b_2$$ | $$e_2$$ |
$$r_3 = \Pi_{R_3}(r)$$
A | B | |
---|---|---|
$$r_3$$ | $$a_1$$ | $$b_1$$ |
$$a_2$$ | $$b_2$$ |
$$r_4 = \Pi_{R_4}(r)$$
C | F | |
---|---|---|
$$r_4$$ | $$c_1$$ | $$f_1$$ |
Теперь соединения:
$$t_1 = r_1 \bowtie_A r_3$$
A | B | C | |
---|---|---|---|
$$t_1$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ |
$$a_2$$ | $$b_2$$ | $$c_1$$ |
$$t_2 = t_1 \bowtie_B r_2$$
A | B | C | E | |
---|---|---|---|---|
$$t_2$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ | $$e_1$$ |
$$a_2$$ | $$b_2$$ | $$c_1$$ | $$e_2$$ |
$$t_3 = t_2 \bowtie_C r_4$$
A | B | C | E | F | |
---|---|---|---|---|---|
$$t_3$$ | $$a_1$$ | $$b_1$$ | $$c_1$$ | $$e_1$$ | $$f_1$$ |
$$a_2$$ | $$b_2$$ | $$c_1$$ | $$e_2$$ | $$f_1$$ |
Соединение выполнилось верно.
Вторая подсхема
Подсхема $$(R_4, R_5)$$:
C | D | F | |
---|---|---|---|
$$R_4$$ | $$a$$ | $$b_4$$ | $$a$$ |
$$R_5$$ | $$a$$ | $$a$$ | $$b_5$$ |
C | D | F | |
---|---|---|---|
$$R_4$$ | $$a$$ | $$a$$ | $$a$$ |
$$R_5$$ | $$a$$ | $$a$$ | $$a$$ |
Получили строку, сплошь состоящую из $$a$$, значит подсхема $$(R_4, R_5)$$ обладает свойством соединения без потерь.
SELECT *
FROM R4, R5
WHERE R4.C = R5.C
Строим проекции:
$$r_4 = \Pi_{R_4}(r)$$
C | F | |
---|---|---|
$$r_4$$ | $$c_1$$ | $$f_1$$ |
$$r_5 = \Pi_{R_5}(r)$$
D | C | |
---|---|---|
$$r_5$$ | $$d_1$$ | $$c_1$$ |
$$d_2$$ | $$c_1$$ |
Теперь соединение:
$$t_1 = r_4 \bowtie_C r_5$$
C | D | F | |
---|---|---|---|
$$t_1$$ | $$c_1$$ | $$d_1$$ | $$f_1$$ |
$$c_1$$ | $$d_2$$ | $$f_1$$ |
Соединение выполнилось верно.
Задача №3
Как минимальным образом изменить схему БД из примера 2, чтобы она обладала свойством соединения без потерь (чтобы запрос на соединение 5 таблиц выполнялся правильно).
Изменяем схему:
Однако, это не самый минимальный способ, потому что мы ввели новую ФЗ. Можно было $$D$$ добавить в ключ, тогда связь была бы идентифицирующая.
Но так тоже можно.
Теперь:
A | B | C | D | E | F | |
---|---|---|---|---|---|---|
$$R_1$$ | $$a$$ | $$b_1$$ | $$a$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ |
$$R_2$$ | $$b_2$$ | $$a$$ | $$b_2$$ | $$b_2$$ | $$a$$ | $$b_2$$ |
$$R_3$$ | $$a$$ | $$a$$ | $$b_3$$ | $$a$$ | $$b_3$$ | $$b_3$$ |
$$R_4$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$b_4$$ | $$b_4$$ | $$a$$ |
$$R_5$$ | $$b_5$$ | $$b_5$$ | $$a$$ | $$a$$ | $$b_5$$ | $$b_5$$ |
A | B | C | D | E | F | |
---|---|---|---|---|---|---|
$$R_1$$ | $$a$$ | $$b_1$$ | $$a$$ | $$b_1$$ | $$b_1$$ | $$a$$ |
$$R_2$$ | $$b_2$$ | $$a$$ | $$b_2$$ | $$b_2$$ | $$a$$ | $$b_2$$ |
$$R_3$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ |
$$R_4$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$b_4$$ | $$b_4$$ | $$a$$ |
$$R_5$$ | $$b_5$$ | $$b_5$$ | $$a$$ | $$a$$ | $$b_5$$ | $$a$$ |
Получили строку, сплошь состоящую из $$a$$, значит схема обладает свойством соединения без потерь.
Задача №4
Задана универсальная схема отношений:
$$R = (A, B, C, D, E, K, V, S, X, G)$$
Задано множество ФЗ:
$$F = (A\rightarrow BCDV, K\rightarrow D, V\rightarrow SX, V\rightarrow G, XG\rightarrow KEV, VX\rightarrow G)$$
Задана схема БД:
$$\rho = (AKE, ABCX, AVGX, VSDG)$$
Обладает ли эта схема БД свойством соединения без потерь и свойством сохранения ФЗ.
Соединение без потерь
$$\rho = (AKE, ABCX, AVGX, VSDG)$$
$$F = (A\rightarrow BCDV, K\rightarrow D, V\rightarrow SX, V\rightarrow G, XG\rightarrow KEV, VX\rightarrow D)$$
$$A$$ | $$B$$ | $$C$$ | $$D$$ | $$E$$ | $$K$$ | $$V$$ | $$S$$ | $$X$$ | $$G$$ | |
---|---|---|---|---|---|---|---|---|---|---|
$$AKE$$ | $$a$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ | $$a$$ | $$a$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ | $$b_1$$ |
$$ABCX$$ | $$a$$ | $$a$$ | $$a$$ | $$b_2$$ | $$b_2$$ | $$b_2$$ | $$b_2$$ | $$b_2$$ | $$a$$ | $$b_2$$ |
$$AVGX$$ | $$a$$ | $$b_3$$ | $$b_3$$ | $$b_3$$ | $$b_3$$ | $$b_3$$ | $$a$$ | $$b_3$$ | $$a$$ | $$a$$ |
$$VSDG$$ | $$b_4$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$a$$ | $$b_4$$ | $$a$$ |
$$A$$ | $$B$$ | $$C$$ | $$D$$ | $$E$$ | $$K$$ | $$V$$ | $$S$$ | $$X$$ | $$G$$ | |
---|---|---|---|---|---|---|---|---|---|---|
$$AKE$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ |
$$ABCX$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$b_2$$ | $$b_2$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ |
$$AVGX$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ | $$b_3$$ | $$b_3$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ |
$$VSDG$$ | $$b_4$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$b_4$$ | $$b_4$$ | $$a$$ | $$a$$ | $$a$$ | $$a$$ |
Получили строку, сплошь состоящую из $$a$$, значит $$\rho$$ обладает соединением без потерь.
Сохранение ФЗ
1-4)
- $$H = \varnothing$$
- $$УНП = A\rightarrow ABCDVSXGKE, K\rightarrow KD, V\rightarrow VSXGKED, XG\rightarrow XGKEVDS, VX\rightarrow VXDSGEK)$$
- $$H = (A\rightarrow S, K\rightarrow D, V\rightarrow KE, XG\rightarrow KEDS, VX\rightarrow DSEK)$$
5)
- $$H\neq\varnothing$$
6)
- $$H\in^? (A\rightarrow BCV, V\rightarrow SXG)$$ нет
$$A\rightarrow DS$$, $$A^+ = ABCVSXG$$
$$DS\notin ABCVSXG$$, значит $$\rho$$ не обладает сохранением ФЗ.