1 ГОУ ВПО Уральский государственный технический университет – УПИ

2 Кафедра «Автоматика и управление в технических системах» направление – Автоматизация и управление специальность – Управление и информатика в технических системах ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ СИСТЕМ УПРАВЛЕНИЯ Лекция ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Четвертая нормальная форма (4НФ) Пятая нормальная форма (5НФ) 5.4. Проектирование реляционных БД на базе функциональных зависимостей Преподаватели: Чесноков Юрий Николаевич, доц., к.т.н., Дружинина Надежда Геннадьевна, доц.

3 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Цель изучения материала: научиться проектировать реляционную модель данных с помощью нормализации отношений; научиться проектировать четвертую нормальную форму (4НФ) БД; научиться проектировать пятую нормальную форму (5НФ) БД; научиться проектировать третью нормальную форму (3НФ) БД; научиться проектировать реляционных БД на базе функциональных зависимостей. Компетенций, формирующиеся в процессе знакомства с материалом: готовность учитывать современные тенденции развития информатики и вычислительной техники, компьютерных технологий в своей профессиональной деятельности; приобретать новые знания, используя современные образовательные и информационные технологии

4 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Содержание лекции ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Четвертая нормальная форма (4НФ) Пятая нормальная форма (5НФ) 5.4. Проектирование реляционных БД на базе функциональных зависимостей

5 Отношение R находится в четвертой нормальной форме 4НФ, если оно находится в НФБК, и в нем отсутствуют многозначные зависимости, которые не являются функциональными [8] (т.е. многозначные зависимости, не содержащие ключа). Другое определение [8] 4НФ требует, чтобы в отношении для любой нетривиальной многозначной зависимости, т.е. Х Y (X 0 или X R-X-Y является тривиальным), Х обязательно содержал ключ отношения. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Четвертая нормальная форма (4НФ)

6 Приведем еще определения 4НФ, взятые из различных источников. Отношение R находится в 4НФ – в том и только том случае, если при существовании многозначной зависимости Х Y все остальные атрибуты R функционально полно зависят от Х [6]. Отношение R находится в 4НФ – в том и только том случае, если оно соответствует НФБК и не имеет многозначных зависимостей [12]. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Четвертая нормальная форма (4НФ)

7 Четвертая нормальная форма запрещает существование между атрибутами (столбцами) многозначной зависимости [13]. Таблица находится в 4НФ – в ней есть не более одной многозначной зависимости [9]. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Четвертая нормальная форма (4НФ)

8 Основой нормализации отношений с многозначными зависимостями является следующее утверждение. Теорема Фейджина (Fagin) гласит: отношение R(A, B, C) можно спроецировать без потерь в отношения R1(A, B), R2(A, C) в том и только том случае, когда существуют две многозначные зависимости A B и B C [6]. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Четвертая нормальная форма (4НФ)

9 На рис приведен пример отношения с информацией о кинокартинах (фильмах), которое не находится в 4НФ [12]. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Четвертая нормальная форма (4НФ)

10 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Четвертая нормальная форма (4НФ) Рис Пример отношения с многозначной зависимостью НазваниеЗвездаПродюсер Большая дорогаБаталовПетров Большая дорогаБаталовСидоров Большая дорогаОрловаПетров Большая дорогаОрловаСидоров Большая дорогаКрючковПетров Большая дорогаКрючковСидоров МракОрловаСидоров МракОтцСидоров

11 В этом отношении есть следующие многозначные зависимости: «Название» «Звезда»; «Название» «Продюсер». Ключ отношения состоит из всех атрибутов. Поскольку неключевых атрибутов нет, то отношение находится в НФБК. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Четвертая нормальная форма (4НФ)

12 Однако в данном отношении имеются аномалии: нельзя ввести сведения о звезде, не зная хотя бы одного продюсера; нельзя ввести сведения о продюсере, не зная хотя бы одну звезду; при удалении только сведений о продюсере картины теряется информация о звездах; при удалении только сведений о звезде картины теряется информация о продюсерах; имя каждого продюсера дублируется для каждой звезды картины и наоборот (аномалия модификации). 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Четвертая нормальная форма (4НФ)

13 Проецирования этого отношения на пары атрибутов («Название», «Звезда»), («Название», «Продюсер») устраняет перечисленные аномалии. Отношение, представленное на рис. 5.5 (см. лекцию 9), следует спроецировать в отношения с атрибутами («Операция», «Фамилия») и («Операция», «Мероприятие») [5]. Результат проекции представлен на рис ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Четвертая нормальная форма (4НФ)

