Глушаков С.В., Ломотько Д.В. Базы данных

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

Часть I. Теория баз данных

Целостность данных

В реляционных моделях вопросу целостности данных отво-

дится особое место. Напомним, что ключ или потенциальный

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

можно однозначно найти требуемый кортеж. Минимальность

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

ет идентифицировать кортеж по оставшимся атрибутам.

Каждое отношение обладает хотя бы одним возможным клю-

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

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

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

бутов. Нежелательно также использовать ключи с длинными тек-

стовыми значениями (предпочтительнее использовать целочис-

ленные атрибуты). Так, для идентификации работника можно

использовать либо уникальный табельный номер или номер пас-

порта, либо набор из фамилии, имени, отчества и номера отдела.

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

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

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

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

вичного ключа, поэтому за этим при проектировании БД необхо-

димо следить особо тщательно.

Теперь поговорим о внешних ключах. Стоит иметь в виду, что

если отношение С связывает отношения А и В, то оно должно

включать внешние ключи, соответствующие первичным ключам

отношений А и В, что представлено на рис. 1.9. Таким образом,

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

БД возникает вопрос о том, каковы же должны быть внешние

ключи. При этом для каждого внешнего ключа необходимо ре-

шить проблему, связанную с возможностью (или невозможно-

стью) появления во внешних ключах неопределенных значений

(NULL-значений - значений атрибута для отсутствующей инфор-

мации). Другими словами, может ли существовать некоторый

кортеж в отношении, для которого неизвестен кортеж в связан-

ном с ним отношении.

С другой стороны, необходимо заранее обдумать вопрос о

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

ния, на которое ссылается внешний ключ. При этом существуют

следующие вероятные возможности:

Отаве 1.2. Реляционная модель базы данных

операция каскадируется - то есть удаление кортежей в

отношении приводит к удалению соответствующих кор-

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

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

отношении приводит к удалению информации о его зара-

ботной плате в другом;

-I

Первичный ключ I Прочие атрибуты

отношения А | отношения А

Внешний ключ А

Первичный ключ

отношения В

Внешний ключ В

Прочие атрибуты

• отношения В

Прочие атрибуты

отношения С

Рис. 1.9. Внешние ключи

• операция ограничивается - то есть удаляются лишь те

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

отношении нет. Если таковая информация имеется, то

удаление осуществить нельзя. Например, удаление ин-

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

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

плате в связанном отношении отсутствует.

Наконец, нужно предусмотреть технологию того, что будет

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

шения, на которое ссылается некоторый внешний ключ. Здесь

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

• операция каскадируется - то есть при обновлении пер-

вичного ключа происходит обновление внешнего ключа в

связанном отношении. Например, обновление первичного

ключа в отношении, где хранится информация о сотруд-

нике приводит к обновлении внешнего ключа в отноше-

нии с информацией о его заработной плате;

• операция-ограничивается - то есть обновляются лишь

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

ции в другом отношении нет. Если таковая информа-

ция имеется, то обновление сделать нельзя. Например,

обновление первичного ключа в отношении, где хра-

нится информация о сотруднике, возможно в том слу-

Часть I. Теория баз данных

чае. если информация о его заработной плате в связан-

ном отношении отсутствует.

Таким образом, для каждого внешнего ключа в БД должны

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

составляющих этот внешний ключ, и отношение, идентифици-

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

смотренных выше случаях.

Реляционная алгебра

Начальный обзор; традиционные операции над множества-

ми; специальные реляционные операции: операции расширения

и подведения итогов; операторы обновления: реляционные

сравнения.

Формальной основой реляционной модели БД являются реля-

ционная алгебра, основанная на теории множеств и рассматри-

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

исчисление, базирующееся на математической логике.

Выборка Проекция Объединение

Пересечение

Вычитание

Произведение

-А

—у

Соединение

Деление

-у

Рис. 1.10. Основные операторы реляционной алгебры

Глава 1.2. Реляционная модель вазы данных

Основных операторов в реляционной алгебре восемь, и схема-

тически их можно представить так, как это показано на рис. 1.10.

Надо отметить, что реляционная алгебра обладает большой мощ-

ностью - сложные запросы к БД могут быть выражены с помо-

щью одного выражения. Именно по этой причине эти механизмы

