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

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

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

К основным операциям относятся следующие операции: объединение отношений; разность отношений; пересечение отношений; декартово произведение отношений; проекция; выборка; деление отношений; q-соединение отношений; естественное соединение; внешнее соединение отношений; полусоединение отношений.

Рассмотрим эти операции подробнее.

Объединение. Эта операция почти полностью соответствует операции объединения в теории множеств. Объединение отношений R и S, обозначаемое как RÈS, представляет собой множество всех таких кортежей, каждый из которых принадлежит R или S или обоим сразу. Операция объединения применяется только к совместимым отношениям одной арности, поэтому все кортежи в объединении имеют одинаковое число компонент.

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

Пересечение. RÇS обозначает множество всех кортежей, принадлежащих одновременно R и S. Ясно, что R и S должны иметь одинаковую арность и быть совместимы. Очевидно, что RÇS=R\(R\S)=S\(S\R).

Примеры.

Декартово произведение. Пусть R и S – отношения арности г и s соответственно. Тогда декартовым произведением RxS отношений R и S называется множество всех кортежей длины r+s, таких что, первые г компонент образуют кортежи, принадлежащие R, а последние s – кортежи, принадлежащие S.

Примеры.

Если имена столбцов в отношениях-сомножителях совпадают, то их помечают именами отношений, например, вместо A, B, C, D, E, F можно писать R.A, R.B, R.C, S.D, S.E, S.F.

Проекция. Сущность этой операции заключается в том, что в исходном отношении удаляются некоторые компоненты (атрибуты) и (или) переставляются оставшиеся. Пусть R – отношение арности г. Обозначим p_{i1, i2, …, im}(R), где i_j– целые числа в диапазоне от 1 до г, проекцию R на компоненты i₁, i₂, …, i_m, то есть множество m-ок, таких, что существует некоторый принадлежащий R кортеж b₁, b₂, …, b_r, удовлетворяющий условию a_j=bi_j.

Например, для построенияp_3,1(R) нужно из каждого кортежа, принадлежащего R, сформировать кортеж длины 2 из третьей и первой его компонентов в указанном порядке, то есть выписать 3-ю, затем 1-ю компоненты. При этом из каждой группы одинаковых кортежей в результирующем отношении оставляется только один кортеж (отношение – это множество кортежей, и оно не может содержать одинаковых, то есть совпадающих по всем компонентам кортежей).

Вместо номеров компонент (столбцов) часто используют атрибуты.

Выборка. Пусть F – формула, образованная:

1) операндами, являющимися константами или номерами компонент (атрибутами);

2) операциями сравнения: <, =, >, £, ³;

3) логическими операциямиL (И – конъюнкция),\/(ИЛИ – дизъюнкция), ù (НЕТ – отрицание).

В этом случаеs_F(R)есть множество всех таких кортежей t, принадлежащих R, что при подстановке i-го компонента вместо всех вхождений i (или соответствующего атрибута) в формулу F она станет истинной.

Например, s_2>3 обозначает множество кортежей, принадлежащих R, второй компонент которых больше третьего.

Заметим, что константы в формулах должны быть заключены в кавычки, это позволит отличить их от номеров или имен столбцов.

Пример.

Деление. Пусть R и S отношения арности r и s соответственно, причем r>s и S¹Æ. Предположим, что R определено на множестве атрибутов A, а S на множестве атрибутов B и BÍA. R¸S (частное) есть множество кортежей t длины r-s, таких, что для всех кортежей uÎS, кортеж tu принадлежит R ( здесь tu означает кортеж полученный приписыванием справа к кортежу t компонент кортежа u).

Пример.

q-соединение. q-соединение отношений R и S по столбцам i и j, записываемое R|><|_iqjS, где q – операция сравнения ( = , < и т. д. ), есть краткая запись выражения: s_iqj(RxS). Таким образом, q-соединение R и S представляет собой множество всех таких кортежей в декартовом произведении R и S, что i-й атрибут R находится в отношении q с j-м атрибутом отношения S. Если q является операцией “=”, то эта операция называется эквисоединением.

Естественное соединение. Эта операция играет фундаментальную роль в теории проектирования реляционных баз данных. Естественное соединение (обозначается Rê><êS) применимо лишь тогда, когда отношения имеют один или несколько общих атрибутов.

Вычислить Rê><êS можно следующим образом:

1) вычислить RxS;

2) для каждого атрибута А, который именует некоторый столбец в R и какой-либо столбец в S, выберем только те кортежи из RxS, у которых совпадают значения в столбцах R.A и S.A;

3) для каждого указанного выше атрибута А удалим столбец R.A.

Формально, если A₁, A₂,…, A_k являются общими атрибутами для R и S, то

Rê><êS = p_{i1, i2, …, im} (s_{R.A1=S.A1Ù…ÙR.Ak=S.Ak} (RxS)),

где i₁, i₂, …, i_m - упорядоченный список всех атрибутов RxS, за исключением атрибутов S.A₁, S.A₂, …, S.A_k.

Рассмотрим ряд примеров, реализующих вышеописанные операции.

Примеры.

Внешнее соединение. Левым внешним соединением RÉ<ïS отношений R и S называется отношение, содержащее все кортежи отношения Rï><ïS, а также кортежи R, не имеющие совпадающих значений в общих столбцах с отношением S. Для обозначения отсутствующих значений во втором отношении используется определитель NULL.

Аналогично вводится операция правого внешнего соединения Rï>ÌS. Существует также полное внешнее соединение RÉÌS, в результирующем отношении которого помещаются все кортежи из обоих отношений и в котором для обозначения несовпадающих значений кортежей используются определители NULL.

Полусоединение. Эту операцию можно определить с помощью операций “проекция” и “q-соединение”. А именно Rï>_iqjS=p_u(Rï><ï_iqjS). Здесь u это набор всех атрибутов отношения R. Аналогично определяются полусоединение по эквивалентности (когда q есть равенство) и полуестественное соединение Rï>S.

Примеры.

Пример, демонстрирующий выполнение полуестественного соединения отношений R и S.