14 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Четвертая нормальная форма (4НФ) Рис Декомпозиция отношения, представленного на рис. 5.5 ОперацияФамилияОперацияМероприятие «Ы»Пронин«Ы»«Прыжок» «Золотой глаз» Бонд«Ы»«Бросок» «Золотой глаз» «Подход» «Золотой глаз» «Контакт» «Золотой глаз» «Связь»

15 «Пятая нормальная форма представляет собой сложный набор критериев, работать с которыми исключительно трудно. Большинство разработчиков стараются не иметь дела с 5НФ, зная о том, что если их отношения соответствуют 3НФ (или 4НФ, если это оправдано), никаких проблем с их проектами не будет» [12]. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Пятая нормальная форма (5НФ)

16 Отношение R(X, Y, …, Z) удовлетворяет зависимости соединения (X, Y, …, Z) в том и только в том случае, когда R восстанавливается без потерь путем соединения своих проекций на X, Y, …, Z. Здесь X, Y, …, Z – наборы атрибутов отношения. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Пятая нормальная форма (5НФ)

17 Отношение R находится в пятой нормальной форме (5НФ) (в нормальной форме проекция – соединение) – в том случае, если любая зависимость соединения в R следует из существования возможного ключа в R. Другими словами, каждая проекция R содержит не менее одного возможного ключа и, по крайней мере, один непервичный атрибут [8]. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Пятая нормальная форма (5НФ)

18 Можно сказать, что «если таблица имеет три или более потенциальных ключей и можно провести ее декомпозицию без потерь данных, то такую таблицу нужно разделить на отдельные таблицы для каждого потенциального ключа» [13]. Таблица находится в 5НФ, если в каждой ее полной декомпозиции все проекции содержат возможный ключ. Если в таблице не имеется ни одной полной декомпозиции, то она также находится в 5НФ [7]. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Пятая нормальная форма (5НФ)

19 Отношение находится в 5НФ, если оно находится в 3НФ и все возможные ключи представляют собой простые одиночные атрибуты [9]. Рассмотрим пример отношения из детективной области (рис. 5.25), в котором отсутствуют ФЗ и многозначные зависимости, т.е. отношение в 4НФ. В качестве ключа – все атрибуты. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Пятая нормальная форма (5НФ)

20 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Пятая нормальная форма (5НФ) Рис Пример отношения с зависимостью соединения ФамилияГруппаМероприятие Пронин«A»«Прыжок» Пронин«T»«Прыжок» Исаев«B»«Связь» Бонд«S»«Контакт»

21 Если предположить, что в отношении имеются зависимости соединения по составным атрибутам : («Фамилия», «Группа»), («Фамилия», «Мероприятие»), («Группа», «Мероприятие»), то, разбив отношение на три проекции по этим атрибутам, можно удовлетворить требованиям 5НФ. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Пятая нормальная форма (5НФ)

22 Наличие зависимости соединения является нетривиальным предположением, основывающимся в большинстве случаев на эвристических соображениях, т.е. в данном случае на уверенности, что при соединении трех таблиц («Фамилия», «Группа»), («Фамилия», «Мероприятие») и («Группа», «Мероприятие») не произойдет каких-либо потерь или появления лишних данных относительно исходной таблицы [5]. Декомпозиция рассматриваемого отношения на три отношения представлена на рис ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Пятая нормальная форма (5НФ)

23 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Пятая нормальная форма (5НФ) Рис Декомпозиция отношения, представленного на рис ФамилияГруппаФамилияМероприятиеГруппаМероприятие Пронин«A»Пронин«Прыжок»«A»«Прыжок» Пронин«T»Исаев«Связь»«T»«Прыжок» Исаев«B»Бонд«Контакт»«B»«Связь» Бонд«S» «Контакт»

24 Чистый проект в БД – когда каждая таблица содержит информацию только об одном типе сущности (каждый факт в одном месте) [2]. Выделяют 5 этапов проектирования БД. Этап I. Определение всех необходимых атрибутов, связей между ними и построение универсального отношения U для БД (целесообразно строить U при количестве атрибутов менее 20). 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.4. Проектирование реляционных БД на базе функциональных зависимостей

25 Этап II. Определение всех ФЗ между атрибутами. ФЗ подробно рассматривались в разделе 5.2. Этап III. Удаление всех избыточных ФЗ из набора ФЗ с целью получения минимального покрытия. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.4. Проектирование реляционных БД на базе функциональных зависимостей

