Улучшение
В результате упрощения запроса не обязательно производится уникальное выражение. Могут существовать другие неизбыточные выражения, семантически эквивалентные тому, которое сгенерировано некоторым методом упрощения. Вычисление выражений, соответствующих одному и тому же запросу может существенно различаться параметрами эффективности, например, размерами промежуточных результатов и числом обращений к элементам отношений. Ниже приводится ряд эвристик для таких преобразований запросов, выполнение которых улучшает выражения в отношении эффективности их вычисления.
Простейшими преобазованиями, рассматриваемыми в этом разделе, являются объединение последовательности проекций в одну проекцию и объединение последовательности ограничений в одно ограничение [Hall 1976; Smith and Chang 1975]. Соответствующими правилами преобразования являются следующие:
A1: Proj(. . . Proj(Proj(rel, A1), A2), . . . , An) ==> Proj(rel, An), A2: Rest(. . . (Rest(Rest(rel, predl), pred2) . . . , predn) ==> Rest(rel, predl AND pred2 AND . . . AND predn).
Объединение внутриотношенческих операций обеспечивает два преимущества. Во-первых, избегается повторяющееся чтение одного и того же отношения, и, во-вторых, существующие пути доступа могут использоваться для объединенной операции, а не только для первой операции последовательности.
Целью ряда улучшающих преобразований является минимизация размера конструируемых, сохраняемых и считываемых промежуточных результатов. Важная эвристика перемещает селективные операции, такие как ограничение и проекция, выше контруктивных операций, таких как соединение и декартово произведение, чтобы выполнять селективные операции как можно раньше [Smith and Chang 1975]. В контексте реляционного исчисления разбор некоторой последовательности вычислений может быть представлен вложенным выражением. Вычисление вложенного выражения начинается с вычисления наиболее внутреннего вложенного выражения, за которым следует непосредственно окружающее его выражение и т.д., пока не будет достигнуто наиболее внешнее выражение.
Вложенное выражение, подразумевающее раннее вычисление одноместных термов (ограничений) приведено в Примере 3.1. Пример 3.1. Вложенное выражение, эквивалентное выражению из Примера 2.1.
[<e.ename) OF EACH e IN [EACH e IN employees: e.status = professor]: SOME p IN [EACH p IN papers: p.year = 1981] (e.enr = p.enr)]
Ранее вычисление селективных операций представляет частный случай отсоединения запроса (query detachment), введенного Вонгом и Юссефи [Wong and Youssefi 1976]. Подвыражение, которое перекрывается с оставшейся частью запроса по одной переменной, отсоединяется и образует внутреннюю вложенность. Отсоединение выполняется рекурсивно на каждом уровне вложенности до тех пор, пока выражение не перестанет сокращаться. Эксперименты, описанные Юссефи и Вонгом [Wong and Youssefi 1979], показали, что это очень сильная эвристика. В Примере 3.2 демонстрируется отсоединение подвыражения сложного выражения. Пример 3.2. Отделы, предлагающие лекции, проводимые профессорами, которые живут в том же городе, в котором находится отдел, и каждый из которых опубликовал какую-либо статью в 1981 г.
Соответствующее выражение:
[EACH d IN departments: SOME l IN lectures SOME e IN employees (e.status = professor AND d.dname = l.dname AND 1.enr = e.enr AND e.city = d.city AND SOME p IN papers (p.year = 1981 AND p.enr = e.enr))]
Вот эквивалентное выражение, произведенное путем отсоединения запроса:
[EACH d IN departments: SOME l IN lectures SOME e IN [EACH e IN [EACH e IN employees: e.status = professor]: SOME p IN [EACH p IN papers: p.year = 1981] (e.enr = p.enr)] (d.dname = 1.dname AND 1.enr = e.enr AND e.city = d.city)]
Объектный граф, представляющий запрос, показан на рис. 4.
Заметим, что результирующее вложенное выражение является неразделимым [Goodman and Shmueli 1980]; т.е. его нельзя разделить на два подвыражения, перекрывающихся по одной переменной. Другими словами, вложенное выражение содержит цикл (см. рис. 4).
Рис 4. Объектный граф для Примера 3.2
Важность различения циклических и ациклических (древовидных) выражения для обработки запросов подробнее обсуждается в разд. 4.3.
Пока мы лишь заметим, что бывают циклы, которые можно преобразовать к эквивалентным ациклическим графам. В число таких циклов входят те, которые (1) вводятся по транзитивности [Bernstein and Chiu 1981; Yu and Ozsoyoglu 1979], (2) содержат некоторые комбинации дуг, соотвествующих соединительным термам с условием сравнения на неравенство [Bernstein and Goodman 1981b; Ozsoyoglu and Yu 1980], (3) являются "замкнутыми" посредством переменных, связанных квантором всеобщности [Jarke and Koch 1983] и (4) содержат переменные, которые можно подвергнуть декомпозиции с использованием функциональных зависимостей [Kambayashi and Yoshikawa 1983].
Понятия расширенных выражений областей определения (extended range expressions) [Jarke and Schmidt 1982] и вложенных областей определения (range nesting) [Jarke and Koch 1983] обеспечивают обобщение отсоединения запросов, поскольку в них учитываются выражения с кванторами всеобщности. Отношения базы данных, задающие область определения кортежной переменной замещаются выражениями исчисления в соответствии со следующими правилами преобразований:
A3: [EACH r IN rel: predl AND pred2] <=> [EACH r IN [EACH r IN rel: predl]: pred2], A4: SOME r IN rel(predl AND pred2) <=> SOME r IN [EACH r IN rel: predl] (pred2), A5: ALL r IN rel: (NOT(predl) OR (pred2) <=> ALL r IN [EACH r IN rel: predl] (pred2).
Заметим, что особенно полезно правило преобразования A5 для переменных, связанных квантором всеобщности, поскольку при сокращении числа конъюнктов на внешнем уровне вложенности можно ожидать существенного уменьшения размеров промежуточных результатов.
В представленных до сих пор улучшающих преобразованиях используется информация из трех источников: общие правила преобразования и эвристики, управляющие их применением, знание сруктур реляционных данных и сам запрос. Пока не рассмотрены два других источника знаний: ограничения целостности, которые во многих базах данных дополняют структурное определение схемы и реальные данных в базе данных.
Ограничения целостности - это предикаты, которые должны быть истинными для каждого элемента некоторого отношения или каждой комбинации элементов некоторой группы отношений. Поэтому их можно добавлять к выражению выборки любого запроса без изменения его истинностного значения. Имеется несколько подходов, в которых это наблюдение используется скорее для улучшения, а не для упрощения (последняя возможность упоминалась в предыдущем разделе). Они называются основанной на знаниях (knowledge-based) [Hammer and Zdonik 1980] или семантической обработкой запросов [King 1979, 1981].
Предположим, например, что ограничение целостости говорит: "Мы принимаем на работу только профессоров, которые публикуют, по крайней мере, одну статью в год". В этом случае вычисление запроса из Примера 2.1 (в котором спрашиваются имена профессоров со статьями в 1981 г.) становится тривиальным, а вычисление запроса из Примера 3.2 существенно упрощается.
Добавление ограничения целостности к выражению выборки может также изменить структуру запроса, делая его более приспособленным для обработки. Нассмотрим ограничение: "Мы принимаем на работу только местных профессоров". В этом случае терм "d.city = e.city" в примере 3.2 можно опустить. В объектном графе оставшегося запроса больше не содержится цикл.
Успех семантической обработки запросов сильно зависит от разработки эффективных эвристик для выбора между многими преобразованиями, делающими возможным добавление к запросу любой комбинации ограничений целостности. В [King 1981] и [Xu 1983] для принятия этого решения для специального класса реляционных баз данных используются правила в духе искусственного интеллекта.
Яо [Yao 1979] указывает, что существуют случаи, в которых оптимальное преобразование является зависимым от данных. Представленные выше эвристики могут быть не всегда оптимальными, особенно в тех случаях, когда некоторые пути доступа поддерживаются структурами физического хранения. Одним из последствий такой зависимости от данных является то, что средства преобразования запросов должны поддерживаться не только во время компиляции, но и во время выполнения.Кроме того, если эвристики не приносят удовлетворительных результатов, требуется одновременная оптимизация на физическом и логическом уровнях. Однако, прежде чем обратиться к таким интегрированным подходам, необходимо описать физическое выполнение компонентов запросов.
