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


Набросок реализации расширенных магических множеств (EMS) - часть 2


Для на основе его использования в t формируется магическое множество m_rα и, если r является хорошей, оно делается опорным и добавляется к табличному выражению для .

Магическая обработка производится для каждого табличного выражения, проходимого при обходе графа запроса. Мы избегаем повторной обработки табличного выражения, за исключением плохих табличных выражений при особых условиях. Для нашего алгоритма EMS справедлива следующая теорема (в предположении, что сначала мы избавляемся ото всех циклов в запросе Q, состоящем исключительно из плохих таблиц).

Теорема 5.1 Для любого графа запроса Q алгоритм EMS завершается, и EMS(Q) эквивалентен Q при применении стратегии выполнения Starburst.

Украшения и магические преобразования объединяются в однофазный алгоритм (разд. 4.3). По большей части используется простое bcf-украшение, хотя для плохих операций требуются специальные улучшенные украшения. Алгоритм EMS является расширяемым по отношению к (1) новым операциям в табличных выражениях и (2) стратегии обхода (в глубину, в ширину, снизу-вверх и т.д.).




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



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