Мартьянова А.Е. Базы данных и знаний. Учебное пособие

Подождите немного. Документ загружается.

Мартьянова А.Е. Базы данных и знаний 31

Работа III. Даталогическое проектирование (продол-

жение). Нормализация отношений

вую -

дая связь связывает только связи встречаются наи-

ущности и свя-

зи тип

ност

е реализации первого шага каждая простая сущность пре-

вращ

вать связи во внешние ключи. На стороне «многие» в

отнош

быть создано

третье отношение – для связи между отношениями. Назо-

вем это отношение «Успеваемость». В число атрибутов нового отноше-

В рассматриваемом нами примере «Учебный процесс» сущест

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

две сущности. Такие

более часто.

В рассматриваемом примере наблюдаются бинарные связи типа

1:M с обязательным классом принадлежности n-связной с

а M:M, поэтому воспользуемся правилами 4 и 6 для формирования

реляционной модели из инфологической модели (рис. I.16).

Первые шаги преобразования состоят в превращении каждой сущ

и в отношение (таблицу). Связь типа М:М, которую называют «сущ-

ность-связь», тоже превращается в отдельное отношение. Каждое свой-

ство становится атрибутом – столбцом соответствующей таблицы.

1. Посл

ается в

таблицу с тем же именем. Таким образом, имеем следующие

таблицы: «Группа», «Студент», «Кафедра», «Преподаватель», «Учебный

план».

2. Каждый атрибут становится столбцом с тем же именем. Столб-

цы, соответствующие необязательным атрибутам, могут содержать не-

определенные значения; столбцы, соответствующие обязательным атри-

бутам, – не могут.

3. Компоненты уникальных идентификаторов сущностей превра-

щаются в первичные

ключи соответствующих отношений. Например,

первичным ключом таблицы «Учебный план» назначим столбец Код

учебного плана.

4. Связи «многие-к-одному» становятся внешними ключами. Необ-

ходимо преобразо

ение согласно правилу 4 должен быть добавлен как внешний ключ

первичный ключ отношения со стороны «один». Например, в отношение

«Студент» должен быть добавлен для связи с отношением «Группа»

внешний ключ «Код группы» из отношения «Группа», где он является

первичным ключом.

5. Связи типа «многие-ко-многим». В ER-диаграмме наблюдается

связь этого типа между сущностями «Студент» и «Учебный план». Рас-

смотрим эту связь «многие-ко-многим». Согласно правилу 6 должн

Мартьянова А.Е. Базы данных и знаний 32

ния «

плана, сочетание которых и образует

уник ь еваемость» (рис. I.17).

Успеваемость» поместим ключи отношений «Студент», «Учебный

план»: Код студента, Код учебного

ал ный ключ нового отношения «Усп

ГРУППА

Код п гру пы

зна ение группы Обо ч

Кол с н

балл при поступлении

иче тво студе тов

Средний

СТУДЕНТ

Код студента

Номер зачетной книжки

Фамилия

Имя

Отчество

Год рождения

Адрес

Домашний телефон

Балл при поступлении

Код группы

КАФЕДРА

Код кафедры

Заведующий

Название кафедры

Телефон

ПРЕПОДАВАТЕЛЬ

Код преподавателя

Табельный номер

Фамилия

Имя

Отчество

Домашний адрес

Домашний телефон

Должность

Ученая степень

Ученое звание

Код кафедры

УЧЕБНЫЙ ПЛАН

Код учебного плана

Наименование

предмета

Программа

Часы

Вид заня

Семестр

тия

Вид сдачи

Оценка

Дата сдачи

Код преподавателя

УСПЕВАЕМОСТЬ

Код студента

Код учебного плана

ование связи типа «многие-ко-многим» реляционной схемы

схемы БД может быть выполнено двумя путями:

Рис. I.17. Преобраз

«Учебный процесс»

Нормализация отношений

Корректной назовем схему БД, в которой отсутствуют нежела-

тельные зависимости между атрибутами отношений [10].

Процесс разработки корректной схемы реляционной БД называется

даталогическим (логическим) проектированием БД.

Проектирование

Мартьянова А.Е. Базы данных и знаний 33

•

нтеза, то есть путем компоновки из заданных исходных

элеме

анной на анализе функциональ-

ных рибутами отношений. Понятие функцио-

наль я фундаментальным в теории нормализации

реля Коснемся смысла этого понятия. Функцио-

наль пределяют устойчивые отношения между объек-

ами и их свойствами в рассматриваемой предметной области. Именно

оэтому процесс поддержки

функциональных зависимостей, характер-

тной области, является базовым для процесса

проек

й форме соответствует

некоторый определен-

ный н

рма Бойса-Кодда (

НФБК);

•

дущих нормальных форм сохраняются.

путем декомпозиции (разбиения), когда исходное множество от-

ношений, входящих в схему БД заменяется другим множеством отноше-

ний (число их при этом возрастает), являющихся проекциями исходных

отношений;

• путем си

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

мы БД.

Классическая технология проектирования реляционных баз

данных

связана с теорией нормализации, основ

зависимостей между ат

ной зависимости являетс

ционных баз данных.

ные зависимости о

ных для данной предме

тирования.

Процесс проектирования с использованием декомпозиции пред-

ставляет собой процесс последовательной нормализации схем отноше-

ний, при этом каждая последующая итерация соответствует нормальной

форме более высокого уровня и обладает лучшими свойствами по срав-

нению с предыдущей.

Каждой нормально

абор ограничений, и отношение находится в некоторой нормаль-

ной форме, если удовлетворяет свойственному ей набору ограничений.

В теории реляционных БД обычно выделяется следующая после-

довательность нормальных форм:

• первая нормальная форма (1НФ);

• вторая нормальная форма (2НФ);

• третья нормальная форма (3НФ);

• нормальная фо

четвертая нормальная форма (4НФ);

• пятая нормальная форма, или форма проекции-соединения

(5НФ).

Основные свойства нормальных форм:

• каждая следующая нормальная форма в некотором смысле улуч-

шает свойства предыдущей;

• при переходе к следующей нормальной форме свойства преды-

Мартьянова А.Е. Базы данных и знаний 34

В основе классического процесса проектирования лежит последо-

вательность переходов от предыдущей нормальной формы к последую-

цессе декомпозиции мы сталкиваемся с проблемой об-

ратим

преобразований сохраняется

множ

ее состояния, то есть они отражают те связи между

атриб

кциональных зависимостей задает разра-

ботчи

ь нормализации сводится к получению

та-

кого п

е при использо-

вании

•

щей. Однако в про

ости, то есть возможности восстановления исходной схемы. Та-

ким образом, декомпозиция должна сохранять эквивалентность схем БД

при замене одной схемы на другую.

Схемы БД называются эквивалентными

, если содержание исход-

ной БД может быть получено путем естественного соединения отноше-

ний, входящих в результирующую схему, и при этом не появляется но-

вых кортежей (строк) в исходной БД.

При выполнении эквивалентных

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

между атрибутами отношений.

Функциональные зависимости определяют не текущее состояние

БД, а

все возможные

утами, которые присущи реальному объекту, которые моделирует-

ся с помощью БД.

Поэтому определить функциональные зависимости по текущему

состоянию БД можно только в том случае, если экземпляр БД содержит

абсолютно полную информацию (то есть никаких добавлений и модифи-

каций БД не

предполагается). В реальной жизни это требование не вы-

полнимо, поэтому набор фун

к, системный аналитик, исходя из глубокого системного анализа

предметной области.

Процесс нормализации – это разбиение таблицы на две или более с

целью ликвидации дублирования данных и потенциальной их противо-

речивости. Окончательная цел

роекта базы данных, в котором «каждый факт появляется лишь в

одном месте».

Использование ненормализованных таблиц может привести к на-

рушению целостности данных (противоречивости информации) в БД.

Обычно различают следующие проблемы, возникающи

ненормализованных таблиц [14]:

• избыточность данных;

• аномалии обновления;

• аномалии удаления;

аномалии ввода.

Мартьянова А.Е. Базы данных и знаний 35

Избыточность данных

Избыточность данных проявляется в том, что в нескольких записях

табли

, будут дублироваться личные данные преподавателей, веду-

щих н

тобы информация, содержащаяся в таблице, была кор-

ректн

Аном

ицы. Пусть, например, в институте некоторые группы

расфо

нформации и называется аномалией удале-

ния. (

лице имеется поле Оценка, в котором

содер

он еще не сдавал

экзамен. Если для этого поля задать ограни-

чение

находится в некоторой нормаль-

ной ф

цы БД повторяется одна и та же информация. Например, один пре-

подаватель может вести несколько предметов. Тогда в общей таблице,

содержащей сведения о преподавателях и предметах, которые ведут пре-

подаватели

есколько предметов столько

раз, сколько предметов они ведут.

Аномалии обновления

Аномалии обновления тесно связаны с избыточностью данных.

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

менился адрес. Ч

ой, необходимо будет внести изменения в те записи, в которых со-

держатся сведения об этом преподавателе. Если же исправление

будет

внесено не во все записи, то возникнет несоответствие информации, ко-

торое и называется аномалией обновления.

алии удаления

Аномалии удаления возникают при удалении записей из ненорма-

лизованной табл

рмировываются. При этом следует удалить соответствующие запи-

си в таблице, в которой содержатся сведения об этих группах

. Однако

удаление приведет к потере информации о студентах, обучающихся в

этих группах. Такая потеря и

Можно привести и другой пример – удаление записей при отчисле-

нии всех студентов из группы может привести к потере информации о

группе, в которой они обучались).

Аномалии ввода

Аномалии ввода возникают

при добавлении в таблицу новых запи-

сей и обычно возникают, когда для некоторых полей таблицы заданы ог-

раничения NOT NULL. Пусть в таб

жится информация об оценках студентов при сдаче экзамена. При

записи в таблицу информации о студенте установить его оценку невоз-

можно, так

NOT NULL, то в таблицу нельзя будет ввести информацию о сту-

денте. Это и называется аномалией ввода.

Каждой нормальной форме соответствует некоторый определен-

ный набор ограничений, и отношение

орме, если оно удовлетворяет свойственному данной форме набору

ограничений [7, 10].

Мартьянова А.Е. Базы данных и знаний 36

Наиболее важные на практике нормальные формы отношений ос-

новываются на фундаментальном в теории реляционных баз данных по-

нятии

детерминантом.

зависимости.

Если неключевой атрибут зависит от всего составного ключа и не

находится в частичной зависимости от его частей, то говорят о его пол-

ной функциональной зависимости от составного ключа.

Если для некоторых атрибутов А, Б и В выполняются условия: Б

функционально зависит от А (А →

Б) и В функционально зависит от Б (Б

→ В), а обратная зависимость отсутствует (Б → А), то говорят, что В

транзитивно зависит от А.

Если в отношении каждому значению атрибута А соответствует

множество значений атрибута Б, не связанных с другими атрибутами

(этого же отношения), то говорят, что атрибут Б

многозначно зависит от

А.

Отношение находится в первой нормальной форме (1НФ) тогда и

только тогда, когда в любом допустимом значении этого отношения ка-

ждая его строка содержит только одно значение для каждого атрибута

(столбца).

Отношение находится во второй нормальной форме (2НФ), если

оно удовлетворяет определению 1НФ и все его атрибуты (

столбцы), не

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

мостью с первичным ключом (нет атрибутов, зависящих от части пер-

вичного ключа).

Отношение находится в третьей нормальной форме (3НФ), если

оно удовлетворяет определению 2НФ и ни один из его неключевых ат-

рибутов не связан функциональной зависимостью с любым другим не-

ключевым

атрибутом (отсутствуют транзитивные зависимости).

функциональной зависимости. Функционально зависимым счита-

ется такой атрибут, значение которого однозначно определяется значе-

нием другого атрибута. Функционально зависимые атрибуты обознача-

ются следующим образом: А → Б. Атрибут, указываемый в левой части,

называетс

Первичный ключ таблицы является детерминантом, так как его

значение однозначно определяет значение любого атрибута таблицы.

