<<
>>

2.2 НОРМАЛИЗАЦИЯ ОТНОШЕНИЙ

Центральная задача проектирования базы данных ЭИС - определение количества отношений (илн иных составных единиц информации) н нх атрибутного состава.

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

Рациональные варианты группировки должны учитывать следующие требования: •

множество отношений должно обеспечивать минимальную избыточность представления информации, •

корректировка отношений не должна приводить к двусмысленности илн потере информации, •

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

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

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

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

Отношение в первой нормальной форме (сокращенно 1НФ) - это обычное отношение с двухуровневой структурой. Недопустимость в структуре отношения третьего и последующих уровней является ограничением, определяющим 1НФ отношения.

Преобразование ненормализованного отношения в представление, соответствующее 1 НФ, - это операция нормализации, рассмотренная выше.

Следует отметить определенное терминологическое несоответствие - нормализация СЕИ приводит к 1НФ, а нормализация отношений реляционной БД обычно производится до ЗНФ или 4НФ.

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

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

2.2.1

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

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

Простейший случай функциональной зависимости охватывает 2 атрибута. В отношении R(A,B,...) атрибут А функционально определяет атрибут В, если в любой момент времени каждому значению А соответствует единственное значение В (обозначается А -» В).

Иначе говорят, что В функционально зависит от А (обозначается В = f(A)). Первое обозначение оказывается более удобным, когда число функциональных зависимостей растет и их взаимосвязи становятся трудиообозримыми; оно и будет использоваться в дальнейшем. Отсутствие функциональной зависимости обозначается А—/-» В. Можно определить ситуацию А В с помощью операции "образ", сказав что множество im В(а) должно содержать один элемент для любого значения а атрибута А.

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

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

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

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

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

В качестве примера рассмотрим отношение R2 с атрибутами Магазин и Расч (номер расчетного счета).

R2

Магазин Расч

ММЗ 704098

Динамо 122095 АТЭ 440182

Можно утверждать, что у каждого магазина единственный номер расчетного счета и каждый расчетный счет принадлежит единственному магазину. Это доказывает справедливость функциональных зависимостей Магазин Расч и Расч Магазин, т.е. Магазин Расч.

Наконец, самыми распространенными являются случаи отсутствия функциональных зависимостей, например, ФИО—/—»Дисциплина и Дисциплина —/-» ФИО в отношении R3, описывающем экзамены студентов. Здесь каждый студент сдает экзамены по нескольким дисциплинам, и по каждой дисциплине экзамен сдается многими студентами. R3 ФИО Дисциплина Петров Федин Алешин Петров Физика Химия Физика Химия Таким образом, для атрибутов А н В некоторого отношения возможны следующие ситуации: •

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

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

налнчневзаимно-однозначногосоответствияА<-> В.

Понятие функциональной зависимости распространяется

на ситуацию с тремя н более атрибутами в следующей форме. Группа атрибутов (для определенности А,В,С) функционально определяет атрибут D в отношении T(A,B,C,D ), если

каждому сочетанию значений <а,Ь,с> соответствует единственное значение d (а - значение A, b - значение В, с - зиачеине С, d - значение D). Наличие такой функциональной зависимости будем обозначать А,В,С D. Случай, когда в правой части функциональной зависимости присутствует несколько атрибутов, не нуждается в специальном рассмотрении. Взанм- ио-однозначные соответствия для трех и более атрибутов также не имеют самостоятельного значения.

78

Пусть в отношении Т1 преястаалены сведения о закончившихся экзаменах. T1 ФИО Дисциплина Дата Преподаватель Оценка Петров Физика 01.06.98 Иванов 4 Федин Химия 01.06.98 Смирнов 5 Алешин Физика 01.06.98 Иванов 5 Петров Химия 07.06.96 Смирнов 5 Ограничение, состоящее в том, что студент не может в однн день сдать два и более экзаменов, означает справедливость ряда функциональных зависимостей: ФИО, Дата -» Дисциплина, ФИО, Дата -» Преподаватель, ФИО, Дата ОЦЕНКА.

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

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

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

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

Вероятных ключей в отношении может быть несколько.

