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

Так что если вы собираетесь начать свое обучение в этой области или вам просто стало интересно, прошу под кат.

Реляционная база данных

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

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

Таблица PRODUCTS

ID	NAME	COMPANY	PRICE
123	Печеньки	ООО ”Темная сторона”	190
156	Чай	ООО ”Темная сторона”	60
235	Ананасы	ОАО ”Фрукты”	100
623	Томаты	ООО ”Овощи”	130

Таблица состоит из 4х строк, строка в таблице является кортежем в реляционной теории. Множество упорядоченных кортежей называется отношением.
Перед тем как дать определение отношения, введем еще один термин - домен. Домены применительно к таблице это столбцы.

Для ясности, теперь введем строгое определение отношения.

Пусть даны N множеств D1,D2, …. Dn (домены), отношением R над этими множествами называется множество упорядоченных N-кортежей вида , где d1 принадлежит D1 и тд. Множества D1,D2,..Dn называются доменами отношения R.
Каждый элемент кортежа представляет собой значение одного из атрибутов, соответствующего одному из доменов.

Ключи в отношениях

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

Таблица DRIVERS

Видно, что в организации может быть несколько водителей, и чтобы однозначно идентифицировать водителя необходимо и значение из столбца “Название организации” и из “Имя водителя”. Такой ключ называется составным.

В реляционной БД таблицы взаимосвязаны и соотносятся друг с другом как главные и подчиненные. Связь главной и подчиненнной таблицы осуществляется через первичный ключ (primary key) главной таблицы и внешний ключ (foreign key) подчиненной таблицы.
Внешний ключ это атрибут или набор атрибутов, который в главной таблице является первичным ключем.

Этой подготовительной теории будет достаточно для знакомства с основными операциями реляционной алгебры.

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

Основные восемь операций реляционной алгебры были предложены Э.Коддом .

• Объединение
• Пересечение
• Вычитание
• Декартово произведение
• Выборка
• Проекция
• Соединение
• Деление

Первая половина операций аналогична таким же операциям над множествами. Часть операций можно выразить через другие операции. Рассмотрим большую часть операций с примерами.

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

Таблица SELLERS

ID	SELLER
123	OOO “Дарт”
156	ОАО ”Ведро”
235	ЗАО “Овоще База”
623	ОАО ”Фирма”

Условимся, что в этой таблице ID это внешний ключ, связанный с первичным ключом таблицы PRODUCTS.

Для начала рассмотрим самую простую операцию - имя отношения. Её результатом будет такое же отношение, то есть выполнив операцию PRODUCTS, мы получим копию отношения PRODUCTS.

Проекция

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

Синтаксис операции:
π (ID, PRICE) PRODUCTS

В условии выборки мы можем использовать любое логическое выражение. Сделаем еще одну выборку с ценой больше 90 и ID товара меньше 300:

σ (PRICE>90 ^ ID<300) PRODUCTS

Умножение

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

Получим декартово произведения таблиц PRODUCTS и SELLERS.
Синтаксис операции:

PRODUCTS × SELLERS
Можно заметить, что у двух этих таблиц есть одинаковый домен ID. В подобной ситуации домены с одинаковыми названиями получают префикс в виде названия соответствующего отношения, как показано ниже.
Для краткости перемножим не полные отношения, а выборки с условием ID<235

(цветом выделены одни и те же кортежи)

PRODUCTS.ID	NAME	COMPANY	PRICE	SELLERS.ID	SELLER
123	Печеньки	ООО ”Темная сторона”	190	123	OOO “Дарт”
156	Чай	ООО ”Темная сторона”	60	156	ОАО ”Ведро”
123	Печеньки	ООО ”Темная сторона”	190	156	ОАО ”Ведро”
156	Чай	ООО ”Темная сторона”	60	123	OOO “Дарт”

