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


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


  • На этапе обхода дерева SXML-документа производится вызов обработчиков на обрабатываемых узлах и формирование нового дерева в соответствии с возвращаемыми результатами обработчиков.
    Количество обработчиков, которое может быть ассоциировано с одним узлом SXML-документа, не превосходит суммарного количества базовых узлов по всем операциям модификации, т.е. произведения m·n .
    Поскольку по семантике предлагаемого языка запросов несколько обработчиков, ассоциированных с одним и тем же узлом, вызываются по правилам суперпозиции, на время выполнения одного обработчика влияют узлы, которые могли быть добавлены в результате вызовов предыдущих по порядку обработчиков, и поэтому это время оценивается сверху выражением T(n+N(n)).
    Произведение максимального времени работы одного обработчика на максимальное количество ассоциированных с одним узлом обработчиков и на количество узлов в исходном документе и дает (5).

  • Производимые проверки корректности сделанных модификаций уже не зависят от вида запроса на модификацию или количества операций модификации в нем, но зависят только от сконструированного результирующего SXML-документа. В терминах введенных в условии теоремы обозначений, данное соображение означает, что временная оценка этапа проверки корректности сделанных модификаций зависит только от числа (n+N(n)), т.е. от количества узлов в новом SXML-документе.
    Среди производимых проверок асимптотически доминирует проверка на отсутствие у данного элемента нескольких атрибутов с одинаковыми именами.
    Проверка на отсутствие совпадающих имен атрибутов у данного элемента производится с помощью известного алгоритма сортировки слиянием по именам атрибутов данного элемента. Время работы алгоритма сортировки слиянием оценивается выражением

    O( (n+N(n))·log2(n+N(n)) )   . 

    Ввиду того, что данная проверка производится для каждого элемента в результирующем SXML-документе, записанная оценка умножается на число узлов в документе, что окончательно дает (6).

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




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



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