4. Лекция: Базисные средства манипулирования реляционными данными: алгебра A Дейта и Дарвена

В этой лекции мы обсудим новый "минимальный" вариант алгебры, предложенный несколько лет тому назад Дейтом и Дарвеном. Как уже отмечалось в предыдущей лекции, возможно, новая алгебра не очень практична, но зато красива и элегантна.

Введение

Обсуждавшаяся в предыдущей лекции алгебра Кодда в большей степени базируется на теории множеств. Базовыми операциями являются переименование атрибутов, объединение, пересечение, взятие разности, декартово произведение, проекция и ограничение. Операция соединения общего вида, хотя и включается в алгебру, является вторичной и явно представляется через другие операции. Фундаментальная же в реляционном подходе операция естественного соединения выражается через соединение общего вида и в алгебру не включается. В терминах алгебры Кодда проще всего определяются алгебраические черты языка SQL, в частности общая семантика оператора SELECT.

Базисом предложенной Крисом Дейтом и Хью Дарвеном Алгебры A являются операции реляционного отрицания (дополнения), реляционной конъюнкции (или дизъюнкции) и проекции (удаления атрибута). Реляционные аналоги логических операций определяются в терминах отношений на основе обычных теоретико-множественных операций и позволяют выражать напрямую операции пересечения, декартова произведения, естественного соединения, объединения отношений и т. д. Путем комбинирования базовых операций выражаются операции переименования атрибутов, соединения общего вида, взятия разности отношений. Алгебра A позволяет лучше осознать логические основы реляционной модели, хотя, безусловно, является в меньшей степени ориентированной на практическое применение, чем алгебра Кодда. Даже сами авторы Алгебры A, Дейт и Дарвен, в своем учебном языке Tutorial D используют не Алгебру A напрямую, а некоторое ее надмножество, в большей степени напоминающее алгебру Кодда.

Базовые операции Алгебры A

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

Пусть r – отношение, A – имя атрибута отношения r, T – имя соответствующего типа (т. е. типа или домена атрибута A), v – значение типа T. Тогда:

  • заголовком Hr отношения r называется множество атрибутов, т.е. упорядоченных пар вида <A, T>. По определению никакие два атрибута в этом множестве не могут содержать одно и то же имя атрибута A;
  • кортеж tr, соответствующий заголовку Hr, – это множество упорядоченных триплетов вида <A, T, v>, по одному такому триплету для каждого атрибута в Hr;
  • тело Br отношения r – это множество кортежей tr. Заметим, что (в общем случае) могут существовать такие кортежи tr, которые соответствуют Hr, но не входят в Br.

Заметим, что заголовок – это множество (упорядоченных пар вида <A, T>), тело – это множество (кортежей tr), и кортеж – это множество (упорядоченных триплетов вида <A, T, v>). Элемент заголовка – это атрибут (т. е. упорядоченная пара вида <A,T>); элемент тела – это кортеж; элемент кортежа – это упорядоченный триплет вида <A, T, v>. Любое подмножество заголовка – это заголовок, любое подмножество тела – это тело, и любое подмножество кортежа – это кортеж.

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

Во всех формальных спецификациях exists обозначает квантор существования; exists tr означает «существует такой tr, что». Символ «» означает принадлежность одного множества другому; trBr означает, что элемент tr принадлежит множеству Br. Выражение trBr означает, что элемент tr не принадлежит множеству Br. Операции minus и union являются традиционными теоретико-множественными операциями взятия разности и объединения множеств.

Поскольку некоторые базовые операции Алгебры A имеют названия обычных логических операций, чтобы избежать путаницы, имена реляционных операций берутся в угловые скобки: <NOT>, <AND>, <OR> и т. д. В исходный базовый набор операций входят операции реляционного дополнения <NOT>, удаления атрибута <REMOVE>, переименования атрибута <RENAME>, реляционной конъюнкции <AND> и реляционной дизъюнкции <OR>.

Операция реляционного дополнения

Пусть s обозначает результат операции <NOT> r. Тогда:

  • Hs = Hr (заголовок результата совпадает с заголовком операнда);
  • Bs = {ts : exists tr (tr Br and ts = tr) } (в тело результата входят все кортежи, соответствующие заголовку и не входящие в тело операнда).