включены в реляционную модель данных. Конкретный язык ма-

нипулирования реляционными БД называется реляционно-

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

ражения реляционной алгебры или одной формулы реляционного

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

этого языка.

Реляционная алгебра обладает важным свойством - она замк-

иуга относительно понятия отношения. Это означает, что выра-

жения реляционной алгебры выполняются над отношениями ре-

ляционных БД и результаты их вычисления также представляют

собой отношения. Поэтому любое выражение может быть пред-

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

выражениях реляционной алгебры.

Основная идея реляционной алгебры состоит в том. что

средства манипулирования отношениями, рассматриваемыми

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

операциях, дополненных некоторыми специфичными опера-

циями для БД.

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

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

интерпретации, но в принципе все они более или менее равно-

сильны. Опишем вариант алгебры, который был предложен Код-

дом. В этом варианте, как уже было показано выше, набор алгеб-

раических операций состоит из восьми основных:

выборка отношения;

проекция отношения;

объединения отношений;

пересечение отношений;

вычитание отношений;

произведение отношений.

соединение отношений;

деление отношений.

Эти операции можно объяснить следующим образом:

• результатом выборки отношения по некоторому условию

является отношение, которое включает только те кортежи

первоначального отношения, которые удовлетворяют

этому условию;

Часть I. Теория баз данных

• при осуществлении проекции отношения на заданный на-

бор его атрибутов будет получено отношение, кортежи

которого взяты из соответствующих кортежей первона-

чального отношения:

• при выполнении операции объединения двух отношений

будет получено отношение, включающее все кортежи,

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

ношений;

• в качестве результата операции пересечения двух отно-

шений получается отношение, включающее все кортежи,

входящие в оба первоначальные отношения;

• отношение, являющееся разностью двух отношений,

включает все кортежи, входящие в первое отношение и

одновременно такие, что ни один из них не входит в от-

ношение, являющееся вторым;

• при выполнении прямого произведения двух отношений

получается отношение, кортежи которого являются соче-

танием кортежей первого и второго отношения:

• при соединении двух отношений по некоторому условию

образуется результирующее отношение, кортежи которо-

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

ношения, удовлетворяющим этому условию;

* операция реляционного деления имеет два операнда - би-

нарное (т. е. состоящее из двух атрибутов) и унарное (со-

держит один атрибут) отношения. Результат операции -

отношение, состоящее из кортежей, включающих значе-

ния первого атрибута кортежей первого отношения, при-

чем таких, что множество значений второго атрибута

совпадает со множеством значений второго отношения.

Помимо вышеперечисленных, есть ряд особых операций,

характерных для работы с БД:

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

ношение, набор кортежей которого совпадает с телом

первоначального отношения, но имена атрибутов изме-

нены;

• операция присваивания позволяет сохранить результат

вычисления реляционного выражения в существующем

отношении БД.

Отсюда следует, что если результатом реляционной операции

является некоторое отношение, то имеется возможность образо-

вывать реляционные выражения, в которых вместо первоначаль-

Глвва 1.2. Реляционная модель базы данных

ного отношения (отношения-операнда) будет использоваться

вложенное реляционное выражение. Это происходит благодаря

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

замкнуты относительно понятия отношения.

Начнем с операции объединения отношений, однако это в

равной мере относится к операциям пересечения и вычитания. В

реляционной алгебре результатом операции объединения должно

являться отношение. Если допустить в реляционной алгебре воз-

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

наборами атрибутов,' то результатом такой операции будет мно-

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

ще говоря, не отношение. Если исходить из требования замкну-

тости реляционной алгебры относительно понятия отношения, то

такая операция объединения является бессмысленной. Это при-

водит к появлению понятия совместимости отношений по объе-

динению: два отношения совместимы по объединению в том и

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

Более точно это означает, что в заголовках обоих отношений со-

держится один и тот же набор имен атрибутов, и одноименные

атрибуты определены на одном и том же домене.

При условии того, что два отношения совместимы по объеди-

нению, то при обычном выполнении над ними операций объеди-

нения, пересечения и вычитания результатом операции является

отношение с корректно определенным заголовком, совпадающим

с заголовком каждого из отношений-операндов. Если же два от-

