Оптимизация запросов в системах баз данных

         

Реляционная алгебра


Реляционная алгебра, как она определена Коддом в [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". Как показывает определение, деление является довольно сложной операцией, что может затруднить понимание запросов.




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