<<
>>

2.2.1. Функциональные зависимости и ключи

Функциональные зависимости определяются для атрибутов, находящихся в одном и том же отношении, удовлетворяющем 1НФ.

Простейший случай функциональной зависимости охваты­вает 2 атрибута.

В отношении 11(А,В,...) атрибут А функцио­нально определяет атрибут В, если в любой момент времени каждому значению А соответствует единственное значение В (обозначается А —» В).

Иначе говорят, что В функционально зависит от А (обо­значается В = ДА)). Первое обозначение оказывается более удобным, когда число функциональных зависимостей растет и их взаимосвязи становятся труднообозримыми; оно и будет использоваться в дальнейшем. Отсутствие функциональной зависимости обозначается А —/—» В.

Можно определить ситуацию А -» В с помощью операции “образ”, сказав что множество т В(а) должно содержать один элемент для любого значения а атрибута А.

Рассмотрим простой пример с атрибутами ФИО и ГР (год рож­дения) в отношении Я1.

Я1
ФИО ГР
Иванов

Зуев

Смирнов

Яшина

1960

1963

1960

1961

Предположим, что в столбце ФИО представлены сведения о разных людях и соответствующие значения в столбце не повторя­ются. Тогда можно утверждать наличие функциональной зависи­мости ФИО —» ГР, поскольку каждому значению атрибута ФИО в отношении ЯI соответствует единственное значение атрибута ГР. Можно утверждать, что это ограничение будет соблюдаться и да­лее, так как оно перефразируется в утверждение: у каждого чело­века единственный год рождения, которое справедливо.

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

Имен­но так мы и будем поступать в дальнейшем. Наличие в столбце ГР повторяющихся годов (1960) не опровергает установленной нами зависимости, но это означает ГР —/-» ФИО.

Одновременное соблюдение двух зависимостей вида А -» В и В —» А называется взаимно-однозначным соответствием и обозна­чается А Расч.

Наконец, самыми распространенными являются случаи отсут­ствия функциональных зависимостей, например, ФИО —/—»Дис­циплина и Дисциплина —/—» ФИО в отношении ЛЗ, описываю­щем экзамены студентов. Здесь каждый студент сдает экзамены по нескольким дисциплинам, и по каждой дисциплине экзамен сдает­ся многими студентами.

лз
ФИО Дисциплина
Петров

Федин

Алешин

Петров

Физика

Химия

Физика

Химия

Таким образом, для атрибутов А и В некоторого отноше­ния возможны следующие ситуации:

• отсутствиефункциональнойзависимости, '

• наличие А —> В (или В —»А), но не обе зависимости вместе,

• наличиевзаимно-однозначногосоответствияА«-» В.

Понятие функциональной зависимости распространяется на ситуацию с тремя и более атрибутами в следующей форме. Группа атрибутов (для определенности А,В,С) функциональ­но определяет атрибут О в отношении Т(А,В,С,0,....), если каждому сочетанию значений соответствует единствен­ное значение Так, для множества учреждений можно утверждать, что каждый отдел (как объект предметной области) относится к единственному учреждению. Однако этого недостаточно для доказательства функциональной зависимости Отдел -> Учреждение. Если в каждом учреждении отделы нумеруются последовательно, начиная с 1, то функциональная зависимость неверна. Если же код отдела, кроме номера, содержит и код учреждения (или уникальность кодов обеспечивается каким-то другим спосо­бом), то функциональная зависимость Отдел -»Учреждение справедлива. Зависимость ФИО -» ГР в Я1 соблюдается, если ФИО является атрибутом- идентификатором для каждого че­ловека, что может быть справедливо только для небольших множеств людей.

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

Для показателя со множеством атрибутов-признаков Р= {Р1 ,Р2,...,Рп} и атрибутом-основанием О справедлива фун­кциональная зависимость Р -» (), хотя нельзя утверждать, что это единственная зависимость на указанных атрибутах.

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

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

Рассмотрим в качестве примера отношение ТЗ (имена и значе­ния атрибутов - условные):
тз
ZEN RAM AST SPIM BIG
31 dwa wii 73
ЗВ 21 bun cup 40
3D 30 тип lam 58
4D 31 sab wii 40
30 sab irt 38

Можно утверждать, что вероятным ключом отношения ТЗ яв­ляется атрибут ZEN (значения в столбце ZEN не повторяются).
Кроме того, еще один вероятный ключ представлен парой атрибу­тов RAM, AST.

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

На практике атрибуты вероятного ключа отношения свя­зываются со свойствами тех объектов и событий, информа­ция о которых хранится в отношении. Если в результате кор­ректировки отношения изменились имена атрибутов, образующих ключ, то это свидетельствует о серьезном иска­жении информации. Следовательно, систематическая провер­ка свойств вероятного ключа позволяет следить за достовер­ностью информации в отношении.

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

Первичным ключом отношения называется такой вероятный ключ, по значениям которого производится контроль досто­верности информации в отношении.

Применительно к экономической информации в подавля­ющем большинстве случаев отношения, полученные из суще­ствующих экономических документов, содержат единственный вероятный ключ, который является и первичным ключом. Это объясняется тем, что содержимое экономических документов понимается всеми пользователями одинаково. Далее будем иметь в виду только такие отношения. Наличие двух и более вероятных ключей в отношениях с осмысленной информаци­ей можно объяснить наличием нескольких возможных спосо­бов интерпретации одних и тех же данных. Первичный ключ часто называется просто ключ.

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

Каждое значение первичного ключа встречается только в одной строке отношения.

