Магия сохраняет силу

программирование для детей

Корреляция и декорреляция


Несколько авторов изучало подзапросы 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




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



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