Операция <NOT> производит дополнение s заданного отношения r. Заголовком s является заголовок r. Тело s включает все кортежи, соответствующие этому заголовку и не входящие в тело r.

Видимо, следует пояснить, почему реляционный аналог операции логического отрицания называется здесь операцией реляционного дополнения. Во-первых, термин «дополнение» полностью соответствует сути операции <NOT>: тело результата операции <NOT> r является дополнением Br до полного множества кортежей, соответствующих Hr. Во-вторых, это не противоречит природе булевской операции NOT: у булевского типа имеются всего два значения – true и false, и NOT true = false, а NOT false = true. (Кстати, обратите внимание, что операцию NOT в трехзначной логике (см. лекцию 1) уже нельзя считать операцией дополнения.)

Чтобы привести пример использования операции <NOT>, предположим, что в состав домена ДОПУСТИМЫЕ_НОМЕРА_ПРОЕКТОВ, на котором определен атрибут ПРО_НОМ отношения НОМЕРА_ПРОЕКТОВ с рис. 4.1 слева, входит всего пять значений {1, 2, 3, 4, 5}. Тогда результат операции <NOT> НОМЕРА_ПРОЕКТОВ будет таким, как показано на рис. 4.1 справа.

Операция удаления атрибута

Пусть s обозначает результат операции r <REMOVE> A. Для обеспечения возможности выполнения операции требуется, чтобы существовал некоторый тип (или домен) T такой, что <A, T> Hr (т. е. в состав заголовка отношения r должен входить атрибут A). Тогда:

Результат операции <NOT> НОМЕРА_ПРОЕКТОВ
Рис. 4.1.  Результат операции <NOT> НОМЕРА_ПРОЕКТОВ

  • Hs = Hr minus {<A, T>}, т. е. заголовок результата получается из заголовка операнда изъятием атрибута A;
  • Bs = {ts : exists tr exists v (tr Br and v T and <A,T,v> tr and ts = tr minus {<A,T,v>})}, т. е. в тело результата входят все кортежи операнда, из которых удалено значение атрибута A.

Операция <REMOVE> производит отношение s, формируемое путем удаления указанного атрибута A из заданного отношения r. Операция эквивалентна взятию проекции r на все атрибуты, кроме A. Заголовок s получается теоретико-множественным вычитанием из заголовка r множества из одного элемента {<A, T>}. Тело s состоит из таких кортежей, которые соответствуют заголовку s, причем каждый из них является подмножеством некоторого кортежа тела отношения r.

Примером операции REMOVE (конечно же, очень похожим на пример использования операции PROJECT из предыдущей лекции) является СЛУЖАЩИЕ REMOVE ПРО_НОМ (получить данные о служащих, участвующих в проектах). Результат этой операции над отношением СЛУЖАЩИЕ, тело которого приведено в верхней части рис. 4.2, показан на рис. 4.2 внизу.

Результат операции СЛУЖАЩИЕ REMOVE ПРО_НОМ
Рис. 4.2.  Результат операции СЛУЖАЩИЕ REMOVE ПРО_НОМ

Операция переименования

Пусть s обозначает результат операции r <RENAME> (A, B). Для обеспечения возможности выполнения операции требуется, чтобы существовал некоторый тип T, такой, что <A, T> Hr, и чтобы не существовал такой тип T, что <B, T> Hr. (Другими словами, в схеме отношения r должен присутствовать атрибут A и не должен присутствовать атрибут B.) Тогда:

  • Hs = (Hr minus {<A, T>}) union {<B, T>}, т. е. в схеме результата B заменяет A;
  • Bs = {ts : exists tr exists v (tr Br and v T and <A, T, v> tr and ts = (tr minus {<A, T, v>}) union {<B, T, v>})}, т. е. в кортежах тела результата имя значений атрибута A меняется на B.

Операция <RENAME> производит отношение s, которое отличается от заданного отношения r только именем одного его атрибута, которое изменяется с A на B. Заголовок s такой же, как заголовок r, за исключением того, что пара <B, T> заменяет пару <A, T>. Тело s включает все кортежи тела r, но в каждом из этих кортежей триплет <B, T, v> заменяет триплет <A, T, v>.

