Обзор методов оптимизации запросов в реляционных системах




Слияние вложенных подзапросов - часть 2


Эту дополнительную сложность иллюстрирует приводимый ниже пример из [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 Я предполагаю, что эта операция не устраняет дубликаты.

- -




Содержание  Назад  Вперед