Функциональные зависимости между атрибутами отношения.

Определим понятие функциональной зависимости (ФЗ) между атрибутами.

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

Функциональная зависимость атрибута В от атрибута А в математической форме обозначается как А → В, а в графической .

Рассмотрим функциональные зависимости, существующие между атрибутами отношения «Библиотека». Эти ФЗ вытекают из семантики предметной области.

Шифр однозначно определяет как автора книги, так и ее название, год издания и количество экземпляров, имеющихся в библиотеке. Номер читательского билета однозначно определяет ФИО читателя и номер его телефона. Функциональной зависимости между ФИО читателя и номером телефона нет, поскольку фамилии и инициалы некоторых читателей большой библиотеки могут и совпадать. Не существует и ФЗ между атрибутами Тел и ФИО, так как один и тот же телефон может быть телефоном разных читателей, если, предположим, они живут в одной квартире. Наконец атрибут Дата находится в функциональной зависимости от сложного атрибута Шифр+Билет, так как это дата закрепления определенной книги за определенным читателем, если, конечно, читатель не берет одну и ту же книгу несколько раз. Рассуждая подобным образом, изобразим диаграмму функциональных зависимостей , отображающую ФЗ между атрибутами отношения.

Рис.4.1. Диаграмма функциональных зависимостей между атрибутами отношения «Библиотека»

Эти же зависимости в математической форме могут быть представлены следующим образом:

1. Шифр → Авт

2. Шифр → Назв

3. Шифр → Год

4. Шифр → Экз

5. Билет → ФИО

6. Билет→ Тел

7. Шифр, Билет → Дата

Лекция 5 Метод декомпозиции

Полученное в предыдущем разделе универсальное отношение следует, подвергнув декомпозиции, привести к нормальной форме Бойса – Кодда (НФБК). Эта нормальная форма позволяет избежать большинства потенциальных аномалий, возникающих в БД. И хотя существуют нормальные формы и более высокого порядка, которые накладывают на зависимости между атрибутами отношений более сильные ограничения, на практике наиболее часто стремятся получить именно НФБК. Рассмотрим, что же представляет собой эта форма .

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

Определим, находится ли в НФБК отношение «Библиотека». Ключом отношения является набор атрибутов (Шифр, Билет), поскольку атрибут Шифр однозначно определяет значения атрибутов Авт, Назв, Год и Экз, атрибут Билет однозначно определяет значения таких атрибутов, как ФИО читателя и Тел – номер его телефона, а для определения даты выдачи книги требуются оба значения – Шифр и Билет. Детерминанты отношения – это левые части всех функциональных зависимостей, если слева находится один атрибут. Если же левая часть представляет собой совокупность атрибутов, то она является детерминантом только в случае, если нет зависимости правой части этой ФЗ от части этих атрибутов. В нашем случае детерминантами отношения являются атрибуты Шифр, Билет и составной атрибут (Шифр, Билет), но только последний является ключом. Следовательно, отношение «Библиотека» не находится в НФБК и его следует подвергнуть декомпозиции. Декомпозиция, которая нас интересует, называется декомпозицией без потерь при естественном соединении. Выполняется она следующим образом.

Пусть имеем отношение R (A, B, C, D, E, …). Атрибут А является первичным ключом этого отношения, от него функционально зависят все остальные атрибуты. Кроме того, существует ФЗ C  D, наличие которой мешает отношению R находиться в НФБК, так как С, являясь детерминантом отношения, не является его ключом. В этом случае следует разбить отношение на два: R1 (C, D) и R2 (A, B, C, E, …). Отношение R1 является проекцией отношения R. Атрибуты функциональной зависимости, на которую выполняется проекция, переходят в новое отношение, при этом атрибут (совокупность атрибутов) левой части остается также и в исходном отношении.

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

Определение. Функциональная зависимость называется избыточной, если не заключает в себе информации, которую нельзя получить из других ФЗ.

Избыточная ФЗ, как не содержащая уникальной информации может и должна быть удалена из набора ФЗ. Рассмотрим, как выявляется наличие в отношении избыточных ФЗ и какие приемы используются для их удаления. Найти и удалить избыточные ФЗ можно с помощью следующих правил, которые называются правилами вывода :

Транзитивность. Если имеем ФЗ A  В и B  C, то существует ФЗ A  С, которая называется транзитивной. Транзитивная зависимость является избыточной и может быть удалена из отношения. Нестандартным случаем транзитивной зависимости является циклическая зависимость A ↔ B, B ↔ C, C ↔ A. При исключении любой из этих ФЗ две оставшиеся перестают быть избыточными.