Значение любого атрибута в этой строке также единственное. Если через К обозначить атрибуты первич­ного ключа в отношении ЩА.В.С,... Д), то справедливы следую­щие функциональные зависимости К -> А, К -> В, К -> С,..., К —» 5. Набор атрибутов первичного ключа функционально опре­деляет любой атрибут отношения. Обратное также верно: если найдена группа атрибутов, которая функционально определяет все атрибуты отношения по отдельности, и эту группу нельзя сократить, то найден первичный ключ отношения.

Вернемся к отношению Т1 с функциональными зависимостями: ФИО, Дата —> Дисциплина,

ФИО, Дата —> Преподаватель,

ФИО, Дата —> Оценка.

Нетрудно установить, что ФИО, Дата —> ФИО,

ФИО, Дата —> Дата (в каждом сочетании значений ФИО, Дата значение ФИО встре­чается один раз). Следовательно, первичный ключ в отношении Т1 составляют атрибуты ФИО, Дата и при поиске ключа не потре­бовались конкретные значения Т1.

Знание ключа отношения позволяет устанавливать ряд функ­циональных зависимостей, например, в ТЗ ZEN —> BIG, RAM, AST -► BIG.

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

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

Теорема 1

А,В -> А и А,В -> В.

Доказательство основано на том, что в строке для атрибутов А и В значение а (как и значение Ь) присутствует один раз.

Теорема 2

А -> В и А -> С тогда и только тогда, когда А —»ВС.

Рассмотрим произвольное значение а атрибута А. Если А-»ВиА-»С, Toim В(а) и im С(а) содержат по одному эле­менту. Предположим, что зависимость А -» ВС неверна и im ВС(а) состоит из 2 или более элементов. Тогда либо im В(а), либо im С(а) должны содержать более одного элемента. Полу­ченное противоречие доказывает зависимость А —> ВС.

Обратно, если А -» ВС, то іт ВС(а) содержит один элемент вида для любого а.

Зафиксируем некоторое значение а 1. Значение Ь (как и значение с) встречается в сочетании с а1 толь­ко один раз, следовательно, справедливо А -» В и А -» С.

Теорема 3

Если А -> В и В -» С, то А -» С.

Предположим, что зависимость А -» С неверна и множе­ство іт С(а) содержит более одного элемента. Каждому значе­нию а соответствует единственное значение Ь (в силу А -» В), поэтому іт С(Ь) содержит более одного элемента. Получилось противоречие с условием В -» С, что и доказывает теорему.

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

Теорема 4

Если А -» В, то АС -» В (С произвольно).

Доказательство

АС —» А (теорема 1), А —> В (условие), следовательно, АС -» В по теореме 3.

Теорема 5

Если А -» В, то АС -» ВС (С произвольно).

Доказательство

АС -» В (теорема 4), АС -» С (теорема 1), следовательно, АС -» ВС по теореме 2.

Теорема б

Если А -» В и ВС -» О, то АС -» О.

Доказательство

Из А -» В следует АС -» ВС (теорема 5). ВС -» О (условие), поэтому АС -> О по теореме 3.

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

Каждой функциональной зависимости вида А -> В можно поставить в соответствие булевскую функцию вида АВ' (знак логического умножения пропущен, через ' обозначено логи­ческое отрицание). Множеству функциональных зависимос­тей соответствует дизъюнкция выражений, соответствующих каждой зависимости в отдельности.

Введем сокращенные обозначения:

А - ФИО, В - Дата, С - Дисциплина,

D - Преподаватель, Е - Оценка.

Тогда для рассмотренных выше функциональных зависи­мостей

ФИО, Дата —» Дисциплина,

ФИО, Дата —» Преподаватель,

ФИО, Дата —> Оценка булевская функция будет выглядеть как

ABC' + ABD' + ABE'

(знаком + обозначено логическое сложение).

Для некоторого множества функциональных зависимостей F введем множество F~, называемое покрытием. Покрытие F~ содержит все функциональные зависимости, которые можно получить из множества F в результате применения теорем 1- 6 (включая и содержимое F). Одно и то же покрытие F~ может быть получено из различных множеств функциональных зависи­мостей. Среди таких множеств выделим множество с минималь­ным числом зависимостей и назовем его минимальным покрытием (базисом) множества зависимостей F. Иначе можно сказать, что минимальным покрытием называется множество функциональ­ных зависимостей, из которого удалены все зависимости, являю­щиеся следствиями оставшихся зависимостей и теорем 1-6.

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

Можно рекомендовать следующие теоремы:

• если А —» ВС, то А —»В и А —»С,

• если А -» В, то AD —» В,

• если А -» В и В —> С, то А С.

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

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

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

<< | >>
Источник: Мишенин А. И.. Теория экономических информационных систем; Учебник. — 4-е изд., доп. и перераб. — М.: Финансы и статистика, - 240 с.: ил. 2002

Еще по теме 2.2.1. Функциональные зависимости и ключи:

  1. 12.1. Функциональная зависимость между прибылью, объемом продаж и себестоимостью
  2. 4.1. Функциональная и стохастическая зависимости
  3. 2.2.1. Функциональные зависимости и ключи
  4. 2.2.2. Вторая и третья нормальные формы отношений
  5. Алгоритм нормализации (к ЗНФ) 1.
  6. 2.2.3. Ациклические базы данных
  7. Алгоритм проверки структуры БД на ацикличность
  8. 2.2.4. Доступ к реляционной базе данных
  9. Организация веерного отношения в памяти ЭВМ
  10. Иерархическая модель данных
  11. Алгоритм получения структуры иерархической БД 1.
  12. ВОПРОСЫ И ЗАДАНИЯ 1.
  13. Теорема Коуза. Варианты интернализации внешних эффек­тов.
  14. § 6. Типология эволюционных форм государства
  15. 14.1. Понятие системы права и ее значение
  16. 5.2.2. Установление связей между доказательствами
  17. 7.1. Концептуальная модель управления маркетингом малого бизнеса