крытием  или  элементарным  функциональным  базисом

 
ношение R для R, удовлетворяющее F, может быть представлено в виде 
),
(
)
(
)
(
2
1
R
R
R
R
k
R
R
R
π
><
><
π
><
π
=
K
 
т. е. R является естественным соединением его проекций на все R
i
. Ясно, 
что  свойство  соединения  без  потерь  весьма  желательно,  поскольку  в 
этом случае может быть восстановлено исходное отношение. 
Рассмотрим основные свойства отображения проекция-соединение. 
Если 
ρ = (R
1
, R
2
, ..., R
k
), обозначим через M
ρ отображение, которое оп-
ределяется соотношением  
)
(
)
(
)
(
)
(
2
1
R
R
R
R
M
k
R
R
R
π
><
><
π
><
π
=
ρ
K
. 
Таким образом, условие соединения без потерь относительно F может 
быть  выражено  следующим  образом:  для  всех  R,  удовлетворяющих  F,  
R = M
ρ(R). 
Для любой декомпозиции выполняются следующие условия: 
а) R 
⊆ Mρ(R); 
б) если S = M
ρ(R), то 
i
R
R
S
i
=
)
(
π
; 
в) M
ρ(Mρ(R)) = Mρ(R). 
Свойство а) означает, что декомпозиция представляет, вообще говоря, 
некоторое большее по количеству кортежей отношение, чем исходное, и 
если  не  выполнено  условие  соединения  без  потерь,  то  мы  можем  полу-
чить кортежи, которых нет в исходном отношении, что естественно на-
рушает адекватность базы данных. 
Для  проверки  свойства  соединения  без  потерь  можно  использовать 
следующий алгоритм. 
Пусть заданы схема отношения R = ({А
1
, А
2
, ..., A
n
}, F) и декомпозиция 
ρ = (R
1
, R
2
, ..., R
k
), R
i
 = (U
i
), i = 1, 2, ..., k. 
Строим таблицу с n столбцами и k строками, столбец j соответствует 
атрибуту A
j
, а строка i – схеме отношения R
i
. На пересечении строки i и 
столбца j поместим символ A
j
, если A
j
 
∈ U
i
. B противном случае помес-
тим туда символ *. 
Просматриваем  каждую  из  зависимостей  Х 
→  Y.  Рассматривая  зави-
симость Х 
→ Y, изменяем строки, которые совпадают по всем столбцам, 
соответствующим  атрибутам  из  X.  При  обнаружении  двух  таких  строк 
отождествляем  их  символы  в  столбцах,  соответствующих  атрибутам  из 
Y. Если при этом один из символов в одной из строк равен A
j
, а символ 
другой строки в этом же столбце равен *, то заменяем * на A
j
. Повторяем 
просмотр  зависимостей  до  тех  пор,  пока:  либо  некоторая  строка  станет 
равной А
1
, А
2
, ..., А
n
; либо больше изменений в таблице провести нельзя. 
 
34

 
В первом случае декомпозиция 
ρ обладает свойством соединения без по-
терь. Во втором – нет. 
П р и м е р ы 
Пусть  для  схемы  R = ({А
1
,  А
2
,  А
3
,  А
4
,  А
5
}, {А
1
 
→  А
2
;  А
2
 
→  A
3
;  А
3
,  
А
4
 
→ А
5
; А
2
 
→ А
4
}) получена декомпозиция 
ρ = (R
l
, R
2
, R
3
), где 
R
1
 = ({А
1
, А
2
}),  R
2
 = ({А
2
, А
3
, А
4
}), R
3
 = ({А
3
, А
4
, А
5
}).  
Требуется проверить, обладает ли она свойством соединения без потерь. 
Построим следующие таблицы: 
1-я (начальная таблица): 
A
1
A
2
* * * 
* 
A
2
A
3
A
4
* 
* * A
3
A
4
A
5
2-я таблица: 
A
1
A
2
A
3
A
4
* 
* 
A
2
A
3
A
4
A
5
* * A
3
A
4
A
5
3-я таблица: 
A
1
A
2
A
3
A
4
A
5
* 
A
2
A
3
A
4
A
5
* * A
3
A
4
A
5
В последней таблице первая строка представляет собой все A
j
, следо-
вательно, декомпозиция обладает свойством соединения без потерь. 
Теперь пусть для схемы 
R = ({А
1
, А
2
, А
3
, А
4
, А
5
}, {A
1
 
→ A
2
; A
2
 
→ A
3
; A
3
, A
5
 
→ A
4
}) получена де-
композиция 
ρ = (R
l
,  R
2
),  где  R
1
 = ({A
1
,  A
2
});  R
2
 = ({A
2
,  A
3
,  A
4
,  A
5
}). 
Построим следующие таблицы: 
1-я таблица: 
A
1
A
2
* * * 
* 
A
2
A
3
A
4
A
5
2-я таблица: 
A
1
A
2
A
3
* * 
* 
A
2
A
3
A
4
A
5
Больше  никаких  изменений  в  таблице  сделать  нельзя,  и  строку,  со-
держащую только А
i
, мы не получили, значит, декомпозиция в этом слу-
 
35

 
чае не обладает свойством соединения без потерь. 
Справедливо следующее утверждение. 
Если 
ρ = (R
1
(U
1
),  R
2
(U
2
))  –  декомпозиция  R = (U,  F),  то 
ρ  обладает 
свойством  соединения  без  потерь  относительно  F  тогда  и  только  тогда, 
когда ((U
1
 
∩ U
2
) 
→ U
1
 \ U
2
) 
∈ F
+
 или ((U
l
 
∩ U
2
) 
→ U
2
 \ U
l
) 
∈ F
+
. 
Это  утверждение  дает  довольно  простой  способ  проверки  свойства 
соединения без потерь при декомпозиции на две подсхемы. 
4.2.6. Декомпозиции, сохраняющие зависимости 
 
Как  уже  отмечалось,  желательно,  чтобы  декомпозиция  обладала 
свойством соединения без потерь. Это является гарантией того, что лю-
бое отношение, являющееся текущим значением схемы, может быть вос-
становлено из его проекций на подсхемы декомпозиции. Другое важное 
свойство декомпозиции 
ρ = (R
1
, R
2
, ..., R
k
) схемы отношения R заключа-
ется в том, чтобы множество зависимостей F, заданных для R, было вы-
водимым из проекций F на подсхемы R
i
. 
Формально  проекцией F на  множество  атрибутов  Z,  обозначаемой 
π
Z
(F), называется множество зависимостей X 
→ Y в F
+
, таких, что X, Y 
⊆ 
Z.  
Часто  удобнее  вместо 
π
Z
(F)  рассматривать  его  минимальное  покры-
тие. Например, если имеется R = ({A
l
, А
2
, А
3
, А
4
}, {A
l
 
→ A
2
; А
2
 
→ А
3
; A
3
 
→ 
A
4
}), Z = {А
1
, А
3
, А
4
}, то 
π
Z
(F) = {А
1
 
→ A
3
; A
3
 
→ A
4
}. Здесь записано ми-
нимальное покрытие проекции F. 

жүктеу/скачать 2,58 Mb.

Достарыңызбен бөлісу: