Ковалевич И.А. Основы баз данных: учебное пособие

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

3. Если в каждой комнате установлен один телефон, то номер

телефона функционально зависит от номера комнаты:

НОМЕР КОМНАТЫНОМЕР ТЕЛЕФОНА

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

неключевые атрибуты функционально зависят от ключа отношения.

Напомним, что ключ отношения называется составным если

содержит несколько атрибутов.

 Неключевой атрибут функционально полно

зависит от составного ключа, если он функционально зависит от

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

какой части составного ключа.

Рассмотрим для примера отношение R2.

Атрибуты ФИО_РОДИТЕЛЯ, ОКЛАД, КОМНАТА и ТЕЛЕФОН не

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

поскольку они функционально зависят от части ключа –

ТАБЕЛЬНОГО_НОМЕРА. Остановимся на атрибуте ОКЛАД. Рационально

ли хранить эту информацию в отношении R2, каждый кортеж которого

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

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

детей и для каждого из них будут храниться сведения об окладе родителя.

Следовательно, при изменении оклада понадобится корректировать не один,

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

сотрудниками, у которых нет детей. Им не соответствует ни один кортеж

отношения, а значит, БД не может содержать сведений о таких сотрудниках.

Иными словами, отношение в первой нормальной форме может

потребовать последующих преобразований.

 Отношение находится во второй нормальной

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

неключевой атрибут функционально полно зависит от составного

ключа.

Очевидно, рассмотренное на Рис.Y 5 .10отношение R2 находится в

первой нормальной форме, но не находится во второй нормальной форме.

Чтобы отношение привести ко второй нормальной форме,

необходимо:

а) построить его проекцию, исключив атрибуты, которые не

находятся в полной функциональной зависимости от составного ключа;

б) построить дополнительно одну или несколько проекций на части

составного ключа и атрибуты, функционально зависящие от этих частей

ключа.

В нашем примере отношение R2 преобразовано в два отношения R3

и R4, каждое из которых находится во второй нормальной форме.

5.5.3.ТРЕТЬЯ НОРМАЛЬНАЯ ФОРМА

 Пусть X, Y, Z - три атрибута некоторого

отношения. При этом X



Y и Y



Z, но обратное соответствие

отсутствует, т. е. X,



,,Z. Тогда говорят, что Z транзитивно

зависит от X. (см. транзитивность)

Обратимся к отношению R4. В нем можно увидеть пример

транзитивной зависимости:

ТАБЕЛЬНЫИ-НОМЕРКОМНАТАТЕЛЕФОН;

Хранение в отношении атрибутов, находящихся в транзитивной

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

атрибута ТЕЛЕФОН в отношении R4.

Номер телефона есть характеристика комнаты, поэтому сведения о

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

места которых расположены в одной комнате. Кроме прочего, изменение

номера телефона потребует корректировки большого числа кортежей.

Сложности возникают, когда в комнате нет, например, временно

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

другую. Отношение R4 позволяет содержать информацию о комнате и

установленном в ней телефоне только, когда за комнатой закреплено

рабочее место хотя бы одного сотрудника.

 Отношение находится в третьей нормальной

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

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

ключа.

Для преобразования отношения к третьей нормальной форме также

необходимо построить несколько проекций. Для нашего примера (см.YРис.Y 5

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

приведено к двум отношениям R5 и R6. Первое содержит список всех

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

всех комнат и данные о номере телефона в каждой комнате.

Как видим, в процессе приведения отношений ко второй и третьей

нормальным формам число отношений в схеме БД увеличивается. Однако

всегда сохраняется возможность получить исходные отношения

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

С другой стороны, появление новых отношений порождает проблемы

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

разных моделей данных.

Более высокие формы нормализации (нормальная форма Бойса-

Кодда, четвертая нормальная форма, пятая нормальная форма) при создании

систем обработки данных применяются нечасто, поэтому мы не будем их

здесь подробно рассматривать.

С целью экономии памяти и ускорения обработки данных

достаточно часто в таблицы добавляются числовые поля (например

автоинкрементные), которые используются вместо текстовых или составных

первичных и внешних ключей. Логично, например вместо конкатенации

полей ФАМИЛИЯ, ИМЯ, ОТЧЕСТВО использовать некоторый числовой

идентификатор ИД, даже если в предметной области он отсутствуют. Ввод

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

самым усложняет процесс нормализации. Для упрощения нормализации

подобных таблиц целесообразно цифровые (или другие) заменители

составных и (или) текстовых первичных и внешних ключей, хотя бы

мысленно подменять их на исходные ключи, а после окончания

нормализации снова восстанавливать.

5.6. СВЯЗИ МЕЖДУ ТАБЛИЦАМИ

Рис. 5.11. Связи между таблицами.

ФАКУЛЬТЕТЫ

КодФакультета Наименование

001 Юридический

…

019 Филологический

ГРУППЫ

НомерГруппы

КодФакультета

Ф 37-1 019

Ф 37-2 019

… …

Ю 98-1 001

СТУДЕНТЫ

КодСтудента Фамилия И. О НомерГруппы

0001 Иванов С. О. Ю 98-1

0002 Сергеев П. И Ю 98-1

… … …

0099 Федоров А. А. Ф 37-1

Мы уже говорили, что математические термины отношение, кортеж,

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

использовать их неформальные эквиваленты: таблица, строка или запись,

столбец или поле, соответственно. Термин отношение будем применять для

определения типа связей между таблицами.

Достаточно часто сведения об одних тех же объектах предметной

области помещаются в разные таблицы. Более того, объекты могут

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

продумать, каким образом СУБД будет объединять эти сведения при их

извлечении из базы данных. Для этого необходимо определить связи между

таблицами. После чего становится возможным получать согласованные

данные из нескольких таблиц сразу.

В приведенном на Рис. 5 .11 примере для получения списка

студентов некоторого факультета данные полей в различных таблицах

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

осуществляется путем установления связей между таблицами. Связь между

таблицами устанавливает отношения между совпадающими значениями в

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

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

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

ключей рекомендуется давать одинаковые имена).

Обычно рассматриваются четыре основных типа отношений между

таблицами: «один – к одному», «один - ко многим», «многие - к одному» и

«многие – ко многим». Рассмотрим их.

5.6.1.ОТНОШЕНИЕ «ОДИН - КО МНОГИМ»

Связь с отношением «один–ко–многим» является наиболее часто

используемым типом связи между таблицами. В такой связи каждой записи

в таблице A могут соответствовать несколько записей в таблице B, а запись

в таблице B не может иметь более одной соответствующей ей записи в

таблице A.

На Рис. 5 .11 показаны отношения «один–ко–многим», связывающие

одну запись таблицы ФАКУЛЬТЕТЫ с несколькими записями таблицы

ГРУППЫ, записи которой, в свою очередь связаны с таблицей СТУДЕНТЫ.

5.6.2.ОТНОШЕНИЕ «МНОГИЕ - К ОДНОМУ»

Отношение «многие–к–одному» противоположно типу «один–ко–

многим» и является его отражением. Отличие состоит в том, что при

удалении всех записей в таблице со стороны «многие» должна быть удалена

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

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

ко–многим» не играет большой роли. В этом случае отношение называется

рефлексивным.

5.6.3.ОТНОШЕНИЕ «ОДИН – К ОДНОМУ»

При отношении «один–к–одному» запись в таблице A может иметь

не более одной связанной записи в таблице B и наоборот. Этот тип связи

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

одну таблицу. Связь с отношением «один–к–одному» используют для

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

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

подмножеству записей в главной таблице.

Например, чтобы определить декана факультета, который в свою

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

таблицами ПРЕПОДАВАТЕЛИ и ФАКУЛЬТЕТЫ. Для поддержания

условия – «один преподаватель может быть деканом только на одном

факультете» тип связи должен быть установлен «один–к–одному». Для

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

«Декан». В этом случае значения полей «Декан» таблицы ФАКУЛЬТЕТЫ

