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


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


Это еще одно соображение в пользу того, что семантика запросов при их преобразованиях должна выражаться более точно.

Преобразования запросов, содержащих предикаты типа D, основаны на следующей лемме:

Пусть Q5 есть запрос

SELECT Ri.Ck FROM Ri WHERE (SELECT Rj.Ch FROM Rj WHERE Rj.Cn = Ri.Cp) op (SELECT Rk.Cm FROM Rk), а Q6 - запрос SELECT Ri.Ck FROM Ri WHERE Ri.Cp = (SELECT C1 FROM Rt), где Rt (C1) определяется запросом SELECT Rj.Cn FROM Rj Rx WHERE (SELECT Rj.Ch FROM Rj RY WHERE RY.Cn = RX.Cn) op (SELECT Rk.Cm FROM Rk).

Запросы Q5 и Q6 эквивалентны.

Заметим, что запрос Q6 содержит предикат типа N, и, следовательно, может быть преобразован к канонической форме. Запрос, определяющий отношение Rt, является формулировкой на SQL реляционной операции деления. (Напомним, что по определению результатом операции реляционного деления отношения R на отношение S арности соответственно r и s, где r > s и S - не пусто, является отношение арности r-s, включающее такие и только такие кортежи t, что для любого кортежа u, принадлежащего S, кортеж tu принадлежит R. Известно, что операция реляционного деления выражается через другие операции реляционной алгебры.)

На лемме основан алгоритм NEST-D, приводящий запрос с предикатом типа D к канонической форме. Пусть задан запрос достаточно общего вида:

SELECT R1.C1 FROM R1 WHERE (SELECT R2.C1 FROM R2 WHERE R2.C2 = R1.C2 AND ... AND R2.Cn = R1.Cn) = (SELECT R3.C1 FROM R3 WHERE R3.C2 = R1.C2 AND ... AND R3.Cm = R1.Cm).

Предположим, что n > m. Тогда действие алгоритма NEST-D состоит в следующем:

  1. Образуем два временных отношения Rt1 (C1, ..., Cm) и Rt2 (C1, ..., Cn). Rt1 определяется запросом

    SELECT C1, ..., Cm FROM R3, а Rt2 - запросом SELECT C1, ..., Cn FROM R2.

  2. Обозначим через Rt3 (Cm+1, ..., Cn) временное отношение, являющееся частным от реляционного деления Rt2 на Rt1.
  3. Преобразуем начальный запрос к каноническому виду. Для этого

    3a) Исключим внутренний блок запроса с отношением R3.

    3b) Заменим все ссылки на поля отношения R2 на ссылки на соответствующие поля отношения Rt3 во внутреннем блоке запроса с отношением R2.



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



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