Объединение. Если имеем ФЗ A  В и А  C, то существует ФЗ A  В, С. Это правило позволяет сократить количество ФЗ отношения путем замены нескольких ФЗ с одинаковыми левыми частями одной.

Добавление. Если имеем A  В, то ФЗ A, Z  B является корректной, но избыточной. Избыточной является также ФЗ A, X  В, X.

Декомпозиция. Если имеем ФЗ A  В, C то ее можно заменить двумя ФЗ: A  В и A  С.

Псевдотранзитивность. Если имеем ФЗ A  В и B, C  X, то существует ФЗ A, C  С, которая называется псевдотранзитивной ФЗ и является избыточной.

Для устранения избыточных ФЗ в отношении «Библиотека» дважды применим правило объединения – сначала по отношению к ФЗ 1, 2, 3, 4, а затем по отношению к ФЗ 5, 6. В итоге получим:

1. Шифр → Авт, Назв, Год, Экз

2. Билет → ФИО, Тел

3. Шифр, Билет → Дата

В графическом виде эти зависимости представлены на рис. 5.1.

Рис. 5.1. Диаграмма функциональных зависимостей между атрибутами отношения «Библиотека» после устранения избыточности

Для рассматриваемого отношения никакие другие правила применить нельзя. Оставшиеся ФЗ не являются избыточными.

Определение. Набор не избыточных ФЗ, полученный путем удаления из исходного набора всех избыточных ФЗ с помощью правил вывода, называется минимальным покрытием..

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

Получив минимальное покрытие, можно, наконец, приступить к декомпозиции отношения. В нашем случае кандидатов на проекцию два – это ФЗ 1 и 2. Выберем, например, первую. Получим два отношения: отношение R1 с атрибутами Шифр, Авт, Назв, Год, Экз, между которыми существует единственная ФЗ:

Шифр → Авт, Назв, Год, Экз,

и отношение R2 с атрибутами Билет, ФИО, Тел, Шифр, Дата, в котором есть две ФЗ:

Билет → ФИО, Тел

Шифр, Билет → Дата

В графическом виде функциональные зависимости между атрибутами отношений R1 и R2 представлены соответственно на рисунках 5.2 и 5.3.

Рис. 5.2. Диаграмма функциональных зависимостей между атрибутами отношения R1

Рис. 5.3. Диаграмма функциональных зависимостей между атрибутами отношения R2

Отношение R1 находится в НФБК, поскольку ФЗ всего одна, и левая ее часть является как детерминантом, так и ключом этого отношения. Отношение R2 в НФБК не находится, поскольку атрибут Билет, являясь детерминантом отношения, не является его ключом. Выполним проекцию отношения R2 на ФЗ Билет → ФИО, Тел. Получим отношение R3 с атрибутами Билет, ФИО, Тел и ФЗ

Билет → ФИО, Тел

В оставшемся отношении R4 с атрибутами Шифр, Билет, Дата, также имеется только одна ФЗ, а именно:

Шифр, Билет → Дата.

Диаграммы ФЗ отношений R3 и R4 изображены на рис. 5.4 и 5.5 соответственно.

Рис. 5.4. Диаграмма функциональных зависимостей между атрибутами отношения R3

Рис. 5.5. Диаграмма функциональных зависимостей между атрибутами отношения R4

Отношения R3 и R4 находятся в НФБК, как и любое отношение, в котором существует только одна ФЗ. Процесс декомпозиции завершен. Мы получили три отношения: R1, R3, R4. Отношение R1, учитывая состав его атрибутов, назовем Книга, отношение R3 – Читатель, а отношение R4 – Читает. Итак, вместо одного универсального отношения Библиотека мы получили 3 отношения. Привели ли наши действия к устранению потенциальных аномалий, присущих БД «Библиотека»?

При наличии в БД единственного отношения Библиотека возникали проблемы с изменением номера телефона читателя. Номер телефона надо было изменить столько раз, сколько книг взял читатель. Теперь, после разбиения отношения на три, нужно изменить номер телефона только в одной строке отношения Читатель.

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

Аномалия добавления тоже исчезла. Теперь не может быть частично заполненных строк в каждом из отношений. Если в библиотеку записывается новый читатель, то строка добавляется в отношение Читатель, и эта операция не затрагивает другие отношения БД. Если библиотека получила новую книгу, то сведения о ней помещаются в отношение Книга, а в случае, когда выполняется операция выдачи книги читателю, добавляется строка со сведениями о том, кто, какую книгу и когда взял, в таблицу Читает. При этом и сведения о книге и сведения о читателе, которому ее выдают, уже есть в БД, соответственно в отношениях Книга и Читатель.

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