26 Этап III. Удаление всех избыточных ФЗ из набора ФЗ с целью получения минимального покрытия. Избыточная ФЗ – содержит в себе такую информацию, которую можно получить из других зависимостей. Избыточная ФЗ не содержит уникальной информации, по этой причине ее можно удалить без ущерба для проекта БД. Существует 5 видов избыточных зависимостей 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.4. Проектирование реляционных БД на базе функциональных зависимостей

27 1. Транзитивные зависимости. Если А В и B С, то А С. 2. Добавленные атрибуты: а) А, В, Z – атрибуты, возможно составные, (А, В) – составной ключ. Если А В, то ФЗ (А, Z) В корректна, но избыточна; б) (А, Z) и (В, Z) – составные ключи. Если А В, то ФЗ (А, Z) (B, Z) корректна, но избыточна. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.4. Проектирование реляционных БД на базе функциональных зависимостей

28 3. Объединенные ФЗ. Если А В и А С, то ФЗ А (В, С). 4. Декомпозиция ФЗ. Если А (В, С), то А В и А С. 5. Псевдотранзитивные ФЗ (возникают, если используются составные детерминанты). Если Х Y и (Y, W) Z, то (X, W) Z. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.4. Проектирование реляционных БД на базе функциональных зависимостей

29 Избыточные ФЗ следует удалять по одной, затем анализировать полученный набор ФЗ на избыточность. Если нет избыточности, то оставшийся набор будет минимальным покрытием. Минимальное покрытие – это набор неизбыточных ФЗ, полученный после удаления всех избыточных ФЗ. Минимальное покрытие не всегда является уникальным, т.е. порядок удаления избыточных ФЗ влияет на конечный результат. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.4. Проектирование реляционных БД на базе функциональных зависимостей

30 Этап IV. Использование ФЗ из минимального покрытия для декомпозиции универсального отношения U в набор НФБК-отношений. Этап V. Сравнение полученных вариантов минимальных покрытий с целью выбора варианта, лучше других отвечающего требованиям пользователя. Имеет смысл, если на третьем этапе получено более одного минимального покрытия. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.4. Проектирование реляционных БД на базе функциональных зависимостей

31 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Выводы и заключение по лекции: научились проектировать реляционную модель данных с помощью нормализации отношений; научились проектировать четвертую нормальную форму (4НФ) БД; научились проектировать пятую нормальную форму (5НФ) БД; научились проектировать третью нормальную форму (3НФ) БД; научились проектировать реляционных БД на базе функциональных зависимостей.

32 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Перечень источников: Четвериков В.Н. Базы и банки данных/ В.Н. Четвериков, Г.И. Ревунков, Э. Н. Самохвалов; под ред. В.Н. Четверикова. М.: Высшая школа, с. Дейт К. Дж. Руководство по реляционной СУБД DB2/ К. Дж. Дейт. М.: Финансы и статистика, с. Дейт К. Дж. Введение в системы баз данных/ К. Дж. Дейт. М.: Издательский дом «Вильямс», 2001, 1072 с. Дмитриев В.И.Прикладная теория информации/В.И. Дмитриев. М.:Высшая школа, с. Гайдамакин Н.А. Автоматизированные информационные системы, базы и банки данных/ Н.А. Гайдамакин. М.: Гелиос АРВ, С. Карпова Т.С. Базы данных: модели, разработка, реализация/ Т.С. Карпова. СПб.: Питер, с. Мамаев Е.В. MS SQL Server 7.0. Проектирование и реализация баз данных/ Е.В. Мамаев. СПб.: БХВ-Санкт-Петербург, с. Озкарахан Э. Машины баз данных и управление базами данных/ Э. Озкарахан. М.: Мир, с. Селко Джо. SQL для профессионалов. Программирование/ Джо Селко. М.:«Лори», с. Системы управления базами данных и знаний/ А.Н. Наумов [и др.]; под общ. ред. А.Н. Наумова. М.: Финансы и статистика, с. Теория автоматического управления/ С.Е. Душин [и др.]; под общ. ред. Б. Б. Яковлева. М.: Высшая школа, с. Харрингтон Дж. Л. Проектирование реляционных баз данных. Просто и доступно/ Дж. Л. Харрингтон. М.: «Лори», с. Хендерсен К. Delphi 3 и системы клиент/сервер: руководство разработчика/ К. Хендерсен. Киев: Диалектика, с.