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