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

В состав теоретикомножественных операций входят операции:••••объединения отношений UNION ;пересечения отношений INTERSECT ;взятия разности отношений MINUS ;взятия декартова произведения отношений TIMES.Специальные реляционные операции включают:••••ограничение отношения WHERE, RESTRICT ;проекцию отношения PROJECT ;соединение отношений JOIN ;деление отношений DIVIDE BY.Кроме того, в состав алгебры включается операция присваивания, позволяющая сохранить в базеданных результаты вычисления алгебраических выражений, и операция переименования RENAMEатрибутов, дающая возможность корректно сформировать заголовок (схему) результирующего отношения.811.3Приоритет операцийRENAMEWHEREPROJECTTIMESJOININTERSECTDIVIDE BYUNIONMINUS43322 .2211912Нормализация отношений, назначение и общая характеристика шагов нормализации. Понятие канонической схемы.Примеры.12.1Понятие нормализацииГоворят, что переменная отношения находится в определенной нормальной форме, если она удовлетворяет заданному набору условий.

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

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

е. декомпозиции отношения, находящегося в предыдущей нормальной форме, на два или более отношений, которые удовлетворяюттребованиям следующей нормальной формы.12.2Шаги нормализацииВ теории реляционных баз данных обычно выделяется следующая последовательность нормальныхформ:••••••12.3первая нормальная форма (1NF);вторая нормальная форма (2NF);третья нормальная форма (3NF);нормальная форма Бойса-Кодда (BCNF);четвертая нормальная форма (4NF);пятая нормальная форма, или нормальная форма проекции-соединения (5NF или PJ/NF).Понятие канонической схемыКаноническая схема - модель данных, с помощью которой представляются существующие в реальноммире структуры данных, вне зависимости от конкретных приложений или аппаратных средств, используемых для представления данных и их эксплуатации, являя собой простейшую форму представленияиз возможных.

.101313.11-ая нормальная форма (1НФ) отношения. Определение. Метод приведения отношения к 1НФ.Определение 1НФТаблица находится в первой нормальной форме, если каждый её атрибут атомарен, то есть можетсодержать только одно значение. Таким образом, не существует 1NF таблицы, в полях которых могутхраниться списки значений.Замечание. В реляционной модели отношение всегда находится в 1 (или более высокой) нормальной форме в том смысле, что иные отношения не рассматриваются в реляционной модели.

То естьсамо определение понятия отношение заведомо подразумевает наличие 1NF.Таблица удовлетворяет 1НФ, строго говоря, только при выполнении следующих условий:1.2.3.4.Отсутствует установленный порядок следования строк сверху-вниз.Отсутствует установленный порядок следования столбцов слева-направо.Отсутствуют дублирующиеся строки.Каждое пересечение строки и столба содержит строго одно значения из возможного домена (иничего более).5.

Все поля стандартны (то есть, у них нет скрытых компонент, таких как номер строки, номеробъекта и т.п.)13.2Атомарность атрибутовАтрибут атомарен, если его значение теряет смысл при любом разбиении на части или переупорядочивании. И наоборот, если какой-либо способ разбиения на части не лишает атрибут смысла, то атрибутнеатомарен. Одно и то же значение может быть атомарным или неатомарным в зависимости от смыслаэтого значения.13.3Метод приведения к 1НФДля приведения таблицы к 1NF обычно требуется разбить таблицу на несколько отдельных таблиц. .111414.1Понятие функциональной зависимости (ФЗ) в отношениях.Свойства и аксиомы ФЗ. Примеры.ОпределенияФункциональная зависимость — это связь типа “многие к одному” между двумя множествами атрибутов заданной переменной отношения (она представляет собой наиболее широко распространенныйи важный вид ограничения целостности).Определение (значение переменной отношения в определенный момент).

Пусть R является отношением, а X и Y произвольными подмножествами множества атрибутов отношения r. Тогда Yфункционально зависимо от х, что в символическом виде записывается как X → Y (X функционально определяет Y) тогда и только тогда, когда каждое значение множества х отношения r связаноточно с одним значением множества Y отношения r. Иначе говоря, если два кортежа отношенияR совпадают по значению X, они совпадают и по значению Y.Формально:r (R) , A ⊆ R, B ⊆ R (A → B) ⇔ ((∀t1 , t2 ∈ r : t1 (A) = t2 (A)) ⇒ (t1 (B) = t2 (B)))Определение (множество всех значений, которые принимает переменная отношения).

