Схема работы с разделом 4
Раздел 4. Базовые элементы реляционных БД
Четвертый раздел курса включает две темы: “Проектирование реляционной базы данных”, “Нормализация отношений в БД”. После изучения каждой темы Вам следует ответить на вопросы для самопроверки.
По материалам раздела также выполняется курсовой проект по дисциплине.
Работа с разделом 4 завершается сдачей контрольного теста. Кроме того, по данному разделу выполняются практические задания 3 и 4, а также лабораторные работы № 1 и № 2.
Для того, чтобы Вы смогли успешно ответить на вопросы контрольного теста, Вам предоставляется возможность поработать с репетиционным тестом. Если Вы испытываете затруднения в ответе на какой-либо вопрос, обратитесь к главам 5-7, 11-13 учебника [1] или к материалам электронного учебного пособия [7] и пособия [8].
4.1. Проектирование реляционной базы данных
При изучении данной темы Вы должны познакомиться с математическим аппаратом, применяемым для проектирования реляционных баз данных.
По данной теме выполняется лабораторная работа № 3, а также раздел “Концептуальное проектирование” курсового проекта. Рекомендации по выполнению этих заданий приведены в методических указаниях 3.4.
Для проверки изучения материала темы Вам предстоит также ответить на вопросы для самопроверки.
Если Вы испытываете затруднения в ответе на какой-либо вопрос, обратитесь к главам 11, 12 учебника [1] или к материалам учебного пособия [8, 9].
4.1.1. Свойства и виды отношений
Отношения
Пусть имеется n множеств {D1, D2,...,Dn}.
R есть отношение на этих множествах, если оно представляет собой множество элементов вида < d1, d2, . . . , dn > , где di Di (i = 1, . . n).
Более строго, R - это подмножество декартова произведения указанных множеств и формально записывается:
R D1 D2 ... Dn,
где - математический символ нестрогого включения;
- математический символ операции декартова произведения.
В исходные множества Di принято называть доменами (областями определения) R, а элементы R < d1, d2, ..., dn > - кортежами или выборками (на рис.3.5 раскрывается суть некоторых понятий, связанных с отношением R).
Будем считать, что элементы доменов элементарны, т.е. сами по себе они не есть множества. Элементарность подразумевает, что это некоторое неразделимое понятие предметной области, например идентификатор информационных объектов или число. Следует отметить также семантическую нагрузку понятия домена: данные считаются сравнимыми только в том случае, когда они относятся к одному домену. Например, значения доменов "Номера телефонов" и "Возраст" относятся к типу целых чисел, но не являются сравнимыми. Заметим, что в большинстве реляционных СУБД понятие домена или не используется, или используется лишь частично.
Так как отношение есть множество, а все элементы множества должны быть попарно различны, то в отношении не может быть двух идентичных кортежей.
Отношение обладает следующими свойствами:
-
Отношение имеет имя, отличающее его от других отношений.
-
Каждый атрибут имеет уникальное имя.
-
Значения атрибута берутся из одного и того же домена.
-
Каждый кортеж является уникальным, т.е. в отношении не может быть дублированных строк.
-
Атрибут (или набор атрибутов), уникально идентифицирующий каждый кортеж, является первичным (primary) ключом отношения.
-
Атрибут (или множество атрибутов) называется внешним (foreign) ключом, если в другом отношении он является первичным.
Идентификатор отношения и множество имен атрибутов составляют схему отношения. Введенное понятие схемы будет формально определено при рассмотрении вопросов, касающихся теории нормализации.
Содержимое отношения (см. рис. 3.5) принято называть состоянием схемы и обозначать r. Совокупность схем отношений составляют схему базы данных. Соответственно состояние схемы базы данных (собственно сама база) - есть совокупность состояний схем отношений.
Примем следующие обозначения. Будем обозначать первыми заглавными латинскими буквами (A, B, ...) имена атрибутов, буквами R, Q – схемы атрибутов, строчными первыми (a, b, ...) – атрибуты, строчными r, q – состояние отношения. Схему R={A1, A2, ..., An} будем обозначать R[A1, A2, ..., An] или A1A2...An , отношение r со схемой R обозначим r(R) или r(A1A2...An).
Значение кортежа t на атрибуте A будем называть A-значением кортежа t. Если XR, будем называть t(X) X-значением кортежа t. Предполагается, что существует значение : t()= для каждого кортежа t, t1()=t2().
Ассоциации между отношениями и внутри отношений коротко рассмотрены в теме 3.1.1.
4.1.2. Реляционная алгебра
В реляционном подходе ответ на конкретный запрос к базе данных также представляется в форме отношения. Поэтому в основе средств, используемых для формулировки запроса, может лежать алгебра отношений, которая используется для моделирования поисковых процессов в базах данных.
Как известно, алгебра есть множество вида
А: < H, S > , где
H -носитель (в данном случае - множество нормализованных отношений);
S -сигнатура (в данном случае - множество операций над отношениями).
Все множество S операций реляционной алгебры разбиты на два подмножества:
Стандартные теоретико-множественные операции:
- объединение U Rrez=R1 U R2,
- пересечение ∩ Rrez=R1 ∩ R2,
- разность \ Rrez=R1 \ R2,
- декартово произведение Rrez= R1 R2.
Специальные операции:
- проекция Rrez (А) = R[A],
- ограничение Rrez = R1[булевское выражение],
- соединение Rrez = R1[булевское выражение]R2,
- деление Rrez = R1 R2.
Операции реляционной алгебры либо унарные (т.е. используют в качестве операнда только одно отношение), либо бинарные, когда имеются два операнда.
Пример с указанными операциями представлен на рис. 3.8. Для имен атрибутов приняты следующие сокращения: ШД – шифр детали, ШМ – шифр материала, ЕИ – единица измерения, НР – норма расхода, НМ – наименование материала, ШМ" – шифр материала на складе.
Исходные отношения R1, R2 и R3:
R1 (ШД, ШМ, ЕИ, НР) R2 (ШД, ШМ, ЕИ, НР) R3 (ШМ", НМ)
д1 м2 1 15 д2 м5 3 3 м2 ст-5
д2 м5 3 3 д2 м3 2 15 м9 ст-7
д2 м9 3 5
д3 м2 1 10
На рис. 3.9 представлен пример декартова произведения отношений R2 и R3.
Rrez (ШД, ШМ, ЕИ, НР, ШМ", НМ)
д2 м5 3 3 м2 ст-5
д2 м3 2 15 м2 ст-5
д2 м5 3 3 м9 ст-7
д2 м3 2 15 м9 ст-7
Рис. 3.9. Декартово произведение двух отношений
Специальные операции
ПРОЕКЦИЯ
Операция унарна и предназначена для уменьшения степени отношения.
Пусть имеется исходное отношение R1(A1,..., An) и список атрибутов А. Проекция отношения R1 на список А обозначается следующим образом:
Rrez (A) = R1 [A] или A(r) { t(A) | tr }.
где - [ ] (квадратные скобки) являются операционными (или A(r)), т.е. используются для обозначения операции ПРОЕКЦИЯ (рис.10.a).
Рис. 3.8. Теоретико-множественные операции над отношениями.
ОГРАНИЧЕНИЕ (СЕЛЕКЦИЯ)
Операция ОГРАНИЧЕНИЕ (селекция, выборка) также, как и проекция, является унарной операцией, но в отличие от проекции ориентирована на выделение нужных строк отношения.
Пусть исходное отношение задано схемой: R1 (A1, . . . , An).
Селекцией A = a(r) называется отношение r (R) = A = a(r){tr | t(A)=a}.
При ограничении производится либо сужение области определения некоторых атрибутов, либо происходит сопоставление атрибутов отношения, которые должны быть определены на одном и том же домене.
Операцию ограничения также записывают следующим образом:
Rrez (A1, ..., An) = R1[булевское выражение для значений атрибутов R1].
На интуитивном уровне операцию ограничения лучше всего представлять как взятие некоторой "горизонтальной" вырезки из отношения-операнда (R1 из рис.3.9).
Rrez (A) = R1 [ШМ, ЕИ] Rrez (A) = ШМ = ”м2” OR ЕИ = ”1”
Результат Результат
м2 1 м2 1
м5 3
м9 3
a) A(r) – проекция b) селекция – R1 [ШМ=”м2” OR ЕИ=”1” ]
Рис. 3.10. Пример операции проекции (a) и селекции (b)
СОЕДИНЕНИЕ
Операция СОЕДИНЕНИЕ двух и более отношений является важнейшей операцией. При этой операции кортежи одного отношения конкатенируют (соединяются) с выборками другого, точно также, как и при декартовом произведении двух отношений, но при условии, что булевское выражение, в каждый терм которого входят атрибуты обоих отношений, принимает значение "истина".
Пусть r(R) и s(S) – отношения. Соединением r и s называется отношение
r s = q(RS) = {t(RS) | tr r, ts s : tr = t(R), ts = t(S)}.
Итак, для двух исходных отношений, заданных схемами:
R1 (A1, ..., An) и R2 (B1, ..., Bm), в результате операции соединения получается отношение со схемой
Rrez (A1, . . . , An, B1, . . . ,Bm) = R1 [булевское выражение] R2.
В булевском выражении термы имеют вид:
(Ai Bj), где - атрибуты Аi и Bj определены на одном домене, а термы сравнения () выбираются из множества: { = , < > , > , < , >= , <= }.
Очень часто булевское выражение состоит из единственного терма. Если таким термом является "=" (знак равенства), то этот частный случай называется операцией эквисоединения двух отношений по атрибутам Ai и Bj.
Если r(R), s(S) – отношения, Ai R , Bi S и dom(Ai) = dom(Bi), 1 i n (Ai и Bi могут быть одинаковыми). Эквисоединением r и s по A1, A2,…,An и B1, B2,…, Bm называется отношение q(RS) = {t | tr r, tss, t(R) = tr, t(S) = ts, t(Ai) = t(Bi)}.
В этом случае булевское выражение есть конъюнкция термов, выражающих равенство соответствующих атрибутов, входящих в список и принадлежащих соединяемым отношениям:
(A1=B1) AND (A2=B2) AND ... AND (Ak=Вk).
Если RS = {B1B2…Bl} = , то соединение rs, результатом которого является множество кортежей t(A1A2…Ak C1C2…Cm), таких, что t(A1A2…Ak)r и t(C1C2…Cm)s, называется декартовым произведением отношений r и s и обозначается r s.
Смысл операции соединения двух отношений более четко можно выразить сведением операции к ранее введенным:
Rrez(A1, ..., An, B1, ..., Bm) = R1 [(булевское выражение)] R2 =
= (R1 R2) [(булевское выражение)],
т.е. операция соединения сводится к декартовому произведению отношений с последующим ограничением (селекцией) получаемого промежуточного отношения.
На рис. 3.11 представлен пример операции эквисоединения отношений R1 и R3, исходное состояние которых показано на рис.3.8.
Rrez (ШД, ШМ, ЕИ, НР, ШМ", НМ) = [R1.ШМ=R3. ШМ"].
д1 м2 1 15 м2 ст-5
д2 м9 3 5 м9 ст-7
д3 м2 1 10 м2 ст-5
Рис. 3.11. Пример операции эквисоединения R1 и R3
При выполнении операции эквисоединения может возникнуть ловушка соединения, т.е. при эквисоединении или -соединения семантически верных отношений может получиться семантически ложное отношение.
ДЕЛЕНИЕ
Пусть r(R) и s(S) – отношения, SR. Положим R = R - S. Тогда r, разделенное на s – это отношение r(R)={t | tss trr: tr(R)=t & tr(S)=ts}.
Отношение rrez – частное от деления r на s, что обозначается rrez = rs. Иначе rs – это максимальное подмножество rrez множества rrez(r), такое, что rrez s r. Соединение – здесь декартово произведение.
Чтобы понять сущность операции деления отношений, целесообразно рассмотреть упрощенный пример.
Пусть задано отношение R1(ШД, ШМ) (рис. 3.12.а), которое задает возможные варианты изготовления деталей из разных материалов. И задано отношение R2 (рис. 3.12.b), указывающее, какие материалы хранятся на складе.
Рис. 3.12. R1 - Варианты изготовления. R2 - Материалы на складе
Если необходимо определить детали, которые могут быть изготовлены из всех материалов, хранимых на складе, то неформально мы можем определить, что такой деталью является только деталь д2, она может быть изготовлена как из материала м5, так и из м9.
Фактически R2 есть подмножество материалов, из которых может быть сделана деталь д2: {м5, м9} {м3, м5, м9}.
Формально этот запрос соответствует операции деления реляционной алгебры, которая обозначается:
Rrez (ШД) = R1[ШМ ШМ"]R2 , где - символ операции деления.
Рассмотрим пример использования алгебры отношений при составлении запросов к базе данных. Пусть БД содержит отношения R1(ШД, ШМ, НР) и R2(ШМ", НМ).
Запрос. Перечислить шифры материалов (ШМ) и их наименования (НМ), которые идут на изготовление одной детали в количестве большем чем 25 кг.
На языке реляционной алгебры запрос будет реализован на основе следующих операций:
Rrez (ШМ, НМ) = ((R1[НР > 25]) [ШМ]) [ШМ=ШМ"] R2[ШМ, НМ]
Круглые скобки определяют последовательность действий:
1) Ограничение отношения R1;
2) Проектирование промежуточного отношения;
3) Эквисоединение с R2;
4) Проектирование полученного результата.
Нетрудно видеть, что при таком подходе закладывается "процедурность" запроса, поэтому для языков манипулирования данными (ЯМД), построенных на алгебре отношений принято говорить как о процедурных языках.
Вопросы для самопроверки по теме 4.1
1. Дайте определение понятию атомарный атрибут.
2. Какой смысл имеет в теории баз данных понятие схемы отношения?
3. Приведите определение понятия ‘отношение’.
4. Какие существуют разновидности ассоциаций между отношениями?
5. Что такое реляционная алгебра?
6. Приведите пример унарной и бинарной алгебраической операции?
7. На какие группы подразделяются алгебраические операции?
8. Что такое состояние отношения и схема БД?
9. Перечислите бинарные операции реляционной алгебры.
4.2. Нормализация отношений в БД
При изучении данной темы Вы должны познакомиться с математическим аппаратом, применяемым для проектирования реляционных баз данных.
По данной теме выполняется лабораторная работа № 3, а также раздел “Концептуальное проектирование” курсового проекта. Рекомендации по выполнению этих заданий приведены в методических указаниях 3.4.
Для проверки изучения материала темы Вам предстоит также ответить на вопросы для самопроверки.
Если Вы испытываете затруднения в ответе на какой-либо вопрос, обратитесь к главам 11, 12 учебника [1] или к материалам учебного пособия [8].
4.2.1. Понятие о нормальных формах
Как отмечалось в предыдущей, теме второй составляющей алгебры является ее носитель. В реляционной модели носителем является набор специальным образом сконструированных нормализованных отношений – то, что на концептуальном уровне и является собственно базой данных. Важнейшие цели, которым служит база данных – это снижение избыточности данных и повышение достоверности отображения информации. Любое априорное знание об ограничениях на данные может служить этим целям. Один из методов формализации этих знаний основан на теории нормализации – установление ограничений между данными, которые частично отражает их семантику. Проектирование реляционной базы это фактически выделение нормальных форм.
Этот метод основан на фундаментальном в теории реляционных баз данных понятии зависимости (FD) между атрибутами отношений и выводимым из него понятия - реляционного ключа (RK).
Определение FD
В схеме отношения R (X, Y, …) атрибут X функционально определяет атрибут Y (условное обозначение XY), если в любой момент времени любому элементу проекции R[X] соответствует только один элемент проекции R[Y], в любом экземпляре схемы R.
Стрелка "" разделяет ФЗ на левую и правую части. При этом левую часть ФЗ, иногда называют детерминантой.
Функциональная зависимость это не функция в точном математическом смысле, так как допускается, что со временем она может изменяться (так же как изменяется и отношение R).
Полный набор имен атрибутов {A1, …, An} отношения R принято обозначать символом UR, Ai UR, (i=1, ..., n где n – степень отношения), а множество постулированных на R ограничений (функциональных, многозначных зависимостей и зависимостей соединений) обозначают FR.
FR может связывать и совокупность атрибутов: f: {A1, ..., An} {B1, ..., Bm}.
Для вывода из заданного множества FR замыкания множества зависимостей (всех зависимостей присущих R, обозначается F+R) или получения минимального покрытия набора FR (такого набора зависимостей H, что H+=F+R и удаление любой зависимости из H приводит к нарушению этого равенства), используют аксиомы Армстронга или их расширения и правила вывода построенные на этих аксиомах.
Например, для функциональных зависимостей FD справедливы следующие аксиомы:
1. Рефлексивность. Если Y X UR, то зависимость X Y логически следует из FD. Зависимость вида X X называют тривиальной.
2. Пополнение. Если справедлива зависимость X Y и Z UR, то также будет справедлива и зависимость XZYZ.
3. Транзитивность (транзитивные зависимости). Если справедлива зависимость X Y и Y Z, то также справедлива и зависимость X Z.
Доказано что перечисленные выше аксиомы являются непротиворечивыми и надежными, поэтому выделенные из UR (на основе аксиом и постулированных FR) заключения (проекции на R) являются истинными.
В отличие от математического определения отношения, отношение R в реляционной модели нормализовано, что подразумевает использование в качестве элементов кортежа атомарных значений (элемент кортежа не может быть множеством, мощность которого превышает единицу).
Отношение, обладающее свойством атомарности элементов его составляющих, называется нормализованным или, что то же самое, находящимся в первой нормальной форме (1НФ). Нормальные формы, в которых находятся отношения, составляют иерархию, в которой формы с большими номерами не обладают некоторыми нежелательными свойствами, характерными для форм с меньшими номерами. В теории нормальных форм для реляционных БД рассматривается пять уровней нормализации: 1НФ – 5НФ и форма Бойса-Кодда (промежуточная между 3НФ и 4НФ). Каждый из следующих уровней ограничивает типы допустимых FD отношения.
Для отношений, не находящихся в нормальных формах, существуют аномалии модификации. Различают аномалии добавления, изменения и удаления.
Как отмечается во всех руководствах по проектированию реляционных схем, выделенные множества UR, F+R являются исходными (входными) данными для автоматизированных методов построения реляционных баз данных (см. параграф 4.2.2). Однако если процессы построения F+R, RK удается формализовать полностью, то процесс формирования FR не поддается полной формализации.
4.2.2. Формальные методы синтеза и декомпозиции нормальных форм
Неформально задача проектирования схемы реляционной базы данных ставится следующим образом. Пусть имеется некоторая схема базы данных SO, надо получить новую схему SD, эквивалентную в некотором смысле старой, но в чем-то лучше ее.
Для построения ‘хорошей’ реляционной реализации концептуальной схемы базы данных (т.е. такой, в которой выполнялась бы свойство соединения без потерь информации и свойство сохранения функциональных зависимостей для результирующего набора нормализованных отношений), которая бы находилась хотя бы в 3НФ, используют следующие методы: декомпозиции, синтеза, метод ER-диаграмм (проектирование с использованием метода сущность – связь) и их комбинации.
Метод декомпозиции, заключающийся в последовательном разбиении исходной Sch(R) и промежуточных схем отношений до тех пор, пока результирующие отношения не будут удовлетворять заданным свойствам.
Наибольшее развитие в этом методе получил алгоритм Фейджина для приведения отношений к 4НФ.
Метод синтеза, состоящий в конструировании (синтезе) набора декомпозиционных подсхем, удовлетворяющих определенным свойствам, из заданного множества атрибутов UR выбранной предметной области на основе заданного множества функциональных зависимостей FD, заданных на этих атрибутах.
Формально задача проектирования реляционной базы данных ставится следующим образом: необходимо устранить избыточность данных путем разбиения исходного отношения на несколько проекций, являющихся нормализованными отношениями, с условием восстановления исходного отношения из полученные проекций.
, при ограничении R = R1 R2 … Rn.
В настоящее время (табл. 4.1) используются автоматизированные подходы к построению схемы реляционной базы данных, формирующих схему модели данных как совокупность схем отношений, находящихся в 3НФ и 4НФ.
Авторы метода
|
Фэйджин
|
Делобель-Кейси
|
Бернштейн
|
Ислур
|
Неклюдова-Цаленко
|
Дьяков
|
Зависимости данных на входе метода
|
Мз
|
Фз
|
Фз
|
Фз
|
Фз
|
Фз
|
Нормальная форма схемы SD
|
4НФ
|
3НФ
|
3НФ
|
3НФ
|
3НФ
|
3НФ
|
Вычислительная сложность алгоритма
|
NP
|
NP
|
O(|FD|2)
|
O(|FD|2)
|
NP
|
-
|
Таблица 4.1. Характеристики методов проектирования реляционных схем
Обозначения: NP-алгоритм включает решение NP – полной задачи, |FD|- длина строки литер необходимая для записи всех FD.
Все методы должны обеспечивать выполнимость свойства соединения без потерь информации и свойства сохранения зависимостей в полученной конфигурации схемы реляционной БД, и восстанавливать исходное R из полученных проекций с помощью алгебраической операции соединения.
При этом каждый экземпляр исходной схемы r(R) является естественным соединением его проекций на все декомпозиционные подсхемы.
Свойство сохранения зависимостей в наборе декомпозиционных подсхем {Sch(R1), …, Sch(Rn)} относительно исходного набора FR, состоит в том, что из объединения всех зависимостей принадлежащих проекциям FR на Sch(Ri), i=1, .., n логически следуют все зависимости из FR :
, где - проекция множества функциональных зависимостей на множество атрибутов принадлежащих , т.е. множество зависимостей (AB)FD+ таких что A, B.
4.2.3. Проектирование с использованием метода сущность – связь
Характеристики перечисленных выше алгоритмов для методов декомпозиции и синтеза сведены в таблицу (Таблица 4.1) из которой видно, что ни один из алгоритмов автоматизации проектирования реляционных схем, не имеет преимущества над остальными по всем характеристикам. Из данных методов, только методы Неклюдовой–Цаленко и Дьякова дают количественно оптимальную схему. Принципиальная невозможность построения “абсолютно лучшего” алгоритма следует из существования таких исходных Sch(R), для которых отсутствует синтаксическое разложение в 4НФ с выполнением свойств сохранения зависимостей и соединения без потерь [12, 15].
Следующий метод, применяемый при проектировании реляционных схем, основан на технологии ER-моделирования и носит название метод ER-диаграмм (или проектирование с использованием метода сущность – связь [9]). Метод основывается на методологии представления данных в виде набора сущностей (Entity) и связей (Relationship) (модель ‘сущность-связь’), и в его основу положены определенные правила формирования результирующих отношений, в зависимости от типов связей (ассоциаций) и класса принадлежности сущностей.
Данный метод получил широкое распространение, поскольку в отличие от формализованных методов проектирования концептуальных моделей, требующих знания основ теории реляционных структур данных, метод ER-диаграмм не является строго формализованным и выполняется на основе здравого смысла и применении небольшого количества правил, которые позволяют конструировать результирующие отношения.
Однако, как отмечается в [8, 12] данному методу присущи определенные недостатки, самым серьезным из которых является отсутствие гарантии соединения без потерь информации для результирующего набора схем отношений. Т.е. для метода ER-диаграмм всегда необходимо проверять результирующие схемы отношения на свойство соединения без потерь информации.
В общем случае для построения реляционной концептуальной схемы базы данных используются сочетания описанных подходов.
Резюме
Применение алгебраического подхода к конструированию структур отношений неразрывно связано с множеством операций определенных на них. Правильно выбранный набор отношений концептуальной модели – гарантия жизнеспособности проектируемой ИС. Пренебрежение принципами нормализации приводит либо к неработоспособности системы, либо требует серьезных финансовых издержек при сопровождении таких систем.
Вопросы для самопроверки по теме 4.2
1. Какие цели теории нормализации?
2. Дайте определение функциональной зависимости атрибутов.
3. Чем различаются метод декомпозиции и синтеза?
3. Что такое ER-технология?
4. Какие существуют разновидности нормальных форм?
5. Включает ли реляционная алгебра операции модификации данных?
6. Как описываются структурные ограничения целостности?
7. Что такое свойство сохранения зависимостей?
|
