Главная » SQL, Базы данных » ДЕКОМПОЗИЦИЯ БЕЗ ПОТЕРЬ И ФУНКЦИОНАЛЬНЫЕ ЗАВИСИМОСТИ

0

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

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

Рис. 12.3. Пример значения переменной отношения S и два возможных варианта ее

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

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

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

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

Примечание. Как и в части II этой книги, высказывание типа "SST является проекцией переменной отношения S" используется вместо более точного высказывания типа "SST является переменной отношения, значение которой в любой момент времени является проекцией значения переменной отношения S, которое она имеет в это же время".

Надеемся, что использование указанной сокращенной формулировки не приведет к путанице.

Обратите внимание, что в случае а сохранение информации в полном объеме означает, что при обратном соединении переменных отношения SST и SC будет получена исходная переменная отношения S. В случае б дело обстоит иначе, поскольку при обратном соединении

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

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

2   Точнее,  в  исходной переменной отношения  S  вместе  со  всеми  кортежами будут  содержаться "фиктивные" кортежи, поскольку при обратной операции никогда не удастся  получить переменную отношения, которая была бы меньше исходной переменной отношения  S.  {Упражнение. Попробуйте доказать это утверждение.) А поскольку не существует общего метода различения фиктивных и подлинных кортежей, информация в этом случае действительно будет утеряна.

исходной переменной отношения R? Именно для получения ответа на этот вопрос необходимо обратиться к функциональным зависимостям. В рассматриваемом  примере переменная отношения S удовлетворяет представленному ниже неприводимому множеству функциональных зависимостей.

S#  →

STATUS S#

→ CITY

Учитывая данный факт, согласно которому переменная отношения S удовлетворяет приведенным функциональным зависимостям, нельзя считать простым совпадением то, что эта переменная отношения равна соединению  своих проекций по атрибутам

