Реляционная алгебра
В этом разделе на ряде примеров рассматриваются операции реляционной алгебры [11]. Для представления каждой операции будем использовать терминологию как алгебры, так и исчисления. Последняя базируется на системе понятий, использованной Коддом. Пять операций являются основными:
– проекция;
– объединение;
– разность;
– декартово произведение;
– селекция.
Другие часто используемые операции пересечения, соединения и деления можно выразить через пять основных операций. Ниже представлены отношения, используемые в примерах [11].
P(D 1 | D2, | D3) | Q(D4 | D5) | R(M, | P, | Q, | T) | S(A, | B) | |||||||||||
1 | 11 | x | x | 1 | x | 101 | 5 | a | 5 | a | |||||||||||
2 | 11 | у | x | 2 | y | 105 | 3 | a | 10 | b | |||||||||||
3 | 11 | z | y | 1 | z | 500 | 9 | a | 15 | c | |||||||||||
4 | 12 | x | w | 50 | 1 | b | 2 | d | |||||||||||||
w | 10 | 2 | b | 6 | a | ||||||||||||||||
w | 300 | 4 | b | 1 | b | ||||||||||||||||
Описание каждого отношения состоит из имени отношения, за которым в круглых скобках следует список атрибутов (это описание называется интенсионалом или схемой отношения). Под описанием приведено некоторое заполнение кортежей отношения (экстенсинал отношения). В последующих примерах буквы R и S
используются для обозначения отношений, а буквы A и B – для обозначения списка атрибутов (для простоты можно считать, что список состоит из единственного атрибута).
Проекция
Алгебра | Исчисление | ||
R[A] | {t[A] t ?R} |
Операция проекции представляет собой выборку из каждого кортежа отношения значений атрибутов, входящих в A, и удаление из полученного отношения повторяющихся строк. В исчислении t обозначает «кортежную» переменную, значениями которой являются кортежи исходного отношения R, a t[A] – часть кортежа R с атрибутами из A.
В соответствии с определением отношения неявно предполагается удаление дубликатов кортежей результирующего отношения.
Пример


Объединение
Алгебра |
Исчисление |
R ![]() |
{t| t ?R ?t ?S} |
Пример


Разность
Алгебра |
Исчисление |
R –S |
{t| t ?R ?t ?S} |


Пример


Декартово произведение
Алгебра |
Исчисление |
R ![]() |
{(r||s) | r ?R ?r ?S} |
Степень(R

Мощность(R

Отсюда следует, что результирующее отношение может иметь очень большие размеры. (На практике используется ограниченны вариант этой операции, называемый соединением.) Пусть
RA=R[M,T] и RB=R[Q,T]

т.е.

Тогда

Степень результирующего отношения равна 4(2+2), а мощность – 8 (2×4).
Селекция (Ограничение)
Алгебра |
Исчисление |
(a) R[A?v] |
{t| t ?R ?(t[A]?v)} |
(б) R[A?B] |
{t| t ?R ?(t[A]?t[B])} |
используется для обозначения одной из операций сравнения (<, ?, =, ?, ?, >).
Примеры
P[D1>D2]=Ø (пустое множество) поскольку в отношении отсутствуют кортежи, где D1>D2.

Пересечение
Алгебра |
Исчисление |
R ![]() |
{t| t ?R ?t ?S} |

Пример


Соединение
Алгебра |
Исчисление |
R[A?B]S |
{(r||s) | r ?R ?s ?S ?(r[A]?s[B])} |
Имеется несколько вариантов операции соединения:
а) тета- и эквисоединение. При этой операции A и B являются совместимыми атрибутами соединения, а степень результирующего отношения равна сумме степеней отношений-операндов. Такое соединение называется ?-соединением (тета-соединением). В случае сравнения на равенство соединение называется экви-соединение;
б) естественное соединение. В этом случае атрибуты соединения имеют общие (одинаковые) домены, и после соединения один из атрибутов отбрасывается. Степень результирующего отношения на единицу меньше суммы степеней отношений-операндов;
в) композиция. Это соединение отличается от естественного тем, что из результирующего отношения удаляются оба атрибута соединения. Поэтому степень результирующего отношения на две единицы меньше суммы степеней отношений-операндов.
Примеры
Тета-соединение R[Q>A]S
При выполнении соединения необходимо для каждого кортежа из R взять значение атрибута Q и сравнить его со значением атрибута A из каждого кортежа S. В результате получим

Следует отметить, что кортеж <w 50 1 b> отношения R не вошел в результирующее отношение.
Естественное соединение P[D3 =D4]Q


Деление
Алгебра |
Исчисление |
R[A÷B]S |
{r[![]() ![]() ![]() |
B являются совместимыми и/или общими атрибутами деления. Для упрощения объяснения можно считать R бинарным отношением, состоящим из A и дополнения A, которое обозначается



• выбрать допустимые строки кортежей r[

из R[


• в результирующее отношение входят кортежи r, для которых выполняется S[B]HgR(r[

Примеры
Р[D3>÷D4]=Ø (пустое множество), так как




Следовательно, подходящие
