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

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

В качестве примера рассмотрим уже знакомое отношение поставщиков S с атрибутами {S#, STATUS, CITY} (для упрощения задачи атрибут SNAME в данном случае игнорируется). На рис. 10.3 показан пример записей этого отношения (некоторое подмножество, приводимых ранее значений этого примера) с указанием двух его возможных декомпозиций: (а) и (б).

Внимательно ознакомившись с этими декомпозициями, можно заметить две особенности.

1. 1. В случае (а) информация не утрачивается, поскольку отношения SST и SC все еще содержат данные о том, что поставщик S3 имеет статус 30 и находится в Париже (Paris), а поставщик S5 имеет статус 30 и находится в Афинах (Athens). Иначе говоря, первая декомпозиция действительно является декомпозицией без потерь.

2. 2. В случае (б), наоборот, некоторая информация утрачивается, поскольку оба поставщика имеют статус 30, но при этом нельзя сказать, какой из них в каком городе находится. Иначе говоря, вторая декомпозиция не является декомпозицией без потерь.

Почему получилось так, что одна декомпозиция происходит без потерь, а другая — с потерей информации? Прежде всего, следует отметить, что процесс, который до сих пор назывался "декомпозицией", на самом деле является проектированием, т.е. каждое из показанных на рис. 10.3 отношений— SST, SC и STC— в действительности является проекцией исходного отношения S. Таким образом, оператор декомпозиции в процедуре нормализации фактически является оператором проектирования.

Обратите внимание, что в случае (а) сохранение информации в полном объеме означает, что при обратном соединении отношений SST и SC будет получено исходное отношение S. В случае (б), наоборот, при обратном соединении отношений SST и SC не будет получено исходное отношение S, а это значит, что некоторая информация будет утрачена. (Точнее, в исходном отношении S вместе со всеми кортежами будут содержаться "ложные" кортежи. Поскольку не существует общего метода для различения ложных и подлинных кортежей, информация в этом случае будет утеряна.) Иначе говоря, "обратимость" означает, что исходное отношение равно соединению его проекций. Если оператором декомпозиции в процедуре нормализации является операция проектирования, то обратной операцией должна быть операция соединения (конечно, в смысле естественного соединения по атрибутам с общими именами).

Исходя из сказанного выше, можно задать следующий вопрос. Пусть R1 и R2 — проекции некоторого отношения R, содержащие все атрибуты отношения R. Какие условия должны быть соблюдены для того, чтобы при обратном соединении R1 и R2 гарантировать получение исходного отношения R? Именно для ответа на этот вопрос и возникает необходимость использования функциональных зависимостей. В рассматриваемом примере отношение S удовлетворяет представленному ниже неприводимому множеству Ф3. (Далее в этой главе будет считаться, что Ф3 независимы от времени, т.е. выполняются для всех допустимых значений соответствующего отношения. Подробнее неприводимые множества Ф3 описаны в главе 9.)

При условии, что данное отношение удовлетворяет приведенным ФЗ, можно предположить, что отношение S равно соединению его проекций {S#, STATUS} и {S#, CITY}. И это действительно так, что подтверждается теоремой Хеза (Heath) [10.4].

■ ■ Теорема Хеза. Пусть R { A, В, С } является отношением, где А, В и С — атрибуты этого отношения. Если R удовлетворяет зависимости A ® В, то R равно соединению его проекций { А, В } и { А, С }.

Если обозначить А как S#, В как STATUS, С как CITY, то эта теорема утверждает, как уже отмечалось выше, что отношение S может быть разбито с помощью операции декомпозиции на проекции {S#, STATUS} и {S#, CITY} без утраты информации.

В то же время уже известно, что отношение S не может быть разбито без потери информации на проекции {S#, STATUS} и {STATUS, CITY}. Теорема Хеза не дает объяснения, почему так происходит. (Дело в том, что она формулируется как "если..., то...", а не "тогда и только тогда, когда...". Об этом также идет речь в упражнениях в конце главы. Более строгая формулировка теоремы Хеза будет представлена в главе 11.) Однако интуитивно можно предположить, что при такой декомпозиции утрачивается одна из функциональных зависимостей, т.е. зависимость S# ® STATUS еще будет присутствовать (благодаря проекции {S#, STATUS}), а зависимость S# ® CITY будет утрачена.