По причине очевидности пример использования этой операции мы приводить не будем.

Операция реляционной конъюнкции

Пусть s обозначает результат операции r1 <AND> r2. Для обеспечения возможности выполнения операции требуется, чтобы если <A, T1>Hr1 и <A, T2>Hr2, то T1=T2. (Другими словами, если в двух отношениях-операндах имеются одноименные атрибуты, то они должны быть определены на одном и том же типе (домене).) Тогда:

  • Hs = Hr1 union Hr2, т. е. заголовок результата получается путем объединения заголовков отношений-операндов, как в операциях TIMES и JOIN из предыдущей лекции;
  • Bs = { ts : exists tr1 exists tr2 ((tr1Br1 and tr2Br2) and ts = tr1 union tr2)}; обратите внимание на то, что кортеж результата определяется как объединение кортежей операндов; поэтому:
    • если схемы отношений-операндов имеют непустое пересечение, то операция <AND> работает как естественное соединение;
    • если пересечение схем операндов пусто, то <AND> работает как расширенное декартово произведение;
    • если схемы отношений полностью совпадают, то результатом операции является пересечение двух отношений-операндов.

Операция <AND> является реляционной конъюнкцией, в некоторых случаях выдающей в результате отношение s, ранее называвшееся естественным соединением двух заданных отношений r1 и r2. Заголовок s является объединением заголовков r1 и r2. Тело s включает каждый кортеж, соответствующий заголовку s и являющийся надмножеством некоторого кортежа из тела r1 и некоторого кортежа из тела r2.

Для иллюстрации воспользуемся примерными отношениями, показанными на рис. 4.3, которые мы уже использовали в примерах предыдущей лекции.

Примерные отношения для иллюстрации операции <AND>
Рис. 4.3.  Примерные отношения для иллюстрации операции <AND>

На рис. 4.4(a) у отношений СЛУЖАЩИЕ и ПРОЕКТЫ имеется общий атрибут ПРО_НОМ. Поэтому операция <AND> работает как операция естественного соединения. На рис. 4.4(b) пересечение заголовков отношений СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 и ПРОЕКТЫ пусто, и поэтому в результате реляционной конъюнкции производится расширенное декартово произведение этих отношений. Наконец, на рис. 4.4(c) схемы отношений СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 и СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 совпадают, и телом операции <AND> является пересечение тел отношений-операндов.

Иллюстрации операции реляционной конъюнкции
Рис. 4.4.  Иллюстрации операции реляционной конъюнкции

Операция реляционной дизъюнкции

Пусть s обозначает результат операции r1 <OR> r2. Для обеспечения возможности выполнения операции требуется, чтобы если <A, T1>Hr1 и <A, T2>Hr2, то должно быть T1 = T2 (одноименные атрибуты должны быть определены на одном и том же типе). Тогда:

  • Hs = Hr1 union Hr2 (из схемы результата удаляются атрибуты-дубликаты);
  • Bs = { ts : exists tr1 exists tr2 ((tr1Br1 or tr2Br2) and ts = tr1 union tr2)}; очевидно, что при этом:
    • если у операндов нет общих атрибутов, то в тело результирующего отношения входят все такие кортежи ts, которые являются объединением кортежей tr1 и tr2, соответствующих заголовкам отношений-операндов, и хотя бы один из этих кортежей принадлежит телу одного из операндов;
    • если у операндов имеются общие атрибуты, то в тело результирующего отношения входят все такие кортежи ts, которые являются объединением кортежей tr1 и tr2, соответствующих заголовкам отношений-операндов, если хотя бы один из этих кортежей принадлежит телу одного из операндов, и значения общих атрибутов tr1 и tr2 совпадают;
    • если же схемы отношений-операндов совпадают, то тело отношения-результата является объединением тел операндов.

Операция <OR> является реляционной дизъюнкцией и обобщением того, что ранее называлось объединением. Заголовок s есть объединение заголовков r1 и r2. Тело s состоит из всех кортежей, соответствующих заголовку s и являющихся надмножеством либо некоторого кортежа из тела r1, либо некоторого кортежа из тела r2.