Рассмотренный нами случай является чрезвычайно простым. Реально функциональных зависимостей, которые мешают отношению находиться в НФБК, может быть гораздо больше двух. В этом случае оказывается не безразлично, какую из ФЗ выбрать для первой проекции. Обычно при выборе ФЗ для проекции руководствуются следующим правилом. Ищут цепочки вида АВС, и используют крайнюю правую зависимость. Это позволяет избежать выбора ФЗ, правая часть которых полностью или частично является детерминантом другой ФЗ. Чем же опасен такой выбор? Попробуем, имея цепочку АВС, выполнить проекцию на ФЗ АВ. Получим отношение R1(A,B) и отношение R2(A,С). Оба эти отношения находятся в НФБК, но ни одно из них не содержит ФЗ ВС, которая присутствует в исходном отношении. Таким образом, в результате декомпозиции произошла потеря одной из ФЗ исходного отношения, что является недопустимым, поскольку искажается семантика предметной области.

Подведем итог. Метод проектирования БД, который носит название метода декомпозиции, состоит из следующих шагов:

1. Разработка универсального отношения.

2. Определение всех ФЗ между атрибутами отношения.

3. Исключение избыточных ФЗ и получение минимального покрытия.

4. Определение того, находится ли отношение в НФБК.

5. Если да, то все оставить без изменения.

6. Если нет, то выбрать ФЗ для проекции и разложить отношение на два.

7. Повторить шаг 4 для каждого нового, полученного при разложении, отношения.

Процесс завершается, когда окажется, что все полученные отношения находятся в НФБК.

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

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

Полученный набор может содержать одно или несколько избыточных отношений, которые следует исключить из набора отношений проектируемой БД. Отношение является избыточным в двух случаях:

• если все его атрибуты присутствуют в другом отношении, например, имеем БД, состоящую из отношений R1(A,B), R2(B,C,Y,Z), R3(A,B,D), отношение R1 в этом наборе является избыточным, поскольку оба его атрибута: А и В содержатся в отношении R3.

• если все его атрибуты присутствуют в отношении, которое может быть получено из других отношений БД с помощью последовательности операций соединения над ними¹. Пусть имеем БД из пяти отношений: R1(A,C,X), R2(D,K,F), R3(D,E,G,H), R4(A,B,D), R5(A,B,E,G). Если применить операцию соединения к отношениям R3 и R4, то получим отношение R6(A,B,D,E,G,H). Поскольку в этом отношении содержатся все атрибуты отношения R5, то R5 является избыточным отношением. Если бы мы применили операцию соединения к паре отношений R3,R5, то избыточным оказалось бы отношение R4.

Проведем анализ полученного набора отношений БД Библиотека. Смысловая связность атрибутов, составляющих каждое из отношений, не нарушена. В отношении Читатель, присутствуют атрибуты, характеризующие читателя – его ФИО, номер билета и телефон. Отношение Книга содержит только атрибуты, характеризующие библиотечную книгу: ее название, шифр, автор, год издания и количество имеющихся в библиотеке экземпляров этой книги. Отношение Читает, являясь связным отношением, содержит первичные ключи объектных отношений Книга и Читатель, а также атрибут Дата, представляющий собой дату закрепления книги за читателем и относящийся в равной степени как к книге, так и к читателю.

Мы пока не имеем перечня предполагаемых запросов к БД Библиотека, поэтому не можем дать заключение о соответствии полученного набора отношений предполагаемым запросам. Однако, если бы в перечне присутствовал запрос: «Кто из читателей является читателем библиотеки уже более 10 лет?», потребовалась бы коррекция набора атрибутов БД и ФЗ, пришлось бы добавить атрибут ДатаЗаписи, который функционально зависит от номера читательского билета и должен размещаться в отношении Читатель. Если при возврате книги читателем строка с указанием того, какую книгу и когда он брал, удаляется из таблицы Читает, то мы не сможем получить правильный ответ на вопрос: «Кто из читателей брал книги в предыдущем месяце?», если часть читателей эти книги уже вернули. Для того, чтобы ответ на такой вопрос стал возможным, надо добавить в отношение Читает атрибут ДатаВозврата, функционально зависящий, как и атрибут Дата (изменим его имя на ДатаЗакрепления), от совокупности атрибутов Шифр и Билет. Теперь удалять строки из отношения Читает не будем. Если читатель еще не вернул книгу, будет заполнено только поле ДатаЗакрепления, а когда книга возвращается в библиотеку, появляется значение и в поле ДатаВозврата. Таким образом, анализ возможных запросов к БД приводит нас к необходимости добавления в БД двух новых атрибутов: ДатаВозврата и ДатаЗаписи. Первый атрибут добавим в таблицу Читает, а второй – в таблицу Читатель. Анализ запросов может потребовать и добавления в БД новых связей между таблицами и даже новых, обычно связных, отношений. Это означает, что при проектировании мы упустили из виду какие-то зависимости, существующие между атрибутами предметной области, а анализ запросов помог обратить на них внимание.