ношения не полностью совместимы по объединению, то есть со-

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

рации типа соединения эти отношения можно сделать полностью

совместимыми по объединению путем применения операции пе-

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

Операция прямого произведения двух отношений вызывает

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

быть получено для любых двух множеств. Элементами результи-

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

ментов первого и второго множеств. Поскольку отношения явля-

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

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

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

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

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

расширенное прямое произведение отношений. При взятии рас-

ширенного прямого произведения двух отношений элементом

результирующего отношения является кортеж, формирующийся

Часть I Теория баз данных

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

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

занная с получением корректно сформированного заголовка ре-

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

понятия совместимости отношений по взятию расширенного

прямого произведения. Два отношения совместимы по взятию

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

ства имен атрибутов этих отношений не пересекаются. Любые

два отношения могут быть преобразованы к совместимому виду

по взятию прямого произведения путем применения операции

переименования к одному из этих отношений.

Операция выборки требует наличия двух отношений: перво-

начального отношения-операнда и простого условия ограниче-

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

отношение, заголовок которого совпадает с заголовком отноше-

ния-операнда, а в тело входят те кортежи отношения-операнда,

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

Введем ряд операторов. Пусть UNION обозначает операцию

объединения, INTERSECT - операцию пересечения, a MINUS -

операцию вычитания. Для обозначения операции выборки будем

использовать конструкцию A WHERE В, где А - отношение-

операнд, а В - простое условие сравнения. Пусть С1 и С2 - два

простых условия выборки. Тогда по определению:

A WHERE Cl AMD C2 обозначает то же самое,

что и (A WHERE Cl) INTERSECT (A WHERE C2)

A WHERE Cl OR C2 обозначает то же.самое, что

и (A WHERE Cl) UNION (A WHERE C2)

A WHERE NOT Cl обозначает то же самое, что и

A MINUS (A WHERE Cl) .

С использованием этих определений можно реализовать опе-

рации выборки, в которых условием выборки является произ-

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

с использованием логических связок AND (логическое И), OR

(логическое ИЛИ), NOT (логическое НЕ) и скобок.

Операция взятия проекции также требует наличия двух

операндов - проецируемого отношения А и списка имен

атрибутов, входящих в заголовок отношения А.

Результатом проекции отношения А по списку атрибутов а,,

;

, ..., а„ будет отношение, заголовком которого является множе-

ство атрибутов a

;-a

..".., К- Тело результата будет состоять из

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

Глава 1.2. Реляционная модель базы данных

которого имеет значение v,, атрибут а

имеет значение v

, • ••,

атрибут а„ имеет значение v

. До сути, при выполнении операции

проекции определяется "вертикальная" вырезка отношения-

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

Операция соединения, называемая иногда соединением по ус-

ловию, требует наличия двух операндов - соединяемых отноше-

ний и третьего операнда - простого условия. Пусть соединяются

отношения А и В. Как и в случае операции выборки, условие со-

единения С имеет вид либо (a comp-op b), либо (а сотр-ор const),

где а и b - имена атрибутов отношений А и В, const - литерально

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

операция сравнения. Тогда по определению результатом опера-

'нии соединения является отношение, получаемое путем выпол-

нения операции ограничения по условию С прямого произведе-

ния отношений А и В.

*]' Имеется важный частный случай соединения - естествен-

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

естественного соединения, если условие соединения имеет вид

(а = Ь), где а и b - атрибуты разных операндов соединения.

Этот случай важен потому, что он особо часто встречается на

практике и для него существуют эффективные алгоритмы реа-

лизации в СУБД. Операция естественного соединения приме-

няется к паре отношений А и В, обладающих общим атрибу-

том R. то есть атрибутом с одним и тем же именем и опреде-

ленным на одном и том же домене. Пусть ab обозначает объе-

динение заголовков отношений А и В. Тогда естественное со-

единение А и В - это спроектированный на ab результат со-

единения А и В. Операция естественного соединения не вклю-

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

но она имеет очень важное практическое значение.

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

объяснении, поскольку наиболее трудная для понимания. Пусть

заданы два отношения - А с заголовком {ai, а

,.... a,,, b

\h,...... Ь„,}

и В с заголовком {Ь

Ьг, ..., b

}. Будем полагать, что атрибут Ь,

