Теория модели реляционных баз данных.

Теоретической основой модели стала теория отношений, основу которой заложили Ч.С. Пирс и Э. Шрёдер. Основоположником теории реляционных баз данных считается сотрудник фирмы IBM доктор A. Codd, опубликовавший в 1970 г. статью «Реляционная модель данных для больших коллективных банков данных». Кодд, будучи математиком по образованию, предложил использовать для обработки данных аппарат теории множеств и предикативной логики для того, чтобы внести в область управления базами данных строгие математические принципы. Предложения Кодда были настолько эффективны для систем баз данных, что за эту модель он был удостоен премии Тьюринга в области теоретических основ вычислительной техники.

Термины реляционной модели и теории множеств:

• Домен (Domain) – некоторое конечное множество. Обозначение: D_i , где i – номер домена. Отдельный элемент домена обозначим d_i с тем же смыслом i.
• Полное декартово произведение множеств – набор всевозможных сочетаний из n элементов каждое, где каждый элемент берётся из своего домена. Описание: D₁´D₂´…´D_n.
• Отношение (relation) R – подмножество декартова произведения множеств D₁, D₂, … D_n (n≥1), необязательно различных. Описание: R Í D₁´D₂´…´D_n.
• Число n называется степенью отношения (n = 1 – унарное, n = 2 – бинарное, в общем случае n-арное).
• Атрибутом (Attribute) называют домен, входящий в отношение. Степень отношения определяет количество атрибутов в отношении.
• Кортежем (Tuple) называют декартово произведение элементов множеств d₁´d₂´…´d_n.
• Атрибуты, значения которых однозначно идентифицируют кортежи, называются ключевыми.Отношение может содержать несколько ключей. Всегда один из ключей объявляется первичным (primary key),его значения не могут обновляться. Все остальные ключи отношения называются возможными (потенциальными) ключами.
• Схемой отношения S называется перечень имён атрибутов данного отношения с указанием домена, к которому они относятся. Описание: S_R= (A₁, A₂, …, A_n), A_i Í D_i.
• Набор именованных схем отношений представляет собой схему базы данных.

Отношения удобно представлять в виде таблиц.

Можно условно связать язык формальной логики, язык инфологических моделей и практический язык терминов реляционных БД с помощью следующей таблицы «синонимов»:

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

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

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

2. В манипуляционной части модели утверждаются два фундаментальных механизма манипулирования реляционными БД: реляционная алгебра и реляционное исчисление.

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

Свойства реляционных баз данных (вытекают из определения отношения и кортежа как множеств):

1. В отношении нет одинаковых кортежей(все строки таблицы различаются по своему содержанию). Следствие: наличие у каждого кортежа первичного ключа. Для каждого отношения, по крайней мере, полный набор его атрибутов является первичным ключом. Однако, при определении первичного ключа должно соблюдаться требование "минимальности", т.е. в него не должны входить те атрибуты, которые можно отбросить без ущерба для основного свойства первичного ключа - однозначно определять кортеж.
2. Отсутствие упорядоченности кортежей(таблица с переставленными строками остаётся той же самой таблицей).
3. Отсутствие упорядоченности атрибутов (таблица с переставленными столбцами остаётся той же самой таблицей).
4. Все значения атрибутов отношения атомарные(в каждой позиции на пересечении столбца и строки расположено только одно значение).

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

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

Алгеброй называется множество объектов с заданной на нём совокупностью операций, замкнутых относительного этого множества. Коддом было предложено 8 операций, хотя это множество избыточное, так как некоторые операции могут быть представлены друг через друга.

Теоретико-множественные операции:

1. Объединение отношений.Результатом объединения двух отношений является отношение, включающее все кортежи, входящие хотя бы в одно из отношений-операндов. Обозначение: R₃ = R₁ È R₂. Операция коммутативна.

2. Пересечение отношений. Результатом пересечения двух отношений является отношение, включающее все кортежи, входящие в оба отношения-операнда. Обозначение: R₃ = R₁ Ç R₂. Операция коммутативна.

3. Разность отношений. Отношение, являющееся разностью двух отношений включает все кортежи, входящие в отношение-первый операнд, такие, что ни один из них не входит в отношение, являющееся вторым операндом. Обозначение: R₃ = R₁ \ R₂. Операция некоммутативна.

Пример на первые три операции:

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