Для примера использования этой операции представим себе необходимость выбрать продавцов с ценами меньше 90. Без произведения необходимо было бы сначала получить ID продуктов из первой таблицы, потом по этим ID из второй таблицы получить нужные имена SELLER, а с использованием произведения будет такой запрос:

π (SELLER) σ (RODUCTS.ID=SELLERS.ID ^ PRICE<90) PRODUCTS × SELLERS

В результате этой операции получим отношение:

SELLER

ОАО ”Ведро”

Соединение и естественное соединение

Операция соединения обратна операции проекции и создает новое отношение из двух уже существующих. Новое отношение получается конкатенацией кортежей первого и второго отношений, при этом конкатенации подвергаются отношения, в которых совпадают значения заданных атрибутов. В частности, если соединить отношения PRODUCTS и SELLERS, этими атрибутами будут атрибуты доменов ID.

Также для понятности можно представить соеднинение как результат двух операций. Сначала берется произведение исходных таблиц, а потом из полученного отношения мы делаем выборку с условием равенства атрибутов из одинаковых доменов. В данном случае условием явлется равенство PRODUCTS.ID и SELLERS.ID.

Попробуем соединить отношения PRODUCTS и SELLERS и получим отношение.

PRODUCTS.ID	NAME	COMPANY	PRICE	SELLERS.ID	SELLER
123	Печеньки	ООО ”Темная сторона”	190	123	OOO “Дарт”
156	Чай	ООО ”Темная сторона”	60	156	ОАО ”Ведро”
235	Ананасы	ОАО ”Фрукты”	100	235	ЗАО “Овоще База”
623	Томаты	ООО ”Овощи”	130	623	ОАО ”Фирма”

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

Синтаксис операции:
PRODUCTS ⋈ SELLERS;

Получится такое отношение:

PRODUCTS.ID	NAME	COMPANY	PRICE	SELLER
123	Печеньки	ООО ”Темная сторона”	190	OOO “Дарт”
156	Чай	ООО ”Темная сторона”	60	ОАО ”Ведро”
235	Ананасы	ОАО ”Фрукты”	100	ЗАО “Овоще База”
623	Томаты	ООО ”Овощи”	130	ОАО ”Фирма”

Пересечение и вычитание.

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

Источники информации

• Основы использования и проектирования баз данных - В. М. Илюшечкин
• курс лекций Introduction to Databases - Jennifer Widom, Stanford University

Буду благодарен за аргументированные замечания

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

СУБД – системы управления базами данных – это специализированное ПО, призванное, ожидаемо, управлять базами данных. Достигается это взаимодействием с пользователем с одной стороны и собственно с базой данных с другой.

СУБД общего назначения должна позволять определение, создание, изменение, администрирование и произведение запросов к БД.

В качестве примеров СУБД можно назвать такие широко известные пакеты, как

• MySQL
• PostgreSQL
• Microsoft SQL Server
• Oracle
• IBM DB2
• Microsoft Access
• SQLite

Базы данных обычно не являются переносимыми между различными СУБД, однако возможно взаимодействие между СУБД (и с пользовательским ПО) с использованием различных стандартов, таких, как SQL, ODBC или JDBC.

СУБД часто классифицируются по поддерживаемой ими модели данных. С 1980х годов, практически все популярные СУБД поддерживают реляционную модель данных, представленную стандартом языка запросов SQL (хотя последние годы набирает популярность NoSQL).

Итак, основные задачи, выполняемые СУБД включают

Определение схемы данных Создание, изменение и удаление структур, которые определяют организацию всех остальных данных в БД Изменение данных Добавление, изменение и удаление самих данных Получение данных Предоставление информации в форме, пригодной к непосредственному использованию другими приложениями. Администрирование БД Регистрация и управление пользователями, обеспечение безопасности данных, поддержание целостности, восстановление информации, управление одновременным доступом, слежение за производительностью и т.п.

