Слияние вложенных подзапросов
Рассмотрим следующий пример запроса с вложенными подзапросами из [13], где Emp# и Dept# - ключи соответствующих отношений:
SELECT Emp.Name FROM Emp WHERE Emp.Dept# IN SELECT Dept.Dept# FROM Dept WHERE Dept.Loc = 'Denver' AND Emp.Emp# = Dept.Mgr
Если для ответа на запрос используется семантика последовательного просмотра кортежей, то внутренний запрос вычисляется один раз для каждого кортежа отношения Emp. Очевидная оптимизация применима в том случае, когда внутренний блок запроса не содержит переменных из внешнего блока запроса (отсутствует корреляция). В таких случаях внутренний запрос требуется вычислить только один раз. Если во внутреннем блоке присутствует переменная из внешнего блока, мы говорим, что блоки запроса коррелируют. Например, в приведенном выше запросе Emp.Emp# действует как корреляционная переменная. Ким [35] и в последствие другие исследователи [16, 13, 44] выявили методы устранения вложенности в SQL-запросе с корреляцией и "уплощения" его до запроса с одним блоком. Например, приведенный запрос со вложенностью приводится к
SELECT E.Name FROM Emp.E, Dept D WHERE E.Dept# = D.Dept# AND D.Loc = 'Denver' AND E.Emp# = D.Mgr
Дайал [13] был первым, кто предложил алгебраическую трактовку устранения вложенности. Сложность проблемы зависит от структуры вложенности, т.е. от того, содержит ли вложенный запрос кванторы (например, ALL, EXISTS) и агрегаты. В простейшем случае, примером которого является приведенный выше пример, семантика перебора кортежей может моделироваться конструкцией Semijoin (Emp, Dept, Emp.Dept # = Dept.Dept#). Опираясь на этот подход, нетрудно заметить, почему может быть произведено слияние запроса, поскольку:
Semijoin ( Emp, Dept, Emp.Dept# = Dept.Dept# ) = Project ( Join (Emp, Dept), Emp* )
Здесь предикатом соединения для Join (Emp, Dept) является Emp.Dept# = Dept.Dept#. Второй операнд операции Project означает, что должны быть оставлены все столбцы отношения Emp.
Проблема становится гораздо более сложной, когда во вложенном подзапросе присутствуют агрегаты, поскольку теперь для слияния блоков требуется вытягивание наверх агрегации без нарушения семантики запроса со вложенными подзапросами.
Эту дополнительную сложность иллюстрирует приводимый ниже пример из [44]:
SELECT Dept.name FROM Dept WHERE Dept.num-of-machines >= ( SELECT COUNT (Emp.*) FROM Emp WHERE Dept.name = Emp.Dept_name )
Особенно сложно сохранить дубликаты и неопределенные отношения. Чтобы оценить эти тонкости, обратите внимание, что если для конкретного значения Dept.name (скажем, d) отсутствуют кортежи с совпадающим значением Emp.Dept_name, т.е. если значением предиката Dept.name = Emp.Dept_name является false для всех кортежей Emp, то кортеж отношения Dept со значением d войдет в результат запроса. Однако, если мы применим преобразование, использованное в первой части этого подраздела, то для dept d в результате запроса кортеж не появится, поскольку предикат соединения примет значение false. Поэтому при наличии агрегации мы должны сохранять все кортежи внутреннего блока запроса, используя левое внешнее соединение. В частности, приведенный запрос может быть корректно преобразован к виду
SELECT Dept.name FROM Dept LEFT OUTER JOIN Emp On (Dept.name = Emp.Dept_name) GROUP BY Dept.name HAVING Dept.num-of-machines < COUNT (Emp.*)
Так что для этого класса запросов единственный слитый блок запроса содержит внешние соединения. Если структура вложенности блоков линейна, то это подход применим, и преобразования производят один блок с линейной последовательностью соединений и внешних соединений. Оказывается, что последовательность соединений и внешних соединений такова, что мы можем использовать правило ассоциативности, описанное в подразделе 4.2.1, для вычисления сначала всех соединений, а затем всех внешних соединений из этой последовательности. Другой подход к устранению вложенных подзапросов состоит в преобразованию запроса к такому виду, в котором используются табличные выражения или представления (и конечно, это не одноблочный запрос). Это было направление работы Kim [35], которая впоследствии была усовершенствована в [44].
2 Semijoin (A,B,P) обозначает полусоединение A и B, сохраняющее атрибуты A; P - предикат полусоединения.
3 Я предполагаю, что эта операция не устраняет дубликаты.
- -
