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

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

Как известно, алгебра есть множество вида

А: < H, S > , где

H -носитель (в данном случае - множество нормализованных отношений);

S -сигнатура (в данном случае - множество операций над отношениями).

Все множество S операций реляционной алгебры разбиты на два подмножества:

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

- объединение U Rrez=R1 U R2,

- пересечение ∩ Rrez=R1 ∩ R2,

- разность \ Rrez=R1 \ R2,

- декартово произведение Rrez= R1  R2.

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

- проекция Rrez (А) = R[A],

- ограничение Rrez = R1[булевское выражение],

- соединение Rrez = R1[булевское выражение]R2,

- деление Rrez = R1  R2.

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

Пример с указанными операциями представлен на рис. 3.8. Для имен атрибутов приняты следующие сокращения: ШД – шифр детали, ШМ – шифр материала, ЕИ – единица измерения, НР – норма расхода, НМ – наименование материала, ШМ" – шифр материала на складе.

Исходные отношения R1, R2 и R3:

R1 (ШД, ШМ, ЕИ, НР) R2 (ШД, ШМ, ЕИ, НР) R3 (ШМ", НМ)

д1 м2 1 15 д2 м5 3 3 м2 ст-5

д2 м5 3 3 д2 м3 2 15 м9 ст-7

д2 м9 3 5

д3 м2 1 10

На рис. 3.9 представлен пример декартова произведения отношений R2 и R3.

Rrez (ШД, ШМ, ЕИ, НР, ШМ", НМ)

д2 м5 3 3 м2 ст-5

д2 м3 2 15 м2 ст-5

д2 м5 3 3 м9 ст-7

д2 м3 2 15 м9 ст-7

Рис. 3.9. Декартово произведение двух отношений

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

ПРОЕКЦИЯ

Операция унарна и предназначена для уменьшения степени отношения.

Пусть имеется исходное отношение R1(A1,..., An) и список атрибутов А. Проекция отношения R1 на список А обозначается следующим образом:

Rrez (A) = R1 [A] или _A(r)  { t(A) | tr }.

где - [ ] (квадратные скобки) являются операционными (или _A(r)), т.е. используются для обозначения операции ПРОЕКЦИЯ (рис.10.a).

Рис. 3.8. Теоретико-множественные операции над отношениями.

ОГРАНИЧЕНИЕ (СЕЛЕКЦИЯ)

Операция ОГРАНИЧЕНИЕ (селекция, выборка) также, как и проекция, является унарной операцией, но в отличие от проекции ориентирована на выделение нужных строк отношения.

Пусть исходное отношение задано схемой: R1 (A1, . . . , An).

Селекцией _{A = a}(r) называется отношение r (R) = _{A = a}(r){tr | t(A)=a}.

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

Операцию ограничения также записывают следующим образом:

Rrez (A1, ..., An) = R1[булевское выражение для значений атрибутов R1].

На интуитивном уровне операцию ограничения лучше всего представлять как взятие некоторой "горизонтальной" вырезки из отношения-операнда (R1 из рис.3.9).

Rrez (A) = R1 [ШМ, ЕИ] Rrez (A) =  _{ШМ = ”м2” OR ЕИ = ”1”}

Результат Результат

м2 1 м2 1

м5 3

м9 3

a) _A(r) – проекция b) селекция – R1 [ШМ=”м2” OR ЕИ=”1” ]

Рис. 3.10. Пример операции проекции (a) и селекции (b)

СОЕДИНЕНИЕ

Операция СОЕДИНЕНИЕ двух и более отношений является важнейшей операцией. При этой операции кортежи одного отношения конкатенируют (соединяются) с выборками другого, точно также, как и при декартовом произведении двух отношений, но при условии, что булевское выражение, в каждый терм которого входят атрибуты обоих отношений, принимает значение "истина".

Пусть r(R) и s(S) – отношения. Соединением r и s называется отношение

r  s = q(RS) = {t(RS) |  t_r  r, t_s  s : t_r = t(R), t_s = t(S)}.

Итак, для двух исходных отношений, заданных схемами:

R1 (A₁, ..., A_n) и R2 (B₁, ..., B_m), в результате операции соединения получается отношение со схемой

