Билеты и ответы, страница 5

R₁ R_{2 =} {(r, q) | r  R₁  q  R₂}. В результирующей таблице будет r*q записей и n + m атрибутов, т.е. получим отношение, которое характеризует все возможные комбинации между элементами различных множеств.

Декартово произведение позволяет связать разные объекты, объединить информацию, описывающую разные типы сущностей или объектов предметной области. Например, если мы имеем отдельную таблицу со списком фирм-производителей, и отдельную таблицу со списком всевозможных товаров, то декартово произведение этих двух таблиц позволит построить всевозможные пары “товар-производитель”:

Таблица “Фирмы-производители”

Производитель	Адрес
Вологда Домик в деревне	Ул.1 Ул.2

Таблица “Товары”

Товар

Кефир Молоко

Результирующая таблица “Товар-производитель”

Товар	Производитель	Адрес
Кефир Молоко Кефир Молоко	Вологда Вологда Домик в деревне Домик в деревне	Ул.1 Ул.1 Ул.2 Ул.2

Рис. 4.6. Декартово произведение двух таблиц

1. ЯМД, основанный на реляционной алгебре. Специальные операции реляционной алгебры. Полная система операций реляционной алгебры. Примеры.

Реляционная алгебра – это теоретический язык операций, позволяющих создавать на основе одного или нескольких отношений другое отношение без изменения исходных отношений. Оба операнда и результат являются отношениями, потому результаты одной операции могут применяться в другой операции – свойство замкнутости. Оно означает, что применение любого количества операций реляционной алгебры не приводит к созданию иных объектов, кроме отношений.

Реляционное исчисление эквивалентно реляционной алгебре. Реляционное исчисление в отличие от реляционной алгебры непроцедурный язык, и в основном используется для оценки избирательной мощности реляционных языков. Язык называется реляционно-полным, если он позволяет получить любое отношение, которое можно получить с помощью реляционного исчисления.

Первоначально Кодд предложил восемь операций, но впоследствии к ним были добавлены и некоторые другие. Пять основных операций реляционной алгебры, а именно выборка (selection), проекция (projection), декартово произведение (Cartesian product), объединение (union) и разность множеств (set difference), выполняют большинство действий по извлечению данных. На основании пяти основных операций можно также вывести дополнительные операции, такие как операции соединения (join), пересечения (intersection) и деления (division).

Специальные операции реляционной алгебры

Проекция - операция, заключающаяся в удалении некоторых столбцов в отношении. Среди оставшихся записей с меньшим числом атрибутов может проводиться удаление дубликатов (одинаковых записей). Смысл операции проекции заключается в выделении из отношения той информации, которая нам нужна. Например, проекция отношения “Товары” по атрибутам “Производитель” и “Адрес” даст нам список всех поставщиков с их адресами:

Производитель	Адрес
Вологда Домик в деревне	Ул.1 Ул.2

Рис.4.7. Проекция таблицы “Товары” для получения списка фирм-производителей

Селекция - операция, заключающаяся в удалении некоторых записей в отношении на основе некоторого условия. Условие определяться как логическое выражение над значениями атрибутов. В этом логическом выражении можно использовать операции “больше”, “меньше”, “равно”, “принадлежит множеству” и т.д. Операция селекции, как и операция проекции, позволяет выделить из отношения ту информацию, которая нам нужна. Но, в отличие от операции проекции, выбираются подходящие записи, а не интересующие нас атрибуты.

Например, селекция отношения “Товары” по условию “атрибут “Производитель” есть “Вологда”” позволит нам получить список всех товаров, поставляемых данной фирмой:

Товар	Производитель	Адрес
Кефир Молоко Сметана	Вологда Вологда Вологда	Ул.1 Ул.1 Ул.1

Рис.4.8. Селекция таблицы “Товары” по условию

Про тета-соединение и деление – см. лекции.

1. Нормализация отношений, назначение и общая характеристика шагов нормализации. Понятие канонической схемы. Примеры.

Процесс преобразования базы данных к виду, отвечающему нормальным формам, называется нормализацией. Нормализация позволяет обезопасить базу данных от логических и структурных проблем, называемых аномалиями данных. К примеру, когда существует несколько одинаковых записей в таблице, существует риск нарушения целостности данных при обновлении таблицы. Таблица, прошедшая нормализацию, менее подвержена таким проблемам, т.к. ее структура предполагает определение связей между данными, что исключает необходимость в существовании записей с повторяющейся информацией.

1. 1-ая нормальная форма (1НФ) отношения.Определение. Метод приведения отношения к 1НФ.

Первая нормальная форма (1NF)

Таблица находится в первой нормальной форме, если каждый её атрибут атомарен. Под выражением «атрибут атомарен» понимается, что атрибут может содержать только одно значение. Таким образом, не соответствуют 1NF таблицы, в полях которых могут храниться списки значений. Для приведения таблицы к 1NF обычно требуется разбить таблицу на несколько отдельных таблиц.

Замечание: в реляционной модели отношение всегда находится в 1 (или более высокой) нормальной форме в том смысле, что иные отношения не рассматриваются в реляционной модели. То есть само определение понятия отношение заведомо подразумевает наличие 1NF.

Пример приведения таблицы к первой нормальной форме

Сотрудник	Номер телефона
Иванов И. И.	283-56-82
Иванов И. И.	390-57-34
Петров П. Ю.	708-62-34

