ТОРА (9) - Лекция №3 - Хорошая схема БД - Соединение без потерь: различия между версиями
ILobster (обсуждение | вклад) Нет описания правки |
ILobster (обсуждение | вклад) мНет описания правки |
||
Строка 1: | Строка 1: | ||
Пусть | Пусть $F$ и $G$ - два множества ФЗ. | ||
$G$ называется ''покрытием'' $F$, если имеет место равенство $G^+ = F^+$ | |||
Существуют различные виды покрытий. Но мы рассмотрим только один - ''условно-неизбыточное покрытие''. | Существуют различные виды покрытий. Но мы рассмотрим только один - ''условно-неизбыточное покрытие''. | ||
Строка 7: | Строка 7: | ||
== Алгоритм построение условно-неизбыточного покрытия == | == Алгоритм построение условно-неизбыточного покрытия == | ||
1) если в множестве ФЗ | 1) если в множестве ФЗ $F$ встречаются ФЗ с одинаковой левой частью $X$, то следует объединить эти ФЗ в одну ФЗ. Это следует из аксиомы объединения. Получившееся множество ФЗ обозначим $G$; | ||
2) для каждой ФЗ | 2) для каждой ФЗ $X\rightarrow Y$ из $G$ заменить её на $X\rightarrow X^+ - X$; | ||
После выполнения 1) и 2) получаем замыкание | После выполнения 1) и 2) получаем замыкание $G^+ = F$ | ||
=== Доказательство === | === Доказательство === | ||
Строка 17: | Строка 17: | ||
1) | 1) | ||
:если ФЗ | :если ФЗ $X\rightarrow Y\in F$, то эта ФЗ принадежит $G^+$, а из этого следует, что $Y \subseteq X^+$ | ||
:По построению G имеет место ФЗ: | :По построению G имеет место ФЗ: $X\rightarrow X^+ - X$ | ||
:Пополним эту ФЗ: | :Пополним эту ФЗ: $X\rightarrow (X^+ - X)\bigcup X = X^+$ | ||
:Теперь по первой аксиоме Армстронга имеем | :Теперь по первой аксиоме Армстронга имеем $X^+\rightarrow Y$ | ||
:Значит, | :Значит, $X\rightarrow Y \in G^+$, по третьей аксиоме Армстронга. | ||
2) | 2) | ||
: | :$X\rightarrow Y \in G$, $X\rightarrow Y \in F^+$ | ||
: | :$Y = X^+ - X$ | ||
: | :$X\rightarrow X^+$ (по определению) | ||
: | :$X^+\rightarrow X^+ - X$ (1 аксиома Армстронга) | ||
: | :$X^+\rightarrow X^+ - X = Y$ (3 аксимома Армстронга) | ||
: | :$X^+\rightarrow Y \in F^+$ | ||
=== Пример === | === Пример === | ||
УСО: | УСО: $R = (A, B, C)$ | ||
Множество ФЗ: | Множество ФЗ: $F = (A\rightarrow B, B\rightarrow A, C\rightarrow A, A\rightarrow C, B\rightarrow C)$ | ||
1) | 1) $G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow A$ | ||
2) | 2) | ||
$A^+ = ABC$, $A^+ - A = BC$ | |||
$B^+ = BAC$, $B^+ - B = AC$ | |||
$C^+ = CAB$, $C^+ - C = AB$ | |||
Тогда | Тогда $G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow AB)$ будет являться УНП. | ||
== Свойства "хорошей" схемы БД == | == Свойства "хорошей" схемы БД == | ||
Строка 73: | Строка 73: | ||
=== Соединение без потерь === | === Соединение без потерь === | ||
Пусть | Пусть $\rho = (R_1 ... R_n)$ - схема БД. Она будет обладать свойствоем соединения без потерь, если для любого экземпляра отношения $r$ из $R$ справедливо равенство: $r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie ... \bowtie \Pi_{R_n}(r)$, где $\Pi_{R_i}(r)$ - это проекция экземпляра отношения $r$ на множество атрибутов $R_i$ | ||
==== Пример БД, не обладающей свойством соединения без потерь ==== | ==== Пример БД, не обладающей свойством соединения без потерь ==== | ||
$R = (A, B, C)$ | |||
$\rho = (AB, BC) = (R_1, R_2)$ | |||
$F = (A\rightarrow B)$ | |||
Достаточно привести пример экземпляра | Достаточно привести пример экземпляра $r$, для которого равенство не выполняется: | ||
{| class="wikitable" | {| class="wikitable" | ||
! !! A !! B !! C | ! !! A !! B !! C | ||
|- align="center" | |- align="center" | ||
| rowspan="2" | | | rowspan="2" | $r$ || $a_1$ || $b_1$ || $c_1$ | ||
|- align="center" | |- align="center" | ||
| | | $a_2$ || $b_1$ || $c_2$ | ||
|} | |} | ||
Строка 98: | Строка 98: | ||
! !! A !! B | ! !! A !! B | ||
|- align="center" | |- align="center" | ||
| rowspan="2" | | | rowspan="2" | $\Pi_{R_1}(r)$ || $a_1$ || $b_1$ | ||
|- align="center" | |- align="center" | ||
| | | $a_2$ || $b_1$ | ||
|} | |} | ||
| | | | ||
Строка 108: | Строка 108: | ||
! !! A !! B | ! !! A !! B | ||
|- align="center" | |- align="center" | ||
| rowspan="2" | | | rowspan="2" | $\Pi_{R_2}(r)$ || $b_1$ || $c_1$ | ||
|- align="center" | |- align="center" | ||
| | | $b_1$ || $c_2$ | ||
|} | |} | ||
|} | |} | ||
Полученное соединение не будет равняться | Полученное соединение не будет равняться $r$: | ||
{| class="wikitable" | {| class="wikitable" | ||
! !! A !! B !! C | ! !! A !! B !! C | ||
|- align="center" | |- align="center" | ||
| rowspan="4" | | | rowspan="4" | $\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)$ || $a_1$ || $b_1$ || $c_1$ | ||
|- align="center" bgcolor="#FFB6C1" | |- align="center" bgcolor="#FFB6C1" | ||
| | | $a_1$ || $b_1$ || $c_2$ | ||
|- align="center" bgcolor="#FFB6C1" | |- align="center" bgcolor="#FFB6C1" | ||
| | | $a_2$ || $b_1$ || $c_1$ | ||
|- align="center" | |- align="center" | ||
| | | $a_2$ || $b_1$ || $c_2$ | ||
|} | |} | ||
Строка 132: | Строка 132: | ||
==== Пример БД, обладающей свойством соединения без потерь ==== | ==== Пример БД, обладающей свойством соединения без потерь ==== | ||
$R = (A, B, C)$ | |||
$\rho = (AB, AC) = (R_1, R_2)$ | |||
$F = (A\rightarrow B)$ | |||
Возьмём тот же экземпляр: | Возьмём тот же экземпляр: | ||
Строка 143: | Строка 143: | ||
! !! A !! B !! C | ! !! A !! B !! C | ||
|- align="center" | |- align="center" | ||
| rowspan="2" | | | rowspan="2" | $r$ || $a_1$ || $b_1$ || $c_1$ | ||
|- align="center" | |- align="center" | ||
| | | $a_2$ || $b_1$ || $c_2$ | ||
|} | |} | ||
Строка 153: | Строка 153: | ||
! !! A !! B | ! !! A !! B | ||
|- align="center" | |- align="center" | ||
| rowspan="2" | | | rowspan="2" | $\Pi_{R_1}(r)$ || $a_1$ || $b_1$ | ||
|- align="center" | |- align="center" | ||
| | | $a_2$ || $b_1$ | ||
|} | |} | ||
| | | | ||
Строка 163: | Строка 163: | ||
! !! A !! B | ! !! A !! B | ||
|- align="center" | |- align="center" | ||
| rowspan="2" | | | rowspan="2" | $\Pi_{R_2}(r)$ || $a_1$ || $c_1$ | ||
|- align="center" | |- align="center" | ||
| | | $a_2$ || $c_2$ | ||
|} | |} | ||
|} | |} | ||
Полученное соединение будет равняться | Полученное соединение будет равняться $r$: | ||
{| class="wikitable" | {| class="wikitable" | ||
! !! A !! B !! C | ! !! A !! B !! C | ||
|- align="center" | |- align="center" | ||
| rowspan="2" | | | rowspan="2" | $\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)$ || $a_1$ || $b_1$ || $c_1$ | ||
|- align="center" | |- align="center" | ||
| | | $a_2$ || $b_1$ || $c_2$ | ||
|} | |} | ||
Строка 183: | Строка 183: | ||
==== Алгоритм проверки схемы БД на свойство соединения без потерь ==== | ==== Алгоритм проверки схемы БД на свойство соединения без потерь ==== | ||
$\rho = (R_1 ... R_n)$ | |||
$R = (A_1 ... A_n)$ | |||
1) построить таблицу T: | 1) построить таблицу T: | ||
{| class="wikitable" | {| class="wikitable" | ||
! !! | ! !! $A_1$ || $A_2$ || ... || $A_k$ | ||
|- align="center" | |- align="center" | ||
! | ! $R_1$ | ||
| || || || | | || || || | ||
|- align="center" | |- align="center" | ||
! | ! $R_2$ | ||
| || || || | | || || || | ||
|- align="center" | |- align="center" | ||
Строка 201: | Строка 201: | ||
| || || || | | || || || | ||
|- align="center" | |- align="center" | ||
! | ! $R_n$ | ||
| || || || | | || || || | ||
|} | |} | ||
И заполнить таблицу T по правилу: если | И заполнить таблицу T по правилу: если $A_j \in R_i$, то $T_{ij}=a$, иначе $T_{ij}=b_i$ | ||
2) изменить таблицу T - циклически просматривать ФЗ из | 2) изменить таблицу T - циклически просматривать ФЗ из $F$ в любом порядке, и для очередной ФЗ $X\rightarrow Y \in F$ выполнить следующие действия: | ||
* найти в таблице T строки, совпадающие по атрибутам | * найти в таблице T строки, совпадающие по атрибутам $X$ (по левой части); | ||
* если хотя бы в одной такой строке значение атрибута | * если хотя бы в одной такой строке значение атрибута $A_m \in Y = a$, то во всех найденных строках присвоить $A_m = a$, иначе присвоить $A_m = b_i$ ($i$ - номер одной из найденных строк, $b_i$ должно быть одинаково во всех указанных строках); | ||
* выполнить предыдущие два пункта для всех атрибутов | * выполнить предыдущие два пункта для всех атрибутов $A_l \in Y$; | ||
* выполнить предыдущие три пункта для всех ФЗ из | * выполнить предыдущие три пункта для всех ФЗ из $F$, циклически их просматривая. | ||
3) алгоритм останавливается, если при очередном просмотре ФЗ из | 3) алгоритм останавливается, если при очередном просмотре ФЗ из $F$: | ||
* не произошло никаких изменений в таблице T; | * не произошло никаких изменений в таблице T; | ||
* какая-нибудь строка в T не стала состоять сплошь из символов | * какая-нибудь строка в T не стала состоять сплошь из символов $a$ (наличие такой строки и говорит о выполнении свойства соединения без потерь). | ||
===== Пример ===== | ===== Пример ===== | ||
Пусть | Пусть $R = (A, B, C)$ | ||
$\rho = (AB, AC) = (R_1, R_2)$ | |||
$F = (A\rightarrow B)$ | |||
Доказать, что | Доказать, что $\rho$ обладает свойством соединения без потерь. | ||
1) | 1) | ||
Строка 233: | Строка 233: | ||
|- align="center" | |- align="center" | ||
! AB | ! AB | ||
| | | $a$ || $a$ || $b_1$ | ||
|- align="center" | |- align="center" | ||
! BC | ! BC | ||
| | | $a$ || $b_2$ || $a$ | ||
|} | |} | ||
Строка 247: | Строка 247: | ||
|- align="center" | |- align="center" | ||
! AB | ! AB | ||
| | | $a$ || $a$ || $b_1$ | ||
|- align="center" | |- align="center" | ||
! BC | ! BC | ||
| | | $a$ || $b_2$ || $a$ | ||
|} | |} | ||
| | | | ||
Строка 259: | Строка 259: | ||
|- align="center" | |- align="center" | ||
! AB | ! AB | ||
| | | $a$ || $a$ || $b_1$ | ||
|- align="center" | |- align="center" | ||
! BC | ! BC | ||
| | | $a$ || bgcolor="lime" | $a$ || $a$ | ||
|} | |} | ||
|} | |} | ||
Получили строку, сплошь состоящую из | Получили строку, сплошь состоящую из $a$. Значит $\rho$ обладает свойством соединения без потерь. | ||
===== Другой пример ===== | ===== Другой пример ===== | ||
Пусть | Пусть $R = (A, B, C, D, E, F, P, S)$ | ||
$\rho = (AB, ACDPS, BCPS, DEF) = (R_1, R_2, R_3, R_4)$ | |||
$F = (B\rightarrow C, D\rightarrow EF, B\rightarrow PS, A\rightarrow CDPS, AP\rightarrow S)$ | |||
Доказать, что | Доказать, что $\rho$ обладает свойством соединения без потерь. | ||
1) | 1) | ||
Строка 284: | Строка 284: | ||
|- align="center" | |- align="center" | ||
! AB | ! AB | ||
| | | $a$ || $a$ || $b_1$ || $b_1$ || $b_1$ || $b_1$ || $b_1$ || $b_1$ | ||
|- align="center" | |- align="center" | ||
! ACDPS | ! ACDPS | ||
| | | $a$ || $b_2$ || $a$ || $a$ || $b_2$ || $b_2$ || $a$ || $a$ | ||
|- align="center" | |- align="center" | ||
! BCPS | ! BCPS | ||
| | | $b_3$ || $a$ || $a$ || $b_3$ || $b_3$ || $b_3$ || $a$ || $a$ | ||
|- align="center" | |- align="center" | ||
! DEF | ! DEF | ||
| | | $b_4$ || $b_4$ || $b_4$ || $a$ || $a$ || $a$ || $b_4$ || $b_4$ | ||
|} | |} | ||
Строка 304: | Строка 304: | ||
|- align="center" | |- align="center" | ||
! AB | ! AB | ||
| | | $a$ || $a$ || bgcolor="lime" | $a$ || bgcolor="lime" | $a$ || $b_1$ || $b_1$ || bgcolor="lime" | $a$ || bgcolor="lime" | $a$ | ||
|- align="center" | |- align="center" | ||
! ACDPS | ! ACDPS | ||
| | | $a$ || $b_2$ || $a$ || $a$ || bgcolor="lime" | $a$ || bgcolor="lime" | $a$ || $a$ || $a$ | ||
|- align="center" | |- align="center" | ||
! BCPS | ! BCPS | ||
| | | $b_3$ || $a$ || $a$ || $b_3$ || $b_3$ || $b_3$ || $a$ || $a$ | ||
|- align="center" | |- align="center" | ||
! DEF | ! DEF | ||
| | | $b_4$ || $b_4$ || $b_4$ || $a$ || $a$ || $a$ || $b_4$ || $b_4$ | ||
|} | |} | ||
Строка 322: | Строка 322: | ||
|- align="center" | |- align="center" | ||
! AB | ! AB | ||
| | | $a$ || $a$ || bgcolor="lime" | $a$ || bgcolor="lime" | $a$ || bgcolor="#32CD32" | $a$ || bgcolor="#32CD32" | $a$ || bgcolor="lime" | $a$ || bgcolor="lime" | $a$ | ||
|- align="center" | |- align="center" | ||
! ACDPS | ! ACDPS | ||
| | | $a$ || $b_2$ || $a$ || $a$ || bgcolor="lime" | $a$ || bgcolor="lime" | $a$ || $a$ || $a$ | ||
|- align="center" | |- align="center" | ||
! BCPS | ! BCPS | ||
| | | $b_3$ || $a$ || $a$ || $b_3$ || $b_3$ || $b_3$ || $a$ || $a$ | ||
|- align="center" | |- align="center" | ||
! DEF | ! DEF | ||
| | | $b_4$ || $b_4$ || $b_4$ || $a$ || $a$ || $a$ || $b_4$ || $b_4$ | ||
|} | |} | ||
Вот и получили строку, сплошь состоящую из | Вот и получили строку, сплошь состоящую из $a$. Значит $\rho$ обладает свойством соединения без потерь. | ||
[[Категория:Теоретические основы реляционной алгебры (9 семестр)]] | [[Категория:Теоретические основы реляционной алгебры (9 семестр)]] | ||
[[Категория:Конспекты лекций и семинаров]] | [[Категория:Конспекты лекций и семинаров]] |
Версия от 01:58, 20 сентября 2012
Пусть $F$ и $G$ - два множества ФЗ.
$G$ называется покрытием $F$, если имеет место равенство $G^+ = F^+$
Существуют различные виды покрытий. Но мы рассмотрим только один - условно-неизбыточное покрытие.
Алгоритм построение условно-неизбыточного покрытия
1) если в множестве ФЗ $F$ встречаются ФЗ с одинаковой левой частью $X$, то следует объединить эти ФЗ в одну ФЗ. Это следует из аксиомы объединения. Получившееся множество ФЗ обозначим $G$;
2) для каждой ФЗ $X\rightarrow Y$ из $G$ заменить её на $X\rightarrow X^+ - X$;
После выполнения 1) и 2) получаем замыкание $G^+ = F$
Доказательство
1)
- если ФЗ $X\rightarrow Y\in F$, то эта ФЗ принадежит $G^+$, а из этого следует, что $Y \subseteq X^+$
- По построению G имеет место ФЗ: $X\rightarrow X^+ - X$
- Пополним эту ФЗ: $X\rightarrow (X^+ - X)\bigcup X = X^+$
- Теперь по первой аксиоме Армстронга имеем $X^+\rightarrow Y$
- Значит, $X\rightarrow Y \in G^+$, по третьей аксиоме Армстронга.
2)
- $X\rightarrow Y \in G$, $X\rightarrow Y \in F^+$
- $Y = X^+ - X$
- $X\rightarrow X^+$ (по определению)
- $X^+\rightarrow X^+ - X$ (1 аксиома Армстронга)
- $X^+\rightarrow X^+ - X = Y$ (3 аксимома Армстронга)
- $X^+\rightarrow Y \in F^+$
Пример
УСО: $R = (A, B, C)$
Множество ФЗ: $F = (A\rightarrow B, B\rightarrow A, C\rightarrow A, A\rightarrow C, B\rightarrow C)$
1) $G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow A$
2)
$A^+ = ABC$, $A^+ - A = BC$
$B^+ = BAC$, $B^+ - B = AC$
$C^+ = CAB$, $C^+ - C = AB$
Тогда $G = (A\rightarrow BC, B\rightarrow AC, C\rightarrow AB)$ будет являться УНП.
Свойства "хорошей" схемы БД
"Хорошая", но не оптимальная. Должна обладать следующими свойствами:
- соединение без потерь;
- сохранение ФЗ;
- каждая схема отношений в этой БД находится в 3НФ. Наличие этого свойства обеспечивает отсутствие в схемах отношений следующих аномалий:
- избыточность;
- потенциальная противоречивсть;
- аномалия обновления;
- аномалия удаления.
Соединение без потерь
Пусть $\rho = (R_1 ... R_n)$ - схема БД. Она будет обладать свойствоем соединения без потерь, если для любого экземпляра отношения $r$ из $R$ справедливо равенство: $r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie ... \bowtie \Pi_{R_n}(r)$, где $\Pi_{R_i}(r)$ - это проекция экземпляра отношения $r$ на множество атрибутов $R_i$
Пример БД, не обладающей свойством соединения без потерь
$R = (A, B, C)$
$\rho = (AB, BC) = (R_1, R_2)$
$F = (A\rightarrow B)$
Достаточно привести пример экземпляра $r$, для которого равенство не выполняется:
A | B | C | |
---|---|---|---|
$r$ | $a_1$ | $b_1$ | $c_1$ |
$a_2$ | $b_1$ | $c_2$ |
|
|
Полученное соединение не будет равняться $r$:
A | B | C | |
---|---|---|---|
$\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)$ | $a_1$ | $b_1$ | $c_1$ |
$a_1$ | $b_1$ | $c_2$ | |
$a_2$ | $b_1$ | $c_1$ | |
$a_2$ | $b_1$ | $c_2$ |
Этот пример показывает, что при неправильном построении БД запросы могут выдавать неправильный результат.
Пример БД, обладающей свойством соединения без потерь
$R = (A, B, C)$
$\rho = (AB, AC) = (R_1, R_2)$
$F = (A\rightarrow B)$
Возьмём тот же экземпляр:
A | B | C | |
---|---|---|---|
$r$ | $a_1$ | $b_1$ | $c_1$ |
$a_2$ | $b_1$ | $c_2$ |
|
|
Полученное соединение будет равняться $r$:
A | B | C | |
---|---|---|---|
$\Pi_{R_1}(r) \bowtie \Pi_{R_2}(r)$ | $a_1$ | $b_1$ | $c_1$ |
$a_2$ | $b_1$ | $c_2$ |
Но это не доказательство, а только один пример, просто чтобы показать, в чём разница.
Алгоритм проверки схемы БД на свойство соединения без потерь
$\rho = (R_1 ... R_n)$
$R = (A_1 ... A_n)$
1) построить таблицу T:
$A_1$ | $A_2$ | ... | $A_k$ | |
---|---|---|---|---|
$R_1$ | ||||
$R_2$ | ||||
... | ||||
$R_n$ |
И заполнить таблицу T по правилу: если $A_j \in R_i$, то $T_{ij}=a$, иначе $T_{ij}=b_i$
2) изменить таблицу T - циклически просматривать ФЗ из $F$ в любом порядке, и для очередной ФЗ $X\rightarrow Y \in F$ выполнить следующие действия:
- найти в таблице T строки, совпадающие по атрибутам $X$ (по левой части);
- если хотя бы в одной такой строке значение атрибута $A_m \in Y = a$, то во всех найденных строках присвоить $A_m = a$, иначе присвоить $A_m = b_i$ ($i$ - номер одной из найденных строк, $b_i$ должно быть одинаково во всех указанных строках);
- выполнить предыдущие два пункта для всех атрибутов $A_l \in Y$;
- выполнить предыдущие три пункта для всех ФЗ из $F$, циклически их просматривая.
3) алгоритм останавливается, если при очередном просмотре ФЗ из $F$:
- не произошло никаких изменений в таблице T;
- какая-нибудь строка в T не стала состоять сплошь из символов $a$ (наличие такой строки и говорит о выполнении свойства соединения без потерь).
Пример
Пусть $R = (A, B, C)$
$\rho = (AB, AC) = (R_1, R_2)$
$F = (A\rightarrow B)$
Доказать, что $\rho$ обладает свойством соединения без потерь.
1)
A | B | C | |
---|---|---|---|
AB | $a$ | $a$ | $b_1$ |
BC | $a$ | $b_2$ | $a$ |
2)
|
|
Получили строку, сплошь состоящую из $a$. Значит $\rho$ обладает свойством соединения без потерь.
Другой пример
Пусть $R = (A, B, C, D, E, F, P, S)$
$\rho = (AB, ACDPS, BCPS, DEF) = (R_1, R_2, R_3, R_4)$
$F = (B\rightarrow C, D\rightarrow EF, B\rightarrow PS, A\rightarrow CDPS, AP\rightarrow S)$
Доказать, что $\rho$ обладает свойством соединения без потерь.
1)
A | B | C | D | E | F | P | S | |
---|---|---|---|---|---|---|---|---|
AB | $a$ | $a$ | $b_1$ | $b_1$ | $b_1$ | $b_1$ | $b_1$ | $b_1$ |
ACDPS | $a$ | $b_2$ | $a$ | $a$ | $b_2$ | $b_2$ | $a$ | $a$ |
BCPS | $b_3$ | $a$ | $a$ | $b_3$ | $b_3$ | $b_3$ | $a$ | $a$ |
DEF | $b_4$ | $b_4$ | $b_4$ | $a$ | $a$ | $a$ | $b_4$ | $b_4$ |
2)
первый просмотр:
A | B | C | D | E | F | P | S | |
---|---|---|---|---|---|---|---|---|
AB | $a$ | $a$ | $a$ | $a$ | $b_1$ | $b_1$ | $a$ | $a$ |
ACDPS | $a$ | $b_2$ | $a$ | $a$ | $a$ | $a$ | $a$ | $a$ |
BCPS | $b_3$ | $a$ | $a$ | $b_3$ | $b_3$ | $b_3$ | $a$ | $a$ |
DEF | $b_4$ | $b_4$ | $b_4$ | $a$ | $a$ | $a$ | $b_4$ | $b_4$ |
второй просмотр:
A | B | C | D | E | F | P | S | |
---|---|---|---|---|---|---|---|---|
AB | $a$ | $a$ | $a$ | $a$ | $a$ | $a$ | $a$ | $a$ |
ACDPS | $a$ | $b_2$ | $a$ | $a$ | $a$ | $a$ | $a$ | $a$ |
BCPS | $b_3$ | $a$ | $a$ | $b_3$ | $b_3$ | $b_3$ | $a$ | $a$ |
DEF | $b_4$ | $b_4$ | $b_4$ | $a$ | $a$ | $a$ | $b_4$ | $b_4$ |
Вот и получили строку, сплошь состоящую из $a$. Значит $\rho$ обладает свойством соединения без потерь.