Язык модификации данных формата XML функциональными методами


Алгоритмическая сложность - часть 2


Доказательство 1 (теоремы)  

Присутствующие в утверждении теоремы слагаемые, помеченные как (4), (5) и (6), относятся соответственно к следующим этапам вычисления запроса на модификацию:

к этапу сопоставления обработчиков с узлами;

  • к этапу обхода дерева документа и вызова обработчиков на обрабатываемых узлах;

  • к проверке корректности модификаций, произведенных по результатам вычисления обработчиков.

    Доказательство теоремы заключается в последовательном рассмотрении каждого из обозначенных этапов и получении верхней оценки времени вычисления по каждому этапу.

    1. Как обсуждалось в разделе , на этапе сопоставления обработчиков с узлами документа производится вычисление выражений_XPath

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

      используется разработанная автором реализация XPath функциональными методами, которая включает в себя средства оптимизации [], позволяющие получить гарантированную верхнюю оценку времени вычисления, равную:

      O( kmax·n5 )   . 

      Выражения XPath вычисляются относительно каждого из базовых узлов каждой из операции модификации. Умножая время вычисления выражения XPath на количество базовых узлов (которых, как показано выше, не больше n для каждой операции модификации) и на количество операций модификации m, получим (4).




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



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