Рассмотрим в качестве примера отношение ТЗ (имена и значения атрибутов - условные):

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

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

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

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

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

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

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

Каждое значение первичного ключа встречается топько в одной строке отношения. Значение любого атрибута в этой строке также единственное. Если через К обозначить атрибуты первичного ключа в отношении R(A,В,С,... J), то справедливы следующие функциональные зависимости К —» А, К В, К —» С,... , К -» J. Набор атрибутов первичного ключа функционально определяет любой атрибут отношения. Обратное также верно: если найдена группа атрибутов, которая функционально определяет все атрибуты отношения по отдельности, и эту группу нельзя сократить, то найден первичный ключ отношения. б"2095 81

Вернемся к отношению Т1 с функциональными зависимостями: ФИО, Дата —* Дисциплина, ФИО, Дата —» Преподаватель, ФИО, Дата —* Оценка. Нетрудно установить, что ФИО, Дата -»ФИО, ФИО, Дата —» Дата (в каждом сочетании значений ФИО, Дата значение ФИО встречается один раз). Следовательно, первичный хлюч в отношении Т1 составляют атрибуты ФИО, Дата и при поиске ключа ие потребовались конкретные значения Т1.

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

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

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

Теорема 1

А,В —» А и А,В В.

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

Теорема 2

А В н А С тогда н только тогда, когда А ВС.

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

Обратно, еслн А ВС, то im ВС(а) содержит один элемент вида <Ь,с> для любого а. Зафиксируем некоторое значение а 1. Значение b (как и значение с) встречается в сочетании с al только одни раз, следовательно, справедливо А —* В и А —» С.

Теорема 3

Еслн А В и В С, то А С.

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

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

Теорема 4

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

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

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

Теорема 5

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

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

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

Теорема 6

Если А В и ВС D, то АС D.

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

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

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

Каждой функциональной зависимости вида А В можно поставить в соответствие булевскую функцию вида АВ' (знак логического умножения пропущен, через ' обозначено логи- ческое отрицание). Множеству функциональных зависимостей соответствует дизъюнкция выражений, соответствующих каждой зависимости в отдельности. Введем сокращенные обозначения: А - ФИО, В - Дата, С - Дисциплина, D - Преподаватель, Е - Оценка.

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

ФИО, Дата -»Дисциплина, ФИО, Дата —» Преподаватель, ФИО, Дата —» Оценка булевская функция будет выглядеть как

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

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

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

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

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

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

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

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

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

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

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

Еще по теме 2.2 НОРМАЛИЗАЦИЯ ОТНОШЕНИЙ:

  1. Установление дипломатических отношений между Японией и СССР
  2. Восстановление отношений с СССР
  3. Восстановление отношений с Китаем
  4. 2.2 НОРМАЛИЗАЦИЯ ОТНОШЕНИЙ
  5. Алгоритм нормализации (к ЗНФ)
  6. Период эмбарго
  7. Роль и место торгово-экономических отношений в общей дискуссии по китайской политике США в 1971—1978 гг.
  8. Курс на сближение с Пекином и сдвиги в расстановке сил в правящих кругах США на рубеже 70—80-х годов
  9. 26. «Новое политическое мышление» в международных отношениях
  10. О МЕТОДОЛОГИИ ИСТОРИИ ЦЕРКОВНО-ГОСУДАРСТВЕННЫХ ОТНОШЕНИЙ С.П. Синельников
  11. Нормализация отношений Афганистана с Великобританией
  12. Нормализация положения в Афганистане
  13. Конфигурация американского общественного мнения в отношении северокорейской проблемы в 2000-е годы
  14. Психологические факторы нормализации стресса жизни у педагогов и учащихся
  15. ОБРАЗОВАТЕЛЬНАЯ ПОЛИТИКА ГОСУДАРСТВА ПО ОТНОШЕНИЮ К ИСКЛЮЧИТЕЛЬНЫМ ДЕТЯМ
  16. 7.3. Образовательная политика государства по отношению к детям с трудностями в обучении
  17. Отношения  СССР с социалистическими   странами        
  18. Нормализация отношений с США, Китаем и другими странами
  19. 2.1.6. Нормализация молока
  20. 7. Зарубежная Европа: обострение межнациональных отношений