Лекция № 13 Реляционная модель и нормализация. Функциональные зависимости.

         Реляционная модель важна по двум причинам. Во-первых, поскольку конструк­ции реляционной модели имеют широкий и общий характер, она позволяет опи­сывать структуры баз данных независимым от СУБД образом Во-вторых, реля­ционная модель является основой почти всех СУБД Таким образом, понимание принципов этой модели существенно

         В этой лекции даются основы реляционной модели (relational model) и объяс­няются фундаментальные принципы нормализации (normalization) Мы начнем с того факта, что не все отношения одинаковы некоторые из них более предпоч­тительны, чем другие Нормализация - это процесс преобразования отношения, имеющего некоторые недостатки, в отношение, которое этих недостатков не име­ет Что еще более важно, нормализацию можно использовать как критерий для определения желательности и правильности отношений. Вопрос о том, что такое хорошо структурированное отношение, был предметом многочисленных теоре­тических исследований Термин нормализация обязан своим появлением одному из пионеров технологии баз данных, Э. Ф Кодду (Е F Codd), который опреде­лил различные нормальные формы (normal forms) отношений. В этой лекции мы об­судим нормализацию. Формальное, более тща­тельное исследование данного вопроса можно найти в работе Дейта и Ульмана (С J. Date и J D Ullman)[1]

1.1        Реляционная модель

         Отношение (relation) — это двумерная таблица. Каждая строка в таблице содержит данные, относящиеся к некоторой вещи или какой-то ее части. Каждый стол­бец таблицы описывает какой-либо атрибут этой вещи. Иногда строки называют­ся кортежами (tuples), а столбцы — атрибутами (attributes).

         Термины отношение, кортеж и атрибут пришли из реляционной математи­ки, которая является теоретическим источником этой модели. Профессионалы MIS предпочитают употреблять аналогичные термины файл (file), запись (record) и поле (field), а большинство пользователей находят более удобными термины таблица (table), строка (row) и столбец (column). Все эти термины сведены в таб­лицу  13.1.

Таблица 13.1. Эквивалентная терминология реляционной модели

         Чтобы таблица была отношением, она должна удовлетворять определенным ограничениям[2]. Во-первых, значения в ячейках таблицы должны быть одиноч­ными - ни повторяющиеся группы, ни массивы не допускаются[3]. Все записи в столбце должны быть одного типа. Например, если третий столбец первой строки таблицы содержит номер сотрудника, то и во всех остальных строках таблицы третий столбец также должен содержать номер сотрудника. Каждый столбец име­ет уникальное имя; порядок столбцов в таблице несуществен. Наконец, в отно­шении не может быть двух одинаковых строк, и порядок строк не имеет значения.

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

Таблица 13.2. Отношение СОТРУДНИК

Таблица 13.2 представляет отдельный экземпляр отношения. Обобщенный фор­мат отношения - СОТРУДНИК (Имя, Возраст, Пол, ТабельныйНомер) - называется структурой отношения, и именно это большинство людей имеет в виду, исполь­зуя термин отношение.

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

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

         Функциональная зависимость (functional dependency) — это связь между атрибутами. Предположим, что если мы знаем значение одного атрибута, то можем вы­числить (или найти) значение другого атрибута. Например, если нам известен номер счета клиента, то мы можем определить состояние его счета. В таком слу­чае мы можем сказать, что атрибут СостояниеСчетаКлиента функционально зависит от атрибута НомерСчетаКлиента.

         Говоря более общим языком, атрибут Y функционально зависит от атрибута X, если значение X определяет значение Y. Другими словами, если нам известно зна­чение X, мы можем определить значение Y.

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

Стоимость = Цена * Количество

         В этом случае мы могли бы сказать, что атрибут Стоимость функционально зависит от атрибутов Цена и Количество.

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

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

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

НомерСтудента > Специальность

СерийныйНомерКомпьютера > ОбъемПамяти

Первое выражение читается так: «атрибут НомерСтудента функционально опре­деляет атрибут Специальность», «атрибут НомерСтудента определяет атрибут Специ­альность» или «атрибут Специальность зависит от атрибута НомерСтудента». Атрибу­ты по левую сторону от стрелки называются детерминантами (determinants).

Как уже говорилось, если номер студента определяет специальность, то каж­дому номеру студента соответствует только одна специальность. Между тем, одной и той же специальности может соответствовать более одного номера студен­та. Пусть студент под номером 123 специализируется на бухгалтерском учете. Тогда для любого отношения, где присутствуют столбцы НомерСтудента и Специ­альность, выполнится условие: если НомерСтудента = 123, то Специальность - Бух-галтерскийУчет. Обратное, однако, неверно: если Специальность = БухгалтерскийУчет, то атрибут НомерСтудента может принимать различные значения, так как на бух­галтерском учете может специализироваться много студентов. Следовательно, мы можем сказать, что связь атрибутов НомерСтудента и Специальность имеет вид N:l. В общем случае можно утверждать, что если А определяет В, связь между значе­ниями А и В имеет вид N:l.

         В функциональные зависимости могут быть вовлечены группы атрибутов. Рассмотрим отношение ОЦЕНКИ (НомерСтудента, Дисциплина, Оценка). Комбинация номера студента и дисциплины определяет оценку. Такая функциональная зави­симость записывается следующим образом:

(НомерСтудента, Дисциплина) > Оценка

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

         Обратите внимание на следующее различие. Если X > (Y, Z), то X > Y и X > Z. Например, если НомерСтудента > (ИмяСтудента, Специальность), то НомерСтудента > ИмяСтудента и НомерСтудента > Специальность. Но если (X, Y) > Z, то в общем случае неверно, что X > Y или X > Z. Следовательно, если (НомерСтудента, Дисциплина) > Оценка, то ни номер студента, ни дисциплина как таковые оценку не определяют.

1.3        Ключи

         Ключ (key) — это группа из одного или более атрибутов, которая уникальным образом идентифицирует строку. Рассмотрим отношение СЕКЦИЯ (рис. 5.3), имею­щее атрибуты НомерСтудента, Секция и Плата. Строка этого отношения содержит информацию о том, что студент посещает определенную секцию за определенную плату. Предположим, что студент одновременно не может посещать более одной секции. В этом случае значение атрибута НомерСтудента идентифицирует единст­венную строку, поэтому данный атрибут является ключом.

СЕКЦИЯ (НомерСтудента, Секция, Плата)

Ключ: НомерСтудента Sample Data

НомерСтудента  Секция       Плата

100            Лыжи             200

150            Плавание         50

175            Теннис             50

200            Плавание         50

Рис. 5.3. Отношение СЕКЦИЯ

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

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

         Допустим, в ходе опроса пользователей мы выяснили, что студентам разре­шено одновременно быть записанными в несколько спортивных секций. Эта си­туация отражена в отношении СЕКЦИИ (рис. 5.4). Как мы отметили, НомерСтуден­та не является ключом этого отношения. В самом деле, студент с номером 100 посещает секцию гольфа и секцию лыж, и атрибут НомерСтудента со значением 100 появляется в двух различных строках. Фактически, для этого отношения ни один атрибут сам по себе не является ключом, то есть ключ должен состоять из двух или более атрибутов.

НомерСтудента  Секция        Плата

100               Лыжи            200

100              Гольф             65

150            Плавание          50

175              Сквош             50

175           Плавание          50

200            Плавание          50

200              Гольф             65

Рис. 5.4. Отношение СЕКЦИИ

         Рассмотрим, какие комбинации из двух атрибутов возможны для данной таб­лицы. Таких комбинаций имеется три: (НомерСтудента, Секция), (НомерСтудента, Плата) и (Секция, Плата). Является ли какая-либо из этих комбинаций ключом? Чтобы быть ключом, группа атрибутов должна уникальным образом идентифи­цировать строку. Опять-таки, ответы на подобные вопросы мы должны получить от пользователей. Наше решение не должно основываться на выборочных данных, подобных тем, которые приведены на рис. 5.4, или на наших собственных предположениях.

         Допустим, поговорив с пользователями, мы пришли к выводу, что плата за абонемент в различных секциях может совпадать. Поскольку это так, комбина­ция (НомерСтудента, Плата) не может уникальным образом определить строку. Например, студент с номером 100 может посещать две различных секции, каж­дая из которых стоит $200. Это означает, что комбинация (100, $200) возникла бы в таблице дважды, поэтому такая комбинация не может быть ключом.

         Может ли быть ключом сочетание (Секция, Плата)? Может ли комбинация (Лыжи, $200) уникальным образом определить строку? Нет, не может, поскольку секцию лыж может посещать много студентов. А как насчет сочетания (Номер-Студента, Секция)? Имея те сведения, которые мы получили от пользователей, можно ли сказать, что комбинация значения атрибутов НомерСтудента и Секция уникальным образом определяет строку таблицы? Да, можно, пока от нас не тре­буется вести записи об истории посещения секций студентом. Иными словами, должна ли эта таблица содержать сведения только о тех секциях, которые сту­дент посещает на данный момент, или же в ней должны быть записи о секциях, которые студент посещал ранее?

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

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

1.4        Резюме

         Реляционная модель важна по двум причинам: во-первых, с ее помощью можно описывать структуры баз данных независимым от СУБД образом, а во-вторых, эта модель лежит в основе значительной части современных СУБД. Критерием правильности и желательности отношений может служить нормализация.

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

         Функциональная зависимость — это связь между атрибутами. Y функцио­нально зависит от X, если значение X определяет значение Y. Детерминантом на­зывается группа из одного или нескольких атрибутов, находящаяся с левой стороны функциональной зависимости. Например, если X определяет Y, то X яв­ляется детерминантом. Ключ — это группа из одного или нескольких атрибутов, которая однозначно определяет кортеж.          Каждое отношение имеет минимум один ключ; поскольку каждая строка уникальна, в самом крайнем случае клю­чом является совокупность всех атрибутов отношения. Хотя ключ всегда уника­лен, детерминант функциональной зависимости может таковым и не быть. Явля­ются ли атрибуты ключами и являются ли они функционально зависимыми — это определяется не абстрактным набором правил, а тем смыслом, который вкла­дывают пользователи в эти атрибуты.

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

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

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

         Отношение находится в доменно-ключевой нормальной форме, если каждое ограничение, накладываемое на отношение, является логическим следствием определения доменов и ключей. Под ограничением здесь понимается любое усло­вие, определяющее возможные статические значения атрибутов, истинность кото­рого может быть проверена. Домены, как они определены нами, имеют физиче­скую и семантическую составляющие. В контексте ДКНФ, однако, под доменом подразумевается только физическое описание.

Неформальная интерпретация ДКНФ заключается в том, что каждое отноше­ние должно иметь только одну тему. Например, в отношении может содержаться информация о профессорах или о студентах, но не о тех и других одновременно.

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

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

Скачано с www.znanio.ru