Если для некоторых атрибутов А и Б всегда каждому значению А

соответствует не более одного значения Б, то говорят, что атрибут Б

функционально зависит от А.

Если неключевой атрибут зависит только от части ключа, то

гово-

рят о частичной

Мартьянова А.Е. Базы данных и знаний 37

Кодд и Бойс обосновали и предложили более строгое определение

для 3НФ, которое учитывает, что в таблице может быть несколько пер-

вичных ключей.

Отношение находится в нормальной форме Бойса-Кодда (НФБК)

тогда и только тогда, когда любая функциональная зависимость между

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

можного первичного ключа.

В следующих нормальных формах (4НФ и 5НФ) учитываются не

только функциональные, но и многозначные зависимости между атрибу-

тами. Для того чтобы привести определения этих нормальных форм, вве-

дем понятие полной декомпозиции отношения.

Полной декомпозицией отношения называют такую совокупность

произвольного числа ее проекций, соединение которых полностью сов-

падает с содержимым отношения.

Проекция – операция реляционной алгебры, создающая новое от-

ношение путем исключения «ненужных» столбцов из имеющегося от-

ношения.

Отношение находится в пятой нормальной форме (5НФ) тогда и

только тогда, когда в каждой его полной декомпозиции все проекции со-

держат возможный ключ. Отношение, не имеющее ни одной полной де-

композиции, также находится в 5НФ

Четвертая нормальная форма (4НФ) является частным случаем

5НФ, когда полная декомпозиция должна быть соединением ровно двух

проекций. На практике непросто подобрать реальное отношение, которое

находилось бы в 4НФ, но не было бы в 5НФ.

Все полученные выше отношения «Группа», «Кафедра», «Препо-

даватель», «Студент», «Успеваемость», «Учебный план» находятся в

первой нормальной

форме, так как каждый столбец таблицы неделим и в

рамках од слу зна-

чениями.

ного отношения нет столбцов с одинаковыми по смы

Поля Оценка и Дата сдачи из отношения «Учебный план» следует

перенести в отношение «Успеваемость», поскольку они будут зависеть

от составного ключа отношения «Успеваемость», состоящего из полей

Код студента и Код

учебного плана (рис. I.18). Теперь все таблицы име-

ют первичные ключи, которые однозначно определяют строки и неизбы-

точны, и можно говорить то том, что таблицы находятся во второй нор-

мальной форме.

Мартьянова А.Е. Базы данных и знаний 38

ГРУППА

Код группы

Обозначение группы

Количество студентов

Средний балл при поступлении

СТУДЕНТ

Код студента

Номер зачетной книжки

Фамилия

Имя

Отчество

Год рождения

Адрес

ний телефон

Балл при поступлении

Код группы

Домаш

КАФЕДРА

Код кафедры

Название кафедры

Телефон

Заведующий

ПРЕПОДАВАТЕЛЬ

Код преподавателя

Табельный номер

Фамилия

Имя

Отчество

Домашний адрес

Домашний телефон

Должность

Ученая степень

Ученое звание

Код кафедры

УЧЕБНЫЙ ПЛАН

Код учебного плана

Наименование

предмета

Программа

Часы

Вид занятия

Семестр

Вид сдачи

Код преподавателя

УСПЕВАЕМОСТЬ

Код студента

Код учебного плана

Оценка

Дата сдачи

Рис. I.18. II нормальная форма отношения «Учебный процесс»

Рассмотрим подробнее отношение «Учебный план», которое со-

держит перечень предметов текущего учебного плана [7]. Отношение

следует привести к третьей нормальной форме. Первичным ключом от-

ношен

местров длится изучение предмета. Тогда хранение

наименований предметов в таблице «Учебный план» становится избы-

ия «Учебный план» служит столбец Код учебного плана, который

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

до семестра. То есть для предмета, протяженность изучения которого бо-

лее

одного семестра, в отношении будет отведено несколько строк –

столько, сколько се

Мартьянова А.Е. Базы данных и знаний 39

точны

записях и

есть в ного и

того ж

чеб-

ный п