СУБД широко используются в банковском деле, транспортных компаниях, учебных заведениях, телекоммуникациях, для управления финансовой информацией и человеческими ресурсами. Ну и не стоит забывать, что большинство бэкэндов Web использует ту или иную СУБД.

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

Модели БД

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

• Иерархическая, или навигационная модель
• Сетевая модель

Иерархическая модель широко использовалась в СУБД, поставляемых компанией IBM в 1960х. Основная идея заключается в том, что запись в такой БД может иметь несколько “дочерних” и одну “родительскую”. В целом, это подозрительно похоже на иерархическую файловую систему. Чтобы получить запись в такой БД, часто необходим проход по всему дереву.

Сетевая модель – более гибкая версия того же подхода. Она позволяет иметь записи несколько “родительских”. Эта модель, появившись в начале 1970х, не получила широкого распространения, и вскоре была вытеснена реляционной моделью.

В 1970х Эдгаром Коддом (сотрудник IBM) была предложена реляционная модель, которая значительно облегчила задачу поиска информации в БД. О реляционной модели можно думать как о “таблицах”, в которых “строки” – это записи в БД. Записи в реляционной БД так же называются кортежами (tuples), а группы записей (“таблицы”) – отношениями (relations). Реляционная модель способна выразить связи иерархической и сетевой моделей, и добавляла собственные связи, соответствующие табличной модели.

На основе предложений Кодда к середине 1970х была разработана СУБД System R, а к концу в ней появилась поддержка стандартизованного языка запросов SQL.

В 1980х, с появлением объектно-ориентированного программирования, все чаще возникали сложности в трансляции объектов на реляционную модель. В конце концов это привело к появлению подходов NoSQL и NewSQL, которые на текущий момент только развиваются. Примерами реализации NoSQL подхода могут быть т.н. документо-ориентированные БД, построенные на основе XML. Основное преимущество NoSQL – высокая горизонтальная масштабируемость, т.е. возможность увеличивать производительность за счет добавления серверов. С появлением облачных технологий, NoSQL стал особенно востребован.

Тем не менее, реляционная модель пока остается самой распространенной, поэтому более подробно остановимся именно на ней.

Реляционная модель

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

Реляционная модель требует строгого определения структуры данных, хранимых в БД, то есть отношения и атрибуты для данной БД фиксированы.

Введем некоторые определения.

Домен Множество, содержащее полный набор всех возможных значений некоторой переменной. Домены часто так же называют типом данных . Атрибут Упорядоченная пара названия атрибута и домена \(D_j\) . Кортеж Конечное упорядоченное множество \((d_1, d_2, \ldots, d_n)\) Заголовок (схема) отношения Кортеж \((A_1, A_2, \ldots, A_n)\) , где \(A_j\) – атрибуты. Значение атрибута Конкретное значение, принадлежащее домену атрибута. Тело отношения Множество кортежей , где \(d^i_j \in D_j\) , \(D_j\) – домены. Запись Кортеж \((d^i_1, d^i_2, \ldots, d^i_n)\) при фиксированном \(i\) . Отношение Совокупность заголовка отношения и тела отношения. Схема базы данных Множество схем всех отношений, входящих в БД.

Можно представить отношение в виде таблицы. Тогда тело отношения – это тело таблицы, заголовок отношения – заголовок таблицы, атрибуты – названия столбцов, записи – строки, а значения атрибутов находятся в ячейках:

\(A_1\)	\(A_2\)	\(\ldots\)	\(A_n\)	← Заголовок
\(d^1_1\)	\(d^1_2\)	\(\ldots\)	\(d^1_n\)	← Запись
\(d^2_1\)	\(d^2_2\)	\(\ldots\)	\(d^2_n\)	← Запись
\(\ldots\)	\(\ldots\)	\(\ldots\)	\(\ldots\)	← Запись
\(d^m_1\)	\(d^m_2\)	\(\ldots\)	\(d^m_n\)	← Запись

Реляционная модель налагает следующие дополнительные требования на отношения:

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

Функциональная зависимость множество атрибутов \(B\) функционально зависит от множества атрибутов \(A\) (записывается \(A\rightarrow B\) ), если для любых двух записей, имеющих одинаковые значения \(A\) , их значения \(B\) совпадают. Иначе, каждому значению \(A\) соответствует единственное значение \(B\) (не обязательно уникальное, именно единственное).

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

В качестве более привычного примера функциональной зависимости, можно привести математическое определение функции. Для функции, каждому значению аргументов соответсвтует единственное значение функции. Обратное в общем случае неверно, например, для функции \(y = sin(x)\) любому значению \(y\) из области определения \(1\geq y \geq -1\) соответствует бесконечное множество значений \(x\) , но для каждого значения \(x\) есть ровно одно значение \(y\) , т.о. \(x \to y\) . Заметим, что понятие функциональной зависимости так же применимо и к функциям многих переменных. Для них, значение функции функционально зависит от всех аргументов одновременно . Скажем, для функции \(z = f(x,y)\) выполняется ФЗ \((x,y)\to z\) , или сокращенно, \(xy\to z\) .

Отношения в данном контексте можно рассматривать как некие табличные или дискретные функции.

Работа с ФЗ

Существуют определенные формальные правила работы с ФЗ отношения.

Формальные правила тесно связаны с понятиями замыкания и неприводимой ФЗ .

Аксиомы Армстронга

Существуют правила вывода новых ФЗ из существующих, называемые аксиомами Армстронга .

Аксиомы Армстронга

1. Правило рефлексивности: если \(B \subset A\) , то \(A\rightarrow B\)
2. Правило дополнения: если \(A\rightarrow B\) , то \(AC\rightarrow BC\)
3. Правило транзитивности: если \(A\rightarrow B\) и \(B\rightarrow C\) , то \(A\rightarrow C\)

Из этих аксиом так же могут быть выведены следующие дополнительные правила:

1. Правило самоопределения: \(A\rightarrow A\)
2. Правило декомпозиции: Если \(A\rightarrow BC\) , то \(A\rightarrow B\) и \(A\rightarrow C\)
3. Правило объединения: Если \(A\rightarrow B\) и \(A\rightarrow C\) , то \(A\rightarrow BC\)
4. Правило композиции: Если \(A\rightarrow B\) и \(C\rightarrow D\) , то \(AC\rightarrow BD\)

Можно заметить, что, вследствие правила рефлексивности, любое множество атрибутов \(A\) подразумевает ФЗ вида \(A\to A\) . Такие ФЗ, а так же следующие из них, не представляют интереса, и называются тривиальными.

Тривиальная функиональная зависимость ФЗ \(A \to B\) , такая, что \(B \subset A\) .

В принципе, этих правил достаточно для того, чтобы найти все ФЗ, следующие из данных. В связи с этим вводится понятие замыкания множества ФЗ.

Замыкание множества ФЗ Замыканием множества ФЗ называется такое множество ФЗ, которое включает все ФЗ исходного множества, а так же все подразумеваемые ими. Другими словами, для отношения \(R\) , обладающего функциональными зависимостями \(S\) , замыканием \(S^+\) называется множество всех ФЗ, возможных для \(R\) , исходя из \(S\) .

Как правило, требуется установить, будет ли некая ФЗ \(X\rightarrow Y\) следовать из данного множества ФЗ \(S\) . Оказывается, это возможно тогда и только тогда, когда множество атрибутов \(Y\) является подмножеством замыкания атрибутов \(X^+\) в \(S\) .

Замыкание атрибутов Замыканием \(X^+\) атрибутов \(X\) по множеству ФЗ \(S\) называется множество всех атрибутов, которые функционально зависят от какого-либо подмножества \(X\) .

Для вычисления замыкания множества атрибутов \(X^+\) по множеству ФЗ \(S\) существует следующее правило: для каждой ФЗ \(A\rightarrow B\) в \(S\) , если \(A \subset X^+\) , то и \(B \subset X^+\) , причем достаточно начать с предположения, что \(X^+ = X\) .

Следует заметить, что для любого замыкания \(X^+\) , существуют ФЗ вида \(X \to B\) , где \(B \subset X^+\) , таким образом, замыкания всех атрибутов отношения по его ФЗ описывают замыкание ФЗ этого отношения.

Это правило используется для вычисления неприводимого множества ФЗ, эквивалентного данному (в смысле эквивалентности их замыканий). Уменьшение количества ФЗ при сохранении замыкания (и, следовательно, внутренней логики, описываемой ФЗ) является важным шагом в проектировании БД.

Множество ФЗ называется неприводимым, если:

1. Правая часть каждой ФЗ содержит только один элемент
2. Ни один атрибут ни одной левой части ФЗ множества не может быть удален без изменения замыкания
3. Ни одна ФЗ множества не может быть удалена без изменения замыкания.

Для любого множества ФЗ существует хотя бы одно эквивалентное неприводимое множество. Такое множество называется минимальным покрытием .

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

Введение

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

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

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

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

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

Общие определения

Пусть задана переменная отношения r , и X и Y являются произвольными подмножествами заголовка r ("составными" атрибутами).

В значении переменной отношения r атрибут Y функционально зависит от атрибута X в том и только в том случае, если каждому значению X соответствует в точности одно значение Y . В этом случае говорят также, что атрибут X функционально определяет атрибут Y (X является детерминантом (определителем ) для Y , а Y является зависимым от X ). Будем обозначать это как r.X->r.Y .

Для примера будем использовать отношение СЛУЖАЩИЕ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ, ПРОЕКТ_РУК} (рис. 6.1). Очевидно, что если СЛУ_НОМ является первичным ключом отношения СЛУЖАЩИЕ , то для этого отношения справедлива функциональная зависимость (Functional Dependency – FD) СЛУ_НОМ->СЛУ_ИМЯ .

На самом деле, для тела отношения СЛУЖАЩИЕ_ПРОЕКТЫ в том виде, в котором оно показано на рис. 6.1 , выполняются еще и следующие FD (1):

Рис. 6.1.

СЛУ_НОМ->СЛУ_ИМЯ СЛУ_НОМ->СЛУ_ЗАРП СЛУ_НОМ->ПРО_НОМ СЛУ_НОМ->ПРОЕКТ_РУК {СЛУ_НОМ, СЛУ_ИМЯ}->СЛУ_ЗАРП {СЛУ_НОМ, СЛУ_ИМЯ}->ПРО_НОМ {СЛУ_НОМ, СЛУ_ИМЯ}->{СЛУ_ЗАРП, ПРО_НОМ} … ПРО_НОМ->ПРОЕКТ_РУК и т.д.

Поскольку имена всех служащих различны, то выполняются и такие FD (2):

СЛУ_ИМЯ->СЛУ_НОМ СЛУ_ИМЯ->СЛУ_ЗАРП СЛУ_ИМЯ->ПРО_НОМ и т.д.

Более того, для примера на рис. 6.1 выполняется и FD (3):

СЛУ_ЗАРП->ПРО_НОМ

Однако заметим, что природа FD группы (1) отличается от природы FD групп (2) и (3). Логично предположить, что идентификационные номера служащих должны быть всегда различны, а у каждого проекта имеется только один руководитель. Поэтому FD группы (1) должны быть верны для любого допустимого значения переменной отношения СЛУЖАЩИЕ_ПРОЕКТЫ и могут рассматриваться как инварианты , или ограничения целостности этой переменной отношения .

FD группы (2) базируются на менее естественном предположении о том, что имена всех служащих различны. Это соответствует действительности для примера из рис. 6.1 , но возможно, что с течением времени FD группы (2) не будут выполняться для какого-либо значения переменной отношения СЛУЖАЩИЕ_ПРОЕКТЫ .

Наконец, FD группы (3) основана на совсем неестественном предположении, что никакие двое служащих, участвующие в разных проектах, не получают одинаковую зарплату. Опять же, данное предположение верно для примера из рис. 6.1 , но, скорее всего, это случайное совпадение.

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

Заметим, что если атрибут A отношения r является возможным ключом, то для любого атрибута B этого отношения всегда выполняется

Жизненный цикл информационных систем

Анализ ситуации (сложность разработки ИС, не эффективное использование ИС), проведенный учеными, показал, что такое положение было вызвано тем, что при разработке программного обеспечения не соблюдались очень важными требования:

· Отсутствие полной спецификации всех требований;

· Отсутствие приемлемой методологии (системы методов) разработки ИС;

· Отсутствие разделения общего глобального проекта на отдельные компоненты, поддающиеся эффективному контролю и управлению.

Жизненный цикл (ЖЦ) информационных систем – это структурный подход к разработке программного обеспечения.

(некая схема) за 26.09.12

1. Планирование разработки ИС. Подготовительные действия, позволяющие с максимальной эффективностью реализовывать этапы ЖЦ ИС. Три основных компонента: оценка объема работ; оценка необходимых ресурсов; оценка общей стоимости проекта.

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

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

4. Проектирование базы данных. Создание проекта базы данных. Два основных подхода к проектированию систем баз данных: «нисходящий » и «восходящий ».

5. Выбор целевой СУБД. Выбор СУБД подходящего типа, предназначенной для поддержки создаваемого приложения базы данных.

6. Разработка приложений. Проектирование интерфейса пользователя и прикладных программ, предназначенных для работы с базой данных.

7. Создание прототипа. Создание рабочей модели приложения баз данных.

8. Реализация. Физическая реализация базы данных и разработанных приложений.

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

10. Тестирование. Процесс выполнения прикладных программ с целью поиска ошибок. Стратегии тестирования: нисходящее тестирование; восходящее тестирование; тестирование потоков; интенсивное тестирование.

11. Эксплуатация и сопровождение. Наблюдение за системой и поддержка её нормального функционирования: контроль производительности; сопровождение и модернизация приложений.

Реляционная теория баз данных

Терминология

В 1970 г. Реляционная модель впервые была предложена Э.Ф. Коддом.

В реляционной СУБД предполагается, что пользователь воспринимает БД как набор таблиц (и не как иначе).

Математические отношения.

Теория реляционных БД основана на математической теории отношений.

Пусть D1, D2, … Dn некоторые множества.

Декартовым произведение D1 D2 … Dn = {(X1,X2,…,Xn) | X1 D1, X2 D2, … Xn Dn}

Отношение – подмножество R D1*D2*…*Dn

Например, n=2, D1={2,4} и D2={1,3,5}, D1 * D2 = {(2,1),(2,3),(2,5),(4,1),(4,3),(4,5)}, R={(2,1),(4,1)}

Подмножество м. б. задано условием, например:

R={(x1,x2) |x1 D1, x2 D2, X2=1}, A1, A2, … An – имена атрибутов с доменами D1, D2, … Втб тогда отношение будем записывать в виде:

R(A1:D1,A2:D2,…An:Dn)

Свойства отношений:

· Отношение имеет уникальное имя;

· Каждый атрибут имеет уникальное имя (в отношении);

· Каждая ячейка отношения содержит только атомарное значение и нет повторяющихся групп (отношение нормализовано);

D1 – студенты
D2 – дисциплины: Математика, Информатика

· Порядок следования атрибутов не имеет никакого значения;

· Порядок следования кортежей произвольный;

· Каждый кортеж является уникальным.

Реляционные ключи

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

Реляционная целостность.

Реляционная алгебра

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

Реляционная алгебра является языком, в котором все кортежи обрабатываются одной командой.