{S#, STATUS} и {S#,CITY}. И то, что это не совпадение, а закономерность,  подтверждается теоремой Хита (Heath) [12.4].

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

Если принять, что А— это атрибут s#, в — это атрибут STATUS, а с — это атрибут CITY, то данная теорема подтверждает, как отмечалось выше, что переменная отношения S может быть разбита с помощью операции декомпозиции на проекции по атрибутам (S#, STATUS} и {S#,CITY} без потери информации. В  то  же время уже известно, что переменная отношения S не может быть разбита без потери информации на проекции по атрибутам {S#, STATUS} и {STATUS,CITY}. Теорема Хита не дает объяснения, почему так происходит3.  Однако интуитивно ясно, что при такой декомпозиции утрачивается одна из функциональных зависимостей, т.е. функциональная зависимость S# → STATUS все еще представлена (благодаря проекции по атрибутам {S#,  STATUS}), а функциональная зависимость S# → CITY утрачена.

В заключение можно отметить, что декомпозиция переменной отношения R на проекции Rl, R2, …, Rn выполняется без потерь, если R равна соединению Rl,  R2,

…,   Rn.

Примечание. Вероятно, с точки зрения практики следовало бы выдвинуть  дополнительное требование, чтобы в соединении обязательно были нужны все проекции R1, R2, …, Rn. Это позволяет гарантировать, что удастся избежать  определенной избыточности, которая могла бы возникнуть в ином случае. Например, вряд ли стоит рассматривать декомпозицию переменной отношения  S  на проекции (скажем) по атрибутам

{S#}, {S#, STATUS} и {S#,CITY} как качественную декомпозицию без потерь, хотя S в конечном итоге становится равной соединению этих трех проекций. Для  простоты в дальнейшем будем считать, что это дополнительное требование всегда остается в силе (если явно не указано иное).

3 Дело в том, что эта теорема сформулирована в выражениях "если…, то…", а не "тогда и только тогда, когда…" (см. упр. 12.1,

приведенное в конце главы). Более строгая формулировка теоремы Хита будетпредставленавразделе13.2главы13.

Глава 12. Дальнейшая нормализация: формы 1НФ, 2НФ, ЗНФ и НФБК    465

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

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

1. Неприводимость. Как указано в главе 11, функциональная зависимость называете; неприводимой слева, если ее левая часть "не слишком велика". Рассмотрим, например, переменную отношения SCP, приведенную в разделе 12.1, которая удовлетворяет следующей функциональной зависимости.

{   S#,   Р#   }    →   CITY

Однако атрибут р# в левой части этой функциональной зависимости является избыточным, поэтому она может быть переписана в следующем виде.

S#  →   CITY

(Иначе говоря, атрибут CITY функционально зависит только от s#.) Последняя функциональная зависимость является неприводимой слева, а предыдущая — нет. Наряду с этим, можно сказать, что атрибут CITY является неприводимо зависимым4 от   атрибута  S#,   но   не  является  неприводимо   зависимым   от   множества атрибутов  {s#,  Р#}.  Неприводимые  слева   ФЗ   и  неприводимые  ФЗ  играют важную роль при определении второй и третьей нормальной форм (подробности приведены в разделе 12.3).

2.  Диаграммы ФЗ. Пусть дана переменная отношения R и пусть к ней применимо некоторое неприводимое множество функциональных зависимостей I (более подробные сведения о неприводимых множествах ФЗ приводятся в главе 11). Удобнее всего можно представить это множество I в виде диаграммы функциональных зависимостей (диаграммы ФЗ). Например, на рис. 12.4 показаны вполне очевидные по смыслу диаграммы функциональных зависимостей, соответственно, для переменных отношения s, SP и Р. Такие диаграммы будут часто использоваться далее в этой главе.

Рис, 12.4. Диаграмма функциональных зависимостей для переменных отношения

S, SP и Р

4  Здесь термины "неприводимая слева ФЗ" и "неприводимо зависимый" используются  вместо терминов "полная ФЗ" и "полностью зависимый", которые часто можно встретить  в  литературе (и в прежних  изданиях  этой  книги).  Хотя   последние  термины  отличаются   краткостью,  они   менее информативны и не очень удобны.

Как можно видеть, на рис. 12.4 каждая стрелка начинается с потенциального ключа (в действительности — с первичного ключа) соответствующей переменной отношения. По определению стрелки должны начинаться с  каждого потенциального ключа5, поскольку одному значению такого ключа  всегда соответствует еще по крайней мере одно какое-либо значение; такие стрелки нельзя удалять ни при каких условиях. Если же на диаграмме  имеются какие-то другие стрелки, то возникают   сложности.   Таким    образом,   процедуру   нормализации   можно довольно  неформально   охарактеризовать  как  процедуру  исключения  стрелок, которые не начинаются с потенциальных ключей.

3.     ФЗ как семантическое понятие. Как было отмечено в главе 11, функциональные зависимости безусловно представляют собой особый вид ограничений целостности. К  тому  же  они,  несомненно,  относятся  к  категории  семантических  понятий (фактически функциональные зависимости входят в состав определения предиката переменной отношения). Выявление функциональных зависимостей представляет собой часть процесса выяснения смысла тех или иных данных. Например, тот факт, что переменная отношения S удовлетворяет функциональной зависимости S# → CITY, по сути означает, что каждый поставщик находится точно в одном городе. Иначе эту ситуацию можно охарактеризовать следующим образом.

■     В реальном мире существует некоторое ограничение, представленное в этой базе данных, согласно которому каждый поставщик находится точно в одном городе.

■     Поскольку это ограничение является частью семантического описания пред метной области, оно должно быть каким-то образом представлено в базе дан ных.

■     Один из способов обеспечения этого состоит в том, что указанное ограничение необходимо задать в определении базы данных таким образом, чтобы оно мог ло быть предписано с помощью средств СУБД.

■     Способ описания ограничения в определении базы данных состоит в объявле нии соответствующей функциональной зависимости.

Как будет показано ниже, концепции нормализации открывают возможность использовать весьма простые способы объявления ФЗ.

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии