Полнота алгебры А. Определение операций алгебры Кодда через алгебру А

Более подробно – на стр. 83-92.

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

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

MINUS

r1 MINUS r2 = r1 <AND> <NOT> r2.

WHERE

Для простоты будем считать, что множества значений доменов в БД ограничено значениями, содержащимися в теле отношения. Рассмотрим ограничения с простыми условиями вида(имя отношения – REL):

· a comp_op const(=) Для выражения условий равенства в терминах алгебры а заводится вспомогательное отношение(CONST_REL), содержащее необходимые атрибуты и кортежи. Потом просто берется REL <AND> CONST_REL (эквивалентно REL WHERE а = const )

· a comp_op const(>) Опять строим вспомогательное отношение, содержащее необходимые нам данные(они считаются ручками, да) и снова делаем REL <AND> CONST_REL (эквивалентно REL WHERE а > const )

· a comp_op const(!=) собственно, все то же самое…

· a comp_op b(=) Для проверки этого ограничения(пример – СЛУ_НОМЕР = РУК_НОМЕР) строится следующая конструкция: <REMOVE> ’ом удаляются все «лишние» атрибуты заголовка, затем переименовываются оставшийся атрибут(он должен быть из одного домена со сравниваемым атрибутом), чтобы совпадали имена у проверяемых значений и берется <AND> построенной и исходной таблицы

· a comp_op b(!=, >, <,…) Аналогично – используется техника работы со вспомогательными таблицами, удалением ненужных атрибутов и переименованием нужных. Ну и <AND>, куда ж без него…

JOIN

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

Вот алгоритм в общем случае:

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

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

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

Поиск по сайту: