Реляционная алгебра – реляционный язык обработки данных.

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

В состав теоретико-множественных операций входят операции:

объединения отношений;

пересечения отношений;

взятия разности отношений;

прямого произведения отношений.

Специальные реляционные операции включают:

ограничение отношения;

проекцию отношения;

соединение отношений;

деление отношений.

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

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

алгебра Кодда (Э. Кодд, 1970)

алгебра A (К. Дейт, Х. Дарвен)

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

Традиционные и специальные операции реляционной алгебры: объединение, пересечение, вычитание, декартово произведение, проекция, выборка. О соединение, естественное соединение, деление.

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

1. если каждое из них имеет одно и то же множество имен атрибутов (следовательно, заметьте, они заведомо должны иметь одну и ту же степень);

2. если соответствующие атрибуты (т.е. атрибуты с теми же самыми именами в двух отношениях) определены на одном и том же домене.

Пересечение

Пересечением двух совместимых по типу отношений А и В (A INTERSECT B) называется отношение с тем же заголовком, как и в отношениях А и В, и с телом, состоящим из множества всех кортежей, принадлежащих одновременно обоим отношениям A и B.

Вычитание

Вычитанием двух совместимых по типу отношений А и В (A MINUS B) называется отношение с тем же заголовком, как и в отношениях А и В, и с телом, состоящим из множества всех кортежей, принадлежащих отношению A и не принадлежащих отношению B.

Произведение

В математике декартово произведение (или для краткости произведение) двух множеств является множеством всех таких упорядоченных пар элементов, что первый элемент в каждой паре берется из первого множества, а второй элемент в каждой паре берется из второго множества. Следовательно, декартово произведение двух отношений, должно быть множеством упорядоченных пар кортежей. Но опять-таки необходимо сохранить свойство замкнутости; иначе говоря, результат должен содержать кортежи, а не упорядоченные пары кортежей.

Декартово произведение двух отношений А и В (A TIMES B), где А и В не имеют общих имен атрибутов, определяется как отношение с заголовком, который представляет собой сцепление двух заголовков исходных отношений А и В, и телом, состоящим из множества всех кортежей t, таких, что t представляет собой сцепление кортежа a, принадлежащего отношению А, и кортежа b, принадлежащего отношению В. Кардинальное число результата равняется произведению кардинальных чисел исходных отношений А и В, а степень равняется сумме их степеней.

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

10) Понятие функциональной зависимости для отношения. Основные определения. Способ определения Ф.З. Тривиальные и нетривиальные зависимости.

Функциональная зависимость. Пусть X и Y - два атрибута некоторого отношения. Говорят, что Y функционально зависит от X, если в любой момент времени каждому значению Х соответствует не более одного значения атрибута Y.

Функциональную зависимость обозначают так X - > У.

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

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

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

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

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

Зависимость называется тривиальной, если она не может не выполняться. Действительно, функциональная зависимость является тривиальной тогда и только тогда, когда правая часть ее символической записи является подмножеством (необязательно правильным подмножеством) левой части.

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

 

11) Замыкание множества зависимостей. Аксиомы Армстронга.

Замыканием множества FD S является множество FD S⁺, включающее все FD, логически выводимые из FD множества S.

Одни функциональные зависимости могут подразумевать другие функциональные зависимости. Например,

.

 

Правила вывода Армстронга

В 1974 году Вильям Армстронг предложил набор правил вывода новых функциональных зависимостей на основе данных.

Пусть у нас есть отношение и множества атрибутов . Для сокращения записи вместо будем писать просто XY.

Рефлексивность:

Пополнение:

Транзитивность:

Самоопределение:

Декомпозиция:

Объединение:

Композиция:

Теорема всеобщего объединения Дарвена:

Теорема: Функциональная зависимость выводима из данного множества функциональных зависимостей S по правилам вывода Армстронга тогда и только тогда, когда .

12)Нормализация. Первая, вторая и третья нормальные формы отношения

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

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

Нормализация отношений — формальный аппарат ограничений на фор­мирование отношений (таблиц), который позволяет устранить дублирова­ние, обеспечивает непротиворечивость хранимых в базе данных, уменьшает трудозатраты на ведение (ввод, корректировку) базы данных.

