Методы оптимизации выполнения запросов в реляционных СУБД


Логическая оптимизация запросов - часть 10


Можно сказать, что Ri и X "антисоединяются" предикатом анисоединения NOT (Ri.Ch = X.Ch). Если допустить наличие предикатов антисоединения в каноническом представлении запроса, то предыдущий запрос эквивалентен следующему:

SELECT Ri.Ck FROM Ri, X WHERE NOT (Ri.Ch = Rj.Ch).

При этом предикаты антисоединения при выполнении запроса должны вычисляться только после выполнения предикатов соединения, полученных из J-предикатов c IS NOT IN. Например, если запрос с J-предикатом

SELECT Ri.Ck FROM Ri WHERE Ri.Ch IS NOT IN SELECT Rj.Cm FROM Rj WHERE Rj.Cn = Ri.Cp

преобразован к псевдоканонической форме

SELECT Ri.Ck FROM Ri, Rj WHERE Ri.Cp = Rj.Cn AND NOT (Ri.Ch = Rj.Cm),

то для сохранения семантики запроса в его исходной формулировки преобразованный запрос нужно понимать следующим образом: для каждого очередного кортежа отношения Ri выполняется соединение с отношением Rj в соответствии с предикатом соединения. При этом производится подотношение R1j, которое заменяет Rj в предикате антисоединения. Несколько забегая вперед, заметим, что гораздо более четко вопрос о преобразовании запросов с предикатами типа J, включающими оператор IS NOT IN, рассмотрен в [65]. Основным наблюдением, на котором основывается это рассмотрение, является связь предиката антисоединения с предикатом полусоединения и теоретико-множественной операцией разности множеств.

Рассмотренные возможные преобразования обобщаются в следующем алгоритме NEST-N-J, преобразующем запросы с предикатами типов N и J к "канонической" форме (понятно, что ее можно считать только псевдоканонической, поскольку отсутствует единая семантика предикатов соединения):

  1. Объединить все списки отношений, встречающихся во всех разделах FROM, в один список FROM.
  2. Объединить через AND логические условия всех разделов WHERE в одно логическое условие.
  3. Заменить предикаты вида Ri.Cn op (SELECT Rj.Cm) на предикаты Ri.Cn op Rj.Cm, если op отлично от IS IN и IS NOT IN; на предикаты Ri.Cn = Rj.Cm, если op - это IS IN; на предикаты NOT( Ri.Cn = Rj.Cm), если op - это IS NOT IN.
  4. Оставить список выборки внешнего запроса.




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



Книжный магазин