отношения А и атрибут Ь, отношения В обладают одним и тем же

именем и определены на одном и том же домене. Назовем мно-

жество атрибутов {aj} составным атрибутом а, множество атри-

бутов {bj} - составным атрибутом Ь. После этого будем говорить

о реляционном делении бинарного отношения А(а,Ь) на унарное

отношение В(Ь).

Результатом деления А на В является унарное отношение

С(а), состоящее из таких кортежей v, что в отношении А имеются

Часть I. Теория баз данных

кортежи <v, w> которые во множестве значений {w} включают

множество значений атрибута b в отношении В.

Поскольку деление наиболее трудная операция, поясним ее

примером. Пусть в БД студентов имеются два отношения: СТУ-

ДЕНТЫ (ФИО, НОМЕР) и ИМЕНА (ФИО), причем унарное от-

ношение ИМЕНА содержит все фамилии, которыми обладают

студенты института. Тогда после выполнения операции реляци-

онного деления отношения СТУДЕНТЫ на отношение ИМЕНА

будет получено унарное отношение, содержащее номера студен-

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

ми в этом институте фамилиями.

Реляционное исчисление

Допустим, что имеется БД, обладающая следующей структу-

рой: отношение СТУДЕНТЫ (СТУД_НОМ. СТУД_ИМЯ,

СТУД_СТИП, ГР_НОМ) и отношение ГРУППЫ (ГРНОМ.

ГРКОЛ, ГР СТАР). Предположим, что необходимо узнать име-

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

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

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

ляционная алгебра, то мы получили бы алгебраическое выраже-

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

• выполнить соединение отношений СТУДЕНТЫ и ГРУП-

ПЫ по условию СТУД_НОМ = ГРСТАР:

• ограничить полученное отношение по условию

ГР_КОЛ>25;

• спроецировать результат предыдущей операции на атри-

бут СТУД_ИМЯ СТУД_НОМ.

Здесь пошагово сформулирована последовательность выпол-

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

ляционной операции. Если же сформулировать тот же запрос с

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

формулу, которую можно было бы прочитать, например, сле-

дующим образом: Выдать СТУД_ИМЯ и СТУД_НОМ для таких

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

ГР_СТАР и значением ГРКОЛ. большим 25.

Во второй формулировке мы указали лишь характеристики

результирующего отношения, но ничего не сказали о способе его

формирования. В этом случае СУБД должна сама решить, что за

операции и в каком порядке нужно выполнить над отношениями

Глава 1.2. Реляционная модель базы данных

СТУДЕНТЫ и ГРУППЫ. Оба рассмотренных в примере способа

на самом деле эквивалентны, и существуют не очень сложные

правила преобразования одного в другой.

Базисными понятиями реляционного исчисления являются

понятие переменной с определенной для нее областью допусти-

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

рающейся на переменные и специальные функции.

В зависимости от того, что является областью определения

переменной, различаются исчисление кортежей и исчисление

доменов. В исчислении кортежей областями определения пере-

менных являются отношения БД, то есть допустимым значением

каждой переменной является кортеж некоторого отношения. В

исчислении доменов областями определения переменных явля-

ются домены, на которых определены атрибуты отношений БД,

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

чение некоторого домена.

Для определения кортежной переменной используется опера-

тор RANGE. Например, для того, чтобы определить переменную

СТУДЕНТ, областью определения которой является отношение

СТУДЕНТЫ, нужно употребить конструкцию

RANGE СТУДЕНТ IS СТУДЕНТЫ

Из этого определения следует, что в .любой момент времени

переменная СТУДЕНТ представляет некоторый кортеж отноше-

ния СТУДЕНТЫ. При использовании кортежных переменных в

формулах можно ссылаться на значение атрибута переменной.

Например, для того, чтобы сослаться на значение атрибута

СТУД_ИМЯ переменной СТУДЕНТ, нужно употребить конст-

рукцию СТУДЕНТ.СТУД_ИМЯ.

Правильно построенные формулы служат для выражения ус-

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

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

операции сравнения значений атрибутов ^переменных или лите-

рально заданных констант. Например, конструкция "СТУ-

ДЕНТ.СТУД_НОМ=123456" является простым сравнением. Бо-