Пять основных операций:

· Выборка,

· Проекция,

· Декартово произведение,

· Объединение,

· Разность.

На основе этих операций могут быть получены другие:

· Соединения,

· Пересечения,

· Деления.

В предикате могут использоваться знаки логических операций ^(And), v(Or), ~(not).

Пример. Получить список всех сотрудником с окладом свыше 300.

Проекция.

Определяет отношение, атрибутами которого являются атр1, …, атрn и содержит только уникальные кортежи.

Декартово произведение

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

Объединение

Разность

Операции соединения.

Тета-соединение

Естественное соединение

Внешнее соединение

То при левом внешнем соединении сохраняется вся исходная информация из отношения R. Аналогично также можно определить правое внешнее соединение.

Полусоединение

Операцию полусоединения можно определить с помощью операторов проекции и соединения.

Пересечение

Представления

Назначение представлений:

· Предоставляет гибкий механизм защиты БД за счет сокрытия некоторой её части от определенных пользователей;

· Позволяет организовать доступ пользователей к данным наиболее удобным для них способом;

· Позволяет упрощать сложные операции с базовыми отношениями.

Правила, которые должны удовлетворить
реляционные СУБД

Для определения того, является ли СУБО реляционной Кодд (1985 г.) предложил 13 правил, которым они должны удовлетворять.

№		Правило
		Фундаментальное правило. Реляционная СУБД должна быть способна управлять базами данных исключительно с помощь её реляционных функций
		Представление информации. Вся информация в реляционной БД представляется в явном виде на логическом уровне только одним способом – в виде значений в таблицах. В том числе, метаданные.
		Гарантированный доступ. Для каждого элемента данных реляционной БД должен быть гарантирован логический доступ на основе комбинации имени таблицы, значения первичного ключа и имени столбца.
		Поддержка неопределенных значений. СУБД поддерживает неопределенные значения (Null).
		Реляционный системный каталог. Описание БД должно представляться на логическом уровне таким образом, как и обычные данные, что позволяет пользователям использовать для обращения к ним тот же реляционный язык.
		Исчерпывающий подъязык данных. реляционная СУБД может поддерживать несколько языков. Однако должен существовать по крайней мерее один язык, операторы которого позволяли бы выполнить следующие функции: 1. Определение данных; 2. Определение представлений; 3. Команды манипулирования данными; 4. Ограничения целостности; 5. Авторизации пользователей; 6. Организации транзакций
		Высокоуровневые операции извлечения, вставки, удаления, обновления. Способность СУБД выполнять операции извлечения данных команд вставки, удаления и обновления как единой операции.
		Физическая независимость от данных. От способа хранения
		Логическая независимость от данных. Независимость приложений от изменения базовых таблиц.
		Независимость ограничений целостности. Ограничения целостности должны определяться на подъязыке реляционных данных и храниться в системном каталоге, а не в прикладных программах.
		Независимость от распределения данных.
		Правило запрета обходных путей. Если СУБД имеет низкоуровневый язык (с последовательной построчной обработкой), он не должен позволять обходить правила и ограничения целостности, описанных на реляционном языке высокого уровня.

Моделирование данных на основе процесса нормализации

Цель нормализации.

Процесс нормализации был предложен в 1972 году Э. Ф. Коддом – три нормальные формы (НФ): первая (1НФ), вторая (2НФ) и третья (3НФ).

Более строгое определение третьей НФ (Р. Бойс и Э. Ф. Кодд, 1974) – нормальная форма Бойса-Кодда (НФБК).

Избыточность данных и аномалии обработки.

Отсутствие нормализации приводит:

· Избыточность данных

· Аномалии вставки (невозможно добавлять записи)

· Аномалии удаления (при удалении информации теряется другая информация)

· Аномалии обновления (требуется обновление многих записей)

· Свойства сохранения без потерь и сохранения зависимости.

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