Править]Декомпозиция без потерь

Декомпозицией^[1] отношения R называется замена R на совокупность отношений { R ₁, R ₂,..., R_n } такую, что каждое из них есть проекция R, и каждый атрибут R входит хотя бы в одну из проекций декомпозиции.

Например, для отношения R с атрибутами { a, b, c } существуют следующие основные варианты декомпозиции:

· { a }, { b }, { c }

· { a }, { b, c }

· { a, b }, { c }

· { b }, { a, c }

· { a, b }, { b, c }

· { a, b }, { a, c }

· { b, c }, { a, c }

· { a, b }, { b, c }, { a, c }

Рассмотрим теперь отношение R', которое получается в результате операции естественного соединения (NATURAL JOIN), применённой к отношениям, полученным в результате декомпозиции R.

Декомпозиция называется декомпозицией без потерь, если R' в точности совпадает с R.

Неформально говоря, при декомпозиции без потерь отношение «разделяется» на отношения-проекции таким образом, что из полученных проекций возможна «сборка» исходного отношения с помощью операции естественного соединения.

Далеко не всякая декомпозиция является декомпозицией без потерь. Проиллюстрируем это на примере отношения R с атрибутами { a, b, c }, приведённом выше. Пусть отношение R имеет вид:

R
a	b	c
Москва	Россия	столица
Томск	Россия	не столица
Берлин	Германия	столица

Декомпозиция R ₁ = { a }, R ₂ = { b, c } имеет вид:

R 1

a

Москва

Томск

Берлин

R 2
b	c
Россия	столица
Россия	не столица
Германия	столица

Результат операции соединения этих отношений:

R' = R 1 NATURAL JOIN R 2
a	b	c
Москва	Россия	столица
Москва	Россия	не столица
Москва	Германия	столица
Томск	Россия	столица
Томск	Россия	не столица
Томск	Германия	столица
Берлин	Россия	столица
Берлин	Россия	не столица
Берлин	Германия	столица

Очевидно, что R' не совпадает с R, а значит такая декомпозиция не является декомпозицией без потерь. Рассмотрим теперь декомпозицию R ₁ = { a, b }, R ₂ = { a, c }:

R 1
a	b
Москва	Россия
Томск	Россия
Берлин	Германия

R 2
a	c
Москва	столица
Томск	не столица
Берлин	столица

Такая декомпозицией является декомпозицией без потерь, в чём читатель может убедиться самостоятельно.

В некоторых случаях отношение вовсе невозможно декомпозировать без потерь. Существуют также примеры отношений, для которых нельзя выполнить декомпозицию без потерь на две проекции, но которые можно подвергнуть декомпозиции без потерь на три или большее количество проекций^[2].