17229

ОСНОВЫ ПРОЕКТИРОВАНИЯ РЕЛЯЦИОННЫХ БД

Лекция

Информатика, кибернетика и программирование

Лекция №8 ОСНОВЫ проектирования реляционных БД При проектировании базы данных решаются две основные проблемы. Проблема логического проектирования баз данных. Каким образом отобразить объекты предметной области в абстрактные объекты модели данных чтобы эт...

Русский

2013-06-30

120.5 KB

5 чел.

Лекция №8

ОСНОВЫ проектирования реляционных БД

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

  •  Проблема логического проектирования баз данных. Каким образом отобразить объекты предметной области в абстрактные объекты модели данных, чтобы это отображение не противоречило семантике предметной области, и было по возможности, наилучшим (эффективным, удобным и т.д.)?
  •  Проблем физического проектирования баз данных. Как обеспечить эффективность выполнения запросов к БД, т. е. каким образом, имея в виду особенности конкретной СУБД, расположить данные во внешней памяти, какие необходимы дополнительные структуры (например, индексов) и т. д.?

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

Будем рассматривать проблему проектирования реляционной БД как обоснование принятия решения о том, из каких отношений должна состоять БД и какие атрибуты должны быть у этих отношений.

Рассмотрим классический подход, при котором весь процесс проектирования БД осуществляется методом последовательных приближений к удовлетворительному набору схем отношений.

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

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

Каждой нормальной форме соответствует определенный набор ограничений, и отношение находится в некоторой нормальной форме (НФ), если удовлетворяет свойственному ей набору ограничений.

Ограничением первой нормальной формы (1НФ) является необходимость приведения всех атрибутов отношения к атомарному виду. Поскольку требование 1НФ является базовым требованием классической реляционной модели данных, т.е.

  •  В отношении нет одинаковых кортежей.
  •  Кортежи не упорядочены.
  •  Атрибуты не упорядочены и различаются по наименованию.
  •  Все значения атрибутов атомарны.

Будем считать, что исходный набор отношений уже соответствует этому требованию.

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

  •  первая нормальная форма (1НФ);
  •  вторая нормальная форма (2НФ);
  •  третья нормальная форма (3НФ);
  •  нормальная форма Бойса-Кодда (БКНФ);
  •  четвертая нормальная форма (4НФ);
  •  пятая нормальная форма, или нормальная форма проекции-соединения (5НФ или PJ/НФ);
  •  и другие.

Основные свойства нормальных форм состоят в следующем:

  •  каждая следующая нормальная форма в некотором смысле лучше предыдущей нормальной формы;
  •  при переходе к следующей нормальной форме свойства предыдущих нормальных форм сохраняются.

Прежде чем рассмотреть методы проектирования укажем некоторые причины, по которым схема БД может оказаться неадекватной требованиям ПрО. Другими словами выделим аномалии противоречащие ПрО.

Например. Рассмотрим отношений Деканат следующего вида:

№зк

ФИО

Группа

Предмет

Преподаватель

Кафедра

Оценка

Структура такой схемы может привести к проблемам.

  1.  Избыточность. Группа, Преподаватель, Кафедра повторяются столько раз, сколько раз сдавались экзамены.
  2.  Аномалия обновления (UPDATE). Вследствие избыточности можно обновить, например, Преподавателя в одном картеже, оставляя его неизменным в другом.
  3.  Аномалия включения (INSERT). В БД не может быть занесено ФИО, если студент в настоящее время не сдавал ни одного экзамена. При этом использование пустых значений может привести к дополнительным трудностям, например, таким как поиск и заполнение пустых значений.
  4.  Аномалия удаления (DELETE). Обратная проблема может возникнуть при необходимости удаления всех ФИО (закончивших ВУЗ), вследствие чего непреднамеренно будет удалена вся информации о Предметах, Преподавателях и т.д.

Причина аномалии - хранение в одном отношении разнородной информации (и о студентах, и о преподавателях, и об успеваемости).

Вывод - структура данных неадекватна требованиям ПрО. БД, основанная на такой структуре, будет работать неправильно.

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

