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

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

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

• выполнить над полученными отношениями операцию <AND>, производящую расширенное декартово произведение;

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

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

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

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

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

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

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

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>).