R₁ = (Номер зачетки, ФИО, Группа) – список студентов, сдававших экзамен в сентябре;

R₂ = (Номер зачетки, ФИО, Группа) – список студентов, сдававших экзамен в декабре;

R₃ = (Номер зачетки, ФИО, Группа) – список студентов, сдавших экзамен по курсу до января месяца;

Ударим реляционной алгеброй по следующим вопросам:

а) Какие студенты сдавали два раза, но так и не сдали экзамен?

Ответ: R = R₁ Ç R₂ \ R₃.

б) Какие студенты сдавали экзамен только один раз, и сдали его?

Ответ: R = (R₁ \ R₂ Ç R₃) È (R₂ \ R₁ Ç R₃).

в) Какие студенты смогли сдать экзамен только со второго раза?

Ответ: R = R₁ Ç R₂ Ç R₃.

г) Какие студенты сдавали экзамен один раз, не сдали, и больше не появлялись?

Ответ: R = (R₁ \ R₂) È (R₂ \ R₁) \ R₃.

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

4. Прямое произведение отношений (расширенное декартово произведение). Результатом прямого произведения двух отношений является отношение, кортежи которого являются конкатенацией (сцеплением) кортежей первого и второго операндов. Обозначение: R₁ Ä R₂. Операция коммутативна. Операция используется для получения отношения, которое характеризует все возможные комбинации между элементами отдельных множеств.

Специальные реляционные операции:

1. Ограничение отношения (горизонтальная фильтрация). Результатом ограничения отношения по некоторому условию является отношение, включающее кортежи отношения-операнда, удовлетворяющее этому условию. Обозначение: R[a(r)], где a - булевское выражение, составленное из термов сравнения с помощью связок «И», «ИЛИ», «НЕ» и скобок. Унарная операция.

На интуитивном уровне операцию ограничения лучше всего представлять как взятие некоторой "горизонтальной" вырезки из таблицы. Пример: выбрать из R₃ студентов из группы 21402. Запишем так: R₄ = R₃ [Группа = 21403].

1. Проекция отношения (вертикальная фильтрация). Результатом проекции отношения R на заданный набор его атрибутов B является отношение, кортежи которого производятся путем взятия соответствующих значений из кортежей отношения-операнда. Обозначение: R[B]. Значения, не принадлежащие атрибутам из набора В, удаляются. Унарная операция.

Продолжаем наш пример: R = R4[Номер зачетки, ФИО].

1. Соединение отношений (соединение по условию). При соединении двух отношений R и Q по некоторому условию b образуется результирующее отношение, кортежи которого являются конкатенацией кортежей первого и второго отношений и удовлетворяют этому условию. Обозначение: R [b]Q.

По определению результатом операции сравнения является отношение, получаемое путем выполнения операции ограничения по условию b прямого произведения отношений R и Q. Операция соединения называется операцией эквисоединения, если условие соединения имеет вид (a = b), где a и b - атрибуты разных операндов соединения. Такое соединения применяется к паре отношений R и Q, обладающих общим атрибутом (т.е. атрибутом с одним и тем же именем и определенным на одном и том же домене). На интуитивном уровне это способ связи таблиц, имеющих одинаковое по смыслу поле.

1. Деление отношений. Пусть заданы два отношения – R(a₁, a₂, ..., a_n, b₁, b₂, ..., b_m) и T(b₁, b₂, ..., b_m). Будем считать, что атрибут b_i отношения R и атрибут b_i отношения T не только обладают одним и тем же именем, но и определены на одном и том же домене. Назовем множество атрибутов {a_j} составным атрибутом A, а множество атрибутов {b_j} - составным атрибутом B. После этого будем говорить о реляционном делении бинарного отношения R(A,B) на унарное отношение T(B). Результатом деления является унарное отношение Q(A), состоящее из таких кортежей v, которые в отношении R фигурировали как кортежи-сцепления <v, w>, в которых множество значений {w} включало множество значений атрибута B в отношении T. Обозначение: R[A:B]T.

Предположим, что имеются два отношения: Студенты(Имя, Группа) и Имена(Имя), причем унарное отношение Имена содержит все имена студентов в университете. Тогда после выполнения операции реляционного деления отношения Студенты на отношение Имена будет получено унарное отношение, содержащее номера групп, в которых студенты обладают всеми возможными в университете именами.