лее сложные варианты правильно построенных формул реализу-

ются с помощью логических связок NOT. AND. OR и IF ... THEN.

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

мул с помощью кванторов. Если F - это правильно построенная

формула, в которой участвует переменная var, то конструкции

EXISTS var (F) и FORALL var (F) являются правильными. Здесь

Часть I. Теория баз данных

квантор EXISTS обозначает "существование", a FOR ALL - "для

всех кортежей".

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

могут быть свободными или связанными. Все переменные, вхо-

дящие в их состав, при построении которой не использовались

кванторы, являются свободными. Фактически, это означает, что

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

менных при вычислении формул получено значение "истина", то

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

рующее отношение. Если же имя переменной использовано сразу

после квантора при построении формул вида EXISTS var (F) или

FOFiALL var (F) то здесь, и во всех формулах, где она использо-

вана, var - связанная переменная. При вычислении значения та-

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

чение связанной переменной, а вся ее область определения.

Пусть СТУД1 и СТУД2 - две кортежные переменные, опреде-

ленные на отношении СТУДЕНТЫ. Тогда, формула

EXISTS СТУД2(СТУД1.СТУД_СТИП>СТУД2.СТУД_СТИП)

для текущего кортежа переменной СТУД1 принимает значение

"истина" только в том случае, если во всем отношении СТУДЕН-

ТЫ найдется такой кортеж, связанный с переменйой СТУД2, что

значение его атрибута СТУД_СТИП удовлетворяет внутреннему

условию сравнения.

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

FORALL СТУД2(СТУД1.СТУД_СТИП > СТУД2.СТУД_СТИП)

для текущего кортежа переменной СТУД1 принимает значение

"истина" только в том случае, если для всех кортежей отношения

СТУДЕНТЫ, связанных с переменной СТУД2, значения атрибута

СТУД_СТИП удовлетворяют условию сравнения.

Таким образом, правильно построенные формулы обеспечи-

вают средства выражения условия выборки из отношений БД.

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

реальной работы с БД, требуется еще один компонент, который

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

ния. Этот компонент называется целевым списком.

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

которых может иметь следующий вид:

• var.attr, где var - имя свободной переменной соответст-

вующей формуле, a attr - имя атрибута отношения, на ко-

тором определена переменная var;

Глава 1.2. Реляционная модель базы данных

• var, что эквивалентно наличию подсписка var.attrl,

var.attr2, ..., var.attrn, где attrl, attr2, ..., attrn включает

имена всех атрибутов определяющего отношения;

• newname = var.attr; newname - новое имя соответст-

вующего атрибута результирующего отношения.

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

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

областью определения.

В исчислении доменов областью определения переменных яв-

ляются не отношения, а домены. Применительно к БД СТУДЕН-

1ЯЫ-ГРУППЫ можно говорить, например, о доменных перемен-

ных ИМЯ (значения домена - допустимые имена) или НОМСТУД

(значения домена - допустимые номера студентов).

Основным отличием исчисления доменов от исчисления

кортежей является наличие дополнительного набора предика-

тов (см. ниже); позволяющих выражать так называемые усло-

вия членства. Если R - это п-арное отношение с атрибутами а

, ..., а

, то условие членства имеет вид

)

где v,, - это либо литерально задаваемая константа, либо имя кор-

тежной переменной. Условие членства принимает значение ИС-

ТИНА только в том случае, если в отношении R существует кор-

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

тов. Если Vj, - константа, то на атрибут а

задается жесткое усло-

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

еели же v,, - имя доменной переменной, то условие членства мо-

жет принимать различные значения при разных значениях этой

переменной.

Несколько слов о предикатах. Предикатом принято называть

некую логическую функцию, которая для некоторого аргумента

возвращает значение ИСТИНА или ЛОЖЬ. Отношение может

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

атрибутами рассматриваемого отношения. Если заданный кон-

кретный набор кортежей присутствует в отношении, то предикат

выдаст истинный результат, в противном случае - ложный.

Во всех остальных отношениях формулы и выражения исчис-

ления доменов выглядят похожими на формулы и выражения

исчисления кортежей. Реляционное исчисление доменов положе-

но в основу большинства языков запросов, основанных на ис-

пользовании форм.

32 Часть I. Теория баз данных

