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


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


В отношении алгоритмической сложности вычисления языка модификаций, предлагаемого в данной статье, можно сформулировать следующую теорему.

Теорема 1  

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

n

— количество узлов в обрабатываемом документе;

m

— количество операций модификации в запросе на модификацию;

kmax

— максимальный размер выражения_XPath

по всем операциям модификации [];

T(n)

— максимальное время работы каждого из обработчиков, присутствующих в запросе на модификацию. Время может зависеть от числа узлов в документе, например, в случае применения обработчика к корневому узлу документа;

N(n)

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

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

Замечание 1  Рассмотренные в разделах 

и 

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

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

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




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



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