Пусть R является переменной отношения, а X и Y — произвольными подмножествами множества атрибутовпеременной отношения R. Тогда Y функционально зависимо от X, (что в символическом виде записывается как X → Y ) тогда и только тогда, когда для любого допустимого значения переменнойотношения R каждое значение множества X отношения R связано точно с одним значением множества Y отношения R. Иначе говоря, для любого допустимого значения переменной отношения R,если два кортежа переменной отношения R совпадают по значению X, они также совпадают и позначению Y.Отметим, что если Х является потенциальным ключом переменной отношения R, то все атрибутыY переменной отношения R должны обязательно быть функционально зависимыми от Х.Каждая переменная отношения обязательно удовлетворяет некоторым тривиальным функциональным зависимостям; причем функциональная зависимость тривиальна тогда и только тогда, когда ееправая (зависимая) часть является подмножеством ее левой части (детерминанта).Левую и правую части символической записи функциональной зависимости иногда называют, соответственно, детерминантом и зависимой частью.

Как говорится в определении, детерминант изависимая часть являются множествами атрибутов. Когда множество содержит только один атрибут,оно называется одноэлементным множеством.14.2Замыкания множества зависимостейОдни функциональные зависимости могут подразумевать другие функциональные зависимости. Например,(A → B) ∧ (B → C) ⇒ (A → C)Множество S + всех функциональных зависимостей, которые подразумеваются данным множествомфункциональных зависимостей S называется замыканием множества S.14.3Замыкания множества атрибутовПусть Z - некоторое множество атрибутов отношения r, а S - множество функциональных зависимостейэтого отношения.12Замыканием Z + множества атрибутов Z в пределах S называется такое множество всех атрибутов Aiотношения r, что функциональная зависимость Z → Ai является членом замыкания S + .r (R) , S, Z ⊆ R, Ai ⊆ R, i = 1, nZ + = Ai : (Z → Ai ) ∈ S +14.4Аксиомы АрмстронгаПусть A, B, C, D - произвольные подмножества множества атрибутов заданной переменной отношенияR.1.2.3.4.5.6.7.8.Рефлексивность.

Если B ⊂ A, то A → BДополнение. Если A → B, то AC → BCТранзитивность. Если A → B, B → C, то A → CСамоопределение. A → AДекомпозиция. Если A → BC, то A → B, A → CОбъединение. Если A → B, A → C, то A → BCКомпозицияи. Если A → B, C → D, то AC → BDОбщая теорема объединения. Если A → B, C → D, то A ∪ (C − B) → BDТеорема (Хита). Пусть R{А, υ, С} является переменной отношения, где А, υ и C множестваатрибутов этой переменной отношения.

Если R удовлетворяет функциональной зависимости A →C то R равна соединению ее проекций по атрибутам {А,B} И {А,С}..131515.12-ая нормальная форма (2НФ) отношения. Определение полной функциональной зависимости и 2НФ. Характеристикаотношения во 2НФ. Алгоритм приведения ко 2НФ.

ТеоремаХита. Примеры.Определение 2НФТаблица находится во второй нормальной форме, если она находится в первой нормальной форме, ипри этом любой её атрибут, не входящий в состав возможного ключа, функционально полно зависитот каждого возможного ключа. Функционально полная зависимость означает, что атрибут функционально зависит от всего составного ключа, но при этом не находится в функциональной зависимостиот какой-либо из входящих в него атрибутов (частей).Другими словами: в 2NF нет неключевых атрибутов, зависящих от части составного ключа (плюсвыполняются условия 1NF).15.2Теорема ХитаТеорема (Хита). Пусть R{А, υ, С} является переменной отношения, где А, υ и C множестваатрибутов этой переменной отношения.

Если R удовлетворяет функциональной зависимости A →C то R равна соединению ее проекций по атрибутам {А,B} И {А,С}.15.3Алгоритм приведения к 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 .9. Если ни одна переменная отношения из D не включает некоторый потенциальный ключ переменной отношения R, заменить D объединением D и проекции R по рас сматриваемому потенциальному ключу переменной отношения R..141616.13-я нормальная форма (3НФ) отношения.