Предположим, у нас имеются отношения ПРОЕКТЫ_1 {ПРОЕКТ_НАЗВ, ПРОЕКТ_РУК} и НОМЕРА_ПРОЕКТОВ {ПРО_НОМ} (рис. 4.5). Предположим также, что домен атрибута ПРОЕКТ_НАЗВ включает значения ПРОЕКТ_1, ПРОЕКТ_2, ПРОЕКТ_3, домен атрибута ПРОЕКТ_РУК ограничен значениями Иванов, Иваненко, а доменом атрибута ПРО_НОМ является множество {1, 2, 3}. Результат операции ПРОЕКТЫ <OR> НОМЕРА_ПРОЕКТОВ показан на рис. 4.5.

Как показано на рис. 4.5, операция <OR> при наличии операндов с несовпадающими схемами производит результат, гораздо более мощный, чем результат операции взятия расширенного декартова произведения из лекции 3, и еще менее осмысленный с практической точки зрения.

Для иллюстрации операции <OR> над операндами, схемы которых имеют непустое пересечение, воспользуемся отношением ПРОЕКТЫ_2 {ПРО_НОМ, ПРОЕКТ_РУК} (рис. 4.6) и унарным отношением НОМЕРА_ПРОЕКТОВ, схема и тело которого показаны на рис. 4.5. Будем предполагать, что множества значений доменов атрибутов такие же, как в предыдущем примере. Результат операции ПРОЕКТЫ_2 <OR> НОМЕРА_ПРОЕКТОВ показан на рис. 4.6.

Как уже отмечалось, при совпадении схем отношений-операндов результатом выполнения над ними операции <OR> является объединение отношений. Это непосредственно следует из спецификации операции. Если этот факт кажется неочевидным, еще раз внимательно посмотрите на спецификацию. Иллюстрирующий пример мы приводить не будем.


Рис. 4.5.  Результат операции <OR> над операндами без общих атрибутов


Рис. 4.6.  Результат операции <OR> над операндами, схемы которых частично пересекаются

Полнота Алгебры A

Покажем, что Алгебра A является полной, т. е. на основе введенных операций выражаются все операции алгебры Кодда, рассмотренной в предыдущей лекции.

К настоящему моменту в состав базовых операций Алгебры A входят операция <REMOVE> в качестве аналога операции PROJECT, а также операция переименования атрибутов <RENAME>. UNION является частным случаем операции <OR>, TIMES, INTERSECT и NATURAL JOIN – частные случаи операции <AND>. Нам осталось показать, что через операции Алгебры A выражаются операции взятия разности MINUS, ограничения (WHERE), соединения общего вида (JOIN) и реляционного деления (DIVIDE BY).

Выводимость операции взятия разности

Покажем, что операция MINUS выражается через другие операции Алгебры A. Для наглядности снова воспользуемся отношениями СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 и СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 c рис. 4.3 (для удобства повторим его в верхней части рис. 4.7). Для простоты (хотя это несущественно) будем предполагать, что множества значений доменов, на которых определены атрибуты СЛУ_НОМЕР, СЛУ_ИМЯ, СЛУ_ЗАРП и СЛУ_ОТД_НОМЕР, ограничены значениями, содержащимися в телах отношений. Также для удобства покажем результат операции СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 MINUS СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 на рис. 4.7a. Заметим, что тело результата содержит все кортежи первого операнда, кроме кортежей Иванова и Петрова, поскольку они входят и в тело второго операнда.

Выразимость операции MINUS через операции <NOT> и <AND>
Рис. 4.7.  Выразимость операции MINUS через операции <NOT> и <AND>

Посмотрим теперь, что является телом результата операции <NOT> СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 (рис. 4.7b). В него входят все кортежи, соответствующие схеме отношения СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 (и схеме отношения СЛУЖАЩИЕ_В_ПРОЕКТЕ_1), которые не входят в тело отношения СЛУЖАЩИЕ_В_ПРОЕКТЕ_2. В том числе в тело результата этой операции входят и кортежи Сидорова, Федорова и Ивановой из тела отношения СЛУЖАЩИЕ_В_ПРОЕКТЕ_1.