Rrez (A₁, . . . , A_n, B₁, . . . ,B_m) = R1 [булевское выражение] R2.

В булевском выражении термы имеют вид:

(A_i  B_j), где - атрибуты А_i и B_j определены на одном домене, а термы сравнения () выбираются из множества: { = , < > , > , < , >= , <= }.

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

Если r(R), s(S) – отношения, A_i R , B_i S и dom(A_i) = dom(B_i), 1  i  n (A_i и B_i могут быть одинаковыми). Эквисоединением r и s по A₁, A₂,…,A_n и B₁, B₂,…, B_m называется отношение q(RS) = {t | t_r r, t_ss, t(R) = t_r, t(S) = t_s, t(A_i) = t(B_i)}.

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

(A₁=B₁) AND (A₂=B₂) AND ... AND (A_k=В_k).

Если RS = {B₁B₂…B_l} = , то соединение rs, результатом которого является множество кортежей t(A₁A₂…A_k C₁C₂…C_m), таких, что t(A₁A₂…A_k)r и t(C₁C₂…C_m)s, называется декартовым произведением отношений r и s и обозначается r  s.

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

Rrez(A₁, ..., A_n, B₁, ..., B_m) = R1 [(булевское выражение)] R2 =

= (R1  R2) [(булевское выражение)],

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

На рис. 3.11 представлен пример операции эквисоединения отношений R1 и R3, исходное состояние которых показано на рис.3.8.

Rrez (ШД, ШМ, ЕИ, НР, ШМ", НМ) = [R1.ШМ=R3. ШМ"].

д1 м2 1 15 м2 ст-5

д2 м9 3 5 м9 ст-7

д3 м2 1 10 м2 ст-5

Рис. 3.11. Пример операции эквисоединения R1 и R3

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

ДЕЛЕНИЕ

Пусть r(R) и s(S) – отношения, SR. Положим R = R - S. Тогда r, разделенное на s – это отношение r(R)={t | t_ss t_rr: t_r(R)=t & t_r(S)=t_s}.

Отношение r_rez – частное от деления r на s, что обозначается r_rez = rs. Иначе rs – это максимальное подмножество r_rez множества _rrez(r), такое, что r_rez  s  r. Соединение  – здесь декартово произведение.

Чтобы понять сущность операции деления отношений, целесообразно рассмотреть упрощенный пример.

Пусть задано отношение R1(ШД, ШМ) (рис. 3.12.а), которое задает возможные варианты изготовления деталей из разных материалов. И задано отношение R2 (рис. 3.12.b), указывающее, какие материалы хранятся на складе.

Рис. 3.12. R1 - Варианты изготовления. R2 - Материалы на складе

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

Фактически R2 есть подмножество материалов, из которых может быть сделана деталь д2: {м5, м9}  {м3, м5, м9}.

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

Rrez (ШД) = R1[ШМ  ШМ"]R2 , где  - символ операции деления.

Рассмотрим пример использования алгебры отношений при составлении запросов к базе данных. Пусть БД содержит отношения R1(ШД, ШМ, НР) и R2(ШМ", НМ).

Запрос. Перечислить шифры материалов (ШМ) и их наименования (НМ), которые идут на изготовление одной детали в количестве большем чем 25 кг.

На языке реляционной алгебры запрос будет реализован на основе следующих операций:

Rrez (ШМ, НМ) = ((R1[НР > 25]) [ШМ]) [ШМ=ШМ"] R2[ШМ, НМ]

Круглые скобки определяют последовательность действий:

1) Ограничение отношения R1;

2) Проектирование промежуточного отношения;

3) Эквисоединение с R2;

4) Проектирование полученного результата.

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

Вопросы для самопроверки по теме 4.1

1. Дайте определение понятию атомарный атрибут.

2. Какой смысл имеет в теории баз данных понятие схемы отношения?

3. Приведите определение понятия ‘отношение’.

4. Какие существуют разновидности ассоциаций между отношениями?

5. Что такое реляционная алгебра?

6. Приведите пример унарной и бинарной алгебраической операции?

7. На какие группы подразделяются алгебраические операции?

8. Что такое состояние отношения и схема БД?

9. Перечислите бинарные операции реляционной алгебры.