Выделены три нормальные формы отношений и предложен механизм, позволяющий любое отношение преобразовать к третьей (самой совершенной) нормальной форме.

Первая нормальная форма

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

Например, отношение Студент = (Номер, Фамилия, Имя, Отчество, Дата, Группа) на­водится в первой нормальной форме.

1НФ (Первая Нормальная Форма)

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

В отношении нет одинаковых кортежей.

Кортежи не упорядочены.

Атрибуты не упорядочены и различаются по наименованию.

Все значения атрибутов атомарны.

В ходе логического моделирования на первом шаге предложено хранить данные в одном отношении, имеющем следующие атрибуты:

СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ (Н_СОТР, ФАМ, Н_ОТД, ТЕЛ, Н_ПРО, ПРОЕКТ, Н_ЗАДАН)

где

Н_СОТР - табельный номер сотрудника

ФАМ - фамилия сотрудника

Н_ОТД - номер отдела, в котором числится сотрудник

ТЕЛ - телефон сотрудника

Н_ПРО - номер проекта, над которым работает сотрудник

ПРОЕКТ - наименование проекта, над которым работает сотрудник

Н_ЗАДАН - номер задания, над которым работает сотрудник

Т.к. каждый сотрудник в каждом проекте выполняет ровно одно задание, то в качестве потенциального ключа отношения необходимо взять пару атрибутов { Н_СОТР, Н_ПРО }.

Аномалии обновления

Даже одного взгляда на таблицу отношения СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ достаточно, чтобы увидеть, что данные хранятся в ней с большой избыточностью. Во многих строках повторяются фамилии сотрудников, номера телефонов, наименования проектов. Кроме того, в данном отношении хранятся вместе независимые друг от друга данные - и данные о сотрудниках, и об отделах, и о проектах, и о работах по проектам. Пока никаких действий с отношением не производится, это не страшно. Но как только состояние предметной области изменяется, то, при попытках соответствующим образом изменить состояние базы данных, возникает большое количество проблем.

Исторически эти проблемы получили название аномалии обновления. Попытки дать строгое понятие аномалии в базе данных не являются вполне удовлетворительными [51, 7]. В данных работах аномалии определены как противоречие между моделью предметной области и физической моделью данных, поддерживаемых средствами конкретной СУБД. "Аномалии возникают в том случае, когда наши знания о предметной области оказываются, по каким-то причинам, невыразимыми в схеме БД или входящими в противоречие с ней" [7]. Мы придерживаемся другой точки зрения, заключающейся в том, что аномалий в смысле определений упомянутых авторов нет, а есть либо неадекватность модели данных предметной области, либо некоторые дополнительные трудности в реализации ограничений предметной области средствами СУБД. Более глубокое обсуждение проблемы строгого определения понятия аномалий выходит за пределы данной работы.

Таким образом, мы будем придерживаться интуитивного понятия аномалии как неадекватности модели данных предметной области, (что говорит на самом деле о том, что логическая модель данных попросту неверна!) или как необходимости дополнительных усилий для реализации всех ограничений определенных в предметной области (дополнительный программный код в виде триггеров или хранимых процедур).

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

Аномалии вставки (INSERT)

Аномалии обновления (UPDATE)

Аномалии удаления (DELETE)

В отношении СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ можно привести примеры следующих аномалий:

Аномалии вставки (INSERT)

В отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ нельзя вставить данные о сотруднике, который пока не участвует ни в одном проекте. Действительно, если, например, во втором отделе появляется новый сотрудник, скажем, Пушников, и он пока не участвует ни в одном проекте, то мы должны вставить в отношение кортеж (4, Пушников, 2, 33-22-11, null, null, null). Это сделать невозможно, т.к. атрибут Н_ПРО (номер проекта) входит в состав потенциального ключа, и, следовательно, не может содержать null-значений.

Точно также нельзя вставить данные о проекте, над которым пока не работает ни один сотрудник.

Причина аномалии - хранение в одном отношении разнородной информации (и о сотрудниках, и о проектах, и о работах по проекту).

Вывод - логическая модель данных неадекватна модели предметной области. База данных, основанная на такой модели, будет работать неправильно.