будут подмножеством значений полей «КодПреподвателя» таблицы

ПРЕПОДАВАТЕЛИ.

Рис. 5.12. Пример отношения "один–к–одному"

5.6.4.ОТНОШЕНИЕ «МНОГИЕ – КО МНОГИМ»

Рис. 5.13. Пример реализации отношения "многие–ко–многим"

ФАКУЛЬТЕТЫ

КодФакультета Декан Наименование

001 0003 Юридический

… … …

019 0001 Филологический

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

КодПреподавателя ФамилияИО

0001 Сергеев И. П.

0002 Антонов С. И.

0003 Федорова А. Т.

… …

ФАКУЛЬТЕТЫ

КодФакультета Наименование

001 Юридический

…

019 Филологический

ГРУППЫ СВЯЗУЮЩАЯ ТАБЛИЦА

Код

Факультета

Номер

Группы

Номер

Группы

Код

Факультета

Код

Студента

019 Ф 37-1 Ю 98-1 001 0001

019 Ф 37-2 Ю 98-1 001 0002

… … … … …

001 Ю 98-1 Ф 37-1 019 0099

Ю 98-1 001 0099

СТУДЕНТЫ

КодСтудента Фамилия И. О

0001 Иванов С. О.

0002 Сергеев П. И

… …

0099 Федоров А. А.

При отношении «многие–ко–многим» одной записи в таблице A

могут соответствовать несколько записей в таблице B, а одной записи в

таблице B несколько записей в таблице A. Такая схема реализуется только с

помощью третьей (связующей) таблицы, ключ которой состоит из по

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

таблицах A и B.

В примере приведенном на Рис. 5 .13 студенты Иванов, Сергеев и

Федоров учатся в одной группе Ю 98-1, в то же время студент Федоров

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

группе Ф 37-1. Для того, чтобы исключить ситуацию, когда один и тот же

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

поле «КодФакультета» и создать уникальный составной ключ по полям

«КодФакультета» и «КодСтудента».

6. ОРГАНИЗАЦИЯ ХРАНЕНИЯ ДАННЫХ

6.1. ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И СТРУКТУРНЫЕ

АССОЦИАЦИИ

6.1.1.ЦЕПНЫЕ СПИСКИ

Память современных вычислительных машин физически устроена

как вектор элементов некоторого типа (байтов, кластеров и т. д.) с индексом

от нуля до некоторого максимального значения. Индекс элемента в памяти

называется его адресом по которому и осуществляется доступ к данным

Поскольку хранение структур данных (например записей) в непрерывных

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

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

связанных распределений. Наиболее распространенный способ - построение

цепных списков.

Головной элемент данных в служебной части содержит адресную

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

(Рис.Y 6 .1). Тем самым образуется цепной список, обходя который, можно

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

Рис.Y6.1. Цепные списки.(ссылки на следующий):

а – разомкнутый; б – замкнутый.

Последний элемент либо содержит ссылку на головной, либо в поле

ссылки—признак конца цепи. В первом случае цепной список будет

замкнутым, а во втором—разомкнутым.

Рассмотренный тип ссылок между элементами данных называется

ссылками «на следующий». В цепном списке могут использоваться и другие

разновидности ссылок.

Рис.Y6.2. Двунаправленный разомкнутый цепной список(ссылки на предыдущий

изображены пунктиром).

Участники цепного списка могут содержать в служебной части

дополнительно ссылку «на предыдущий». При наличии такой ссылки

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

ссылка «на предыдущий», то она формируется у всех участников цепного

списка, включая головной. Головной при этом будет содержать, кроме

ссылки на первый элемент, еще ссылку на последний (Рис.Y 6 .2). Такой

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

Использование списков позволяет легко включать и исключать

элементы данных из информационных структур. Положим, после

извлечения элементаY2 (см.YРис.Y 6 .1) принято решение об его удалении.

Удаление будет выполнено корректно, если после его завершения элемент 1

будет содержать в служебной части адресную ссылку на элемент 3.