Алгоритмическая сложность
В отношении алгоритмической сложности вычисления языка модификаций, предлагаемого в данной статье, можно сформулировать следующую теорему.
Теорема 1
Введем следующие обозначения для характеристик запроса на модификацию и XML-документа, обрабатываемого с помощью данного запроса:
n
— количество узлов в обрабатываемом документе;
m
— количество операций модификации в запросе на модификацию;
kmax
— максимальный размер выражения_XPath
по всем операциям модификации [];
T(n)
— максимальное время работы каждого из обработчиков, присутствующих в запросе на модификацию. Время может зависеть от числа узлов в документе, например, в случае применения обработчика к корневому узлу документа;
N(n)
— суммарное количество новых узлов, добавляемых в документ в результате выполнения запроса на модификацию.
Тогда время вычисления запроса на модификацию может быть оценено сверху следующим выражением:
Замечание 1 Рассмотренные в разделах
и
обработчики для наиболее употребительных операций модификации вычисляются за константное время.
В справедливости данного замечания легко убедиться простым анализом реализаций рассмотренных обработчиков. Отметим, что те из обработчиков, которые требуют параметризации (например, узлом, добавляемым в документ, или новым именем узла), будучи параметризованы, выполняются за константное время. Сама параметризация относится к фазе статического анализа запроса на модификацию, равно как и разбор участвующих в запросе на модификацию выражений XPath.
Замечание 2 Данной теоремой устанавливается гарантированное полиномиальное от размера документа и от количества операций модификации время вычисления произвольного запроса на модификацию, при условии, что T(n) и N(n) полиномиальны от своих аргументов, т.е. время выполнения каждого обработчика полиномиально от размера документа, и суммарное количество новых узлов, добавленных в документ в результате выполнения запроса на модификацию, полиномиально от размера исходного документа.
Доказательство 1 (теоремы)
Присутствующие в утверждении теоремы слагаемые, помеченные как (4), (5) и (6), относятся соответственно к следующим этапам вычисления запроса на модификацию:
к этапу сопоставления обработчиков с узлами;
к этапу обхода дерева документа и вызова обработчиков на обрабатываемых узлах;
к проверке корректности модификаций, произведенных по результатам вычисления обработчиков.
Доказательство теоремы заключается в последовательном рассмотрении каждого из обозначенных этапов и получении верхней оценки времени вычисления по каждому этапу.
Как обсуждалось в разделе , на этапе сопоставления обработчиков с узлами документа производится вычисление выражений_XPath
всех операций модификации относительно базовых узлов этих операций.
Ключевым моментом на данном этапе обработки является то, что в соответствии с семантикой предлагаемого в настоящей статье языка запросов максимальное количество базовых узлов для произвольной операции модификации не зависит от количества операций модификации в запросе на модификацию. Даже в том случае, когда все операции модификации в некотором запросе на модификацию связаны посредством базовых узлов (т.е. базовыми узлами каждой последующей операции модификации являются обрабатываемые узлы предыдущей операции модификации), максимальное количество базовых узлов для любой операции модификации не может превосходить общее число узлов в обрабатываемом документе, т.е. число n .
Для вычисления выражений_XPath
используется разработанная автором реализация XPath функциональными методами, которая включает в себя средства оптимизации [], позволяющие получить гарантированную верхнюю оценку времени вычисления, равную:
O( kmax·n5 ) .
Выражения XPath вычисляются относительно каждого из базовых узлов каждой из операции модификации. Умножая время вычисления выражения XPath на количество базовых узлов (которых, как показано выше, не больше n для каждой операции модификации) и на количество операций модификации m, получим (4).
На этапе обхода дерева SXML- документа производится вызов обработчиков на обрабатываемых узлах и формирование нового дерева в соответствии с возвращаемыми результатами обработчиков.
Количество обработчиков, которое может быть ассоциировано с одним узлом SXML-документа, не превосходит суммарного количества базовых узлов по всем операциям модификации, т.е. произведения m·n .
Поскольку по семантике предлагаемого языка запросов несколько обработчиков, ассоциированных с одним и тем же узлом, вызываются по правилам суперпозиции, на время выполнения одного обработчика влияют узлы, которые могли быть добавлены в результате вызовов предыдущих по порядку обработчиков, и поэтому это время оценивается сверху выражением T(n+N(n)).
Произведение максимального времени работы одного обработчика на максимальное количество ассоциированных с одним узлом обработчиков и на количество узлов в исходном документе и дает (5).
Производимые проверки корректности сделанных модификаций уже не зависят от вида запроса на модификацию или количества операций модификации в нем, но зависят только от сконструированного результирующего SXML-документа. В терминах введенных в условии теоремы обозначений, данное соображение означает, что временная оценка этапа проверки корректности сделанных модификаций зависит только от числа (n+N(n)), т.е. от количества узлов в новом SXML-документе.
Среди производимых проверок асимптотически доминирует проверка на отсутствие у данного элемента нескольких атрибутов с одинаковыми именами.
Проверка на отсутствие совпадающих имен атрибутов у данного элемента производится с помощью известного алгоритма сортировки слиянием по именам атрибутов данного элемента. Время работы алгоритма сортировки слиянием оценивается выражением
O( (n+N(n))·log2(n+N(n)) ) .
Ввиду того, что данная проверка производится для каждого элемента в результирующем SXML-документе, записанная оценка умножается на число узлов в документе, что окончательно дает (6).
Сумма полученных временных оценок по каждому из этапов вычисления запроса на модификацию и обеспечивает утверждение теоремы.
