Пространство поиска
Как отмечалось в , пространство поиска для оптимизации зависит от набора алгебраических преобразований, сохраняющих эквивалентность, и набора физических операций, поддерживаемых в оптимизаторе. В этом разделе я буду обсуждать некоторые из обнаруженных важных алгебраических преобразований. Следует заметить, что преобразования не обязательно снижают стоимость, и поэтому для гарантирования положительного результата их следует применять в стиле основанного на оценочной стоимости алгоритма перебора.
В жизненном цикле оптимизации оптимизатор может использовать несколько представлений запроса. Исходным представлением часто является дерево грамматического разбора, а окончательное представление - это дерево операций. В качестве промежуточного представления используются также деревья логических операций (называемых еще и деревьями запросов), которые изображают алгебраические выражения. На рис. 3 приведен пример дерева запроса. Часто узлы деревьев запроса аннотируются дополнительной информацией.
Рис. 3. Дерево запроса
- -
