Корреляция и декорреляция
Несколько авторов изучало подзапросы SQL ([ISO89, ABC+76]) и описывали преобразования для миграции предикатов сквозь них [Kim82, GW87, Day87]. Корреляция, подобно магии, «проталкивает (push down) предикаты» в подзапросы. Обратное преобразование – декорреляция – «вытягивает (pull up) предикаты» из подзапросов. Одним из основных различий между магией и подобными другими методами является то, что магия применяется единообразно к иерархическим (древовидным) и рекурсивным запросам (а также к запросам с общими подвыражениями), а другие методы применяются только к иерархическим запросам. Сравнение эффективности этих методов приводится в разд. 6.
ПРИМЕР 2.1 (Корреляция, декорреляция и магия):
(C): SELECT Ename FROM emp el WHERE Job = 'Sr Programmer' AND Sal > (SELECT AVG(e2.Sal) FROM emp e2 WHERE e2.Dno = el.Dno)
Запрос (C) выбирает старших программистов, которые получают зарплату, большую средней зарплаты своего отдела. Запрос написан так, что в нем имеется корреляция: для каждого служащего, являющегося старшим программистом, вычисляется средняя зарплата в его отделе, и выбирается служащий, зарплата которого больше вычисленного значения. Не обрабатывается ненужная информация, но средняя заплата отдела может вычисляться много раз (если в отделе работает несколько служащих). Кроме того, доступ к el и e2 должен производиться в специальном порядке (сначала el, потом e2). Наконец, обработка e2 является скорее покортежной, чем ориентированной на множества, а именно ориентация на обработку множеств обеспечивает основное преимущество реляционной модели в отношении эффективности. Таким образом, корреляция сокращает преимущества реляционной модели касательно непроцедурности и ориентированности на множества и может приводить к избыточным вычислениям.
Запрос C можно преобразовать в декоррелированный запрос D, в котором используется временная таблица dep-avgsal(Dno, Asal), определяемая внутри запроса:
(Dl): SELECT Ename FROM emp, dep_avgsal WHERE Job = 'Sr Programmer' AND Sal > Asal AND emp.Dno = dep_avgsal.Dno
(D2): dep_avgsal(Dno, Asal) AS (SELECT Dno, AVG(Sa1) FROM emp GROUPBY Dno)
В отличие от коррелированного запроса, декоррелированный запрос является ориентированным на множества (средние зарплаты вычисляются для всех отделов за одну операцию вместо того, чтобы вычислять среднее значение зарплаты для одного отдела за один раз, когда выбирается служащий этого отдела). Кроме того, новый запрос непроцедурный (два сканирования служащих могут меняться местами). План выполнения может предполагать доступ к таблице служащих по Dno, вычисление средней зарплаты для этого Dno с формированием кортежа таблицы dep_avgsal, и нахождение в каждом отделе всех старших программистов с зарплатой выше средней зарплаты отдела. Но у декорреляции имеется существенный недостаток: средняя зарплата определяется для всех отделов, независимо от того, работают ли в них старшие программисты. Если имеется много отделов, и только в некоторых из них имеются старшие программисты, то стоимость ненужных вычислений будет значительной.
В подходе магических множеств объединяются достоинства методов корреляции и декорреляции, хотя и не бесплатно. После преобразования запроса C методом магических множеств мы получим следующий магический запрос S:
(Sl): SELECT Ename FROM s_mag, mag_avgsal WHERE Sal > Asal AND s_mag.Dno = mag_avgsal.Dno
(S2): mag_avgsal(Dno, Asal) AS (SELECT Dno, AVG(Sa1) FROM mag, emp WHERE mag.Dno = emp.Dno GROUPBY Dno)
(S3): mag(Dno) AS (SELECT DISTINCT Dno FROM s_mag)
(S4): s_mag(Ename, Dno, Sal) AS (SELECT Ename, Dno, Sal FROM emp WHERE Job = 'Sr Programmer')
Один из возможных планов выполнения S состоит в том, чтобы выбрать служащих, являющихся старшими программистами (s_mag), определить, в каких отделах имеется хотя бы один из таких служащих (mag), вычислить среднюю зарплату только для этих отделов (mag_avgsal) и затем выбрать всех старших программистов (s_mag), которые получают зарплату выше средней зарплаты своего отдела. Порядок доступа может быть другим, как если бы запрос был декоррелированным, и операции являются ориентированными на множества.Более того, не затрагиваются нерелевантные данные, поскольку средняя зарплата вычисляется только для отделов, содержащих старших программистов. Однако эта магика становится возможной за счет вычисления дополнительных таблиц s_mag и mag.
Магический запрос S напоминает приведенный в разд. 2.1 пример с полусоединением. Информация об уместных связываниях (отделы, включающие старших программистов) передается «сторонним образом» от emp к mag_avgsal.