Тогда очевидно, что результат операции СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 <AND> <NOT> СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 (пересечение тела первого операнда с телом результата операции <NOT>) является в точности тем же, что и результат операции СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 MINUS СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 (рис. 4.7c).

В общем случае нетрудно доказать, что если отношения r1 и r2 совместимы по объединению, то r1 MINUS r2 = r1 <AND> <NOT> r2.

Интерпретация операции ограничения

В лекции 3 мы определяли операцию ограничения r WHERE comp, где r – отношение, а comp – простое условие ограничения вида (a comp-op b), где а и b – имена атрибутов ограничиваемого отношения, для которых осмыслена операция сравнения comp-op либо вида (a comp-op const), где a – имя атрибута ограничиваемого отношения, а const – литерально заданная константа. Операцией сравнения comp-op может быть «=», « », «>», «<», « », « ». Покажем, как можно выразить операцию ограничения с помощью базовых операций Алгебры A для всех простых допустимых условий.

Для иллюстрации будем использовать отношение СЛУЖАЩИЕ_1 {СЛУ_НОМЕР, СЛУ_ИМЯ, СЛУ_ЗАРП, РУК_НОМ} (рис. 4.8). Атрибут РУК_НОМ содержит уникальные номера служащих, являющихся руководителями проектов, и определен на том же домене, что и СЛУ_НОМЕР. Мы снова предположим (для упрощения примеров), что множества значений доменов, на которых определены атрибуты отношения СЛУЖАЩИЕ_1, ограничены значениями, содержащимися в теле этого отношения. Начнем с обсуждения операции WHERE с условием вида a comp-op const.

Предположим, что мы хотим найти всех служащих с заработной платой, равной 20000.00 руб. Возьмем отношение ЗАРП_20000 {СЛУ_ЗАРП} 1) . Мы видим, что результат операции СЛУЖАЩИЕ_1 <AND> ЗАРП_20000 в точности совпадает с результатом операции СЛУЖАЩИЕ_1 WHERE СЛУ_ЗАРП = 20000.00 (рис. 4.8).

Выражение WHERE (a = const) через <AND>
Рис. 4.8.  Выражение WHERE (a = const) через <AND>

Если требуется найти служащих, чья заработная плата превышает 20000.00 руб., то возьмем отношение ЗАРП_БОЛЬШЕ_20000 2) (рис. 4.9). Тогда снова результат операции СЛУЖАЩИЕ_1 <AND> ЗАРП_БОЛЬШЕ_20000.00 будет совпадать с результатом операции СЛУЖАЩИЕ_1 WHERE СЛУ_ЗАРП > 20000.00 (рис. 4.9).

Выражение WHERE (a > const) через <AND>
Рис. 4.9.  Выражение WHERE (a > const) через <AND>

Понятно, что аналогичным образом выражаются через <AND> операции ограничения с условиями вида a comp_op const, в которых comp_op является «<», « » или « ». Некоторый особый случай представляет условие вида a const, и мы проиллюстрируем этот случай на примере запроса «Выбрать всех служащих, не получающих заработную плату в размере 22 000.00 руб.». Возьмем отношение ЗАРП_НЕ_22000 3) (рис. 4.10). Результат операции СЛУЖАЩИЕ_1 <AND> ЗАРП_НЕ_22000 будет совпадать с результатом операции СЛУЖАЩИЕ_1 WHERE СЛУ_ЗАРП <>22000.00 (рис. 4.10).

Выражение WHERE (a <> const) через <AND>
Рис. 4.10.  Выражение WHERE (a <> const) через <AND>

Теперь обратимся к ограничениям с простым условием вида a comp-op b. Опять начнем со случая, когда comp-op = «=». Предположим, что нам требуется найти данные о служащих, являющихся руководителями проектов, т. е. выполнить операцию СЛУЖАЩИЕ_1 WHERE СЛУ_НОМЕР = РУК_НОМ. Утверждается, что результат этой операции совпадает с результатом следующего выражения 4) :

СЛУЖАЩИЕ_1 <AND> ((((СЛУЖАЩИЕ_1 <REMOVE> СЛУ_НОМЕР) <REMOVE>
СЛУ_ИМЯ) <REMOVE> СЛУ_ЗАРП) <RENAME> (РУК_НОМ, СЛУ_НОМЕР))
        

