Математические отношения
Для понимания термина отношение рассмотрим несколько математических понятий. Допустим, что имеется два множества D1 и D2, где D1 = {2, 4} и D2 = {1, 3, 5}.
Декартовым произведением этих двух множеств (обозначается как D1 × D2) называется набор из всех возможных пар, в которых первым идет элемент множества D1, а вторым – элемент множества D2. Альтернативный способ выражения этого произведения заключается в поиске всех комбинаций элементов, в которых первым идет элемент множества D1, а вторым – элемент множества D2. В данном примере получим следующий результат
D1 × D2 = {(2, 1), (2, 3), (2, 5), (4, 1), (4, 3), (4, 5)}
Любое подмножество этого декартова произведения является отношением. Например, в нем можно выделить отношение R
R = {(2, 1), (4, 1)}
Для определения всех возможных пар, которые будут входить в отношение, можно задать некоторые условия их выборки. Например, если обратить внимание на то, что отношение R содержит все возможные пары, в которых второй элемент равен 1, то определение отношения R можно сформулировать следующим образом:
R = {(x, y) | x Î D1, y Î D2, и y = 1}
На основе этих же множеств можно сформулировать другое отношение S, в котором первый элемент всегда должен быть в два раза больше второго. Тогда определение отношения S можно сформулировать так:
S = {(x, y) | x Î D1, y Î D2, и x = 2y}
В данном примере только одна возможная пара данного декартова произведения соответствует этому условию:
S = {(2, 1)}
Свойства отношений
Отношение обладает следующими характеристиками:
отношение имеет имя, которое отличается от имен всех других отношений;
каждая ячейка отношения содержит только атомарное (неделимое) значение;
каждый атрибут имеет уникальное имя;
|
|
значения атрибута берутся из одного и того же домена;
порядок следования атрибутов не имеет никакого значения;
каждый кортеж является уникальным, т. е. дубликатов кортежей быть не может;
теоретически порядок следования кортежей в отношении не имеет никакого значения. Однако на практике этот порядок может существенно повлиять на эффективность доступа к ним.
Большая часть свойств отношений происходит от свойств математических отношений:
поскольку отношение является множеством, то порядок элементов не имеет значения. Следовательно, порядок кортежей в отношении несущественен;
в множестве нет повторяющихся элементов. Аналогично, отношение не может содержать элементов-дубликатов;
при вычислении декартова произведения множеств с простыми однозначными элементами (например, целочисленными значениями), каждый элемент в каждом кортеже имеет единственное значение. Аналогично, каждая ячейка отношения содержит только одно значение. Однако математическое отношение не нуждается в нормализации. Э.Ф. Кодд предложил запретить наличие повторяющихся групп с целью упрощения реляционной модели данных;
набор возможных значений для данной позиции отношения определяется множеством или доменом, на котором определяется эта позиция. В таблице все значения в каждом столбце должны происходить от одного и того же домена, определенного для данного атрибута.
Однако в математическом отношении порядок следования элементов в кортеже имеет значение. Например, допустимая пара значений (1, 2) совершенно отлична от допустимой пары (2, 1). Это утверждение неверно для отношений в реляционной модели, где специально оговаривается, что порядок атрибутов несущественен. Дело в том, что заголовки столбцов однозначно определяют, к какому именно атрибуту относится данное значение. Следствием этого факта является положение о том, что порядок следования заголовков столбцов в заголовке отношения несущественен. Однако, если структура отношения уже определена, то порядок элементов в кортежах тела отношения должен соответствовать порядку имен атрибутов.
|
|
Реляционные ключи
Необходимо иметь возможность уникальной идентификации каждого отдельного кортежа отношения по значениям его атрибутов.
Суперключ (superkey) – атрибут или множество атрибутов, которое единственным образом идентифицирует кортеж данного отношения.
Поскольку суперключ может содержать дополнительные атрибуты, которые необязательны для уникальной идентификации кортежа, наиболее интересными являются суперключи, состоящие только из тех атрибутов, которые действительно необходимы для уникальной идентификации кортежей.
Потенциальный ключ – это суперключ, который не содержит подмножества, также являющегося суперключом данного отношения.
Потенциальный ключ K для данного отношения R обладает двумя свойствами:
уникальность. В каждом кортеже отношения R значение ключа K единственным образом идентифицируют этот кортеж;
неприводимость. Никакое допустимое подмножество ключа K не обладает свойством уникальности.
Отношение может иметь несколько потенциальных ключей. Если ключ состоит из нескольких атрибутов, то он называется составным ключом.
|
|
Отметим, что любой конкретный набор кортежей отношения нельзя использовать для доказательства того, что некий атрибут или комбинация атрибутов являются потенциальным ключом. Тот факт, что в некоторый момент времени не существует значений-дубликатов, совсем не означает, что их не может быть вообще. При этом наличие значений-дубликатов в конкретном наборе кортежей можно использовать для демонстрации того, что некоторая комбинация атрибутов не может быть потенциальным ключом. Для идентификации потенциального ключа требуется знать смысл используемых атрибутов в «реальном мире», только это позволит обоснованно принять решение о возможности существования значений-дубликатов. Только исходя из подобной семантической информации можно гарантировать, что некоторая комбинация атрибутов является потенциальным ключом отношения.
Первичный ключ – это потенциальный ключ, который выбран для уникальной идентификации кортежей внутри отношения.
Поскольку отношение не содержит кортежей-дубликатов, всегда можно уникальным образом идентифицировать каждую его строку. Это значит, что отношение всегда имеет первичный ключ. В худшем случае все множество атрибутов можно использовать как первичный ключ, но обычно, чтобы различить кортежи, достаточно использовать несколько меньшее подмножество атрибутов. Потенциальные ключи, которые не выбраны в качестве первичного ключа, называются альтернативными ключами.
Минимальность означает, что исключение из набора любого атрибута не позволяет идентифицировать сущность по оставшимся. Каждая сущность обладает хотя бы одним возможным ключом. Один из них принимается за первичный ключ. При выборе первичного ключа следует отдавать предпочтение несоставным ключам или ключам, составленным из минимального числа атрибутов. Нецелесообразно также использовать ключи с длинными текстовыми значениями (предпочтительнее использовать целочисленные атрибуты). Так, для идентификации студента можно использовать либо уникальный номер зачетной книжки, либо набор из фамилии, имени, отчества, номера группы и может быть дополнительных атрибутов, так как не исключено появление в группе двух студентов (а чаще студенток) с одинаковыми фамилиями, именами и отчествами. Плохо также использовать в качестве ключа не номер блюда, а его название.
Не допускается, чтобы первичный ключ стержневой сущности (любой атрибут, участвующий в первичном ключе) принимал неопределенное значение. Иначе возникнет противоречивая ситуация: появится не обладающий индивидуальностью, и, следовательно не существующий экземпляр стержневой сущности. По тем же причинам необходимо обеспечить уникальность первичного ключа.
Внешний ключ - это атрибут или множество атрибутов внутри отношения, которое соответствует потенциальному ключу некоторого (может быть, того же самого) отношения.
Если некий атрибут присутствует в нескольких отношениях, то его наличие обычно отражает определенную связь между кортежами этих отношений. Такие общие атрибуты играют важную роль в манипулировании данными.
Если сущность С связывает сущности А и В, то она должна включать внешние ключи, соответствующие первичным ключам сущностей А и В. Если сущность В обозначает сущность А, то она должна включать внешний ключ, соответствующий первичному ключу сущности А(миграция ключа).
Проектирование схемы БД должно решать задачи минимизации дублирования данных и упрощения процедур их обработки и обновления. При неправильно спроектированной схеме БД могут возникнуть аномалии выполнения операций включения, удаления и модификации данных. Эти аномалии обусловлены отсутствием средств явного представления типов множественных связей между объектами ПО и неразвитостью средств описания ограничений целостности на уровне реляционной модели данных.
Аномалии модификации данных
В качестве примера возьмём отношение со следующими атрибутами (ключевые атрибуты выделены подчёркиванием):
ПОСТАВКИ (Номер поставки, Название товара, Цена товара, Количество, Дата поставки, Название поставщика, Адрес поставщика)
Различают три вида аномалий: аномалии обновления, удаления и добавления.
Аномалия обновления может возникнуть в том случае, когда информация дублируется. Другие аномалии возникают тогда, когда две и более независимые сущности объединены в одно отношение.
Например:
1. Аномалия обновления: в отношении ПОСТАВКИ она может возникнуть, если у какого-либо поставщика изменился адрес. Изменения должны быть внесены во все кортежи, соответствующие поставкам этого поставщика; в противном случае данные будут противоречивы.
2. Аномалия удаления: при удалении записей обо всех поставках одного поставщика все данные о поставщике будут утеряны.
3. Аномалия добавления: в нашем примере она возникнет, если с поставщиком заключен договор, но поставок от него еще не было. Информация о таком поставщике не может быть внесена в отношение ПОСТАВКИ, т.к. для него не определён ключ (номер поставки и название товара) и другие обязательные поля.
Для решения проблемы аномалии модификации данных при проектировании РБД проводится нормализация отношений.
Нормализация отношений
При проектировании базы данных в реляционной СУБД основной целью разработки логической модели данных является создание точного представления данных, связей между ними и требуемых ограничений. Для достижения этой цели прежде всего необходимо определить подходящий набор отношений. Метод, который используется для решения последней задачи, называется нормализацией (normalization). Нормализация представляет собой вариант восходящего подхода к проектированию базы данных, который начинается с установления связей между атрибутами. Однако нормализация также используется и при нисходящем подходе к проектированию базы данных, который начинается с выявления основных сущностей и связей, в качестве метода проверки корректности полученного результата.
Определение. Нормализация – это метод создания набора отношений с заданными свойствами на основе требований к данным, установленным в некоторой организации.
Процесс нормализации был впервые предложен Э. Ф. Коддом (1972). Нормализация часто выполняется в виде последовательности тестов для некоторого отношения с целью проверки его соответствия (или несоответствия) требованиям заданной нормальной формы. Таким образом, процесс нормализации основывается на концепции нормальных форм. Говорят, что отношение находится в некоторой нормальной форме, если удовлетворяет заданному набору условий.
Сначала Э. Ф. Коддом были предложены три вида нормальных форм: первая (1НФ), вторая (2НФ) и третья (3НФ). Затем Р. Бойсом и Э. Ф. Коддом (1974) было сформулировано более строгое определение третьей нормальной формы, которое получило название нормальной формы Бойса – Кодда (НФБК). Все эти нормальные формы основаны на функциональных зависимостях, существующих между атрибутами отношения. Впоследствии Фейгином (Fagin, 1977, 1979) были определены четвертая (4НФ) и пятая (5НФ) нормальные формы. Однако на практике нормальные формы более высоких порядков используются крайне редко.
Зачастую нормализация осуществляется в несколько последовательно выполняющихся этапов, каждый из которых соответствует некоторой нормальной форме, обладающей известными свойствами. В ходе нормализации формат отношений становится все более строгим и менее уязвимым по отношению к аномалиям обновления. При работе с реляционной моделью данных важно понимать, что только удовлетворение требований первой нормальной формы (1НФ) обязательно для создания отношений приемлемого качества. Все остальные формы могут использоваться по желанию проектировщиков. Однако, для того чтобы избежать аномалий обновления, рекомендуется выполнять нормализацию как минимум до 3НФ.
Ненормализованная форма – это таблица, содержащая одну или несколько повторяющихся групп данных.
Первая нормальная форма – это отношение, в котором все используемые домены содержат только скалярные значения.
Процесс нормализации начинается с преобразования данных из формата источника (например, из формата стандартной формы ввода данных) в формат таблицы со строками и столбцами. На исходном этапе таблица находится в ненормализованной форме (ННФ) и часто называется ненормализованной таблицей. Для преобразования ненормализованной таблицы в первую нормальную форму (1НФ) в исходной таблице следует найти и устранить все повторяющиеся группы данных. Повторяющейся группой называется группа, состоящая из одного и более атрибутов таблицы, в которой возможно наличие нескольких значений для единственного значения ключевого атрибута таблицы. Существует два подхода исключения повторяющихся групп из ненормализованных таблиц.
В первом подходе повторяющиеся группы устраняются путем ввода соответствующих данных в пустые столбцы строк с повторяющимися данными. Иными словами, пустые места при этом заполняются дубликатами неповторяющихся данных. Этот подход часто называют «выравниванием» (flattening) таблицы. Полученные в результате этих действий таблица, которая теперь будет называться отношением, содержит атомарные (или единственные) значения на пересечении каждой строки с каждым столбцом, а потому находится в первой нормальной форме. В результате такого подхода в полученное отношение вносится некоторая избыточность данных, которая в ходе дальнейшей нормализации будет устранена.
Во втором подходе один атрибут или группа атрибутов назначаются ключом ненормализованной таблицы, а затем повторяющиеся группы изымаются и помещаются в отдельные отношения вместе с копиями ключа исходной таблицы. Далее в новых отношениях устанавливаются первичные ключи. Иногда ненормализованные отношения могут содержать одну или несколько повторяющихся групп внутри повторяющихся групп первого порядка. В таких случаях данный прием применяется до тех пор, пока повторяющихся групп совсем не останется. Полученный набор отношений будет находиться в первой нормальной форме только тогда, когда ни в одном из них не будет повторяющихся групп атрибутов.
Хотя оба подхода одинаково корректны, следует отметить, что при использовании второго подхода полученные отношения находятся как минимум в 1НФ и обладают меньшей избыточностью данных. При выборе первого подхода выровненное 1НФ-отношение декомпозируется в ходе дальнейшей нормализации на те же отношения, которые могли бы быть получены с помощью второго подхода.
Каждой нормальной форме соответствует некоторый определенный набор ограничений, и отношение находится в некоторой нормальной форме, если удовлетворяет свойственному ей набору ограничений.
В теории реляционных баз данных обычно выделяется следующая последовательность нормальных форм:
· первая нормальная форма (1NF);
· вторая нормальная форма (2NF);
· третья нормальная форма (3NF);
· нормальная форма Бойса-Кодда (BCNF);
· четвертая нормальная форма (4NF);
· пятая нормальная форма, или нормальная форма проекции-соединения (5NF или PJ/NF).
В основе процесса проектирования лежит метод нормализации, декомпозиция отношения, находящегося в предыдущей нормальной форме, в два или более отношения, удовлетворяющих требованиям следующей нормальной формы.
Введём понятие простого и сложного атрибута.
Простой атрибут – это атрибут, значения которого атомарны (т.е. неделимы).
Сложный атрибут может иметь значение, представляющее собой конкатенацию нескольких значений одного или разных доменов. Аналогом сложного атрибута может быть агрегат или повторяющийся агрегат данных.