Базы данных. Вводный курс

Назад Содержание Вперёд

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть имеются отношения 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 мы получим желаемый результат.

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

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

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

5.4. Избыточность Алгебры 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>).

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

Более того, в алгебре логики существуют две операции, через каждую из которых выражаются все три «базовые» операции: «штрих Шеффера» – 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>.

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

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

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

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

5.5. Заключение