Ответы к экзамену по БД, страница 6

Определение транзитивной зависимости и 3НФ. Алгоритм приведения к 3НФ.Нормальная форма Бойса-Кодда (НФБК). Определение иалгоритм приведения к НФБК. Характеристика отношенияв 3НФ и в НФБК. Примеры.Определение 3НФСогласно определению Кодда, таблица находится в 3NF тогда и только тогда, когда выполняютсяследующие условия:• Отношение R (таблица) находится во второй нормальной форме;• Каждый непервичный атрибут R находится в нетранзитивной (то есть прямой) зависимости откаждого ключа R.Непервичный (неключевой) атрибут R — это атрибут, который не принадлежит ни одному из возможных (альтернативных) ключей R.Транзитивная зависимость — это функциональная зависимость, при которой X → Z (X определяет Z)не напрямую, а посредством отношения X → Y и Y → Z (отношение Y → X не является обязательнымусловием).Определение 3NF, эквивалентное определению Кодда, но по-другому сформулированное, дал Карло Заниоло.

Согласно ему, таблица находится в 3НФ тогда и только тогда, когда для каждой из еефункциональных зависимостей X → A выполняется хотя бы одно из следующих условий:• Х содержит А (то есть X → A — тривиальная функциональная зависимость)• Х — суперключ• А — первичный атрибут (то есть А входит в состав альтернативного ключа).Определение Заниоло четко определяет разницу между 3NF и более строгой нормальной формойБойса-Кодда (НФБК): НФБК исключает третье условие (А — первичный атрибут).16.2Алгоритм приведения к 3НФНиже приведен алгоритм, с помощью которого может быть выполнена декомпозиция без потерь произвольной переменной отношения R (с сохранением функциональных зависимостей) на множество Dпроекций, находящихся в ЗНФ (2НФ получаем в процессе приведения).

Предположим, что дано множество функциональных зависимостей S, удовлетворяемых в переменной отношения R. В таком случаедекомпозиция может быть выполнена, как показано далее.1. Инициализировать D значением пустого множества.2. Пусть I является неприводимым покрытием для S.3. Пусть х — множество атрибутов, присутствующих в левой части некоторой функ циональнойзависимости X → Y из I.4. Пусть полным множеством функциональных зависимостей из I с левой частью X является X →Y1 , X → Y2 , ..., X → Yn .5. Пусть объединением Y1 , Y2 , ..., Yn является z.6.

Заменить множество D объединением множества D и проекции R по X и z.7. Повторить шаги 4—6 для каждого отдельного X. Таким образом получена форма 2НФ.8. Пусть A1 , A2 , ..., An являются теми атрибутами R (если только они вообще имеются), которыевсе еще не охвачены этим алгоритмом (т.е. не включены ни в одну переменную отношения из D);заменить множество D объединением множе ства D и проекции R по A1 , A2 , ..., An .159. Если ни одна переменная отношения из D не включает некоторый потенциальный ключ переменной отношения R, заменить D объединением D и проекции R по рас сматриваемому потенциальному ключу переменной отношения R.16.3Нормальная форма Бойса-КоддаОтношение находится в BCNF тогда и только тогда, когда каждая его нетривиальная и неприводимаяслева функциональная зависимость имеет в качестве своего детерминанта некоторый потенциальныйключ.

Менее формально, переменная отношения находится в нормальной форме Бойса-Кодда тогда итолько тогда, когда детерминанты всех ее функциональных зависимостей являются потенциальнымиключами.Определение. Пусть R является переменной отношения, а X и Y — произвольными подмножествами множества атрибутов переменной отношения R. Y функционально зависимо от X тогдаи только тогда, когда для любого допустимого значения переменной отношения R, если два кортежа переменной отношения R совпадают по значению X, они также совпадают и по значению Y.Подмножество X называют детерминантом, а Y — зависимой частью.Функциональная зависимость тривиальна тогда и только тогда, когда ее правая (зависимая) частьявляется подмножеством ее левой части (детерминанта). Ситуация, когда отношение будет находитьсяв 3NF, но не в BCNF, возникает, например, при условии, что отношение имеет два (или более) потенциальных ключа, которые являются составными и имеют общий атрибут.

На практике такая ситуациявстречается достаточно редко, для всех прочих отношений 3NF и BCNF эквивалентны.16.4Алгоритм приведения к НФБКАлгоритм, состоящий из четырех шагов, с помощью которого произвольная переменная отношения Rможет быть подвергнута декомпозиции без потерь на множество D проекций НФБК (но при этом необязательно сохраняются все зависимости).1. Инициализировать множество D так, чтобы в нем содержалась только переменная отношения R.2.

Для каждой переменной отношения τ из множества D, не находящейся в НФБК, выполнить шаги3 и 4.3. Пусть X → Y является функциональной зависимостью для τ , которая нарушает требованияНФБК.4. Заменить переменную отношения τ из множества D двумя ее проекциями: по атрибутам X и Y ипо всем атрибутам, кроме тех, что находятся в Y.16.5Пример 3НФ и НФБКПредположим, создаётся таблица бронирования для теннисных кортов на день: (Номер корта, Времяначала, Время окончания, Тариф, Член клуба). Тариф зависит от выбранного корта и членства в клубе. Таким образом, возможны следующие составные первичные ключи: (Номер корта, Время начала),(Номер корта, Время окончания), (Тариф, Время начала), (Тариф, Время окончания).Таблица соответствует второй и третьей нормальной форме, так как атрибуты, не входящие в состав первичного ключа, зависят от составного первичного ключа целиком (2NF) и нет транзитивныхзависимостей (3NF).Тем не менее, существует функциональная зависимость тарифа от номера корта.

