XML - статьи

         

/A>Родственные работы по предметной области


При исследовании работ по данной предметной области нельзя не упомянуть статью [7], в которой производится конструктивное доказательство того, что SXML является полной моделью Информационного Пространства XML [6]. В статье предлагаются методы восстановления изоморфизма между SXML и моделью данных XPath.

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

parent(x) = { y | y=child*(root), x=child(y) }   ,

где символ child* обозначает транзитивное замыкание оси

child, а символом root обозначен корень дерева SXML-документа.

Очевидным недостатком поиска родительского узла от корня документа является его временная дороговизна, поскольку данный метод в общем случае требует сканирования всего дерева документа. Необходимо отметить, что до настоящего времени обратные оси в SXPath были реализованы именно с помощью метода поиска родительского узла от корня документа. Одной из целей, достигнутых в настоящей работе, было повышение производительности SXPath за счет оптимизации вычисления обратных осей.

В статье [7] также предлагается 3 метода восстановления указателей к родительским узлам за счет присоединения аннотаций к дочерним узлам дерева SXML-документа. Каждый из данных методов имеет свои преимущества и недостатки для конкретной решаемой задачи, однако общим недостатком всех этих 3-х методов является значительное усложнение структуры данных, используемой для представления XML-документа в виде S-выражения. С добавленными к узлам аннотациями документ на SXML теряет свое важное преимущество – являться одновременно внутренним представлением данных и наглядной внешней нотацией. Указатели на родительские узлы, добавленные к документу в виде аннотаций, также усложняют обработку SXML-документа, поскольку превращают дерево документа в ориентированный граф с двунаправленными указателями. Как отмечается в [7], обработка циклических структур в чисто функциональном стиле программирования является далеко не простой задачей.


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

В статье [13] предлагается алгоритм, основанный на правилах перезаписи, позволяющий преобразовать путь доступа XPath в эквивалентный путь доступа, не содержащий обратных осей. Хотя в [13] решалась задача обеспечения потокового вычисления путей доступа XPath, полученные результаты в определенной степени могут быть использованы и в SXML для решения проблемы указателей на родительские узлы. Необходимо отметить, что правила перезаписи требуют предварительного расширения языка XPath дополнительным оператором сравнения узлов, которого нет в Спецификации XPath версии 1.0.

Алгоритм перезаписи, предложенный в [13], обладает тем недостатком, что не любое выражение XPath может быть с его помощью преобразовано в эквивалентное выражение, не содержащее обратных осей [7]. Предлагаемый в настоящей работе алгоритм вычисления обратных осей применим для вычисления произвольного выражения языка XPath без необходимости иметь указатели на родительские узлы в дереве документа.


Содержание раздела