Алгоритмы выполнения операций с множествами, проекции, внешнего соединения

Проекция.

Состоит в занесение в результат указанных атрибутов каждого кортежа и в исключении дубликатов. Основная проблема связана с дубликатами. Удалять их можно с использованием сортировки.

При внешней сортировке смещением дубликаты, найденные внутри фрагментов удаляются из них еще до записи на диск, остальные дубликаты удаляются в процессе смещения, таким образом, в результирующем отношении дубликаты отсутствуют. Операция удаления дубликатов может потребовать дополнительных затрат, поэтому в большинстве СУБД по умолчанию в проекции не производится удаление дубликатов. Необходимость выполнения этой операции пользователь должен задать явно.

Операции с множествами.

/*Объединение, пересечение и деление */. Алгоритмы работы таких операций основаны на том, что оба отношения уже отсортированы. В этом случае производится сканирование обоих отношений, и в зависимости от операции, кортежи заносятся в результат. /*При объединении, если есть в обоих, то заносится только одна. При пересечении, если есть в первом и втором, деление, если нет в первом, но есть во втором. */ Стоимость выполнения этих операций br+bs, так как сортировка однозначно определяет место кортежа. Если исходные кортежи не отсортированы, то стоимость увеличивается на стоимость операций сортировки отношений.

Внешнее соединение. Пусть существуют два отношения r(R) и s(S). Для вычисления левого внешнего соединения r ><qs существует два подхода.

При первом подходе вычисляется внутреннее соединение r ><qs, результат записывается во временную таблицу q1. Затем выбирают строки, не вошедшие во временную таблицу, но существующие в отношении r, то есть r - П(R(q1)). Полученные таким образом строки дополняют null-значениями на месте атрибутов второго отношения и включают в результат вместе с таблицей q1. Для правого соединения аналогично, но выбирают кортежи отношения s, которые не вошли во временную таблицу s - П(S(q1)).

Второй подход основан на изменении алгоритмов соединения. Например, при соединении смещением строки первого отношения, для которых не было найдено соответствия во втором отношении, не отбрасываются, а дополняются null-значениями и включаются в результат.