Реляционная алгебра
Реляционная алгебра, как она определена Коддом в [Codd 1972] является набором операций над отношениями. Эти операции распадаются на два класса: традиционные операции над множествами, такие как декартово произведение, объединение, пересечение и разность, и специальные операции реляционной алгебры, такие как ограничение, проецирование, соединение и деление. Ниже специальные операции определяются путем их связывания с эквивалентными выражениями реляционного исчисления.
Операция ограничения, примененная к отношению "rel", конструирует горизонтальное подмножество в соответствии с безкванторным предикатом, содержащим только одноместные термы или "внутриотношенческие" двуместные термы (сравнения между атрибутами одного элемента отошения):
Rest(rel, pred) = [EACH r IN rel: pred].
Операция проекции служит для конструирования вертикального подмножества отношения "rel" путем выбора набора указанных атрибутов A и удаления кортежей-дубликатов из этих атрибутов:
Proj(rel, A) = [(r.A) OF EACH r IN rel: true].
Операция соединения позволяет соединять два отношения "rel1" и "rel2" в одно отношение, атрибуты которого являются объединением атрибутов "rel1" и "rel2":
Join(rel1, A op B, rel2) = [EACH rl IN rel1, EACH r2 IN rel2: rl.A op r2.B].
Допускаемые в соединениях операции сравнения "op" являются такими же, как в двуместных термах реляционного исчисления. Если "op" является операцией сравнения на равенство, в результате "естественного" соединения опускается A или B.
Операция деления является алгебраическим двойником квантора всеобщности. Она определяется следующим образом:
Divi(rel1, A by B, rel2) = [(r.compl(A)) OF EACH rl IN rel1: ALL rel2 IN rel2 SOME r3 IN rel1 (rl.compl(A) = rel2.compl(A) AND rel2.B = r3.A)],
где compl(A) - это дополнение A во множестве атрибутов "rel1". Как показывает определение, деление является довольно сложной операцией, что может затруднить понимание запросов.
В Примере 2.2 представляется запрос Примера 2.1 в терминах реляционной алгебры.
Пример 2.2. Имена профессоров, опубликовавших какую-либо статью в 1981 г.
Proj (Rest(Join(employees, enr = enr, Rest(papers, year = 1981)), status = professor), ename)
В противоположность выражению реляционного исчисления, которое описывает отношение, проиходящее из запроса, в терминах его свойств, выражение релционной алебры определяет алгоритм конструирования результирующего отношения. Выражение исчисления кажется лучшей стартовой точкой для оптимизации запросов, поскольку оно обеспечивает оптимизатор только базовыми свойствами запроса; возможности оптимизации могут быть скрыты в конкретной последовательности операций алгебры. Однако в отношении реляционной полноты реляционная алгебра, по меньшей мере, настолько же полна, как и реляционное исчисление. В [Codd 1972] показано, что любое выражение реляционного исчисления можно отрранслировать в эквивалентное выражение алгебры. Аналогичный результат для выражений алгебры и исчисления, расширенных агрегатыми функциями доказан Клугом [Klug 1982a].
