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

         

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


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

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


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

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



Содержание раздела