Глава 1.3

Проектирование логической структуры

базы данных

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

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

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

множествами атрибутов внутри отношения. Для примера рас-

смотрим БД структуры, приведенной на рис 1. 11.

Глава 1.4. Функции защиты базы данных

NAME

(Студенты)

GROUP ] SPEC

Р (Предметы)

PNAME

TEACHER

KAFEDRA

SP (Оценки)

' NAME

SN OCENKA

Рис. 1.11. Структура БД

Здесь отношение S (студенты) - имеет четыре атрибута:

SN - номер студенческого билета;

NAME - фамилия, имя, отчество студента:

GROUP - студенческая группа;

SPEC - наименование специальности.

Отношение Р (предметы) имеет четыре атрибута:

PN - код предмета;

PNAME - наименование предмета;

TEACHER - фамилия, имя, отчество преподавателя:

KAFEDRA - наименование кафедры, на которой читается

данный предмет.

Отношение SP (оценки) состоит из трех атрибутов:

PN - код предмета;

NAME - фамилия, имя, отчество студента;

SN - номер студенческого билета;

OCENKA - оценка по предмету.

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

висимость между множеством атрибутов {SN, PN} и {OCENKA},

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

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

по предмету.

Необходимо заметить тот факт, что следует четко различать

значения того или иного отношения и набор всех возможных

значений, которые данное отношение может принимать в тот или

иной момент времени.

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

зависимости. Если R - некоторое отношение, а X и Y - некоторые

подмножества множества атрибутов отношения R, то Y функ-

ционально зависимо от X при условии, что каждое значение

множества X отношения R связано с одним значением множества

Y отношения R. Это записывается в следующем виде:

Например, в отношении SP все кортежи удовлетворяют усло-

вию {SN, PN} — SP.

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

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

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

симости, имеющие место для всех возможных значений данной

переменной. В нашем случае зависимость

PN - NAME

выполняется для всех возможных значений SP.

Таким образом, если R является переменной отношения, а X и

Y - некоторые подмножества множества атрибутов отношения R,

то Y функционально зависимо от X при условии, что для любого

допустимого значения R каждое значение X связано с одним зна-

чением множества Y.

Кроме того, если X является потенциальным ключом отноше-

ния R, то все атрибуты Y отношения R должны быть функцио-

нально зависимы от X. Например:

PN -~ {PN, NAME, SN,OCENKA}

Если же отношение R удовлетворяет функциональной зави-

симости X —• Y. но X не является потенциальным ключом, то

можно говорить об избыточности R. Так. в отношении PN све-

2 «Базы данных»

Часть I. Теория баз данных

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

оценки.

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

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

стей. Например.

Зависимость {SN, PN} - SP означает и

Зависимости {SN, PN} -> NAME и

{SN, PN} - OCENKA.

В более сложном случае, если имеется отношение R с тремя

атрибутами X, Y, Z, то при условии выполнения функциональных

зависимостей X —<• Y и Y —<• Z, очевидно, имеет место зависи-

мость X —» Z. При этом набор всех функциональных зависимо-

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

зависимостей, принято называть замыканием.

Таким образом, изложенные выше понятия и определения по-

зволяют перейти к вопросам нормализации БД.

Нормализация базы данных

Рассмотрим для начала классический подход, при котором

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

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

приемлемому набору схем отношений. Началом должно служить

представление предметной области (то есть той реальной инфор-

мации, которая будет храниться в БД) в виде одного или несколь-

ких отношений. Рекомендуется на каждом шаге проектирования

производить некоторый набор схем отношений, обладающих

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

Вообще говоря, процесс проектирования представляет собой в

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

дующая нормальная форма (НФ) обладает свойствами лучшими,

чем предыдущая.

Так, скажем, в структуре БД, приведенной на рис. 1.11, интуи-

тивно чувствуется, что имеется избыточность. Действительно, в

отношении SP присутствует атрибут NAME, однако и в отноше-

нии S этот атрибут имеет место. Таким образом, информация о

фамилии и имени студента дублируется При этом возникают

проблемы; например связанные с тем, что при изменении фами-

лии студента возникает необходимость ее изменения в обоих от-

ношениях.

Глава 1.4. Функции защиты базы данных