То есть, по ошибкеможно нарушить логическую целостность и, например, приписать тариф Premium для первого корта,хотя тариф Premium может относиться только ко второму корту.Можно улучшить структуру, разбив таблицу на две: (Номер корта, Время начала, Время окончания,Член клуба) и (Тариф, Номер корта, Член клуба).

Данное отношение будет соответствовать НФБК.1617Многозначные зависимости (МЗ). Определение. Свойства иаксиомы МЗ. Четвертая нормальная форма (4НФ) отношения. Характеристика отношения в 4НФ.17.1Определение многозначных зависимостейОпределение. Пусть R - переменная отношения, а А, B и C являются произвольными подмножествами множества атрибутов переменной отношения R. Тогда подмножество в многозначнозависит от подмножества А, что символически выражается следующей: →→ (читается как “Амногозначно определяет B”), тогда и только тогда, когда в каждом допустимом значении R множество значений B, соответствующее заданной паре значений А, С, зависит только от значенияА и не зависит от значения С.Многозначная зависимость A →→ B называется тривиальной, если выполняется хотя бы одно изусловий:1.2.3.4.Множество A является надмножеством B;B⊆AОбъединение A и B образует весь заголовок отношения.A∪B =R17.2Свойства и аксиомы МЗ17.2.1Связные парыФеджин показал, что многозначные зависимости образуют связные пары (в обозначениях определения):(A →→ B) ⇔ (A →→ C) .Поэтому их часто представляют вместе в символической записи:A →→ B|C17.2.2Функциональные зависимостиВсякая функциональная зависимость является многозначной.

Другими словами, функциональная зависимость - это многозначная зависимость, в которой множество зависимых значений, соответствующее заданному значению детерминанта, всегда имеет единичную мощность.(A → B) ⇒ (A →→ B)17.2.3АксиомыПусть у нас есть отношение r (R) и множества атрибутов A, B, C, D ⊆ R. Для сокращения записивместо X ∪ Y будем писать просто XY .Группа 1: базовые правила.1.2.3.4.5.6.7.Дополнение(A ∪ B ∪ C = R) ∧ (B ∩ C ⊆ A) ⇒ ((A →→ B) ⇔ (A →→ C))Транзитивность(A →→ B) ∧ (B →→ C) ⇒ (A →→ C\B)Рефлексивность(B ⊆ A) ⇒ (A →→ B)Приращение178. (A →→ B) ∧ (C ⊆ D) ⇒ (AD →→ BC)Группа 2: выводятся несколько дополнительных правил, упрощающих задачу вывода многозначных зависимостей.1.2.3.4.5.6.Псевдотранзитивность(A →→ B) ∧ (BC →→ D) ⇒ (AC →→ D\BC)Объединение(A →→ B) ∧ (A →→ C) ⇒ (A →→ BC)Декомпозиция(A →→ BC) ⇒ (A →→ B ∩ C) ∧ (A →→ B\C) ∧ (A →→ C\B)Группа 3: устанавливается связь между функциональными и многозначными зависимостями.1.2.3.4.Репликация (копирование)(A → B) ⇒ (A →→ B)Слияние(A →→ B) ∧ (C → D) ∧ (D ⊆ B) ∧ (B ∩ C = nothing) ⇒ (A → D)Группа 4: для функциональных зависимостей, выводятся из вышеприведенных правил.

(A →→ B)∧(AB → C) ⇒ (A → C\B)Правила вывода Армстронга вместе с изложенными здесь правилами групп 1 и 3 образуют полный(используя их, можно вывести все остальные многозначные зависимости, подразумеваемые данным ихмножеством) и надежный («лишних» многозначных зависимостей вывести нельзя; выведенная многозначная зависимость справедлива везде, где справедливо то множество многозначных зависимостей,из которого она была выведена) набор правил вывода многозначных зависимостей.Теорема (Феджина). Пусть дано отношение r (A, B, C).

Отношение r будет равно соединению егопроекций r [A, B] и r [A, C] тогда и только тогда, когда для отношения r выполняется нетривиальнаямногозначная зависимость A →→ B|C.(r (A, B, C) = r [A, B] JOIN r [A, C]) ⇔ (A →→ B|C)17.3Четвертая нормальная форма отношенияОпределение. Отношение находится в 4NF, если оно находится в НФБК и не содержит нетривиальных многозначных зависимостей. То есть все многозначные зависимости являются, по сути,функциональными зависимостями от ключей отношения.17.4ПримерПредположим, что рестораны производят разные виды пиццы, а службы доставки ресторанов работают только в определенных районах города.

Составной ключ таблицы такого отношения включает триполя: {Ресторан, Вид пиццы, Район доставки}.Такая таблица не соответствует 4NF, так как существует многозначная зависимость:{Ресторан} →→ {Вид пиццы}{Ресторан} →→ {Район доставки}То есть, например, при добавлении нового вида пиццы придется внести по одной новой записи длякаждого района доставки. Возможна логическая аномалия, при которой определенному виду пиццыбудут соответствовать лишь некоторые районы доставки из обслуживаемых рестораном районов.18Для предотвращения аномалии нужно разбить многозначную зависимость — разместить независимыефакты в разных таблицах. В данном примере — {Ресторан, Вид пиццы} и {Ресторан, Район доставки}.191818.118. Общая характеристика языка SQL.