Тема 1. Базы данных специального назначения Лекция 4: Нормализация баз данных Учебные цели занятия: Сформировать представление о: 1)Функциональных зависимостях и их назначении, 2)Процессе нормализации и его назначении, 3)Нормальных формах 1НФ, 2НФ, 3НФб НФБК 4)Процедурах нормализации (до 3НФ, НФБК) Учебные вопросы: 1)Функциональные зависимости 2)Нормализация: формы 1НФ, 2НФ, 3НФ и НФБК 3)Нормализация: более высокие нормальные формы Базы данных специального назначения. Лекция 4 1

1. Функциональная зависимость Базы данных специального назначения. Лекция 4 2 Пусть R является переменной-отношением, а X и Y – произвольными подмножествами множества атрибутов переменной-отношения R. Тогда Y функционально зависимо от X, что в символическом виде записывается как: X Y (читается либо как «X функционально определяет Y», либо «X стрелка Y») тогда и только тогда, когда для любого допустимого значения переменной-отношения R каждое значение множества X отношения R связано в точности с одним значением множества Y отношения R. Иначе говоря, для любого допустимого значения переменной-отношения R, если два кортежа переменной-отношения R совпадают по значению X, они также совпадают и по значению Y.

1.2 Основные определения Левая и правая части функциональной зависимости (X и Y соответственно), называют детерминантом и зависимой частью соответственно Следует отметить, что если X является потенциальным ключом переменной-отношения R, то все атрибуты Y переменной-отношения R должны обязательно быть функционально зависимы от X. Если переменная-отношение R удовлетворяет функциональной зависимости A B и A не является потенциальным ключом, то R будет характеризоваться некоторой избыточностью. Например, в переменной- отношении SCP наличие ФЗ S# CITY приведет к тому, что сведения о месте расположения поставщика в определенном городе повторятся много раз

Функциональные зависимости (примеры) Базы данных специального назначения. Лекция 4 4 S#CITYP#QTY S1S1МоскваP1100 S1МоскваP2100 S2ТверьP1200 S2ТверьP2200 S3ТверьP2300 S4МоскваP2400 S4МоскваP4400 S4МоскваP5400 SCP {S#,P#} QTY {S#,P#} CITY {S#,P#} {CITY, QTY} {S#,P#} S# {S#,P#} {S#, P#, CITY, QTY} {S#} CITY Примеры функциональных зависимостей для SCP:

1.3 Тривиальные и нетривиальные зависимости Зависимость называется тривиальной, если она не может не выполняться. В качестве примера приведем тривиальную ФЗ, существующую в переменной-отношении SCP, которая обсуждалась в предыдущем разделе: {S#, P#} S# Функциональная зависимость называется тривиальной тогда и только тогда, когда первая часть ее символической записи является подмножеством (не обязательно собственным) левой части. Формальное определение выглядит следующим образом: Функциональная зависимость называется тривиальной тогда и только тогда, когда ее зависимая часть является подмножеством (не обязательно собственным) детерминанта. С практической точки зрения такие зависимости не представляют никакого интереса – в отличие от нетривиальных зависимостей, которые действительно являются реальными ограничениями целостности. Однако в формальной теории зависимостей необходимо учитывать все зависимости, как тривиальные, так и нетривиальные

1.4 Замыкание множества зависимостей Как уже упоминалось, одни ФЗ могут подразумевать другие ФЗ. Например, рассмотрим приведенную ниже ФЗ. {S#, P#} {CITY, QTY} Она подразумевает следующие ФЗ: {S#, P#} CITY {S#, P#} QTY В качестве более сложного примера рассмотрим переменную- отношение R с атрибутами A, B, C, для которых выполняются ФЗ A B и B C. Нетрудно заметить, что в этом случае выполняется и ФЗ A C, которая называется транзитивной ФЗ, т.е. C зависит от A транзитивно, через B. Множество всех ФЗ, которые подразумеваются заданным множеством ФЗ S, называется замыканием множества S и обозначается символом S+. Из этого определения следует, что необходим способ вычисления S+ на основе S.

Правила вывода (аксиомы Армстронга) Базы данных специального назначения. Лекция Правило рефлексивности: если множество B является подмножеством множества A, то A B. 2.Правило дополнения: если A B, то AC BC. 3.Правило транзитивности: если A B и B C, то A C. 4.Правило самоопределения: A A. 5.Правило декомпозиции: если A BC, то A B и A C. 6.Правило объединения: если A B и A С, то A BC. 7.Правило композиции: если A B и C D, то AC BD. 8.Если A B и С D, то A (C - B) BD. (Общая теорема объединения)

Пример 4.2. Пусть дана переменная-отношение R с атрибутами A, B, C, D, E, F и следующими ФЗ: A BC B E CD EF Можно показать, что для переменной-отношения R выполняется ФЗ AD F, которая вследствие этого принадлежит замыканию множества ФЗ. A BC (дано) A C (декомпозиция из п.1) AD CD (дополнение из п.2) CD EF (дано) AD EF (транзитивность из пп.3 и 4) AD F (декомпозиция из п.5)

1.5 Замыкание множества атрибутов Базы данных специального назначения. Лекция 4 9 CLOSURE[Z,S] := Z; do for each FD X Y in S /* для каждой ФЗ X Y в S */ do if X CLOSURE[Z,S]/* = */ then CLOSURE[Z,S] := CLOSURE[Z,S] Y; end; if CLOSURE[Z,S] then leave loop;/* вычисления завершаются */ end; для заданной переменной-отношения R, заданного множества ФЗ S, выполняющихся для переменной-отношения R, можно найти множество всех атрибутов переменной-отношения R, которые функционально зависимы от Z, т.е. так называемое замыкание Z+ множества Z в пределах S+.

1.5 Замыкание множества атрибутов (пример) Пример 4.3. Пусть дана переменная-отношение R с атрибутами A, B, C, D, E, F и следующими ФЗ: A BC E CF B E CD EF Вычислим замыкание {A,B}+, исходя из указанного множества ФЗ: Присвоим замыканию CLOSURE[Z,S] начальное значение – множество {A,B}.

1.5 Замыкание множества атрибутов (пример) Выполним внутренний цикл четыре раза – по одному для каждой ФЗ. На первой итерации будет обнаружено, что левая часть действительно является подмножеством замыкания CLOSURE[Z,S]. Таким образом, к результату добавляются атрибуты B и C. В результате замыкание CLOSURE[Z,S] представляет собой множество {A,B,C}. На второй итерации (E CF) к замыканию не добавляется атрибутов. На третьей итерации (B E) к замыканию CLOSURE[Z,S] добавляется атрибут E. Теперь замыкание CLOSURE[Z,S] представляет собой множество {A,B,C,E}. На четвертой итерации (CD EF) к замыканию не добавляется атрибутов. Далее внутренний цикл выполняется еще четыре раза, в ходе чего на второй итерации (E CF) к замыканию добавится атрибут F. После еще одного четырехкратного прохождения внутреннего цикла замыкание не изменится, и процесс завершится с результатом {A,B}+={A,B,C,E,F}. Данный алгоритм представляет простой способ определения, будет ли данная ФЗ X Y в замыкание S+ множества S.

1.6 Неприводимые множества зависимостей Базы данных специального назначения. Лекция 4 12 Множество ФЗ S называется неприводимым тогда и только тогда, когда оно обладает всеми перечисленными ниже свойствами: Зависимая часть каждой ФЗ из множества S содержит только один атрибут (т.е. является одноэлементным множеством). Детерминант каждой ФЗ из множества S является неприводимым, т.е. ни один атрибут из детерминанта не может быть удален без изменения замыкания S +. В этом случае ФЗ называется неприводимой слева. Ни одна ФЗ из множества S не может быть удалена без изменения его замыкания S +.

Пусть S1 и S2 – два множества ФЗ. Если любая ФЗ, которая выводится из множества ФЗ S1, также выводится из множества ФЗ S2 (т.е. S1+ - подмножество S2+), то множество S2 называется покрытием множества S1. Это означает, что если СУБД поддерживает все ограничения целостности, представленных ФЗ S2, то она автоматически поддерживает и все ограничения целостности, представленные ФЗ S1. Если множество S1 является покрытием для множества S2, а множество S2 одновременно является покрытием для множества S1 (S1+=S2+), то множества S1 и S2 называются эквивалентными.

Пример 4.4. Пусть дана переменная-отношение R с атрибутами A, B, C, D и следующими ФЗ: A BC B C A B AB C AC D Найдем неприводимое множество ФЗ, эквивалентное данному множеству. Прежде всего, перепишем заданные ФЗ, чтобы каждая из них имела одноэлементную правую часть, используя правило декомпозиции, при этом удалив одну из ФЗ A B: A B A C

B C AB C AC D Затем в детерминанте ФЗ AC D может быть опущен атрибут C, поскольку имеется зависимость A C, из которой по правилу дополнения можно получить зависимость A AC. Кроме того, дана ФЗ AC D, из которой по правилу транзитивности можно получить ФЗ A D. Таким образом, атрибут C в детерминанте ФЗ AC D является избыточным. Далее, ФЗ AB C может быть исключена, поскольку дана зависимость A C, из которой по правилу дополнения можно получить ФЗ AB CB, а затем по правилу декомпозиции – ФЗ AB C. Наконец ФЗ A C подразумевается зависимостями A B и B C, а следовательно может быть отброшена. В результате получаем неприводимое множество ФЗ: A B B C A D Множество ФЗ I, которое неприводимо и эквивалентно другому множеству ФЗ S, называется неприводимым покрытием множества S. Таким образом, в системе вместо исходно множества ФЗ S может использоваться его неприводимое покрытие I. Однако следует отметить, что для заданного множества ФЗ не всегда существует уникальное неприводимое покрытие.

2. Нормализация: формы 1НФ, 2НФ, 3НФ и НФБК Процесс дальнейшей нормализации, который ниже будет упоминаться просто как нормализация, основывается на концепции нормальных форм. Говорят, что переменная- отношение находится в определенной нормальной форме, если она удовлетворяет некоторому набору условий. Например, переменная-отношение находится во второй нормальной форме (2НФ), если она находится в первой нормальной форме и удовлетворяет некоторым дополнительным условиям.

Уровни нормализации Базы данных специального назначения. Лекция 4 17 Переменные-отношения в 1НФ Переменные-отношения в 2НФ Переменные-отношения в 3НФ Переменные-отношения в НФБК Переменные-отношения в 4НФ Переменные-отношения в 5НФ

2.2 Декомпозиция без потерь и функциональные зависимости Базы данных специального назначения. Лекция 4 18 S#STATUSCITY S330Москва S530Смоленск S S#STATUS S330 S530 S#CITY S3Москва S5Смоленск SCа) SST б) SST S#STATUS S330 S530 STATUSCITY 30Москва 30Смоленск STC Теорема Хита. Пусть R{A,B,C} является переменной-отношением, где A, B и C – множества атрибутов этой переменной-отношения. Если R удовлетворяет ФЗ A B, то R равна соединению проекций {A, B} и {A, C}.

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

Нормализация (пример 1НФ) Базы данных специального назначения. Лекция 4 20 S#STATUSCITYP#QTY S120МоскваP1300 S120МоскваP2200 S120МоскваP3400 S120МоскваP4200 S120МоскваP5100 S120МоскваP6100 S210СмоленскP1300 S210СмоленскP2400 S310СмоленскP2200 S420МоскваP2200 S420МоскваP4300 S420МоскваP5400 FIRST Диаграмма ФЗ:

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

Нормализация (пример 2НФ) Базы данных специального назначения. Лекция 4 22 SECOND Диаграмма ФЗ: S#P#QTY S1P1300 S1P2200 S1P3400 S1P4200 S1P5100 S1P6100 S2P1300 S2P2400 S3P2200 S4P2200 S4P4300 S4P5400 SP S#STATUSCITY S120Москва S210Смоленск S310Смоленск S420Москва

Третья нормальная форма (3НФ) Базы данных специального назначения. Лекция 4 23 Третья нормальная форма. Переменная-отношение находится в третьей нормальной форме тогда и только тогда, когда она находится во второй нормальной форме, и каждый неключевой атрибут нетранзитивно зависит от ее первичного ключа. SC Диаграмма ФЗ: CS S#CITY S1Москва S2Смоленск S3Смоленск S4Москва CITYSTATUS Москва20 Смоленск10

Нормальная форма Бойса-Кодда (НФБК) Базы данных специального назначения. Лекция 4 24 Переменная-отношение находится в нормальной форме Бойса-Кодда тогда и только тогда, когда каждая ее нетривиальная и неприводимая слева ФЗ имеет в качестве детерминанта некоторый потенциальный ключ. Диаграмма ФЗ в переменной-отношении S для случая, когда атрибут SNAME является ее потенциальным ключом

Четвертая нормальная форма (4НФ) Базы данных специального назначения. Лекция 4 25 COURSETEACHERSTEXTS Физика Профессор ИвановМеханика ФизикаПрофессор ИвановОсновы оптики ФизикаДоцент Колосов Механика ФизикаДоцент КолосовОсновы оптики МатематикаПрофессор ИвановВекторный анализ МатематикаПрофессор ИвановТригонометрия МатематикаПрофессор ИвановДифференцирование CTX НCTX

Четвертая нормальная форма (4НФ) Продолжение Базы данных специального назначения. Лекция 4 26 CXCT COURSETEACHERS Физика Профессор Иванов ФизикаДоцент Колосов МатематикаПрофессор Иванов COURSETEXTS Физика Механика ФизикаОсновы оптики МатематикаВекторный анализ МатематикаТригонометрия МатематикаДифференцирование Пусть A, B и C являются произвольными подмножествами множества атрибутов переменной-отношения R. Тогда подмножество B многозначно зависит от подмножества A, что символически выражается записью: A B (читается как «A многозначно определяет B» или «A двойная стрелка B»), тогда и только тогда, когда множество значений B, соответствующее заданной паре (значение A, значение C) переменной-отношения R, зависит от A, но не зависит от C.

Четвертая нормальная форма (4НФ) Окончание Базы данных специального назначения. Лекция 4 27 Теорема Фейгина. Пусть A, B и C являются множествами атрибутов переменной-отношения R{A,B,C}. Переменная- отношение R будет равна соединению ее проекций {A,B} и {A,C} тогда и только тогда, когда для переменной-отношения R выполняется многозначная зависимость A B | C. Переменная-отношение R находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда в случае существования таких подмножеств A и B атрибутов этой переменной-отношения R, для которых выполняется нетривиальная многозначная зависимость A B, все атрибуты переменной-отношения R также функционально зависят от атрибута A. МЗЗ A B называется тривиальной, если либо A является супермножеством B, либо объединение A и B образует весь заголовок отношения.

Пятая нормальная форма (5НФ) Базы данных специального назначения. Лекция 4 28 SP SPJ S#P#J# S1P1J2 S1P2J1 S2P1J1 S1P1J1 PJJS S#P# S1P1 S1P2 S2P1 P#J# P1J2 P2J1 P1J1 S#J# S1J2 S1J1 S2J1 S#P#J# S1P1J2 S1P2J1 S2P1J1 S2P1J2 S1P1J1 SPJ Соединение по атрибуту P# Исходное состояние SPJ Соединение по комбинации атрибутов S#,J#

Пятая нормальная форма (5НФ) Продолжение ЕСЛИпара(s1,p1)присутствует в SP Ипара(p1,j1)присутствует в PJ Ипара(j1,s1)присутствует в JS ТОтройка(s1,p1,j1)присутствует в SPJ ЕСЛИкортежи (s1,p1,j2), (s2,p1,j1), (s1,p2,j1) присутствуют в SPJ ТО кортеж (s1,p1,j1) также присутствует в SPJ. Пусть R является переменной-отношением, а A,B,…,Z – произвольными подмножествами множества ее атрибутов. Переменная-отношение R удовлетворяет зависимости соединения: * {A,B,…,Z} (читается «звездочка A,B,…,Z») тогда и только тогда, когда любое допустимое значение переменной-отношения R эквивалентно соединению ее проекций по подмножествам атрибутов A,B,…,Z. 29 Базы данных специального назначения. Лекция 4

Пятая нормальная форма (5НФ) Продолжение Теорема Фейгина. Переменная-отношение R{A,B,C} удовлетворяет зависимости соединения *{AB,AC} тогда и только тогда, когда она многозначной зависимости A B | C. S#P#J# S1P1J2 S1P2J1 SPJ S#P#J# S1P1J2 S1P2J1 S2P1J1 S1P1J1 Если вставляется кортеж (S2,P1,J1), то также должен быть вставлен кортеж (S1,P1,J1) Обратное утверждение неверно. Кортеж (S2,P1,J1) может быть удален без побочных эффектов. Если удаляется кортеж (S1,P1,J1), то также должен быть удален еще один кортеж (но какой?) Примеры аномалий обновления: 30 Базы данных специального назначения. Лекция 4

Пятая нормальная форма (5НФ) Окончание Переменная-отношение R находится в пятой нормальной форме (5НФ), которую иногда иначе называют проекционно- соединительной нормальной формой (ПСНФ), тогда и только тогда, когда каждая нетривиальная зависимость соединения в переменной-отношении R подразумевается ее потенциальными ключами. Зависимость соединения * {A,B,…,Z} называется тривиальной тогда и только тогда, когда одна из проекций A,B,…,Z является проекцией идентичной R. 31 Базы данных специального назначения. Лекция 4

1.Функциональные зависимости. Замыкание множества зависимостей (правила вывода). Примеры. 2.Функциональные зависимости. Замыкание множества атрибутов. Неприводимые множества зависимостей. Примеры. 3.Концепция нормальных форм. Декомпозиция без потерь (теорема Хита). Диаграммы ФЗ. Примеры. 4.Нормализация. Первая, вторая и третья нормальные формы. Аномалии обновления. 1-ый и 2-ой этапы нормализации. Пример. Нормальная форма Бойса- Кодда. 5.Нормализация. Четвертая и пятая нормальные формы. Общая процедура проектирования БД. 32 Базы данных специального назначения. Лекция 4 Вопросы на самоподготовку:

Общая схема процедуры нормализации Весь процесс нормализации можно неформально определить с помощью перечисленных ниже правил. Переменную-отношение в 1НФ следует разбить на такие проекции, которые позволят исключить все функциональные зависимости, не являющиеся неприводимыми. В результате будет получен набор переменных-отношений в 2НФ. Полученные переменные-отношения в 2НФ следует разбить на такие проекции, которые позволят исключить все существующие транзитивные ФЗ. В результате будет получен набор переменных-отношений в 3НФ. Полученные переменные-отношения в 3НФ следует разбить на проекции, позволяющие исключить любые оставшиеся ФЗ, в которых детерминанты не являются потенциальными ключами. В результате такого разбиения будет получен набор переменных-отношений в НФБК. Полученные переменные-отношения в НФБК следует разбить на проекции, позволяющие исключить любые многозначные зависимости, которые не являются функциональными. В результате будет получен набор переменных- отношений в 4НФ. Полученные переменные-отношения в 4НФ следует разбить на проекции, позволяющие исключить любые зависимости соединения, которые не подразумеваются потенциальными ключами. В результате получаем набор переменных-отношений в 5НФ.

Общая схема процедуры нормализации Процесс разбиения на проекции на каждом этапе должен быть выполнен без потерь и с сохранением зависимостей. Общее назначение процесса нормализации заключается в следующем: исключение некоторых типов избыточности; устранение некоторых аномалий обновления; разработка проекта БД, который является достаточно «хорошим» представлением реального мира, интуитивно понятен и может служить хорошей основой для последующего расширения; упрощение процедуры описания необходимых ограничений целостности. Зависимости и нормализация являются чисто семантическими понятиями, т.е. связаны со смыслом данных, тогда как реляционная алгебра и реляционное исчисление, а также построенные на их основе языки наподобие SQL, наоборот, имеют дело со значениями данных и не требуют выполнения нормализации выше первого уровня. Рекомендации по выполнению дальнейшей нормализации должны рассматриваться, прежде всего, как некая упорядоченность, позволяющая разработчику БД (и, следовательно, ее пользователю) зафиксировать некую часть, пусть даже небольшую, семантики реального мира в простой и понятной форме.