Из вышесказанного следует простейший вывод - хорошая

структура БД содержит по одному элементу информации и толь-

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

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

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

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

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

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

• нормальная форма Бойса-Кодда (НФБК);

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

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

ции-соединения (5НФ или НФПС).

Каждая НФ более высокого порядка является более выгодной

с точки зрения концепции реляционных БД, чем-- предыдущая.

При этом необходимо заметить тот факт, что если некоторая БД

находится, скажем, во 2НФ, то не исключено, что ее часть уже

находится в ЗНФ, внутри которой может находиться часть в

НФБК и т. д.

Основные свойства НФ:

• каждая следующая НФ в некотором смысле лучше

предыдущей;

• при переходе к следующей НФ свойства предыдущих

нормальных форм сохраняются.

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

ции - декомпозиция отношения, находящегося в предыдущей НФ.

$ два или более отношения, удовлетворяющих требованиям сле-

дующей НФ.

Каждой НФ соответствует некоторый набор ограничений. От-

ношение, находящееся в некоторой НФ, должно удовлетворять

свойственному этой форме набору ограничений. Поскольку требо-

вание 1НФ является базовым в классической реляционной модели

данных, начнем изложение с требований именно к этой форме.

Отношение будет находиться в 1НФ при условии, что оно

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

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

обходимо заметить, что приведенное определение говорит о

нахождении любого нормализованного отношения в 1НФ В то

же время отношение, находящееся только в 1НФ, обладает

структурой не совсем желательной, например, по причине ее

возможной избыточности.

36 Часть I. Теория баз данных

Допустим, что отношение SP (см. рисунок 1.11) содержит всю

информацию о студенческой группе и оценках. Назовем его SP1,

что приведено на рис. 1.12.

SP1 (Оценки)

OCENKA SN SPEC GROUP PN

Рис. 1.12. Структура отношения SP1

Для отношения SP1 имеем в качестве первичного ключа ком-

бинацию {SN, PN}. Кроме того, имеет место функциональная

зависимость номера группы студента и его специальности, то

есть GROUP —• SPEC. Если построить диаграмму функциональ-

ных зависимостей для отношения SP1, то она будет иметь вид.

представленный на рис. 1.13 (для упрощения некоторые функ-

циональные связи не показаны).

Рис. 1.13. Диаграмма функциональных зависимостей

для отношения SP1

Нежелательность такой структуры связана, например, с тем.

что неключевые атрибуты не являются взаимно независимыми

(GROUP —> SPEC), или с тем, что неключевые атрибуты не все

неприводимо зависимы от первичного ключа (GROUP и SPEC

зависимы от SN каждый в отдельности).

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

с избыточностью SP1. Так. скажем, при выполнении операции

INSERT (вставка) нельзя вставить данные о студентах и студен-

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

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

При выполнении операции DELETE (удаление) будет удалена

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

ному экзамену, но и информация о том. в какой группе и на какой

специальности этот студент учится.

Наконец, при выполнении операции UPDATE (обновление)

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

Глава 1.4. Функции защиты базы данных

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

искать всю информацию об этом студенте, внося соответствую-

щие коррективы, либо в отношении будет иметь место несовмес-

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

менно находиться в разных группах.

Избежать этих ситуаций можно путем замены отношения

SP1 на два - SP2 и SP, диаграмма функциональных зависимо-

стей для которых приведена на рис. 1.14. Такая структура по-

зволяет выполнить без проблем операцию INSERT в отноше-

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

нах; операцию DELETE над оценками без потери информации

о студенте; операцию UPDATE без необходимости исправле-

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

другую группу студенту.

OCENKA

Рис. 1.14. Диаграмма функциональных зависимостей

для отношений SP2 и SP

Отношение находится во 2НФ в том случае, когда оно уже

считается находящимся в 1НФ, и каждый неключевой атрибут

полностью (неприводимо) зависит от первичного ключа. Кроме

того, всякое отношение, которое находится в 1НФ и не находится

во 2НФ, всегда можно преобразовать и свести к эквивалентному

набору отношений, находящихся во 2НФ. Этот процесс заключа-

ется заменой отношения, находящегося в 1НФ. набором проек-

ций, эквивалентных исходному. Соответственно, соединение

этих проекций даст исходное отношение.

