Декомпозиция без потерь и функциональные зависимости

Прежде чем приступить к изложению подробностей процедуры нормализации, следует обсудить один существенный аспект этой процедуры, а именно – концепцию декомпозиции без потерь. Как отмечалось, процедура нормализации включает разбиение, или декомпозицию, данной переменной-отношения на другие переменные-отношения, причем она должна быть обратимой. Иначе говоря, интерес представляют лишь те операции, которые выполняются без потерь информации. Вопрос происходит ли утрата информации при декомпозиции, тесно связан с концепцией функциональной зависимости.

В качестве примера рассмотрим знакомую переменную-отношение поставщиков без атрибута SNAME. Два возможных варианта проведения ее декомпозиции приведены на рис. 11.2: а и б.

S

S#	STATUS	CITY
S3		Москва
S5		Смоленск

а) SST

S#	STATUS
S3
S5

SC

S#	CITY
S3	Москва
S5	Смоленск

б) SST

S#	STATUS
S3
S5

STC

STATUS	CITY
	Москва
	Смоленск

Рис. 11.2. Переменная-отношение S и два возможных варианта ее декомпозиции

Можно отметить, что первый вариант является декомпозицией без потерь, поскольку информация, содержащаяся в двух новых переменных-отношениях, соответствует информации в исходной переменной-отношении, т.е. при обратном соединении переменных-отношений SST и SC будет получена исходная переменная-отношение S. Однако второй вариант не является декомпозицией без потерь, так как здесь информация утрачивается, поскольку оба поставщика имеют статус 30, но при этом нельзя сказать, кто и где находится.

Возникает вопрос, почему в одном случае идет потеря информации, а в другом – нет. Прежде всего, следует отметить, что процесс, который до сих пор назывался декомпозицией, на самом деле является операцией проекции, т.е. фактически в процессе нормализации оператор декомпозиции есть оператор проекции.

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

Формально: Пусть R1 и R2 являются проекциями некоторой переменной-отношения R, содержащими все атрибуты переменной-отношения R. Какие условия должны быть соблюдены для того, чтобы при обратном соединении проекций R1 и R2 гарантировать получение исходной переменной-отношения R?

Для ответа на этот вопрос необходимо рассмотреть ФЗ. В нашем примере для переменной-отношения S имелось следующее неприводимое множество ФЗ:

S# ® STATUS

S# ® CITY

Можно предположить, что переменная-отношение S равна соединению проекций {S#, STATUS} и {S#, CITY}. И это подтверждается теоремой Хита (Heath).

Теорема Хита. Пусть R{A,B,C} является переменной-отношением, где A, B и C – множества атрибутов этой переменной-отношения. Если R удовлетворяет ФЗ A ® B, то R равна соединению проекций {A, B} и {A, C}.

Дата добавления: 2015-05-09