Базы Данных - Сибилев, 2007

121

сываются в виде предиката, содержащего атрибуты отношений-

источников данных.

Любой запрос к РБД может быть сформулирован в одном выражении РА или формуле РИ. Это свойство называется свойством реляционной пол-

ноты ЯМД. Реляционная полнота – это одно из основных требований,

предъявляемых к реализациям ЯМД.

РА и РИ эквивалентны, т.е., для каждого выражения РА существует формула РИ, производящая тот же результат, и наоборот. Параллельное существование в РМД двух принципиально различных, но эквивалентных механизмов манипулирования данными обычно объясняют историческими причинами («так сложилось»!). Однако, по-видимому, причины глубже,

т.к. все дожившие до настоящего времени реализации реляционных ЯМД используют оба абстрактных механизма.

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

6.2.1 Основные операции

Первый вариант набора операций РА был предложен Э. Коддом в

1970 г. Он содержал 8 операций. Позднее различными авторами были предложены различные дополнения этого набора. Мы здесь познакомимся с операторами, обеспечивающими основные потребности манипулирова-

ния данными.

Реляционная алгебра замкнута относительно множества отношений,

т.е., операндами операций РА являются отношения, и любая операция РА производит отношение.

Операция РА по сути является набором правил построения

–схемы производного отношения из атрибутов схем операндов и

–тела производного отношения из кортежей операндов.

Из имен отношений, знаков операций РА и скобок можно строить

выражения произвольной степени сложности. Очень сложные запросы к

122

реляционной БД можно сформулировать в виде одного выражения РА. По-

этому реляционная алгебра обладает большой выразительной мощностью.

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

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

Выделяют две группы операций РА.

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

−объединение;

−разность;

−пересечение;

−расширенное прямое произведение.

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

−селекция (ограничение, выборка);

−проекция;

−соединение по условию;

−естественное соединение;

−взятие реляционного частного (реляционное деление)

−переименование.

Этот набор операций избыточен, так как некоторые из них выража-

ются через другие. Тем не менее, все они включаются в состав алгебры как

элементарные, исходя из интуитивных потребностей пользователей БД. В

этом подразделе приведены формальные определения операций, а в сле-

дующем – синтаксис абстрактного языка РА.

Специфика отношений накладывает ограничения на операции. Так,

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

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

ресекающимися схемами.

123

Введём определения операций. Будем обозначать подмножества ат-

рибутов символами X, Y, Z,…, а значения подмножеств – символами

X:x, Y:y, Z:z,….

Определение 1. Говорят, что отношения со схемами R1(X) и R2(Y)

совместимы по объединению, если X = Y.

Определение 2. Говорят, что отношения со схемами R1(X) и R2(Y) совместимы по взятию расширенного прямого произведения, если

X ∩ Y = .

Определение 3. Объединением отношений со схемами R1(X) и

Определение 4. Разностью отношений со схемами R1(X) и R2(X)

называется отношение R = R1 – R2, имеющее А) схему R(X),

В) тело, составленное только из тех кортежей X:x R1, которые не принадлежат R2.

Пример:

Определение 5. Пересечением отношений со схемами R1(X) и R2(X) называется отношение R = R1 ∩ R2, имеющее

А) схему R(X),

В) тело, составленное только из тех кортежей X:x R1, которые

принадлежат R2.

Это неэлементарная операция. Она представляется через операции

объединения и разности:

R1 ∩ R2 = R1 R2 – (R1 – R2) (R2 – R1 ).

Определение 6. Пусть отношения со схемами R1(X) и R2(Y) со-

вместимы по взятию расширенного прямого произведения. Расширенным

Селекция или ограничение по условию – это унарная операция. Она

производит отношение, составленное из кортежей операнда, удовлетво-

126

ряющих заданному условию. Это можно представить себе как вычеркива-

ние ненужных строк таблицы.

Определение 7. Пусть R – отношение со схемой R1(X) и F(X) –

предикат, определенный на атрибутах схемы. Селекцией отношения R по

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

Определение 8. Пусть R – отношение со схемой R(X, Y). Проек-

цией отношения R на X называется отношение Rπ = πx(R), имеющее А) схему Rπ(X),

Б) тело, составленное из всех подкортежей X:x, для которых суще-

ствуют подкортежи Y:y такие, что { X:x, Y:y} R.

128

смысл только для сравнимых, т.е. определенных на общем домене, атрибу-

тов.

Естественное соединение. Это наиболее важный для практики вид

соединения. Эта операция применяется к отношениям, схемы которых имеют одноименные атрибуты, определенные на общем домене, т.е. к от-

ношениям с пересекающимися схемами.

Определение 10. Пусть R1 и R2 – отношения со схемами R1(X, Y)

и R2(Y, Z). Естественным соединением этих отношений называется отношение R = R1 R2, имеющее

А) схему R(X, Y, Z),

Б) тело, образованное всеми кортежами {X:x, Y:y, Z:z} таки-

ми, что в R1 существует кортеж {X:x, Y:y} и в R2 – кортеж {Y:y,

Z:z}.

Определение 11. Пусть X и Y – подмножества атрибутов, R1 и R2

- отношения со схемами R1(X, Y), R2 (Y). Реляционным частным

Здесь символом ‘+’ помечены кортежи R1, подкортежи которых вой-

дут в реляционное частное.

Это неэлементарная операция. Она выражается через операции про-

екции, прямого произведения и разности.

Переименование атрибутов. Эта операция вводится в состав опе-

раций РА для разрешения конфликтов имен в бинарных операциях. В ре-

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

димость вычислить соединение по условию отношений с пересекающими-

ся схемами или построить объединение отношений с “почти совпадающи-

ми” схемами, отличающимися только именами атрибутов и т.п.

Эта операция сохраняет тело отношения, изменяя лишь имена ука-

занных атрибутов:

ρА →С (R (A, B)) = R (C, B).

130

6.2.2 Синтаксис реляционных выражений

Определим теперь синтаксис для операций РА, который будем ис-

пользовать в дальнейшем4. Основной синтаксической единицей является

выражение РА, производящее отношение. Любое выражение является бе-

зымянным производным отношением.

выражение ::= унарное-выражение | бинарное-выражение;

унарное-выражение ::= переименование | выборка | проекция;

переименование ::= терм RENAME атрибут AS атрибут;

терм ::= отношение | (выражение);

выборка ::= терм WHERE предикат;

предикат ::= сравнение | предикат AND предикат |

предикат OR предикат | NOT предикат5;

сравнение ::= символ θ символ;

символ ::= атрибут | константа;

θ ::= < | > | =;

Проекция ::= терм | терм [список];

Бинарное-выражение ::= проекция бинарная-операция выражение;

Бинарная-операция ::= UNION | INTERSECT | MINUS | TIMES | JOIN | DIVIDEBY;

Здесь атрибут – идентификатор, список – список разделенных за-

пятыми атрибутов, константа – литеральное значение.

4 Его не следует рассматривать как язык конечного пользователя. Это просто основа для обсуждения реляционных операторов.

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