Отношения SP и SP2 находятся во 2НФ с первичными ключа-

ми соответственно SN и {SN, PN}. Действительно, если над от-

ношениями SP и SP2 произвести соединение по атрибуту SN. то

получим отношение SP1.

Однако в отношении SP2 из-за функциональной зависимости

GROUP —> SPEC все равно могут возникнуть проблемы при ма-

нипуляции с данными. Так, при выполнении операции INSERT

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

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

-Если над отношением SP2 будет выполнена операция DELETE,

Часть I, Теория баз данных

то вместе с информацией о группе будет утрачена информация о

специальности, по- которой проходит обучение данная группа. В

то же время, при выполнении операции UPDATE, при изменении

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

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

отношении, внося соответствующие изменения, либо будет иметь

место несовместимый результат

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

SP2 на две проекции - SG и GS. структура которых приведена на

рис. 1.15.

SN GROUP

GROUP SPEC

Рис. 1.15. Структура отношений SG и GS

Действительно, путем декомпозиции была исключена "двой-

ная" зависимость атрибута SPEC от первичного ключа SN и ат-

рибута GROUP. Таким образом, диаграмма функциональных за-

висимостей для отношений SG и GS будет иметь вид. показанный

на рис. 1. 16.

GROUP ]—»4~ SPEC

Рис. 1.16. Диаграмма функциональных зависимостей

отношений SG и GS

Отношение находится в ЗНФ в том случае, если оно находит-

ся во 2НФ, неключевые атрибуты взаимно независимы и каждый

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

(то есть возможно изменять значение атрибутов без изменения

первичного ключа и других неключевых атрибутов). Отношение,

находящееся во 2НФ, всегда может быть приведено к эквива-

лентному набору* отношений в ЗНФ.

Отношения SG и GS находятся в ЗНФ. причем первичными

ключами в них являются соответственно атрибуты SN и GROUP

На практике схема отношений в ЗНФ в большинстве случаев

достаточна, то есть приведением к ЗНФ процесс проектирования

реляционной БД обычно заканчивается. Однако иногда полезно

продолжить процесс нормализации.

Введем определение детерминанта - это любой атрибут, от

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

атрибут Тогда отношение будет находиться в НФБК, если каж-

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

Глава 1.4. Функции защиты базы данных

39.

Для рассмотренных выше примеров можно сказать, что отно-

шение SP1 не находится в НФБК, а отношения SP, SG и GS нахо-

дятся в НФБК.

Действительно, отношение SP1 (см. рисунок 1.13) содержит

три детерминанта - S№ GROUP и {SN. PN}. из которых только

{SN, PN} является потенциальным ключом. Отсюда и сделан вы-

вод, что SP1 не находится в НФБК. Для отношений SP. SG и GS

можно говорить о том, что они находятся в НФБК. поскольку в

каждом из них единственный потенциальный ключ является

единственным детерминантом.

Рассмотрим схему отношения PR (ПРЕДМЕТЫ), приведен-

ную на рис. 1.17.

PR (Предметы)

PN PNAME

PZAN

Рис. 1.17. Структура отношения PR (ПРЕДМЕТЫ)

Отношение ПРЕДМЕТЫ содержит номера (коды) предметов,

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

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

курсу. При этом по курсу их может быть несколько, а разные кур-

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

Каждый кортеж отношения связывает некоторый предмет с

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

данного курса. По причине сформулированных выше условий,

единственным возможным ключом отношения является состав-

ной атрибут {PN, PNAME, PZAN} и нет никаких других детер-

минантов. Следовательно, отношение ПРЕДМЕТЫ находится в

НФБК. Но при этом оно обладает недостатками: если, например,

некоторое задание добавляется к данному курсу, необходимо

вставить в отношение ПРЕДМЕТЫ столько кортежей, сколько

заданий в нем предусмотрено.

Дело в том. что в данном отношении существуют многознач-

ные зависимости. В отношении R {А, В, С} существует много-

значная зависимость между А и В (А —•—• В) в том случае, если

множество значений В, соответствующее паре значений А и С,

зависит только от А и не зависит от С.

В отношении ПРЕДМЕТЫ существуют следующие две мно-

гозначные зависимости:

PN -—. PNAME

PN —. PZAN