Для устранения указанных аномалий (а на самом деле для правильного проектирования структуры данных!) приведем структуру БД к нормальной форме более высокого порядка, для чего введем понятие функциональной зависимости атрибутов отношения.

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

.

Другими словами:

Если даны два атрибута X и Y некоторого отношения R, то говорят, что Y функционально зависит от X, если в любой момент времени каждому значению X соответствует ровно одно значение Y.

При этом X и Y могут быть составными, то есть составленные из нескольких атрибутов одного отношения.

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

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

Замечание. Если атрибуты  составляют потенциальный ключ отношения , то любой атрибут отношения  функционально зависит от .

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

Декомпозицией схемы отношения R называется замена ее совокупностью  = {R1,…,Rm} подмножеств R, таких, что R1  Rm = R. При этом не требуется, чтобы Ri были непересекающимися, т.е. Ri  Rj = .

При “правильном” проектировании схемы БД необходимо, чтобы декомпозиция обладала свойством соединения без потерь, то есть должно выполняться условие:

R = R1(R) >< R2(R) ><>< Rn(R)

То есть R является естественным соединение его проекций на все Ri.

Вторая нормальная форма

Пример. В отношении Деканат можно привести следующие примеры функциональных зависимостей:

  1.  №зк ФИО, Группа
  2.  №зк, Предмет Оценка
  3.  Предмет Преподаватель
  4.  Преподаватель Кафедра

Замечание. Приведенные ФЗ не выведены из внешнего вида отношения. Эти зависимости отражают взаимосвязи, обнаруженные между объектами ПрО и являются дополнительными ограничениями, определяемыми ПрО. Таким образом, ФЗ - семантическое понятие. Она возникает, когда по значениям одних данных в ПрО можно определить значения других данных.

Например, зная №зк студента, можно определить его фамилию и группу где он учиться, по №зк и предмету можно определить полученную оценку и т.д. Для корректности БД (адекватности предметной области) необходимо при выполнении операций модификации данных проверять все ограничения, определенные ФЗ.

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

Замечание. Если потенциальный ключ отношения является простым, то отношение автоматически находится в 2НФ.

С другой стороны для определения 2НФ вводят понятие неполной ФЗ.

Определение. Неключевой атрибут функционально полно зависит от составного ключа если он функционально зависит от всего ключа в целом, но не находится в функциональной зависимости от какого-либо из входящих в него атрибутов.

Формально можно записать как

Если X  Y и Z  Y, то при Z  X функциональная зависимость Z  Y будет неполной. При этом необязательно, чтобы зависимые части (т.е. Y) совпадали.

Тогда определение 2НФ можно сформулировать следующим образом.

Определение. Отношение  находится во второй нормальной форме (2НФ) тогда и только тогда, когда отношение находится в 1НФ, и все неключевые атрибуты функционально полно зависят от потенциального ключа.

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

Рассмотреть пример с таблицей Деканат.

Найдем неполные ФЗ среди заданных ФЗ для отношения Деканат. Неполной является 1я ФЗ относительно 2ой. Для приведения БД к 2НФ необходимо вынести неполную ФЗ в отдельную таблицу, т.е. построить декомпозицию таблицы Деканат на таблицы Список и Успеваемость.

       Список                               Успеваемость 

№зк

ФИО

Группа

№зк

Предмет

Преподаватель

Кафедра

Оценка

При этом ФЗ распределяться следующим образом:

для таблицы Список будет соответствовать ФЗ

№зк ФИО, Группа

для таблицы Успеваемость будут соответствовать ФЗ

№зк, Предмет Оценка

Предмет Преподаватель

Преподаватель Кафедра

Отметим, что таблица Список находится во 2НФ, т.к. среди соответствующих ФЗ нет неполных. А таблица Успеваемость не соответствует 2НФ, т.к. множество зависимостей таблицы содержит неполные ФЗ, зависимость

Предмет Преподаватель

относительно зависимости

№зк, Предмет Оценка.

Однако, пока не вдаваясь в подробности, заметим, что выполнить декомпозицию просто выделив ФЗ Предмет  Преподаватель в отдельную таблицу нельзя, т.к. при декомпозиции исходное отношений не изменится, все вынесенные атрибуты должны остаться, чтобы не нарушались оставшиеся ФЗ.