Результат вычисления правого операнда операции <AND> и окончательный результат операции показаны на рис. 4.11.

Конечно же, можно выразить операцию СЛУЖАЩИЕ_1 WHERE СЛУ_НОМЕР = РУК_НОМ через операцию <AND>, используя «константное» отношение. Для этого можно воспользоваться отношением СЛУ_НОМЕР_РУК_НОМ 5) , показанным на рис. 4.12. Очевидно, что в результате выполнения операции СЛУЖАЩИЕ_1 <AND> СЛУ_НОМЕР_РУК_НОМ будет получен тот же результат, что показан на рис. 4.11.

Выражение WHERE (a = b) через <REMOVE>, <RENAME> и <AND>
Рис. 4.11.  Выражение WHERE (a = b) через <REMOVE>, <RENAME> и <AND>

Чтобы показать возможность выполнения операции ограничения вида r WHERE (a > b), предположим, что имеется отношение СЛУЖАЩИЕ_2 {СЛУ_НОМЕР, СЛУ_ИМЯ, СЛУ_ЗАРП, СЛУ_ПРЕМ} (рис. 4.12), причем атрибут СЛУ_ПРЕМ содержит значения премиального вознаграждения служащего. Естественно, атрибуты СЛУ_ЗАРП и СЛУ_ПРЕМ определены на одном и том же домене (напомним, что в целях наших примеров мы предполагаем, что множество значений доменов ограничено значениями, содержащимися в теле примерного отношения). Пусть нас интересуют данные о служащих, получающих дополнительные вознаграждения в размере, превышающем размер основной зарплаты, т. е. нам нужен результат операции СЛУЖАЩИЕ_2 WHERE (СЛУ_ПРЕМ > СЛУ_ЗАРП).

Константное отношение СЛУ_НОМЕР_РУК_НОМ
Рис. 4.12.  Константное отношение СЛУ_НОМЕР_РУК_НОМ

Возьмем отношение ПРЕМ_БОЛЬШЕ_ЗАРП {СЛУ_ПРЕМ, СЛУ_ЗАРП}, тело которого включает все соответствующие заголовку кортежи {b, s} такие, что b > s. Другими словами, отношение ПРЕМ_БОЛЬШЕ_ЗАРП снова является литеральной константой типа отношения с двумя атрибутами СЛУ_ПРЕМ и СЛУ_ЗАРП. Конечно, даже в случае нашего примера мощность тела этого отношения достаточно велика 6) . Тело отношения ПРЕМ_БОЛЬШЕ_ЗАРП показано в средней части рис. 4.13.

Результат выполнения операции СЛУЖАЩИЕ_2 <AND> ПРЕМ_БОЛЬШЕ_ЗАРП показан в нижней части рис. 4.13. Мы видим, что он совпадает с результатом операции СЛУЖАЩИЕ_2 WHERE (СЛУ_ПРЕМ > СЛУ_ЗАРП).

Аналогичным образом через операции Алгебры A выражаются операции ограничения, условия сравнения которых вида a comp_op b базируются на операциях сравнения «<», « », « », « ».

Выражение WHERE (a > b) через <AND>
Рис. 4.13.  Выражение WHERE (a > b) через <AND>

Соединения общего вида

При наличии того факта, что операция взятия расширенного декартова произведения TIMES является частным случаем операции <AND>, после того как мы научились с помощью Алгебры A выполнять ограничения, становится очевидно, что через операции Алгебры A выражаются и соединения общего вида. В общем случае, чтобы получить результат соединения общего вида произвольных отношений A и B, нужно:

  • выполнить над одним из отношений одну или несколько операций <RENAME>, чтобы избавиться от общих имен атрибутов;
  • выполнить над полученными отношениями операцию <AND>, производящую расширенное декартово произведение;
  • и для полученного отношения выполнить одну или несколько операций <AND> с отношениями-константами, чтобы должным образом ограничить его.

Реляционное деление

Пусть имеются отношения r1{A, B} и r2{B}. Утверждается, что результат r1 DIVIDE BY r2 совпадает с результатом выражения (r1 PROJECT A) MINUS (((r2 TIMES (r1 PROJECT A)) MINUS r1) PROJECT A) в терминах операций реляционной алгебры Кодда или (r1 <REMOVE> B) <AND> <NOT> (((r2 <AND> (r1 <REMOVE> B)) <AND> <NOT> r1) <REMOVE> B) в терминах операций Алгебры A.

Действительно, результатом выполнения операции r1 PROJECT A является унарное отношение со схемой {A}, кортежи тела которого содержат все значения атрибута A из тела отношения r1. Результат выражения r2 TIMES (r1 PROJECT A) – это бинарное отношение со схемой {A, B}, в тело которого входят все возможные комбинации значений атрибута B в теле отношения r2 и атрибута A в теле отношения r1. В теле результата вычисления выражения (r2 TIMES (r1 PROJECT A)) MINUS r1 останутся только те кортежи, которые не входят во второй операнд, т. е. кортежи с таким значением атрибута A, что значение атрибута B, принадлежащее телу r2, не является значением атрибута B ни в одном кортеже тела отношения r1. Следовательно, если мы возьмем проекцию результата выражения (r2 TIMES (r1 PROJECT A)) MINUS r1 на ат рибут A, то в результирующем унарном отношении останутся только те значения A, которые не должны попасть в результат операции r1 DIVIDE BY r2. После выполнения завершающей операции MINUS мы получим желаемый результат.

Для иллюстрации воспользуемся отношениями СЛУЖАЩИЕ и НОМЕРА_ПРОЕКТОВ, которые мы уже применяли в предыдущих примерах. Для удобства мы воспроизводим их на рис. 4.14. На этом же рисунке показаны промежуточные и окончательный результаты вычисления выражения (СЛУЖАЩИЕ PROJECT {СЛУ_НОМЕР, СЛУ_ИМЯ, СЛУ_ЗАРП}) MINUS ((((СЛУЖАЩИЕ PROJECT {СЛУ_НОМЕР, СЛУ_ИМЯ, СЛУ_ЗАРП}) TIMES НОМЕРА_ПРОЕКТОВ) MINUS СЛУЖАЩИЕ) PROJECT {СЛУ_НОМЕР, СЛУ_ИМЯ, СЛУ_ЗАРП}).


Рис. 4.14.  Выражение операции DIVIDE BY через другие операции Алгебры A

Тем самым, мы показали, что пяти операций Алгебры A достаточно для выражения всех операций алгебры Кодда из лекции 3. Но на самом деле число операций можно еще более сократить, что мы и продемонстрируем в следующем разделе.

Избыточность Алгебры A

В формальной математической логике стандартным базисом для выражения всех возможных булевских функций является набор {NOT, AND, OR} (отрицание, дизъюнкция и конъюнкция). Известно, что этот набор традиционен, но избыточен, поскольку верны тождества A AND B NOT (NOT A OR NOT B) и A OR B NOT (NOT A AND NOT B). (Эти тождества легко проверяются по таблицам истинности операций.) Оказывается (и это тоже легко проверить, опираясь на определения операций), что аналогичные тождества справедливы для операций <NOT>, <AND> и <OR> Алгебры A. Тем самым, в наборе базовых операций Алгебры A можно оставить операции <AND> и <NOT> (или <OR> и <NOT>).

Реляционные аналоги штриха Шеффера и стрелки Пирса

Более того, в алгебре логики существуют две операции, через каждую из которых выражаются все три «базовые» операции: «штрих Шеффера» – sh (A, B) NOT A OR NOT B – и «стрелка Пирса» – pi (A, B) NOT A AND NOT B.

Легко видеть, что

  • sh (A, A) NOT A;
  • sh (NOT A, NOT B) A OR B и
  • NOT sh (A, B) A AND B.

Аналогично,

  • pi (A, A) NOT A;
  • pi (NOT A, NOT B) A AND B и
  • NOT pi (A, B) A OR B.

Снова нетрудно проверить, что аналогичные тождества справедливы для реляционных вариантов штриха Шеффера (<sh> (r1, r2) <NOT> r1 <OR> <NOT> r2) и стрелки Пирса (<pi> (r1, r2) <NOT> r1 <AND> <NOT> r2).