учим отношение «Предмет» со

столбцами Код предмета и

Наим

ключ Код предмета. Будем

счита

иальности, например,

предм

естить в отноше-

ние «

рибутом Код предмета, поскольку Программа пред-

мета

оизво-

дить

данны

ально, то столбцы «Телефон» и «Заведующий» могут нахо-

диться в полной функциональной за симости от него. То есть столбец

Название кафедры является возможным ключом. Аналогично можно

рассмотреть «Предмет»,

столб

Кодда.

м: например, если изучение математики длится четыре семестра,

то наименование «Математика» будет повторено в четырех

ероятность сделать четыре различные ошибки при вводе од

е наименования.

Чтобы избежать этого, проведем декомпозицию отношения «У

лан», выделив наименования предметов в отдельное отношение. В

результате пол

енование предмета, а в отношение «Учебный план» для связи с от-

ношением «Предмет» поместим внешний

ть, что Код предмета однозначно идентифицирует конкретный

предмет, изучаемый студентами какой-либо спец

ет «Базы данных и знаний специальности 032001.65». Столбец

Программа из отношения «Учебный план» следует

пом

Предмет», так как этот столбец связан функциональной зависимо-

стью с ключевым ат

зависит от Кода предмета, характеризующего предмет, изучаемый

студентами какой-либо специальности.

Возможно выделение еще двух отдельных отношений «Вид сдачи»

и «Вид занятия» из отношения «Учебный план». Мы не будет

пр

дальнейшую декомпозицию отношения «Учебный план» чтобы не

увеличивать число таблиц и не затруднять в дальнейшем работу с базой

х «Учебный процесс».

Таблицы находятся в нормальной форме Бойса-Кодда (НФБК). На-

пример, в отношении «Кафедра» столбец Название кафедры тоже может

быть первичным ключом, тогда, если предположить, что название ка-

федры уник

ви

столбец Наименование предмета в отношении

ец Табельный номер в отношении «Преподаватель», столбец Номер

зачетной книжки в отношении «Студент», столбец Название группы в

отношении

«Студент». Таким образом, рассматриваемая нами схема на-

ходится в нормальной форме Бойса-

На практике нормальная форма Бойса-Кодда в большинстве случа-

ев достаточна, и приведением к ней процесс проектирования реляцион-

ной базы данных обычно заканчивается. Поэтому здесь не будем рас-

сматривать другие нормальные формы, тем более что в работе

они ис-

пользуются редко.

Мартьянова А.Е. Базы данных и знаний 40

Теперь можно говорить о базе данных «Учебный процесс», реля-

ционная схема которой представлена следующими таблицами:

«Группа» – содержит по одной строке для каждой из групп;

ной таблицы нет

столбцов с одинаковыми по смыслу значениями (1НФ);

• ервичные ключи однозначно определяют запись и неизбыточны,

все по ного ключа (2НФ);

•

чи. Задание первичных и

внешних кл ительных струк-

тур –

«Студенты» – содержит по одной строке для каждого из студентов;

«Кафедра» – содержит по одной строке для каждой из кафедр;

«Преподаватель» – содержит по одной строке для каждого

из пре-

подавателей;

«Предмет» – содержит по одной строке для каждого из предметов

учебного плана какой-либо специальности;

«Учебный план» – содержит по одной строке для каждого вида за-

нятия по каждому предмету отдельного семестра;

«Успеваемость» – содержит по одной строке для каждого резуль-

тата сдачи отдельным студентом отдельного предмета.

Таблицы базы

данных «Учебный процесс» находятся в третьей

нормальной форме:

• каждый столбец таблицы неделим, и в рамках од

ля каждой из таблиц зависят от ее первич

значение любого поля, не

входящего в первичный ключ, не зависит

от значения другого поля, тоже не входящего в первичный ключ (3НФ).

На рис. I.19 в графической форме изображены перечисленные таб-

лицы, их столбцы, первичные и внешние клю

ючей сопровождается построением дополн

индексов, обеспечивающих быстрый доступ к данным через значе-

ние

ключа.

Рис. I.19. Структура базы данных «Учебный процесс»