Рассмотрим теперь набор ФЗ, присутствующих в отношениях, составляющих БД Библиотека. В отношении Книга присутствует единственная ФЗ - Шифр → Авт, Назв, Год, Экз, в отношении Читатель ФЗ Билет → ФИО, Тел , в отношении Читает также имеется только одна ФЗ, а именно: Шифр, Билет → Дата. При этом каждая ФЗ присутствует только в одном отношении, а набор из трех ФЗ, распределенный по трем отношениям совпадает с исходным минимальным покрытием.

Избыточных отношений нет, поскольку то, что атрибуты ни одного из отношений полностью не присутствуют в другом, очевидно. Что же касается второго случая, то выполнять операции соединения имеет смысл, если атрибут, находящийся в одном отношении, находится также и в другом. Это в полной мере относится к атрибутам правых частей ФЗ, что же касается атрибутов левых частей, то их присутствие в нескольких отношениях может быть оправдано наличием связи между отношениями, устанавливаемой по этим атрибутам. В нашем случае атрибуты Авт, Назв, Год, Экз, находятся только в отношении Книга, атрибуты ФИО и Тел – только в отношении Читатель, а атрибут Дата – только в отношении Читает. Атрибут Шифр присутствует в двух отношениях – Книга и Читает, а атрибут Билет – в отношениях Читатель и Читает, но оба используются для связи между отношениями. Связи между отношениями БД Библиотека изображены на рис. 5.6.

Рис. 5.6. Связи между отношениями БД Библиотека

Вообще, отношение, которое является связующим звеном между двумя объектными отношениями, и обе эти связи, как в нашем случае, являются связями «один – ко – многим», не может быть исключено, как избыточное, даже, если все его атрибуты полностью входят в какое-то другое отношение. Это определяется тем, что в любой СУБД можно установить межтабличные связи типа «один – к – одному» или «один – ко – многим», но не «многие – ко – многим».

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

На стадии программной реализации выполняются следующие действия.

1. Средствами выбранной для реализации СУБД вводятся описания (схемы) всех составляющих базу данных отношений.

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

3. Разрабатывается программное обеспечение прикладной системы, реализующее все необходимые операции с БД для всех категорий пользователей.

4. БД заполняется отладочными данными

5. Производится тестирование разработанной прикладной системы.

Этап логического проектирования БД предшествует этапу ее реализации в рамках выбранной СУБД и является важным, поскольку грамотный проект позволяет упростить процесс реализации системы и избежать большинства проблем при ее эксплуатации. Однако, рассмотренный нами метод декомпозиции работает не всегда. Считается [2], что, если количество атрибутов предметной области более двадцати, то метод становится излишне громоздким и сложным для применения. В этом случае рекомендуется использовать метод проектирования «сущность – связь» или, как его еще называют, ER – метод (Entity-сущность, Relationship- связь). Он является универсальным методом проектирования баз данных и применим при любом количестве атрибутов. Как и в методе декомпозиции в нем используются ФЗ, но не на начальном, а на завершающем этапе проектирования. Основу ER-метода составляет модель «сущность-связь» или ER-модель, которая будет рассмотрена на следующей лекции.

1Операция соединения – это теоретико-множественная операция вида R3 = R1⊲_iθj⊳R2, где R1, R2 – исходные отношения, R3 – результирующее отношение, i- атрибут отношения R1, j – атрибут отношения R2,θ– оператор сравнения. Еслиθ– это равенство, то операция называется эквисоединением и записывается так: R3 = R1⊲⊳R2. В этом случае отношения R1 и R2 должны иметь в своем составе одинаковые атрибуты. Результирующее отношение включает все атрибуты как первого, так и второго отношения, одинаковые атрибуты не дублируются. В результирующее отношение включаются только строки, в которых значения одинаковых атрибутов отношений равны.

34