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

Пусть дано множество отношений R = {r1, r2,…},

где ri = {t1, t2,…}| ti = (d1, d2,...), di D} - отношение, t = (d1, d2,...) – кортеж,

di Di - значение атрибута Ai, Di – домен атрибута Ai, множество доменов D = {D1, D2,…},

множество атрибутов A = {A1, A2,...},

множество схем отношений Rel(R) = {rel(r1), rel(r2),…}? где rel(ri) = (A1, A2,..., An) - схема отношения ri

и множество операторов Σ={ , ∩, \, , ¬, δB(r), π rel(r), ><, >θ<},

гдеоператор объединения отношений,

∩- оператор пересечения отношений,

\- оператор разности отношений,

- оператор прямого произведения отношений, ¬ - оператор дополнения отношения,

δB(r) - оператор выбора кортежа по условию B,

π rel’(r) - оператор проекции отношения на новую схему rel, >< - оператор естественного соединения отношений, >θ< - оператор θ - соединения отношений, : - оператор деления отношений.

Совокупность R и ∑ представляют реляционную алгебру

Apел=<R, ∑>,

где R – носитель алгебры, ∑ – алгебраические операторы. Задание логических операторов Ψ= {&, , ¬} и опера-

* по материалам [14]

торов сравнения θ={=, ≠, >, ≥, <, ≤} позволяют формировать условия исполнения алгебраических операций. Совокупность отношений и множества операторов ∑, Ψ, θ представляют алгебраическую систему:

Мрел=<R, ∑, Ψ, θ>,

где {∑, Ψ, θ} – сигнатура алгебраической системы. Рассмотрим исполнение алгебраических операций над

пятью отношениями r1, r2, r3, r4 и r5. Поскольку наглядно и наиболее удобно представлять отношения таблицами, то исполнение операций проследим в графической форме. Имена атрибутов в таблицах обозначены прописными буквами латинского алфавита с индексами А1, А2, A3, A4, A5 и А6, а значения атрибутов - строчными буквами латин-

ского алфавита с индексами {a1, a2, a3, a4, b1, b2, b3, b4, c1, c2, d1, d2, d3} и цифрами {1, 2, 3}.

(A1, A5),

r4- (A4, A5, A6). В шапках таблиц ключи подчеркнуты и выделены полужирным шрифтом.

1.3.1.1. Унарные операции

Оператор выбора δB(r) позволяет извлекать из отно-

118 Математическая логика

шения r кортежи по условию В, и создавать новое отношение. Условия выбора В описывают с помощью арифметических операторов сравнения θ = {=, ≠, >, ≥, <, ≤} и/или логических операторов Ψ= {&, , ¬}.

Например, B=(Аi=ki) означает «выбрать в заданном отношении кортежи, для которых атрибут Аi имеет значение di=ki». Также можно описать B=(Аi≠ki), B=(Аi>ki ), B=(Аi≥ki ),… Условие B=((Ai,…, Aj,..., Ak)=(ki,…, kj,…, kk))

означает «выбрать в заданном отношении кортежи, для которых атрибут Ai имеет значение ki, атрибут Aj имеет значение kj, атрибут Ak имеет значение kk». Если условия заданы логическими операторами, то B=(Bi&Bj) означает «выполнить условие Bi и Bj», а B=(Bi Bj) – «выполнить ус-

ловие Bi или Bj» и т. п.

Результатом исполнения операции выбора будет но-

вое отношение r’= δB(r)={ t’| t’ r, B, rel(r’)=rel(r)} r.

Пример 1.80. Выбрать кортежи отношения r1 по зна-

чению ключа А1=а2, т.е. r’1={t’| B:=(A1=a2)}, r2 - по значению атрибута A3=1, т.е. r’2={t’| B:=(A3=1)}, r5 – по значениям атрибутов {A1=a1, A2=b1, A3=1}, т.е. r’5={t’| B:=(A1=a1)&(A2=b1)&(A3=1)}.

В табл. 1.12а. - 1.12с. соответственно показаны ре-

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

В программировании это будет записано так: r’=SELECT (отношение, УСЛОВИЯ).

Для данного примера это будет: r’1=SELECT(r1, A1=’a2’), r’2=SELECT(r2, A3=1),

r’5=SELECT(r5, A1=’a1’ AND A2=’b1’ AND A3=1).

Значения атрибутов заключены в апострофы. Это означает, что строка символов, заключенная в апострофы является значением поля записи. Данное правило относится к любым одиночным символам и строкам, представляющим значение атрибута. Это делается для того, чтобы отличить значение от имени атрибута, переменных параметров и числовых констант.

При программировании логические связки {&, , ¬} замещаются операторами AND, OR и NOT соответственно.

Пример 1.81. Выбрать кортежи отношения r1 по зна-

чению атрибута A3=¬3, т.е. r’1={t’| B:=(A3=¬3}, r2 - по зна-

чению атрибутов A3=1 или A2=b1, т.е. r’2={t’| B=(A3=1 A2=b1}, r5 – по значению атрибутов (A1=a1, A2=b1,

A3=1 и A4≠c2), т.е. r’5={t’| B=((A1=a1)&(A2=b1)&(A3=1)&(A4≠c2)}.

В программировании исполнение этих операций будет описано так:

r’1=SELECT(r1, A3=NOT 3) (см. табл. 1.13a), r’2=SELECT(r2, A3=1OR A2=’b1’) (см. табл. 1.13b),

r’5=SELECT(r5, A1=’a1’AND A2=’b1’AND A3=1AND A4=NOT’c2’) (см. табл. 1.13c.

данного отношения r со схемой rel(r)=(A1, A2,.., An) новое отношение r’ со схемой rel(r’)=(Ai, Aj,…, Ak), где 1≤i, j, k≤n, путем удаления и/или переупорядочения атрибутов.

Результатом выполнения этой операции будет новое отношение, удовлетворяющее новой схеме r’=πrel(r)={ t’|

|rel(r’)|≤|rel(r)|}.

Число атрибутов схемы формируемого отношения меньше или равно числа атрибутов схемы заданного отношения, т.е. |rel(r’)|≤|rel(r)|, а число кортежей формируемого отношения равно числу кортежей заданного отноше-

ния, т.е. |r’|=|r|.

Пример 1.82. Выбрать только ключи отношений r1, r3

иr5, т.е. rel(r’1)= (A1), rel(r’3)= (A1, A5), rel(r’5)=(A1, A2, A3).

Впрограммировании операцию проекции записывают

так r’=PROJECT(отношение, СПИСОК AТРИБУТОВ). Для данного примера это - r’1= PROJECT(r1, A1), r’3= PROJECT

(r3, A1, A5), r’5= PROJECT(r5, A1, A2, A3).

В таблицах 1.14а.-1.14с. соответственно показаны ре-