Программа по формированию навыков безопасного поведения на дорогах и улицах «Добрая дорога детства» 2
Скачать 2.46 Mb.
|
Процесс проектирования.1-ый шаг: 1 NF → 2 NFИз схемы организации работы фирмы на рис. 1 определим схему отношений: ТОВАРЫ-ЗАКАЗЫ ТОВАРЫ {товарНом, товарНазв, товарОпис, товарРис, товарЦена, колНаСкладе, типНом, типНазв} ЗАКАЗЫ {заказНом, заказДата, ПокупНом, ФИОПокуп, ЭлпочтаПокуп, адресПокуп, товарНом, количТовЗаказа, видДост, ценаДост, налогНДС, общСумма, заказСост} В атрибутах «типНом» и «типНазв» содержится информация о типах товаров, например, название типа — Процессоры (типНом = 1), к которому относятся конкретные товары - Intel 386, Intel 486, AMD, и т.д. Атрибут «колНаСкладе» содержит общее количество товаров с данным номером на складе. В одном заказе может заказываться несколько товаров с разными номерами. Атрибут «количТовЗаказа» содержит количество товаров данного типа, заказанных в данном заказе. В атрибутах «ПокупНом», «ФИОПокуп», «ЭлпочтаПокуп», «адресПокуп» содержится информация о покупателе — номер, ФИО, Электронная почта и адрес. В атрибутах «видДост», «ценаДост» хранится информация о доставке — номер, вид и цена доставки. Атрибут «заказСост» содержит состояние заказа, который может быть иметь значение «Сделка совершена» либо «Сделка выполнена неполно». Для вычисления общей суммы заказа применяем формулу общСумма = ТоварЦена*количТов + налогНДС + ценаДост. На 1-м шаге проектирования форма 1NF приводится к виду 2NF. Для этого проверяем следующее определение: Отношение R находится в второй нормальной форме (2NF) в том и только в том случае, когда находится в 1NF, и каждый неключевой атрибут полностью зависит от первичного ключа. Рассмотрим отношение ЗАКАЗЫ. В этом отношении существует неполная функциональная зависимость от первичного ключа, поскольку все атрибуты, кроме товарНом и количТовЗаказа, зависят от ЗаказНом, а первичным ключом является заказНом, товарНом. И поэтому мы приводим отношение ко второй нормальной форме то есть, производим декомпозицию отношения ЗАКАЗЫ в два отношения ТИП ЗАКАЗА и ЗАКАЗЫ: ТИП ЗАКАЗА {заказНом, товарНом, количТовЗаказа} Первичный ключ: заказНом, товарНом Функциональные зависимости: заказНом, товарНом → количТовЗаказа ЗАКАЗЫ {заказНом, заказДата, ФИОПокуп, ЭлпочтаПокуп, адресПокуп, видДост, ценаДост, налогНДС, общСумма, заказСост} Первичный ключ: заказНом Функциональные зависимости: заказНом → заказДата заказНом → ФИОПокуп заказНом → ЭлпочтаПокуп заказНом → адресПокуп заказНом → видДост заказНом → ценаДост заказНом → налогНДС заказНом → общСумма заказНом → заказСост Рассмотрим отношение ТОВАРЫ. В этом отношении первичным ключом является атрибут «товарНом», и оно уже находится во второй нормальной форме. ТОВАРЫ {товарНом, типНом, товарНазв, товарОпис, товарЦена, товарРис, типНазв, колНаскладе} Первичный ключ: товарНом Функциональные зависимости: товарНом → типНом товарНазв товарНом → товарОпис товарНом → товарЦена товарНом → товарРис товарНом → колНаСкладе типНом → типНазв  Рис. 2. Схема отношений в виде 1NF 2-ой шаг: 2 NF → 3 NFНа 2-м шаге проектирования форма 2NF приводится к виду 3NF. Для этого проверяется следующее определение: Отношение R находится в третьей нормальной форме (3NF) в том и только в том случае, когда находится в 2NF, и каждый неключевой атрибут нетранзитивно зависит от первичного ключа. При проверке на транзитивность определяется существования зависимостей R.X → R.Z и R.Z → R.Y и отсутствие зависимости R.Z → R.X. То есть при отсутствии последнего требования мы имели бы «неинтересные транзитивные зависимости» в любом отношении, обладающем несколькими ключами. Имея в виду выше рассмотренные ФЗ отношения ТОВАРЫ, где атрибут типНазв напрямую не зависит от первичного ключа товарНом, а непосредственно зависит от его составного атрибута типНом, мы заключаем, что здесь имеется транзитивная ФЗ товарНом → типНом → типНазв. Другими словами, название типа товара на самом деле является характеристикой не товара, а типа товара, к которому он относится. В результате сказанного, мы приводим отношение Товары к третьей нормальной форме. Теперь можно произвести декомпозицию отношения ТОВАРЫ в два отношения ТИП ТОВАРА и ТОВАРЫ: ТИП ТОВАРА {типНом, типНазв} Первичный ключ: типНом Функциональные зависимости: типНом → типНазв ТОВАРЫ {товарНом, тип_Ном, товарНазв, товарОпис, товарЦена, товарРис, колНаСкладе} Первичный ключ: товарНом Функциональные зависимости: товарНом → типНом товарНазв товарНом → товарОпис товарНом → товарЦена товарНом → товарРис товарНом → колНаСкладе В результате из одного отношения (таблицы) ТОВАРЫ получается два отношения (две таблицы) ТИП ТОВАРА и ТОВАРЫ. Отношение ТОВАРЫ разделяется на отношения — ТИП ТОВАРА и ТОВАРЫ, где ТИП ТОВАРА — основная таблица, а ТОВАРЫ — подчиненная таблица. На практике третья нормальная форма схем отношений достаточна в большинстве случаев, и приведением к третьей нормальной форме процесс проектирования реляционных баз данных обычно заканчивается. Рис 3. Схема отношений в виде 3NF Техническое решениеПриложение базы данных было выполнена в среде Access 2003. Определив все взаимосвязи между отношениями, получим окончательную схему данных (структуру данных): Рис 4. Схема данных БД Из схемы видно, что между отношениями существуют связи:
Типы данных для каждого отношения приведены в следующих таблицах: а) для отношения «Тип товара» б) для отношения «Товары»   в) для отношения «Типы заказа» г) для отношения «Заказы»   Функциональные зависимости отношений и математическое понятие функциональной зависимости Функциональная зависимость атрибутов отношения напоминает понятие функциональной зависимости в математике. Но это не одно и то же. Для сравнения напомним математическое понятие функциональной зависимости: Определение 2. Функциональная зависимость (функция) - это тройка объектов  , где  - множество (область определения),  - множество (множество значений),  - правило, согласно которому каждому элементу  ставится в соответствие один и только один элемент  (правило функциональной зависимости). Функциональная зависимость обычно обозначается как  или  . Замечание. Правило может быть задано любым способом - в виде формулы (чаще всего), при помощи таблицы значений, при помощи графика, текстовым описанием и т.д. Функциональная зависимость атрибутов отношения тоже напоминает это определение. Действительно: В качестве области определения выступает домен, на котором определен атрибут (или декартово произведение доменов, если является множеством атрибутов) В качестве множества значений выступает домен, на котором определен атрибут (или декартово произведение доменов) Правило реализуется следующим алгоритмом - 1) по данному значению атрибута найти любой кортеж отношения, содержащий это значение, 2) значение атрибута в этом кортеже и будет значением функциональной зависимости, соответствующим данному . Определение функциональной зависимости в отношении гарантирует, что найденное значение не зависит от выбора кортежа, поэтому правило определено корректно. Отличие от математического понятия отношения состоит в том, что, если рассматривать математическое понятие функции, то для фиксированного значения соответствующее значение функции всегда одно и то же. Например, если задана функция  , то для значения  соответствующее значение  всегда будет равно 4. В противоположность этому в отношениях значение зависимого атрибута может принимать различные значения в различных состояниях базы данных. Например, атрибут ФАМ функционально зависит от атрибута Н_СОТР. Предположим, что сейчас сотрудник с табельным номером 1 имеет фамилию Иванов, т.е. при значении детерминанта равного 1, значение зависимого аргумента равно "Иванов". Но сотрудник может сменить фамилию, например на "Сидоров". Теперь при том же значении детерминанта, равного 1, значение зависимого аргумента равно "Сидоров". Таким образом, понятие функциональной зависимости атрибутов нельзя считать полностью эквивалентным математическому понятию функциональной зависимости, т.к. значение этой зависимости различны при разных состояниях отношения, и, самое главное, эти значения могут меняться непредсказуемо. Функциональная зависимость атрибутов утверждает лишь то, что для каждого конкретного состояния базы данных по значению одного атрибута (детерминанта) можно однозначно определить значение другого атрибута (зависимой части). Но конкретные значение зависимой части могут быть различны в различных состояниях базы данных. Определение 1. Функциональная зависимость В отношении R атрибут Y функционально зависит от атрибута X (X и Y могут быть составными) в том и только в том случае, если каждому значению X соответствует в точности одно значение Y: R.X (r) R.Y. Определение 2. Полная функциональная зависимость Функциональная зависимость R.X (r) R.Y называется полной, если атрибут Y не зависит функционально от любого точного подмножества X. Определение. Пусть r - отношение, R - его схема. Ключом K отношения r называется подмножество атрибутов {A1, A2, , Am} <= R, обладающее следующим свойством: для любых двух различных кортежей t1 и t2 из r существует A€K такое, что t1(A) != t2(A). Т.е. не существует двух кортежей, которые бы имели одно и то же значение на всех атрибутах из K. Таким образом, K-значение кортежа однозначно идентифицирует кортеж в r. (Из-за ограничений символьного набора, доступного при публикации статьи на сайте, мне пришлось воспользоваться следующими обозначениями: здесь и далее символ "<=" означает "является несобственным подмножеством", символ "€" "означает принадлежит множеству", а "!=" означает "не равно"). То же самое неформальным языком: ключом отношения называется набор атрибутов отношения, однозначно определяющий кортеж. Или еще проще: ключ - это набор столбцов таблицы, значения которых уникально определяют строку. Суперключ (super key) – сложный ключ с большим числом столбцов, чем необходимо для того, чтобы быть уникальным идентификатором. Это не всегда плохо, так как избыточность может оказаться полезной пользователю. «Первичный ключ (primary key) – это ключ, который может быть выбран АБД (администратором базы данных) для представления таблицы. В оригинальной реляционной модели Кодда таблица должна иметь первичный ключ. Однако большинство теоретиков реляционной модели признают факт, что ключ есть ключ, и логически здесь нет ничего особенного относительно первичного ключа. В SQL-машинах, тем не менее, первичный ключ может обладать особенными свойствами. Машины баз данных часто создают предопределённые соединения в специальных индексных структурах для первичного ключа. Первичный ключ также по умолчанию используется ссылочными ограничениями. Так могут быть другие специальные индексные структуры, которые поддерживают ограничения между таблицами. Таблицей, на которую ссылаются, и таблицей, которая ссылается. Вторичный ключ (secondary key) или ключ-кандидат (candidate key) – комбинация столбцов, отличная от комбинации, составляющей первичный ключ. Эти ключи могут сопровождаться уникальными (UNIQUE) и не пустыми (NOT NULL) ограничениями в SQL. Существует различие в SQL между уникальным ограничением (UNIQUE) и ограничением первичного ключа. Ограничение первичного ключа всегда NOT NULL у всех его столбцов, в то время как ограничение UNIQUE позволяет одно и только одно значение NULL в каждом столбце, если не наложено иного ограничения. Простой ключ (simple key) – ключ, содержащий только один атрибут. В идеале мы бы хотели самый короткий и самый простой из возможных типов данных, чтобы операции объединения (JOIN) производились быстрее. С этой точки зрения нам больше всего подходит тип INTEGER или другой числовой тип данных, который имеет аппаратную поддержку для операций над ним и сравнений. Сложный (compound) или составной ключ (composite key) – ключ, состоящий более чем из одного атрибута. Суррогатный ключ (surrogate key) – ключ создаваемый внутри базы данных, который не содержит в себе никакой информации. Суррогатный ключ часто используют вместо значимого сложного ключа, который является слишком громоздким, чтобы использоваться в реальной базе данных. Идея состоит в том, что система поддерживает его, и он никогда не показывается пользователю. Если дополнить множество  всеми вытекающими из него логическими следствиями, то получится замыкание множества функциональных зависимостей  . Для построения нужно иметь правила вывода логических следствий. Существует полное множество правил вывода, которые позволяют выводить логические следствия функциональных зависимостей, и являются надежными в том смысле, что с помощью этих правил нельзя получить функциональную зависимость, не являющуюся логическим следствием. Один из вариантов такого набора правил был сформулировам Армтсронгом (1974 г.) и по этой причине называется аксиомами Армстронга. Пусть задана некоторая схема отношения с множеством атрибутов  и множество функциональных зависимостей , связывающих атрибута из . Имеются следующие правила вывода:
Из указанных аксиом вытекает важное следствие. Если  , то функциональная зависимость  ( ) справедлива тогда и только тогда, когда справедлива каждая функциональная зависимость  ( ). Подход к решению проблемы поиска замыкания S+ множества FD S впервые предложил Вильям Армстронг1). Им был предложен набор правил вывода новых FD из существующих (эти правила обычно называют аксиомами Армстронга, хотя справедливость правил доказывается на основе определения FD). Обычно принято формулировать эти правила вывода в следующей форме. Пусть A, B и C являются (в общем случае, составными) атрибутами отношения r. Множества A, B и C могут иметь непустое пересечение. Для краткости будем обозначать через AB A UNION B. Тогда:
Истинность первой аксиомы Армстронга следует из того, что при B  A FD A B является тривиальной.Справедливость второй аксиомы докажем от противного. Предположим, что FD AC BC не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t1 и t2, такие, что t1 {AC} = t2 {AC} (a), но t1 {BC}  t2 {BC} (b) (здесь t {A} обозначает проекцию кортежа t на множество атрибутов A). По аксиоме рефлексивности из равенства (a) следует, что t1 {A} = t2 {A}. Поскольку имеется FD AB, должно соблюдаться равенство t1 {B} = t2 {B}. Тогда из неравенства (b) следует, что t1 {C} t2 {C}, что противоречит наличию тривиальной FD ACC. Следовательно, предположение об отсутствии FD ACBC не является верным, и справедливость второй аксиомы доказана.Аналогично докажем истинность третьей аксиомы Армстронга. Предположим, что FD A C не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t1 и t2, такие, что t1 {A} = t2 {A}, но t1 {C} t2 {C}. Но из наличия FD AB следует, что t1 {B} = t2 {B}, а потому из наличия FD BC следует, что t1 {C} = t2 {C}. Следовательно, предположение об отсутствии FD AC не является верным, и справедливость третьей аксиомы доказана.Можно доказать, что система правил вывода Армстронга полна и совершенна (sound and complete) в том смысле, что для данного множества FD S любая FD, потенциально выводимая из S, может быть выведена на основе аксиом Армстронга, и применение этих аксиом не может привести к выводу лишней FD. Тем не менее Дейт по практическим соображениям предложил расширить базовый набор правил вывода еще пятью правилами:
Пусть заданы отношение r, множество Z атрибутов этого отношения (подмножество заголовка r, или составной атрибут r) и некоторое множество FD S, выполняемых для r. Тогда замыканием Z над S называется наибольшее множество Z+ таких атрибутов Y отношения r, что FD Z Y входит в S+.Алгоритм вычисления Z+ очень прост. Один из его вариантов показан на рис. 6.2.  Рис. 6.2. Алгоритм построения замыкания атрибутов над заданным множеством FD Докажем корректность алгоритма по индукции. На нулевом шаге Z[0] = Z, FD Z Z[I], очевидно, принадлежит S+ (тривиальная FD "выводится" из любого множества FD). Пусть для некоторого K выполняется FD ZZ[K], и пусть мы нашли в S такую FD AB, что AZ[K]. Тогда можно представить Z[K] в виде AC, и, следовательно, выполняется FD ZAC. Но по правилу (8) мы имеем FD ZACB, т.е. FD Z(Z[K] UNION B) входит во множество S+, что переводит нас на следующий шаг индукции.Пусть для примера имеется отношение с заголовком {A, B, C, D, E, F} и заданным множеством FD S = {A D, ABE, BFE, CDF, EC}. Пусть требуется найти {AE}+ над S. На первом проходе тела цикла DO Z[1] равно AE. В теле цикла FOR EACH будут найдены FD AD и EC, и в конце цикла Z[1] станет равным ACDE. На втором проходе тела цикла DO при Z[2], равном ACDE, в теле цикла FOR EACH будет найдена FD CDF, и в конце цикла Z[2] станет равным ACDEF. Следующий проход тела цикла DO не изменит Z[3], и Z+ ({AE}+) будет равно ACDEF.Алгоритм построения замыкания множества атрибутов Z над заданным множеством FD S помогает легко установить, входит ли заданная FD Z B в замыкание S+. Очевидно, что необходимым и достаточным условием для этого является B Z+, т. е. вхождение составного атрибута B в замыкание Z2).Обобщив случаи так называемых аномалий модификации данных можно сформулировать определение аномалии модификации данных. Пусть A, B, K, X не пересекающиеся подмножества множества атрибутов таблицы R*. Пусть t некоторый кортеж совместимый с R*. R — множество кортежей находящихся в таблице R*. Аномалия модификации данных возникает в следующих случаях:
аждой нормальной форме соответствует определенный набор ограничений, и отношение находится в некоторой нормальной форме, если удовлетворяет свойственному ей набору ограничений. Примером может служить ограничение первой нормальной формы – значения всех атрибутов отношения атомарны1). Поскольку требование первой нормальной формы является базовым требованием классической реляционной модели данных, мы будем считать, что исходный набор отношений уже соответствует этому требованию. В теории реляционных баз данных обычно выделяется следующая последовательность нормальных форм:
Основные свойства нормальных форм состоят в следующем:
6.1.1. Вторая нормальная формаРассмотрим следующий пример схемы отношения: СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ (СОТР_НОМЕР, СОТР_ЗАРП, ОТД_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН) Первичный ключ: СОТР_НОМЕР, ПРО_НОМЕР Функциональные зависимости: СОТР_НОМЕР -> СОТР_ЗАРП СОТР_НОМЕР -> ОТД_НОМЕР ОТД_НОМЕР -> СОТР_ЗАРП СОТР_НОМЕР, ПРО_НОМЕР -> СОТР_ЗАДАН Как видно, хотя первичным ключом является составной атрибут СОТР_НОМЕР, ПРО_НОМЕР, атрибуты СОТР_ЗАРП и ОТД_НОМЕР функционально зависят от части первичного ключа, атрибута СОТР_НОМЕР. В результате мы не сможем вставить в отношение СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ кортеж, описывающий сотрудника, который еще не выполняет никакого проекта (первичный ключ не может содержать неопределенное значение). При удалении кортежа мы не только разрушаем связь данного сотрудника с данным проектом, но утрачиваем информацию о том, что он работает в некотором отделе. При переводе сотрудника в другой отдел мы будем вынуждены модифицировать все кортежи, описывающие этого сотрудника, или получим несогласованный результат. Такие неприятные явления называются аномалиями схемы отношения. Они устраняются путем нормализации. Определение 6. Вторая нормальная форма (в этом определении предполагается, что единственным ключом отношения является первичный ключ) Отношение R находится во второй нормальной форме (2NF) в том и только в том случае, когда находится в 1NF, и каждый неключевой атрибут полностью зависит от первичного ключа. Можно произвести следующую декомпозицию отношения СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ в два отношения СОТРУДНИКИ-ОТДЕЛЫ и СОТРУДНИКИ-ПРОЕКТЫ: СОТРУДНИКИ-ОТДЕЛЫ (СОТР_НОМЕР, СОТР_ЗАРП, ОТД_НОМЕР) Первичный ключ: СОТР_НОМЕР Функциональные зависимости: СОТР_НОМЕР -> СОТР_ЗАРП СОТР_НОМЕР -> ОТД_НОМЕР ОТД_НОМЕР -> СОТР_ЗАРП СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН) Первичный ключ: СОТР_НОМЕР, ПРО_НОМЕР Функциональные зависимости: СОТР_НОМЕР, ПРО_НОМЕР -> CОТР_ЗАДАН Каждое из этих двух отношений находится в 2NF, и в них устранены отмеченные выше аномалии (легко проверить, что все указанные операции выполняются без проблем). Если допустить наличие нескольких ключей, то определение 6 примет следующий вид: Определение 6~ Отношение R находится во второй нормальной форме (2NF) в том и только в том случае, когда оно находится в 1NF, и каждый неключевой атрибут полностью зависит от каждого ключа R. Здесь и далее мы не будем приводить примеры для отношений с несколькими ключами. Они слишком громоздки и относятся к ситуациям, редко встречающимся на практике. 6.1.2. Третья нормальная формаРассмотрим еще раз отношение СОТРУДНИКИ-ОТДЕЛЫ, находящееся в 2NF. Заметим, что функциональная зависимость СОТР_НОМЕР -> СОТР_ЗАРП является транзитивной; она является следствием функциональных зависимостей СОТР_НОМЕР -> ОТД_НОМЕР и ОТД_НОМЕР -> СОТР_ЗАРП. Другими словами, заработная плата сотрудника на самом деле является характеристикой не сотрудника, а отдела, в котором он работает (это не очень естественное предположение, но достаточное для примера). В результате мы не сможем занести в базу данных информацию, характеризующую заработную плату отдела, до тех пор, пока в этом отделе не появится хотя бы один сотрудник (первичный ключ не может содержать неопределенное значение). При удалении кортежа, описывающего последнего сотрудника данного отдела, мы лишимся информации о заработной плате отдела. Чтобы согласованным образом изменить заработную плату отдела, мы будем вынуждены предварительно найти все кортежи, описывающие сотрудников этого отдела. Т.е. в отношении СОТРУДИКИ-ОТДЕЛЫ по-прежнему существуют аномалии. Их можно устранить путем дальнейшей нормализации. Определение 7. Третья нормальная форма. (Снова определение дается в предположении существования единственного ключа.) Отношение R находится в третьей нормальной форме (3NF) в том и только в том случае, если находится в 2NF и каждый неключевой атрибут нетранзитивно зависит от первичного ключа. Можно произвести декомпозицию отношения СОТРУДНИКИ-ОТДЕЛЫ в два отношения СОТРУДНИКИ и ОТДЕЛЫ: СОТРУДНИКИ (СОТР_НОМЕР, ОТД_НОМЕР) Первичный ключ: СОТР_НОМЕР Функциональные зависимости: СОТР_НОМЕР -> ОТД_НОМЕР ОТДЕЛЫ (ОТД_НОМЕР, СОТР_ЗАРП) Первичный ключ: ОТД_НОМЕР Функциональные зависимости: ОТД_НОМЕР -> СОТР_ЗАРП Каждое из этих двух отношений находится в 3NF и свободно от отмеченных аномалий. Если отказаться от того ограничения, что отношение обладает единственным ключом, то определение 3NF примет следующую форму: Определение 7~ Отношение R находится в третьей нормальной форме (3NF) в том и только в том случае, если находится в 1NF, и каждый неключевой атрибут не является транзитивно зависимым от какого-либо ключа R. На практике третья нормальная форма схем отношений достаточна в большинстве случаев, и приведением к третьей нормальной форме процесс проектирования реляционной базы данных обычно заканчивается. Однако иногда полезно продолжить процесс нормализации. 6.1.3. Нормальная форма Бойса-КоддаРассмотрим следующий пример схемы отношения: СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, СОТР_ИМЯ, ПРО_НОМЕР, СОТР_ЗАДАН) Возможные ключи: СОТР_НОМЕР, ПРО_НОМЕР СОТР_ИМЯ, ПРО_НОМЕР Функциональные зависимости: СОТР_НОМЕР -> CОТР_ИМЯ СОТР_НОМЕР -> ПРО_НОМЕР СОТР_ИМЯ -> CОТР_НОМЕР СОТР_ИМЯ -> ПРО_НОМЕР СОТР_НОМЕР, ПРО_НОМЕР -> CОТР_ЗАДАН СОТР_ИМЯ, ПРО_НОМЕР -> CОТР_ЗАДАН В этом примере мы предполагаем, что личность сотрудника полностью определяется как его номером, так и именем (это снова не очень жизненное предположение, но достаточное для примера). В соответствии с определением 7~ отношение СОТРУДНИКИ-ПРОЕКТЫ находится в 3NF. Однако тот факт, что имеются функциональные зависимости атрибутов отношения от атрибута, являющегося частью первичного ключа, приводит к аномалиям. Например, для того, чтобы изменить имя сотрудника с данным номером согласованным образом, нам потребуется модифицировать все кортежи, включающие его номер. Определение 8. Детерминант Детерминант - любой атрибут, от которого полностью функционально зависит некоторый другой атрибут. Определение 9. Нормальная форма Бойса-Кодда Отношение R находится в нормальной форме Бойса-Кодда (BCNF) в том и только в том случае, если каждый детерминант является возможным ключом. Очевидно, что это требование не выполнено для отношения СОТРУДНИКИ-ПРОЕКТЫ. Можно произвести его декомпозицию к отношениям СОТРУДНИКИ и СОТРУДНИКИ-ПРОЕКТЫ: СОТРУДНИКИ (СОТР_НОМЕР, СОТР_ИМЯ) Возможные ключи: СОТР_НОМЕР СОТР_ИМЯ Функциональные зависимости: СОТР_НОМЕР -> CОТР_ИМЯ СОТР_ИМЯ -> СОТР_НОМЕР СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН) Возможный ключ: СОТР_НОМЕР, ПРО_НОМЕР Функциональные зависимости: СОТР_НОМЕР, ПРО_НОМЕР -> CОТР_ЗАДАН Возможна альтернативная декомпозиция, если выбрать за основу СОТР_ИМЯ. В обоих случаях получаемые отношения СОТРУДНИКИ и СОТРУДНИКИ-ПРОЕКТЫ находятся в BCNF, и им не свойственны отмеченные аномалии. 6.1.4. Четвертая нормальная формаРассмотрим пример следующей схемы отношения: ПРОЕКТЫ (ПРО_НОМЕР,ПРО_СОТР, ПРО_ЗАДАН) Отношение ПРОЕКТЫ содержит номера проектов, для каждого проекта список сотрудников, которые могут выполнять проект, и список заданий, предусматриваемых проектом. Сотрудники могут участвовать в нескольких проектах, и разные проекты могут включать одинаковые задания. Каждый кортеж отношения связывает некоторый проект с сотрудником, участвующим в этом проекте, и заданием, который сотрудник выполняет в рамках данного проекта (мы предполагаем, что любой сотрудник, участвующий в проекте, выполняет все задания, предусмотренные этим проектом). По причине сформулированных выше условий единственным возможным ключем отношения является составной атрибут ПРО_НОМЕР, ПРО_СОТР, ПРО_ЗАДАН, и нет никаких других детерминантов. Следовательно, отношение ПРОЕКТЫ находится в BCNF. Но при этом оно обладает недостатками: если, например, некоторый сотрудник присоединяется к данному проекту, необходимо вставить в отношение ПРОЕКТЫ столько кортежей, сколько заданий в нем предусмотрено. Определение 10. Многозначные зависимости В отношении R (A, B, C) существует многозначная зависимость R.A -> -> R.B в том и только в том случае, если множество значений B, соответствующее паре значений A и C, зависит только от A и не зависит от С. В отношении ПРОЕКТЫ существуют следующие две многозначные зависимости: ПРО_НОМЕР -> -> ПРО_СОТР ПРО_НОМЕР -> -> ПРО_ЗАДАН Легко показать, что в общем случае в отношении R (A, B, C) существует многозначная зависимость R.A -> -> R.B в том и только в том случае, когда существует многозначная зависимость R.A -> -> R.C. Дальнейшая нормализация отношений, подобных отношению ПРОЕКТЫ, основывается на следующей теореме: Теорема Фейджина Отношение R (A, B, C) можно спроецировать без потерь в отношения R1 (A, B) и R2 (A, C) в том и только в том случае, когда существует MVD A -> -> B | C. Под проецированием без потерь понимается такой способ декомпозиции отношения, при котором исходное отношение полностью и без избыточности восстанавливается путем естественного соединения полученных отношений. Определение 11. Четвертая нормальная форма Отношение R находится в четвертой нормальной форме (4NF) в том и только в том случае, если в случае существования многозначной зависимости A -> -> B все остальные атрибуты R функционально зависят от A. В нашем примере можно произвести декомпозицию отношения ПРОЕКТЫ в два отношения ПРОЕКТЫ-СОТРУДНИКИ и ПРОЕКТЫ-ЗАДАНИЯ: ПРОЕКТЫ-СОТРУДНИКИ (ПРО_НОМЕР, ПРО_СОТР) ПРОЕКТЫ-ЗАДАНИЯ (ПРО_НОМЕР, ПРО_ЗАДАН) Оба эти отношения находятся в 4NF и свободны от отмеченных аномалий. 6.1.5. Пятая нормальная формаВо всех рассмотренных до этого момента нормализациях производилась декомпозиция одного отношения в два. Иногда это сделать не удается, но возможна декомпозиция в большее число отношений, каждое из которых обладает лучшими свойствами. Рассмотрим, например, отношение СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ (СОТР_НОМЕР, ОТД_НОМЕР, ПРО_НОМЕР) Предположим, что один и тот же сотрудник может работать в нескольких отделах и работать в каждом отделе над несколькими проектами. Первичным ключем этого отношения является полная совокупность его атрибутов, отсутствуют функциональные и многозначные зависимости. Поэтому отношение находится в 4NF. Однако в нем могут существовать аномалии, которые можно устранить путем декомпозиции в три отношения. Определение 12. Зависимость соединения Отношение R (X, Y, ..., Z) удовлетворяет зависимости соединения * (X, Y, ..., Z) в том и только в том случае, когда R восстанавливается без потерь путем соединения своих проекций на X, Y, ..., Z. Определение 13. Пятая нормальная форма Отношение R находится в пятой нормальной форме (нормальной форме проекции-соединения - PJ/NF) в том и только в том случае, когда любая зависимость соединения в R следует из существования некоторого возможного ключа в R. Введем следующие имена составных атрибутов: СО = {СОТР_НОМЕР, ОТД_НОМЕР} СП = {СОТР_НОМЕР, ПРО_НОМЕР} ОП = {ОТД_НОМЕР, ПРО_НОМЕР} Предположим, что в отношении СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ существует зависимость соединения: * (СО, СП, ОП) На примерах легко показать, что при вставках и удалениях кортежей могут возникнуть проблемы. Их можно устранить путем декомпозиции исходного отношения в три новых отношения: СОТРУДНИКИ-ОТДЕЛЫ (СОТР_НОМЕР, ОТД_НОМЕР) СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, ПРО_НОМЕР) ОТДЕЛЫ-ПРОЕКТЫ (ОТД_НОМЕР, ПРО_НОМЕР) Пятая нормальная форма - это последняя нормальная форма, которую можно получить путем декомпозиции. Ее условия достаточно нетривиальны, и на практике 5NF не используется. Заметим, что зависимость соединения является обобщением как многозначной зависимости, так и функциональной зависимости. |
, то 
логически следует из 
и 
, то 
логически следует из 
, то 
. 