Поэтому можно свести набор операций Алгебры A к трем операциям: <sh> (или <pi>), <RENAME> и <REMOVE>.

Избыточность операции переименования

Наконец, покажем, что избыточна и операция <RENAME>. Для иллюстрации снова воспользуемся отношением СЛУЖАЩИЕ из рис. 4.14. Пусть нам нужен результат операции СЛУЖАЩИЕ <RENAME> (ПРО_НОМ, НОМЕР_ПРОЕКТА) (мы по-прежнему предполагаем, что множество значений домена атрибута ПРО_НОМ ограничено значениями, представленными в теле отношения СЛУЖАЩИЕ). Возьмем бинарное отношение ПРО_НОМ_НОМЕР_ПРОЕКТА (рис. 4.15), где каждый из кортежей содержит два одинаковых значения номера проекта и в тело отношения входят все значения домена атрибута ПРО_НОМ 7) . Тогда, как показано на рис. 4.15, вычисление выражения (СЛУЖАЩИЕ <AND> ПРО_НОМ_НОМЕР_ПРОЕКТА) <REMOVE> (ПРО_НОМ) приводит к желаемому результату.

Избыточность операции <RENAME>
Рис. 4.15.  Избыточность операции <RENAME>

Тем самым, можно сократить набор операций Алгебры A до двух операций: <sh> (или <pi>) и <REMOVE> 8) .

Заключение

Базисом Алгебры A являются операции реляционного отрицания (дополнения), реляционной конъюнкции (или дизъюнкции) и проекции (удаления атрибута). Реляционные аналоги логических операций определяются в терминах отношений на основе обычных теоретико-множественных операций и позволяют выражать напрямую операции пересечения, декартова произведения, естественного соединения и объединения отношений. Путем комбинирования базовых операций выражаются операции переименования атрибутов, соединения общего вида, взятия разности отношений. Алгебра A позволяет лучше осознать логические основы реляционной модели, хотя, безусловно, является в меньшей степени ориентированной на практическое применение, чем алгебра Кодда.

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

  1)   Здесь необходимо пояснить, что отношение ЗАРП_20000 в действительности представляет собой литеральную константу соответствующего типа отношений. Мы не вводим здесь строгого понятия типа отношения; для понимания данного подраздела нужно всего лишь осознать, что по своей природе отношение ЗАРП_20000 и числовой литерал 20000.00 не различаются.
  2)   Отношение ЗАРП_БОЛЬШЕ_20000 – это тоже литеральная константа того же типа отношения, что и ЗАРП_20000, однако мощность тела этого литерального отношения в общем случае (если бы мы не ввели ограничения на множество значений домена СЛУ_ЗАРП) могла бы быть очень большой.
  3)   Особенность этого случая состоит в том, что число кортежей в теле литеральной константы ЗАРП_НЕ_22000 всего лишь на единицу меньше мощности множества значений домена СЛУ_ЗАРП. Конечно, эта мощность конечна, поскольку мы имеем дело с компьютерными типами данных, но в общем случае может быть очень большой. Поэтому принципиальная возможность выражения операции ограничения через операцию реляционной конъюнкции не означает, что было бы разумно реализовывать ее таким образом на практике.
  4)   Конечно, тот же результат даст и выражение СЛУЖАЩИЕ_1 <AND> ((((СЛУЖАЩИЕ_1 <REMOVE> СЛУ_РУК) <REMOVE> СЛУ_ИМЯ) <REMOVE> СЛУ_ЗАРП) <RENAME> (СЛУ_НОМЕР, РУК_НОМ)).
  5)   Конечно, в общем случае мощность тела такого константного отношения будет равна мощности соответствующего домена.
  6)   Легко убедиться, что в общем случае, если мощность общего домена атрибутов A и B равняется n, то мощность тела константного отношения A_БОЛЬШЕ_B будет составлять (n+1)n/2.
  7)   Это «константное» отношение, тело которого не зависит от текущего содержания тела отношения СЛУЖАЩИЕ.
  8)   И конечно, в Алгебре A, как и в алгебре Кодда, должна присутствовать операция присваивания переменной отношения.