Стандартизация
В нескольких подходах к оптимизации запросов стандартизованная стартовая точка определяется через нормализованный вариант используемой формы представления запроса [Jarke and Schmidt 1981; Kim 1982; Palermo 1972; Wong and Youssefi 1976]. Здесь мы представляем две нормальные формы для реляционного исчисления, а также правила, которым должна подчиняться процедура нормализации.
Говорят, что представление запроса с использованием реляционного исчисления находится в предваренной нормальной форме (prenex normal form), если его выражение выборки имеет вид
SOME/ALL rel1 IN rel1 . . . SOME/ALL rn IN reln(M),
где M - предикат, не содержащий кванторов. M называется матрицей (matrix) и тоже может быть стандартизован. Говорят, что матрица, состоящая из дизъюнкции конъюнкций (термов Aij), такая как
(A11 AND . . . AND A1n) OR . . . OR (Am1 AND . . . AND Amn),
находится в дизъюнктивной нормальной форме, а матрица, состоящая из конъюнкции дизъюнктов, такая как
(A11 OR . . . OR A1n) AND . . . AND (Am1 OR . . . OR Amn),
находится в конъюнктивной нормальной форме
Предваренная нормальная форма с нормальными формами матрицы приводит к двум нормальным формам выражений реляционного исчисления: дизъюнктивной предваренной нормальной форме (disjunctive prenex normal form, DPNF) и конъюнктивной предваренной нормальной форме (conjunctive prenex normal form, СPNF). Использование DPNF мотивируется целью раздельной оптимизации и выполнения независимых компонентов запросов [Bernstein et al. 1981]. CPNF оказалась полезной для декомпозиции запросов [Wong and Youssefi 1976] и для зависящего от данных улучшения запроса (например, проверка в первую очередь наиболее ограничительного дизъюнта).
Запросы в CPNF могут подвергаться дальнейшему преобразованию к не содержащей кванторов форме, популярной в приложениях доказательства теорем искусственного интеллекта, к так называемой
клаузальной форме (clausal form) [Nilsson 1982]. Языки баз данных, основанные на логике, такие как Prolog [Kowalski 1981], основываются на клаузальной форме.
Поскольку клаузальная форма редко используется при оптимизации запросов (в качестве исключений см. Grant and Minker [1981], Jarke et al. [1984] и Warren [1981]) здесь мы опускаем подробности.
Преобразование произвольного выражения реляционного исчисления к предваренной нормальной форме состоит в перемещении кванторов по термам (справа налево). Перемещение кванторов управляется правилами преобразований, представленными в таб. 1. Нормализация матрицы может достигаться с применением правил ДеМоргана, правил дистрибутивности и правила двойного отрицания (см. таб. 2).
Таб. 1. Правила преобразований для выражений с кванторами
Таб. 2. Правила преобразований для общих выражений
Различия для случаев пустых и непустых отношений областей определения в правилах Q2 и Q3 таб. 1 возникают из-за изменчивости отношений во времени и многосортности реляционного исчисления [Jarke and Schmidt 1982]. Выражение реляционного исчисления может быть преобразовано к односортному исчислению путем введения области определения, такой как (r IN rel), как еще одного типа атомарного предиката:
O1: SOME r IN rel(pred) <=> SOME r((r IN rel) AND pred), O2: ALL r IN rel(pred) <=> ALL r((r IN rel) Т pred).
Применение правил Q2a и Q3a при перемещение квантора из терма вызвало бы поэтому неверный результат в случае пустого отношения области определения. Из этого следует, что при нормализации произвольного выражения реляционного исчисления во время компиляции необходимо сохранять информацию об исходных определениях областей определения переменных, чтобы при необходимости во время выполнения можно было произвести модификации в соответствии с правилами Q2b и Q3b.