Для решения этого вопроса необходимо вместе с ФЗ Предмет  Преподаватель вынести ФЗ Преподаватель Кафедра, таким образом, решается вопрос с аномалией избыточности в таблице Успеваемости, и отваляем корректными все ФЗ.

Декомпозиция таблицы Успеваемость представляется двумя таблицами Экзамен и Кафедра.

                Экзамен                                    Кафедра

№зк

Предмет

Оценка

Предмет

Преподаватель

Кафедра

При этом ФЗ распределяться следующим образом:

для таблицы Экзамен будет соответствовать ФЗ

№зк, Предмет Оценка

для таблицы Кафедра будут соответствовать ФЗ

Предмет Преподаватель

Преподаватель Кафедра

Таким образом, среди полученных множеств ФЗ нет неполных, следовательно, каждое полученное отношений находится во 2НФ и БД в целом также находится во 2НФ.

Третья нормальная форма

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

Пусть X, Y, Z - три атрибута некоторого отношения. При этом --> Y и Y --> Z, но обратное соответствие отсутствует, т.е. Z -/-> Y и Y -/-> X. Тогда Z транзитивно зависит от X.

Тогда определение 3НФ сформулируем следующим образом.

Определение. Отношение  находится в третьей нормальной форме (3НФ) тогда и только тогда, когда отношение находится в 2НФ, и каждый неключевой атрибут нетранзитивно зависит от потенциального ключа.

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

Рассмотреть пример с отношением Деканат.

Отношению Список и Экзамен соответствует по одной ФЗ, и, следовательно, они находятся в 3НФ, так как транзитивность заведомо отсутствует.

Отношению Кафедра соответствует две ФЗ:

Предмет Преподаватель

Преподаватель Кафедра

проанализируем их.

Атрибут Кафедра транзитивно зависит от атрибута Предмет, следовательно отношение Кафедра не находится в 3НФ. Таким образом, необходимо выполнить декомпозицию по соответствующим ФЗ.

Декомпозиция представляется двумя отношениями Предмет и Кафедра.

                       Предмет                                 Кафедра

Предмет

Преподаватель

Преподаватель

Кафедра

При этом ФЗ распределяться следующим образом:

для таблицы Предмет будет соответствовать ФЗ

Предмет Преподаватель

для таблицы Кафедра будут соответствовать ФЗ

Преподаватель Кафедра

Таким образом, среди полученных множеств ФЗ соответствующих каждой таблицы нет транзитивных, следовательно, каждое полученное отношений находится во 3НФ и БД в целом также находится во 3НФ.

Спроектированная БД в 3НФ имеет следующую структуру:

 Список 

№зк

ФИО

Группа

                   1

                                               Экзамен

№зк

Предмет

Оценка

                                                              

                  Предмет          1                                         1    Кафедра

Предмет

Преподаватель

Преподаватель

Кафедра

Следует отметить, что в данном примере первичные ключи каждой таблицы соответствуют левым атрибутам ФЗ, так как каждой таблицы соответствует одна ФЗ, которая определяет остальные атрибуты, и, следовательно, определяет первичный ключ.

Проанализировав последовательность декомпозиции можно установить связи между таблицами, которые будут соответствовать типу “1:М”.

Схема последовательности декомпозиции представляется следующим образом:

Исходная таблица:

 Деканат

2НФ:

Список  Экзамен по атрибуту №зк 

Экзамен  Кафедра по атрибуту Предмет

3НФ:

Список  Экзамен по атрибуту №зк 

Экзамен  Предмет по атрибуту Предмет

Кафедра  Кафедра по атрибуту Преподаватель

Алгоритм нормализации (приведение к 3НФ)

Итак, алгоритм нормализации (т.е. алгоритм приведения отношений к 3НФ) описывается следующим образом.

Шаг 1 (Приведение к 1НФ). На первом шаге задается одно или несколько отношений, отображающих понятия предметной области. По модели предметной области (не по внешнему виду полученных отношений!) выписываются обнаруженные функциональные зависимости. Все отношения автоматически находятся в 1НФ.

