Развитие идей и приложений реляционной СУБД System R


Оптимизация в System R - часть 2


Упоминается еще один способ выполнения запроса на выборку, в котором условие выборки представляет собой логическое выражение, состоящее из простых предикатов сравнения (типа "имя-поля операция-сравнения константа") и включающее только те поля, для которых существуют индексы. Способ состоит в том, что в соответствии с заданными простыми предикатами из индексов выбираются списки tid'ов кортежей, удовлетворяющих предикатам, а затем над этими списками выполняются теоретико-множественные операции объединения и пересечения (объединение соответствует логической операции "или" в логическом условии выборки, пересечение - "и"). Реальная выборка результирующих кортежей производится по произведенному таким образом окончательному списку tid'ов.

Здесь следует заметить, что в System R принято довольно простое решение по поводу выполнения запросов со вложенными подзапросами: они выполняются именно так, как указано в исходном запросе, т.е. до того, как выполняется внешний запрос, формируются результаты всех его вложенных подзапросов и т.д. В принципе это является упрощением; имеются работы, показывающие, что можно преобразовать запрос, содержащий вложенные подзапросы, к одноуровневому запросу, содержащему соединения отношений. При этом запрос в преобразованной форме допускает более эффективное выполнение. В System R оптимизационные преобразования этого типа не употребляются, и это, конечно, является ограничением этой системы. Справедливости ради заметим, что публикации, связанные с преобразованием запросов со вложенностями, появились позже основной части публикаций по System R.

Тем не менее, с использованием SQL можно явно формулировать запросы на выборку, содержащие предикаты соединения. Тривиальный способ выполнения таких запросов на основе формирования прямого произведения отношений с последующим выделением кортежей, удовлетворяющих условию выборки не рассматривается в числе кандидатов. Для выполнения (экви)соединения двух отношений R и S употребляются четыре следующих способа:




Начало  Назад  Вперед