Исходная, ненормализованная, таблица:

Сотрудник	Номер телефона
Иванов И. И.	283-56-82 390-57-34
Петров П. Ю.	708-62-34

Таблица, приведённая к 1NF:

1. Понятие функциональной зависимости (ФЗ) в отношениях. Свойства и аксиомы ФЗ. Примеры.

Функциональные зависимости.

Реляционная база данных содержит как структурную, так и семантическую информацию. Структура базы данных определяется числом и видом включенных в нее отношений, и связями типа "один ко многим", существующими между кортежами этих отношений. Семантическая часть описывает множество функциональных зависимостей, существующих между атрибутами этих отношений. Дадим определение функциональной зависимости.

Определение: Если даны два атрибута X и Y некоторого отношения, то говорят, что Y функционально зависит от X, если в любой момент времени каждому значению X соответствует ровно одно значение Y. Функциональная зависимость обозначается X -> Y. Отметим, что X и Y могут представлять собой не только единичные атрибуты, но и группы, составленные из нескольких атрибутов одного отношения. Можно сказать, что функциональные зависимости представляют собой связи типа "один ко многим", существующие внутри отношения.

1. 2-аянормальная форма (2НФ) отношения. Определение полной функциональной зависимости и 2НФ. Характеристика отношения во 2НФ. Алгоритм приведения ко 2НФ. Теорема Хита. Примеры.

Понятие полной функциональной зависимости.

Определение: неключевой атрибут функционально полно зависит от составного ключа если он функционально зависит от всего ключа в целом, но не находится в функциональной зависимости от какого-либо из входящих в него атрибутов. 

Определение: избыточная функциональная зависимость - зависимость, заключающая в себе такую информацию, которая может быть получена на основе других зависимостей, имеющихся в базе данных.

2NF - вторая нормальная форма.

Определение второй нормальной формы: отношение находится во 2НФ, если оно находится в 1НФ и каждый неключевой атрибут функционально полно зависит от ключа.

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

Условие обратимости требует, чтобы декомпозиция сохраняла эквивалентность схем при замене одной схемы на другую, т.е. в результирующих отношениях:

1)не должны появляться ранее отсутствовавшие кортежи;

2)на отношениях новой схемы должно выполняться исходное множество функциональных зависимостей.

Теорема Хита

Пусть дано отношение .

Если r удовлетворяет функциональной зависимости , то оно равно соединению его проекций и

1. 3-я нормальная форма (3НФ) отношения. Определение транзитивной зависимости и 3НФ.Алгоритм приведения к 3НФ.Нормальная форма Бойса-Кодда (НФБК).Определение и алгоритм приведения к НФБК. Характеристика отношения в 3НФ и в НФБК. Примеры.

Третья нормальная форма (3NF)

Таблица находится в третьей нормальной форме, если она находится во второй нормальной форме, и при этом любой её неключевой атрибут функционально зависит только от первичного ключа. Или что тоже самое - "нет зависимостей неключевых атрибутов от других неключевых атрибутов + 2НФ".

При решении практических задач в большинстве случаев третья нормальная форма является достаточной. Процесс проектирования реляционной базы данных, как правило, заканчивается приведением к 3NF.

Пример приведения таблицы к третьей нормальной форме

Фамилия	Отдел	Телефон
Гришин	1	11-22-33
Васильев	1	11-22-33
Петров	2	44-55-66

В результате приведения к 3NF получим две таблицы:

Фамилия	Отдел
Гришин	1
Васильев	1
Петров	2

Отдел	Телефон
1	11-22-33
2	44-55-66

BCNF - нормальная форма Бойса-Кодда.

Эта нормальная форма вводит дополнительное ограничение по сравнению с 3НФ. 
Определение нормальной формы Бойса-Кодда:

Отношение находится в BCNF, если оно находится во 3НФ и в ней отсутствуют зависимости атрибутов первичного ключа от неключевых атрибутов.

Ситуация, когда отношение будет находится в 3NF, но не в BCNF, возникает при условии, что отношение имеет два (или более) возможных ключа, которые являются составными и имеют общий атрибут. Заметим, что на практике такая ситуация встречается достаточно редко, для всех прочих отношений 3NF и BCNF эквивалентны.

1. Многозначные зависимости (МЗ). Определение. Свойства и аксиомы МЗ. Четвертая нормальная форма (4НФ) отношения. Характеристика отношения в 4НФ.

Многозначные зависимости и четвертая нормальная форма (4NF).

Четвертая нормальная форма касается отношений, в которых имеются повторяющиеся наборы данных. Декомпозиция, основанная на функциональных зависимостях, не приводит к исключению такой избыточности. В этом случае используют декомпозицию, основанную на многозначных зависимостях.

Многозначная зависимость является обобщением функциональной зависимости и рассматривает соответствия между множествами значений атрибутов.

В качестве примера рассмотрим отношение ПРЕПОДАВАТЕЛЬ (ИМЯ, КУРС, УЧЕБНОЕ_ПОСОБИЕ), хранящее сведения о курсах, читаемых преодавателем, и написанных им учебниках. Пусть профессор N читает курсы "Теория упругости" и "Теория колебаний" и имеет соответствующие учебные пособия, а профессор K читает курс "Теория удара" и является автором учебников "Теория удара" и "Теоретическая механика". Тогда наше отношение будет иметь вид: