Упрощение
Мы уже видели, что может существовать несколько семантически эквивалентных выражений одного и того же запроса. Одним из источников различия между двумя эквивалентными выражениями являеься из уровень избыточности [Hall 1976; Stroet and Engmann 1979]. Прямолинейное вычисление избыточного выражения привело бы к выполнению набора операций, некоторые из которых являются излишними. Поэтому оптимизатор запросов стремится к устранению избыточности путем преобразованию избыточного выражения к эквивалентному выражению, не являющемуся избыточным.
Избыточное выражение выражение может быть упрощено путем применения правил преобразования M4a-M4j, в которых учитывется идемпотентность (см. таб. 2). Применение этих правил усложняется тем фактом, что идемпотентность может встретиться на любом уровне выражения по причине наличия общих подвыражений, т.е. подвыражений, которые могут встретиться более одного раза в выражении, представляющем запрос. Поэтому, чтобы упростить, например, выражение
[EACH e IN employees: e.ename = 'Smith' OR (e.status = assistant OR e.status = professor) AND NOT(e.status = professor OR e.status = assistant)]
до
[EACH e IN employees: e.ename = 'Smith']
посредством правил M4d и M4g, сначала нужно распознать эквивалентность подвыражений
(e.status = assistant OR e.status = professor)
и
(e.status = professor OR e.status = assistant)
Алгоритмы приводятся в [Downey et al. 1980 и Hall 1974, 1976]. Распознавание общих подвыражений и применение правил идемпотентности должно выполняться скорее совместно, чем последовательно, поскольку при упрощении выражения на основе правил идемпотентности могут появиться новые общие подвыражения, которые, в свою очередь, являются предметом упрощения. Выражения, связанные с пустыми отношениями, также можно упрощать. Правила преобразований для их упрощения приводятся в таб. 3. (Заметим, что эти правила можно применять только во время выполнения.)
Таб. 3. Правила преобразований для выражений с пустыми отношениями
Термы, как они определены в разд. 2.1, в реляционном исчислении служат атомарными предикатами.
Однако эти термы могут быть упрощены или удалены, если явно учитывается семантика операций сравнения. Важным приложением является так называемое распространение констант, в котором используются законы транзитивности, такие как
r.A op s.B AND s.B = const => r.A op const,
позволяющее сократить в запросе число двуместных термов. В алгоритмах минимизации числа строк в табло (см. разд. 2.4) систематически используются такие правила упрощения для конъюнктивных запросов [Aho et al. 1979a; Sagiv 1981, 1983]. Поскольку число строк в табло больше числа соединений (двуместных соединительных термов) в выражении, минимизация числа строк соответствует исключению избыточных соединений.
Сагив и Яннакакис [Sagiv and Yannakakis 1980] расширяют методы табло для обеспечения возможности упрощения выражений, содержащих дизъюнкты. Однако обобщение методов для всех выражений реляционно полного языка все еще остается открытой проблемой.
Для "семантического" упрощения запросов может использоваться информация о семантических ограничениях целостности [Aho et al. 1979a, 1979b, 1979c; Jarke et al. 1984; Johnson and Klug 1982; Ott and Horlaender 1982; Rosenthal and Reiner 1984]. В качестве простого примера рассмотрим случай ограничений ключа. Если r и r' - это (свободные или связанные квантором существования) переменные с одной и той же область определения, отношением "rel", то эквисоединение вида "r.key = r'.key" является избыточным в том смысле, что этот терм и одна из переменных, например, r' могут быть удалены с подстановкой r вместо r' в любом терме, в который входит r'. Этот тип упрощения особенно пригоден в контексте обработки представлений, когда преобразование пользовательских запросов над представлениями к системным запросам над хранимыми отношениями может привнести существенную избыточность. Область применения семантического упрощения может быть расширена за счет привлечения дополнительных ограничений, порождаемых структурой запроса [Klug 1980; Koch et al. 1981].
Заключительная возможность упрощения возникает в тех случаях, когда удается показать, что один или несколько конъюнктов матрицы стандартизованного запроса никогда не удовлетворяются [Eswaran et al. 1976; Klug 1983; Munz et al. 1979; Ozsoyoglu and Yu 1980]. Для примера рассмотрим выражение
r.A ≥ s.B AND s.B > t.C AND t.C ≤ r.A,
которое порождает противоречие r.a > r.a и поэтому может быть заменено булевским значением false. Проблема определения невыполнимости условия терма эффективно решается во время компиляции для конъюнкции термов с операциями сравнения (=, <, &le , >, &ge) [Rosenkrantz and Hunt 1980], но вычислительно сложна, если допускается операция сравнения на неравенство.
