9: «Метод декомпозиции. Алгоритм метода»

При декомпозиции - одного отношения получаем два или более отношений, каждое из кот. содержит часть атрибутов исходного отношения. В полученных новых отношениях необходимо удалить дубликаты строк, если таковые возникли. Это значит, что декомпозиция отношения -взятие одной или нескольких проекций исходного отношения так, чтобы эти проекции в совокупности содержали (возможно, с повторениями) все атрибуты исходного отношения. Т.е., при декомпозиции не должны теряться атрибуты отношений. Но при декомпозиции также не должны потеряться и сами данные. Данные можно считать не потерянными в том случае, если возможна обратная операция - по декомпозированным отношениям можно восстановить исходное отношение в точности в прежнем виде. Операцией, обратной операции проекции, является операция соединения отношений. Т.к. при восстановлении исходного отношения путем соединения проекций не должны появиться новые атрибуты, то необходимо использовать естественное соединение.

Проекция R[X] отношения R на множество атрибутов X называется собственной, если множество атрибутов X является собственным подмножеством множества атрибутов отношения R (т.е. множество атрибутов X не совпадает с множеством всех атрибутов отношения R).

Собственные проекции R1 и R2 отношения R называются декомпозицией без потерь, если отношение R точно восстанавливается из них при помощи естественного соединения для любого состояния отношения R: R1><R2=R

Теорема (Хеза). Пусть R(A,B,C) является отношением, и A,B,C - атрибуты или множества атрибутов этого отношения. Если имеется функциональная зависимость AB, то проекции R1=R[A,B] и R2=R[A,C] образуют декомпозицию без потерь.

Доказательство. Д-ть, что R1><R2=R для любого состояния отношения R. В левой и правой части равенства стоят множества кортежей, поэтому для доказательства достаточно доказать два включения для двух множеств кортежей: R1><R2R и R1><R2R.

Докажем первое включение. Возьмем произвольный кортеж r=(a,b,c)R. Докажем, что он включается также и в R1><R2. По определению проекции, кортежи r1=(a,b) R1 и r2=(a,c)R2. По определению естественного соединения кортежи r1 и r2, имеющие одинаковое значение a общего атрибута A, будут соединены в процессе естественного соединения в кортеж (a,b,c) R1><R2. Таким образом, включение доказано.

Докажем обратное включение. Возьмем произвольный кортеж r=(a,b,c) R1><R2. Докажем, что он включается также и в R. По определению естественного соединения получим, что в имеются кортежи r1=(a,b) R1 и r2=(a,c)R2. Т.к. R1=R[A,B], то существует некоторое значение c1, такое что кортеж r1=(a,b,c1)R. Аналогично, существует некоторое значение b1, такое что кортеж r2=(a,b1,c)R. Кортежи r1 и r2 имеют одинаковое значение атрибута A, равное a. Из этого, в силу функциональной зависимости AB, следует, что b=b1. Таким образом, кортеж r2=(a,b,c)R. Обратное включение доказано. Теорема доказана. Основной смысл теоремы Хеза заключается в доказательстве того, что при этом не появятся новые кортежи, отсутствовавшие в исходном отношении.

Варианты декомпозиции. 1) если отношение имеет 1 ключ, то оно декомпозируется путем последовательного применения сначала во 2НФ потом в 3НФ. Или путем выделения крайних ФЗ в отдельное отношение, при этом на каждом этапе контролируетчся эквивалентность множеств детерминант и ключей. 2) если отношение имеет несколько ключей, то строится кольцевое покрытие и декомпозиция осуществляется путем выделения каждой СF зависимости в отдельное отношение. 3) если ключей несколько и они пересекаются, то целесообразно применить Теорему Хеза. После завершения декомпозиции целесообразно проверить чтобы все ФЗ были навязаны БД. Если какая-либо схема отношений явл-ся собствнным подмножеством другой схемы отношения, то это отношение является избытосным и подлежит исключению из проекта. Не ключевые атрибуты, т.е. атрибуты которые не являются потенуиальным ключом, или не являются собственным подмножеством, должны хранится не более чем в 1 отношении. Не целесообразно иметь в проекте отношения с обинаковыми потенциальными ключами. Наличие таких отношений свидетельствует о том, что декомпозиция была сделана не на минимальном покрытии.