Шаг 2 (Приведение к 2НФ). Если в некоторых отношениях обнаружена зависимость атрибутов от части составного потенциального ключа, то проводим декомпозицию этих отношений на несколько отношений следующим образом: те атрибуты, которые зависят от части составного потенциального ключа выносятся в отдельное отношение вместе с этой частью ключа. В исходном отношении остаются все ключевые атрибуты:

Исходное отношение: .

Ключ:  - сложный.

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

 - зависимость всех атрибутов от ключа отношения.

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

Декомпозированные отношения:

 - остаток от исходного отношения. Ключ .

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

Шаг 3 (Приведение к 3НФ). Если в некоторых отношениях обнаружена транзитивная зависимость некоторых неключевых атрибутов, то проводим декомпозицию этих отношений следующим образом: те неключевые атрибуты, которые транзитивно зависят от атрибутов потенциального ключа, выносятся в отдельное отношение. В новом отношении ключом становится детерминант функциональной зависимости:

Исходное отношение: .

Ключ: .

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

- зависимость всех атрибутов от ключа отношения.

- транзитивная зависимость неключевых атрибутов от потенциального ключа .

Декомпозированные отношения:

- остаток от исходного отношения. Ключ .

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

Устно. На практике, при создании логической модели данных, как правило, не следуют прямо приведенному алгоритму нормализации. Часто можно сразу построить отношения в 3НФ.

Тем не менее, приведенный алгоритм важен по двум причинам. Во-первых, этот алгоритм показывает, какие проблемы возникают при разработке слабо нормализованных отношений. Во-вторых, как правило, модель предметной области никогда не бывает правильно разработана с первого шага.

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

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


 

А также другие работы, которые могут Вас заинтересовать

55962. The Ecological Problems of our Settlement 34 KB
  Good afternoon, everybody! I am glad to see you at our ecological party which is called "A Boomerang". I am sure that everybody who has come here is indifferent to everything that is around us, and understands that the Earth is our home. Today we will discuss and try to solve the environmental problems of our settlement.
55963. Пори року. Техніка - модульне орігамі 2.31 MB
  Вона складається із старого клубка ниток обмотаного грофованим папером білого кольору. Обличчя намальоване фломастерами, волосся і корона з двостороннього кольорового паперу.
55964. Подорож до країни Математики 40 KB
  Діти сьогодні ми з вами можемо потрапити до країни Математики. Добрий день діти Пишу вам з чарівної країни Математики. Розчаклувати жителів країни Математики можуть тільки розумні уважні й кмітливі діти. До зустрічі Королева Математики...
55965. Читання оповідання В. Сухомлинського «Петрик, собака і кошеня» 37 KB
  Продовжувати знайомити дітей з творчістю В. Сухомлинського. Повторити твори, що читали раніше. Ознайомити з оповіданням В. Сухомлинського «Петрик, собака і кошеня». Вчити дітей уважно слухати твір, відповідати на запитання відповідно до змісту.
55968. Шана Великому Кобзарю 73.5 KB
  Життя Тарасику дала Кріпачкамати вбита горем. Читання напам’ять вірша Якби ви знали паничіâ€ Інсценізація На сцену виходить Тарас і Оксана. Оксана Оце на хвильку забігла до тебе Тарасику. Не сумуй Тарасику.
55969. Шар. Площадь поверхности и объём шара 599 KB
  Цели урока: Образовательные цели: Ознакомить учащихся с фигурой шар сфера Показать как изображаются данные фигуры на плоскости Познакомить учащихся с формулами вычисления площади поверхности и объёма шара Развивающие цели: развитие исследовательских навыков учащихся умений анализировать полученные данные и делать выводы...
55970. Мовні шаради як спосіб активізації пізнавальної діяльності учнів на уроках української мови та в позакласній роботі 206 KB
  Так як людина реалізується в культурі думки, культурі праці й культурі мови, то важливим елементом виховання справжньої культурної людини є саме переконаність учителя в тому, що його учні уміють правильно говорити і писати, добирати мовно-виражальні засоби відповідно до мети та обставин спілкування.