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

На правах^рукописи

8)им/

ЛИЗОРКИН ДМИТРИЙ АЛЕКСЕЕВИЧ

ФУНКЦИОНАЛЬНЫЕ МЕТОДЫ ОБРАБОТКИ ХМЬ-ДАННЫХ

05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА 2005

Работа выполнена на кафедре системного программирования факультета вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова.

Научный руководитель: член-корреспондент РАН,

профессор

Иванников Виктор Петрович.

Официальные оппоненты: доктор физико-математических наук,

профессор

Абрамов Сергей Михайлович;

кандидат физико-математических наук, старший научный сотрудник Кулямин Виктор Вячеславович.

Ведущая организация: Вычислительный центр имени А. А. Дородницына Российской академии наук.

Защита диссертации состоится 2005 года в К часов

на заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория

С диссертацией можно ознакомиться^ в библиотеке факультета ВМиК МГУ. Автореферат разослан О^М^Л 2005 г.

Ученый секретарь

диссертационного совета, у

профессор / /У Ау/ А--ЧН-П. Трифонов

Общая характеристика работы Актуальность темы

В настоящее время язык XML используется как основное средство для представления слабоструктурированных данных. Поскольку большинство языков платформы XML не является языками программирования общего назначения, при реализации XML-приложений языки платформы XML обычно используются совместно с некоторыми традиционными языками программирования. Комбинирование различных по своей природе языков приводит к проблеме, известной как потеря соответствия (impedance mismatch). Преодоление проблемы потери соответствия в контексте обработки XML-данных, разработка и оптимизация алгоритмов обработки XML-данных функциональными методами и интеграция языка функционального программирования Scheme с языками платформы XML и определяют актуальность диссертационной работы.

Цель и задачи работы

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

Для достижения основной цели работы поставлены следующие задачи:

• создать язык запросов к XML-данным, обладающий следующими свойствами:

- язык запросов должен обеспечивать тесную интеграцию языка адресации частей XML-документа XPath с функциональным языком

программирования общего назначения Ochcmfr

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С. Re ОЭ

Winv 9 I. |\Л

33&

— язык запросов должен обеспечивать средство формулирования запросов к совокупности XML-документов, семантически связанных при помощи XLink - языка ссылок XML;

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

Научная новизна

Научной новизной обладают следующие результаты работы:

• преодолена проблема потери соответствия при интеграции языка адресации частей XML-документа XPath с языком программирования общего назначения;

• разработан язык запросов с поддержкой семантики языка ссылок XML — XLink;

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

Практическая значимость

Достигнутая интеграция языка адресации частей XML-документов XPath с языком функционального программирования Scheme может быть использована для достижения большей гибкости и расширяемости при формулировании критериев выборки XML-данных.

Разработанный язык запросов к совокупности XML-документов, связанных ссылками языка XLink, может быть использован для повышения наглядности представления объектов прикладной предметной области на XML и упрощения задач обработки XML-данных для приложения.

Разработанные способы оптимизации выполнения запросов могут быть использованы для повышения эффективности процессоров языков XPath и XQuery и вычислителей запросов в XML-СУБД.

Реализованный прототип среды разработки XML-приложений функциональными методами был использован при создании в Институте системного программирования РАН промышленной системы виртуальной интеграции BizQuery и XML-СУБД Sedna.

Апробация работы и публикации

По материалам диссертации опубликовано восемь работ [1-8]. Основные положения работы докладывались на следующих конференциях и семинарах:

• на восьмой международной конференции "Advances in Databases and Information Systems" (ADBIS) (2004 r);

• на восьмидесятом и девяносто восьмом семинарах Московской Секции ACM SIGMOD (2002 и 2005 гг);

• на семинаре "Современные сетевые технологии" под руководством д.ф.-м.н., профессора Васенина В.А. (2005 г).

Структура и объем диссертации

Работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Общий объем диссертации составляет 229 страниц. Список литературы содержит 71 наименование.

Краткое содержание работы

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

работы, ее Приводится

Первая глава является обзорной и содержит изложение методов и средств, которые лежат в основе разработок, описываемых в последующих трех главах.

В первом разделе данной главы дается краткий обзор основных понятий платформы XML: расширяемого языка разметки (XML), механизма пространств имен в XML, языка адресации частей XML-доку мента XPath и языка ссылок XLink.

Во втором разделе первой главы рассматриваются существующие подходы к обработке XML-данных и обсуждается присущая существующим подходам проблема потери соответствия (impedance mismatch). Отмечается сходство между XML-данными и S-выражениями, где последние служат текстуальным представлением нетипизированных вложенных списков, являющихся основной конструкцией для представления программ и данных в языках функционального программирования Lisp и Scheme. Выбор функциональных методов для обработки XML-данных мотивируется как средство преодоления проблемы потери соответствия.

В третьем разделе первой главы рассматривается SXML — представление XML-доку мента в виде S-выражения. Составляющие XML-документ информационные единицы информационного пространства XML (XML Information Set) хорошо поддаются описанию в виде S-выражения, что делает внешние текстуальные нотации XML и SXML достаточно похожими. Поскольку внутренним представлением S-выражений в языках функционального программирования Lisp и Scheme служат вложенные списки, формат SXML обеспечивает возможность использования стандартных функций обработки списков для обработки XML-данных: конструирования тегов разметки, выполнения запросов и проведения трансформаций.

В четвертом разделе первой главы рассматривается библиотека SXPath, предоставляющая интерфейс прикладного программирования на

Scheme для вычисления некоторых конструкций языка XPath над SXML-документами Описываются основные низкоуровневые функции библиотеки SXPath, внутренняя логика которых иллюстрирует удобство формата SXML для адресации частей документа при вычислении практически важных конструкций языка XPath. Рассматривается высокоуровневый списковый синтаксис библиотеки SXPath, выступающий в качестве "родного" синтаксиса для языка функционального программирования Scheme и являющийся аналогом сокращенного синтаксиса языка XPath по сравнению с его полным синтаксисом.

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

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

Предла! ае1ся построение вычислителя языка XPath функциональными методами. Для достижения преимуществ наличия двух отдельных фаз обработки, определенных в спецификации XPath 2.0, фазы статического анализа и фазы динамического вычисления — предлагается представление данных фаз функцией высокого порядка. Фазе статического анализа сопоставляется вызов разработанной автором функции, которая принимает выражение XPath и возвращает снова функцию, представляющую данное выражение XPath в прекомпилированном виде. При вызове последней функции с входными данными формата SXML, вычислению этой функции соответствует фаза динамического вычисления выражения XPath, а

возвращаемым результатом служит результат вычисления выражения XPath над входными данными.

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

Библиотека SXPath была расширена поддержкой выражений XPath, благодаря чему формулирование запросов к документам формата SXML может осуществляться в двух различных синтаксисах: в текстовом синтаксисе языка XPath и в списковом синтаксисе библиотеки SXPath. Каждый из двух синтаксисов обладает своими преимуществами. Так, текстовый синтаксис позволяет прозрачным образом переносить существующие навыки программистов XML-приложений на созданную среду обработки XML-данных функциональными методами. Списковый синтаксис за счет своей близости к синтаксису языка функционального программирования Scheme обеспечивает приложение удобными и наглядными возможностями по конструированию и анализу запросов.

Преимущества каждого из двух синтаксисов - текстового и спискового -делают привлекательным комбинирование обоих синтаксисов внутри единого запроса. В работе предлагается расширение спискового синтаксиса возможностью использования выражения XPath в текстовом синтаксисе в качестве составного шага доступа. Предложенный способ комбинирования текстового и спискового синтаксисов обеспечивает расширение языка XPath за счет его интеграции со Scheme:

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

• Поскольку функции в языке функционального программирования Scheme являются объектами первого класса, в роли шага доступа может выступать произвольная функция Scheme, которая принимает объект типа "набор узлов" языка XPath и возвращает новый набор узлов:

/ : набор_узлов —> набор_узлов .

Возможность использования произвольной функции Scheme с заданной сигнатурой в качестве шага доступа обеспечивает расширение языка XPath до языка запросов к XML-данным. Тогда как в языке XPath путь доступа позволяет получить набор узлов, с необходимость принадлежащих исходному XML-документу, язык запросов предоставляет возможность создания XML-данных в рамках используемого внутреннего представления. Так, язык запросов к XML-данным XQuery консорциума W3C содержит, помимо прочих операций, конструкторы новых узлов дерева XML во внутреннем представлении.

Для узлов, представленных на SXML, операции конструирования новых узлов достигаются стандартными функциями языка Scheme по конструированию списков. Более того, операции квази-цитирования (quasiquote) и снятия цитирования (unquote) языка Scheme предоставляют наглядный синтаксис для комбинирования вычислимых фрагментов с фрагментами результата и являются близкой аналогией вычислимых и литеральных конструкторов языка XQuery.

В работе отмечается, что семантика FLWOR-выражения — основной конструкции языка XQuery, обеспечивающей итерацию и связывание

локальных переменных с промежуточными результатами, — в значительной степени напоминает семантику выражения, записанного с использованием функциональной парадигмы организации вычислений "перечисление-фильтрация-отображение-накопление" (enumerate-filter-map-accumulate). Ввиду семантического сходства между операциями FLWOR-выражения и этапами обработки в парадигме "перечисление-фильтрация-отображение-накопление", FLWOR-выражения из практически важного подмножества запросов языка XQuery имеют прямолинейные аналоги в терминах парадигмы "перечисление-фильтрация-отображение-накопление". Поскольку все необходимые составляющие для организации вычислений в парадигме "перечисление-фильтрация-отображение-накопление" представлены в языке Scheme стандартными функциями обработки списков, достигнутая интеграция возможностей языка XPath по адресации частей документа с возможностями Scheme по обработке списковых структур данных обеспечивает функциональность языка запросов для XML-данных, представленных на SXML.

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

Третья глава посвящена описанию разработанного автором расширения языка запросов, которое предоставляет приложению возможность формулирования запросов к совокупности XML-документов, семантически связанных ссылками XLink - языка ссылок XML, - и осуществления переходов по дугам, определяемым этими ссылками.

Язык XLink консорциума W3C является инструментом для описания

взаимосвязей между ресурсами в виде ссылок на XML. Ссылка языка XLink позволяет устанавливать отношение связи между более чем двумя ресурсами и содержит несколько дуг, каждая из которых характеризуется своим исходным ресурсом и целевым ресурсом.

В спецификации XLink определяются лишь структуры данных для описания ссылок и минимальная модель их поведения. Все действия по распознаванию элементов языка XLink в XML-документе и обработке k описываемых этими элементами ссылок перекладываются на приложение.

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

Существующие языки запросов и интерфейсы прикладного программирования не обеспечивают высокоуровневых средств обработки ссылок XLink в XML-документах Так, язык XQuery, позиционируемый консорциумом W3C как язык запросов к разнообразным типам источников XML-данных, не предоставляет специализированных возможностей по обработке имеющихся в XML-документе ссылок языка XLink в соответствии со спецификацией XLink. Интерфейсы прикладного программирования для обработки соединенных ссылками языка XLink XML-документов являются достаточно низкоуровневыми и, кроме того, страдают от проблемы потери соответствия.

В работе предлагается расширение языка запросов поддержкой семантики ссылок XLink. Разработанное расширение базируется на языке адресации частей XML-документа XPath и состоит в добавлении трех новых осей к грамматике XPath и добавлении к узлу каждого типа, представленного в модели данных, по одному дополнительному свойству.

Разработанное расширение языка запросов поддержкой XLink может быть использовано для повышения наглядности представления объектов прикладной предметной области на XML и упрощения задач обработки XML-

данных для приложения. Расширение языка запросов способствует удобству применения ссылок языка XLink при моделировании и обработке объектов прикладной предметной области.

Автором было замечено, что термин "ось" (axis) в XPath очень близок термину "переход" (traverse) в XLink, поскольку оба подразумевают перемещение с одного места в документе на другое. Из данного наблюдения был сделан вывод, что при построении на основе XPath языка запросов к совокупности связанных XML-документов операции перехода по дуге XLink органичным образом соответствует ось. По аналогии с англоязычным названием для перехода в XLink данная ось была названа traverse. Следуя общему стилю, принятому в спецификации XPath при определении осей, определение оси traverse записывается следующим образом:

Определение 1 Ось traverse содержит все узлы, являющиеся целевыми ресурсами для всех дуг XLink, для которых контекстный узел служит исходным ресурсом.

С помощью оси traverse могут быть выбраны узлы, находящиеся в другом XML-документе, нежели контекстный узел, т.к. дугами языка XLink могут быть соединены ресурсы, находящиеся в разных XML-документах. Предлагаемая ось traverse позволяет приложению осуществлять переходы по дугам языка XLink полностью прозрачным образом, - независимо от того, в ссылке какого типа и в каком XML-документе была определена дуга.

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

XML, что может рассматриваться как "представление" ('View") в терминах реляционных баз данных и позволяет формулировать запросы к дуге XLink единообразно с другими информационными единицами XML-документа. В полной аналогии с атрибутами и объявлениями пространств имен, в работе предлагается расширение модели данных XPath наличием ассоциированного с узлом любого типа набора выходящих из него дуг XLink. Каждая дуга реализуется в расширенной модели данных XPath узлом типа "элемент" и является представлением дуги в виде информационной единицы.

Операция получения всех дуг, исходным ресурсом которых служит контекстный узел, была оформлена в виде новой оси XPath. По аналогии с англоязычным термином для дуги, введенным в спецификации языка XLink, данная ось получила название arc:

Определение 2 Ось arc содержит все узлы, являющиеся представлением в виде информационных единиц всех дуг XLink, для каждой из которых контекстный узел служит исходным ресурсом.

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

Когда интересующие приложение дуги XLink выбраны, приложению может потребоваться осуществить по ним переход. Для перехода к целевому ресурсу дуги XLink из информационной единицы, представляющей дугу, в работе предлагается дополнительная ось, названная traverse-arc. Семантика оси traverse-arc во многом напоминает семантику оси traverse.

При реализации предложенного расширения языка запросов были использованы функциональные методы программирования и формат SXML. С целью создания единообразной среды для работы приложения как с SXML-документом, так и с дугой XLink, в реализации последняя также представлена в формате SXML. Предложенные в работе три дополнительные оси, обеспечивающие поддержку в XPath языка XLink, были реализованы в качестве дальнейшего расширения библиотеки SXPath.

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

В первом разделе данной главы рассматриваются результаты экспериментов, которые показывают проблему экспоненциального времени, в неблагоприятном случае затрачиваемого на вычисление выражений XPath промышленными процессорами языка XPath — Saxon, Xalan и ХТ. Выделяются такие конструкции языка XPath, недостаточно предусмотрительный подход к вычислению которых может приводить к экспоненциальной алгоритмической сложности всего вычислителя языка XPath от размера вычисляемых выражений:

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

• Предикаты, синтаксически вложенные внутрь других предикатов, могут требовать экспоненциального роста времени вычисления с ростом глубины вложенности.

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

и размера XML-документа. Среди предложенных в работе способов оптимизации в качестве наиболее значимых для улучшения оценки сложности можно выделить следующие:

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

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

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

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

4. Предварительное вычисление всех глубоко вложенных предикатов. Глубоко вложенными были названы такие предикаты, которые при прямолинейном способе их вычисления, заданном в спецификации XPath, требуют своего вычисления потенциально большее количество раз по сравнению с максимальным количеством различных контекстов. Автором разработан способ выявления на фазе статического анализа выражения XPath всех глубоко вложенных предикатов, и предлагается вычислять такие предикаты в самом начале фазы динамического вычисления, для всех возможных на данной фазе контекстов. Получение значения глубоко вложенного предиката в процессе вычисления выражения XPath достигается возвращением заранее вычисленного значения данного предиката для требуемого контекста.

Для формулирования утверждения основной теоремы вводятся определения размера XML-документа и размера выражения XPath.

Определение 3 Размером XML-документа назовем положительное число, равное сумме количества узлов в документе, общей длины текстовых строк в текстовых узлах и значениях атрибутов и максимальной длины квалифицированного имени по всем именованным узлам.

Определение 4 Размером выражения языка XPath назовем положительное число, равное сумме количества вершин в абстрактном синтаксическом дереве этого выражения, соответствующем грамматике языка XPath, и максимальной длины строки по всем фигурирующим в выражении строковым литералам (XPath literals).

Теорема 1 Пусть даны произвольный ХМЬ-документ, имеющий размер |£>|, и произвольное выражение языка ХРаимеющее размер \Е\. Предложенные в диссертационной работе способы оптимизации обеспечивают вычисление данного выражения ХРаЛ над данным ХМЬ-документом с алгоритмической сложностью, не превосходящей величины

0(|2?МД|5) •

Теоремой 1 устанавливается гарантированная полиномиальная алгоритмическая сложность вычисления любого выражения XPat.li над любым ХМЬ-документом, что достигается благодаря предложенным способам оптимизации.

Следствие 1 Полученная в теореме 1 гарантированная верхняя оценка алгоритмической сложности может быть значительно улучшена для широких классов практически важных выражений языка ХРаЬк.

Так, если выражение ХРаЛ является путем доступа, не содержащим предикатов, то предлагаемые в работе способы оптимизации обеспечивают линейную алгоритмическую сложность вычисления данного выражения от размера ХМЬ-документа и от размера выражения:

0(\Е\.\Ю\) .

Если выражение ХРаШ является путем доступа, не содержащим позиционных предикатов, операций обобщенного сравнения и вызовов функции сопса-Ь, строковые литералы в котором имеют ограниченную длину, то алгоритмическая сложность вычисления такого выражения:

0(\Е\ ■ |£>|2) .

Полученные в теореме 1 результаты естественным образом распространяются на случай формулирования запросов к совокупности ХМЬ-документов, связанных ссылками языка Х1лпк. Верхняя оценка

сложности, утверждаемая теоремой, в этом случае также справедлива, с той модификацией, что в качестве величины \D\ берется суммарный размер XML-доку ментов, на которые может быть осуществлен переход по дугам языка XLink в процессе выполнения запроса, и размер этих дуг, представленных в виде информационных единиц.

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

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

В последнем разделе четвертой главы рассматриваются результаты экспериментов, произведенных в отношении сделанной в работе реализации. Результаты экспериментов показывают, что сделанная в работе реализация языка запросов функциональными методами в сравнении с промышленными процессорами языка XPath Saxon, Xalan и ХТ обеспечивает полиномиальное время выполнения и в целом не проигрывает по производительности процессорам XPath также и на множестве практически важных выражений XPath.

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

Основные результаты работы

В работе были получены следующие основные результаты:

• Создан язык запросов к XML-данным, обладающий следующими свойствами:

— язык запросов обеспечивает тесную интеграцию языка адресации частей XML-документа XPath с функциональным языком программирования общего назначения Scheme;

- язык запросов обеспечивает средство формулирования запросов к совокупности XML-документов, семантически связанных ссылками языка XLink.

• Разработаны методы оптимизации выполнения запросов, гарантирующие полиномиальную сложность от размера запроса и размера документа.

• Реализован прототип среды разработки XML-приложений, поддерживающей единую модель данных и позволяющей облегчить и ускорить процесс создания XML-приложений.

По теме диссертации опубликованы следующие работы

1. Лизоркин Д.А., Лисовский К.Ю. SXML: XML-документ как S-выражение // Электронные библиотеки. - М.: ИРИО, 2003. - Т. 6, вып. 2. - с. 9-17. - ISSN 1562-5419 = Russian digital libraries journal. http://www.elbib.ru/index.phtml?page=elbib/rus/journal/2003/part2/LK

2. Лизоркин Д.А., Лисовский К.Ю. Пространства имен в XML и SXML // Электронные библиотеки. - М.: ИРИО, 2003. - Т. 6, вып. 3. - с. 42-52. -ISSN 1562-5419 — Russian digital libraries journal.

http://www.elbib.ru/index.phtml?page=elbib/rus/journal/2003/part3/LL <

3. Лизоркин Д.А., Лисовский К Ю. Язык XML Path (XPath) и его функциональная реализация SXPath // Электронные библиотеки. - М.: ИРИО, 2003. - Т. 6, вып. 4. - с. 34-46. - ISSN 1562-5419 = Russian digital libraries journal.

http: //www.elbib.ru/index.phtml?page=elbib/rus/journal/2003/ part4/LL

4. Лизоркин Д.А., Лисовский К.Ю. Языки XSLT и XLink и их реализация

функциональными методами // Электронные библиотеки. - М.: ИРИО, 2003. - Т. 6, вып. 5. - с. 36-48. - ISSN 1562-5419 = Russian digital libraries journal.

http://www.elbib.ru/index.phtml?page=elbib/rus/journal/2003/part5/LL

5. Grinev M., Lizorkin D. XQuery Function Inlining for Optimizing XQuery Queries : Proc. 8th East-European conf. on Advances in Databases and Information Systems (ADBIS'2004), Budapest, 22-25 Sep., 2004. - ADBIS'04 Proceedings / Bencziir A., Demetrovics J. (eds.). - Budapest: CARI, 2004. -260 pp. - pp. 32-47. - ISBN 963 311 358 X.

http://www.sztaki.hu/conferences / ADBIS/4-Lizorkin.pdf

6. Лизоркин Д.А. Оптимизация вычисления обратных осей языка XML Path при его реализации функциональными методами // Сборник трудов

Института системного программирования РАН / Под ред. чл.-корр. РАН Иванникова В.П. - М.: ИСП РАН, 2004. - Т. 8, ч. 2. - 214 с. - с. 93-119. -ISBN 5-89823-026-2.

http://modis.ispras.ru/Lizorkin/Publications/xpath-context.ps

7. Лизоркин Д.А., Лисовский К.Ю. Реализация XLink - языка ссылок XML - с помощью функциональных методов // Программирование. -М.: Наука, 2005. - N 1. - С. 52-72. - ISSN 0361-7688 = Programming and computer software.

8. Лизоркин Д.А. Язык запросов к совокупности XML-документов, соединенных при помощи ссылок языка XLink // Программирование. -М : Наука, 2005. - N 3. - ISSN 0361-7688 = Programming and computer software.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИДЫ 00510 от01.12.99 г. Подписано к печати 05.10.2005 г. Формат 60x90 1/16. Усл.печл. 1,5. Тираж 100 экз. Заказ 601. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М В. Ломоносова, 2-й учебный корпус, 627 к

О

i

«16454

РНБ Русский фонд

2006-4 19738

Введение

1 Платформа XML и функциональные методы

1.1 Платформа XML.

1.1.1 Расширяемый язык разметки - XML.

1.1.2 Пространства имен n XML.

1.1.3 Язык XML Path (XPath).

1.1.4 Язык ссылок XML (XLink).

1.2 Обработка XML-даппых п проблема потери соответствия.

1.3 SXML: XML-документ как S-выражепие.

1.3.1 XML, информационное пространство XML н SXML

1.3.2 Спецификация SXML.

1.3.3 Пространства имен в SXML.

1.3.4 Свойства SXML.

1.4 Библиотека SXPath: реализация некоторых конструкций языка XPath функциональными методами.

1.4.1 Низкоуровневые функции SXPath.

1.4.2 Высокоуровневая функция SXPath.

2 Интеграция XPath с языком функционального программирования и язык запросов к XML-данным

2.1 Статический анализ и динамическое вычисление выражений XPath.

2.2 Расширение набора примитивов библиотеки SXPath.

2.3 Отображение выражения XPath на суперпозицию функций.

2.3.1 Лексический и синтаксический анализ выражений XPath.

2.3.2 Грамматическое правило "выражение пути".

2.3.3 Грамматическое правило "абсолютный путь доступа"

2.4 Расширение XPath за счет интеграции со Scheme.

2.5 SXPath как язык запросов.G

2.С Абстрактное синтаксическое дерево ныражепия XPatli и виде SXML.Со

3 Расширение языка запросов для обработки совокупностей XML-докумеитоп, связанных ссылками XLink С

3.1 Мотивация поддержки XLink в языке запросов.С

3.2 Пример связанных XML-докумептов.G

3.3 Родственные работы в области обработки связанных XML-докумептов

3.3.1 XQnery.

3.3.2 Браузеры с поддержкой XLink.

3.3.3 Интерфейсы прикладного программирования.

3.4 Расширение XPatli переходами по дугам языка XLink.

3.5 Адресация к дугам языка XLink.

3.5.1 Дуга XLink в виде информационной единицы.

3.5.2 Оси для адресации к дугам XLink.

3.G Реализация.

3.G.1 Разбор разметки языка XLink.

З.С.2 Реализация предложенных осей как расширение библиотеки SXPath

3.7 Ограничения предлагаемого языка запросов.

4 Оптимизация выполнения запросов

4.1 Эксперименты в отношении существующих промышленных реализаций XPatli

4.1.1 Эксперимент 1: дублирующие узлы.9G

4.1.2 Эксперимент 2: глубоко вложенные предикаты.

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

4.2.1 Родственные работы и области вычисления обратных осей XPatli

4.2.2 Иллюстрация предлагаемого подхода.

4.2.3 Алгоритм вычисления выражений XPatli, содержащих обратные осп . 10G

4.2.4 Свойства предложенного алгоритма.11С

4.2.5 Ограничения алгоритма

4.2.С Эксперименты.

4.3 Удаление дублирующих узлов при вычислении осей XPath.

4.3.1 Предварительные соглашения.

4.3.2 Осп ancestor и ancestor-or-self.12С

4.3.3 Ось attribute.

4.3.4 Ось child

4.3.5 Оси descendant п desceiiclant-or-self.

4.3.С Оси following н preceding.

4.3.7 Оси following-sibling и preceding-sibling.

4.3.8 Ось namcspace.

4.3.9 Ось parent

4.3.10 Ось self.

4.4 Вычисление осей XPath для случая расположения узлов на одном уроине

4.4.1 Осп child, descendant и descendant-or-self.1G

4.4.2 Оси following н preceding.1G

4.4.3 Оси following-sibling и preceding-sibling.1G

4.4.4 Ось parent .1GG

4.5 Вычисления осей XPath и присутствии в шаге доступа позиционных предикатов 1G7 4.5.1 Выявление позиционных предикатои с помощью статического вывода типов.

4.6 Оптимизации вычисления глубоко вложенных предикатов.

4.7 Оптимизация вычисления операций обобщенного сравнения.

4.7.1 Вычисление обобщенного сравнения сортировкой слиянием.

4.7.2 Вычисление обобщенного сравнения поразрядной сортировкой.

4.8 Верхняя оценка сложности выполнения запросов ввиду предложенных способов оптимизации.

4.9 Детали реализации

4.10 Эксперименты.

4.10.1 Эксперимент 1: устранение дублирующих узлов

4.10.2 Эксперимент 2: глубоко вложенные предикаты.

4.10.3 Сравнительные тесты производительности.

Актуальность темы

В настоящее время язык XML используется как основное средство для представления слабоструктурированных данных.

Для обработки XML-даппых могут использоваться языки платформы XML, такие как XPath, XQuery и XSLT. Поскольку большинство языков платформы XML не являются языками программирования общего назначения, при реализации XML-приложений они обычно используются совместно с некоторыми традиционными языками программирования. Комбинирование двух различных но своей природе языков (например, XPath и Java), — использующих разные модели данных и разные парадигмы программирования, — приводит к проблеме, известной как потеря соответствия (impedance mismatch). Для XML-приложений необходим язык, который бы по своей природе понимал структуры данных XML и предоставлял оптимизированные алгоритмы для обработки XML-даппых.

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

• Естественным представлением вложенных элементов XML являются вложенные списки, п язык Scheme использует вложенные списки для представления и своих данных, и своего кода.

• Язык Scheme является функциональным языком, как и большинство языков платформы XML (XSLT, XQuery).

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

Цель и задачи работы

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

Для достижения основной цели работы поставлены следующие задачи:

• создать язык запросов к XML-данным, обладающий следующими свойствами: язык запросов должен обеспечивать тесную интеграцию языка адресации частей XML-документа XPath с функциональным языком программирования общего назначения Scheme; язык запросов должен обеспечивать средство формулирования запросов к совокупности XML-докумептов, семантически связанных при помощи XLink -языка ссылок XML;

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

Основные результаты работы

В работе были получены следующие основные результаты:

• Создан язык запросов к XML-данпым, обладающий следующими свойствами: язык запросов обеспечивает тесную интеграцию языка адресации частей XML-документа XPath с функциональным языком программирования общего назначения Scheme; язык запросов обеспечивает средство формулирования запросов к совокупности XML-документов, семантически связанных ссылками языка XLink.

• Разработаны методы оптимизации выполнения запросов, гарантирующие полиномиальную сложность от размера запроса и размера документа.

• Реализован прототип среды разработки XML-приложеппй, поддерживающей единую модель данных и позволяющей облегчить и ускорить процесс создания XML-приложеппй.

Научная новизна работы

Научной новизной обладают следующие результаты работы:

• преодолена проблема потери соответствия при интеграции языка адресации частей XML-документа XPath с языком программирования общего назначения;

• разработан язык запросов к совокупности XML-докумемтов, связанных между собой при помощи XLink - языка ссылок XML;

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

Практическая значимость

Достигнутая интеграция языка адресации частей XML-документов XPath с языком функционального программирования Schemc может быть использована для достижения большей гибкости и расширяемости при формулировании критериев выборки XML-данных.

Разработанный язык запросов к совокупности XML-документов, связанных ссылками языка XLink, может быть использован для повышения наглядности представления объектов прикладной предметной области на XML и упрощения задач обработки XML-данных для приложении.

Разработанные способы оптимизации выполнения запросов могут быть использованы для повышения эффективности процессоров языков XPath и XQnery и вычислителей запросов в XML-СУБД.

Реализованный прототип среды разработки XML-приложепий функциональными методами был использован при создании в Институте системного программирования РАН промышленной системы виртуальной интеграции BizQuery и XML-СУБД Sedna.

Доклады и публикации

Основные положения работы докладывались па восьмой международной конференции "Advances in Databases and Information Systems" (ADBIS) (2001 г), па восьмидесятом и девяносто восьмом семинарах Московской Секции ACM SIGMOD (2002 и 2005 гг) и па семинаре 'Современные сетевые технологии" (2005 г).

По материалам диссертации опубликовано восемь работ [1, 2, 3, 4, 5, б, 7, 8].

Структура ii объем диссертации

Работа состоит из введения, четырех глав, заключения и списка литературы. Общий объем диссертации составляет 22G страниц. Список литературы содержит 71 наименование.

Заключение

В диссертационной работе получены следующие основные результаты:

• Создан язык запросов к XML-данпым, обладающий следующими свойствами: язык запросов обеспечивает тесную интеграцию языка адресации частей XML-документа XPath с функциональным языком программирования общего назначения Scheme; язык запросов обеспечивает средство формулирования запросов к совокупности XML-документов, семантически связанных ссылками языка XLink.

• Разработаны методы оптимизации выполнения запросов, гарантирующие полиномиальную сложность от размера запроса и размера документа.

• Реализован прототип среды разработки XML-нриложепий, поддерживающей единую модель данных и позволяющей облегчить и ускорить процесс создания XML-приложеиий.

1. Лизоркин Д.А., Лисовский К.Ю. Пространства имен в XML и SXML // Электронные библиотеки. М.: ИРИО, 2003. - Т. 6, вып. 3. - с. 42-52. - ISSN 1562-5419 = Russian digital libraries journal.http://www.elbib.ru/index.phtml?page=elbib/rus/journal/2003/part3/LL

2. Лизоркин Д.Л., Лисовский К.Ю. Реализация XLink языка ссылок XML - с помощью функциональных методов // Программирование. - М.: Наука, 2005. - N 1. - С. 52-72. -ISSN 03G1-7C88 = Programming and computer software.

3. Когаловский M.P. Глоссарий по технологиям платформы XML. М.: ИРИО, 2003. http://www.dbib.ru/index.phtml?page=elbib/rus/methodology/xmlbase/glossaryXML

4. Консорциум W3C. Расширяемый язык разметки (XML) 1.0 = Extensible Markup Language (XML) 1.0 : Рекомендация Консорциума W3C. 2-я ред. / Под ред. Bray Т. и др.; пер. с апгл. Усмаиов Р. - 2000, G окт.littp: / / www.w3.org/XML/Core/Translations

5. Kiselyov O., Lisovsky K. XML, XPath, XSLT Implementation as SXML, SXPath and SXSLT : Proc. International Lisp Conf. ILC'2002, San Francisco, 27-31 Oct., 2002. http://www.okmij.org/ftp/papers/SXs.pdf

6. The World Wide Web Consortium (W3C). Namespaces in XML : W3C recommendation / Bray T. et al. (cds.). 1999, 14 Jan.http://www.w3.org/TR/REC-xml-names/

7. Лизоркин Д.Л., Лисовский К.Ю. XML и (функциональное программирование : Методические материалы по стандартам платформы XML / Когалоиский М.Р. М.: IIPIIO, 2003.http://www.elbib.ru/index.phtml?page=elbib/rus/methodology/xmlbase/xmlfp

8. Kokkelink S., Schwiinzl R. Expressing Qualified Dublin Core in RDF/XML : DCMI proposed recommendation / Dublin Core Metadata Initiative. 2002, 15 May.littp://dublincore.org/documents/dcq-rdf-xml /

9. The World Wide Web Consortium (W3C). XML Linking Language (XLink) Version 1.0 : W3C recommendation / DeRose S. et al. (eds.). 2001, 27 Jun. http://www.w3.org/TR/xlink/

10. The World Wide Web Consortium (W3C). Extensible Markup Language (XML): Part 2. Linking : W3C working draft / Bray Т., DeRose S. (eds.). 1997, 00 Apr. http://www.w3.org/TR/\VD-xml-link-970-106.html

11. The World Wide Web Consortium (W3C). XML XLink Requirements Version 1.0 : W3C note / DeRose S.J. (editor). 1999, 24 Feb.http://www. w3 .org/TR/NOTE-xlink-req

12. Network Working Group. RFC 2396: Uniform Resource Identifiers (URI): Generic Syntax : Internet official protocol standards / Berners-Lee T. et al. 1998, Aug. http://www.cs.tut.fi/~jkorpela/rfc/2396/full.htinl

13. The World Wide Web Consortium (W3C). XPointer Framework : W3C recommendation / Grosso P. et al. (eds.). 2003, 25 Mar.http://www.w3.org/TR/2003/REC-xptr-framework-20030325/

14. Лисовский К.Ю. Разработка XML-ириложсний на языке Scheme // Программирование. -М.: Наука, 2002 Вып. 28, N 1. - С. 20-32. - ISSN 0361-7688 = Programming and computer software.

15. Кузнецов С.Д. Основы современных баз данных : информационно-аналитические материалы. Центр Информационных Технологий. http://www.citforum.ru/databasc/osbd/contents.slitml

16. Филд Л., Харрисон П. Функциональное программирование / Пер. с англ. Рябипин Л.А. и др.; под ред. акад. Горбатова В.Л. М.: Мир, 1993. - G37 е.: пл. - ISBN 5-03-001870-0 (РУС-)

17. Lisovsky K. Scheme Program Source Code as a Semistructured Data : Proc. 2nd Workshop on Scheme and Functional Programming, Florence, Italy, Sep. 2001 / Serrano M. (ed.). http://citeseer.ist.psu.edu/lisovsky01sclicme.html

18. Abclson II., Sussman G.J., Sussman J. Structure and Interpretation of Computer Programs. -2nd ed. London; New York: The MIT Press; McGraw Hill, 199G. - G57 pp. - ISBN 0-2G2-01153-0.http://mitpress.mit.edu/sicp/

19. Kisclyov O. Implementing Metcast in Scheme : Proc. Workshop on Scheme and Functional Programming, Montreal, 17 Sep., 2000 // Rice Tech. Report 00-3G8. 2000, Sep. - pp. 23-27. http://www.ccs.neu.edu/home/matthias/Schcme2000/olcg.ps

20. The World Wide Web Consortium (W3C). XML Information Set : W3C recommendation / Cowan J., Tobin R. (eds.). 2nd edition. - 2004, 4 Feb.http://www.w3.org/TR/xml-infoset/

21. Kisclyov O. SXML specification / Rev. 3.0. ACM SIGPLAN Notices. - New York: ACM Press, 2002. - Vol. 37, N G. - pp. 52-58. - ISSN 03G2-1310. http://okinij.org/ftp/Scliemc/SXML.litml

22. Organization for the Advancement of Structured Information Standards (OASIS). RELAX NG Specification : Committee specification / Clark J., Murata M. (eds.). 2001, 3 Dec.http://www.oasis-open.org/committces/relax-ng/spec-20011203.html

23. Laurent S.St. XML Elements of Style. Osborne: McGraw-Hill, 2000. - 301 pp. - ISBN 0-07-212220-X.

24. Shivers O. List Library : Scheme Request for Implementation (SRFI) 1. Final status.1999, 10 Sep.http://srfi.scliemers.org/srn-l/

25. The World Wide Web Consortium (W3C). XML Path Language (XPath) 2.0 : W3C working draft / Berglund A. et al. (eds.). 2001, 23 Jul. http://www.w3.org/TR/2004/WD-xpath20-20040723

26. Консорциум W3C. Язык преобразований XSL (XSLT). Версия 1.0 = XSL Transformations (XSLT). Version 1.0 : Рекомендация Консорциума W3C / Под ред. Clark J.; пер. с аигл. Усмапов Р. 1999, 1С ноя.http://www.rol.ru/news/it/helpdesk/xslt01.htm

27. Steele G.L. (Jr.). Lambda: The Ultimate Declarative : Artificial Intelligence Memo. Cambridge: Massachusetts Institute of Technology, 197G. - N. 379. http://repository.readsclieme.org/ftp/papers/ai-lab-pubs/AIM-379.pdf

28. Серебряков В.А. Лекции по конструированию компиляторов. М., ВЦ РАН, 1994. -175 с. - ISBN 5-201-09911-4.

29. Волкова И.А., Рудеико Т.В. Формальные грамматики и языки. Элементы теории трансляции. 2-е изд. - М.: МГУ, изд. отдел факультета ВМК, 1999. - G2 с. - ISBN 589107-032-5.http://sp.cmc.msii.rii/courscs/prak2/langgrams.pdf

30. The World Wide Web Consortium (W3C). XQuery 1.0: An XML Query Language : W3C working draft / Boag S. et al. (eds.). 2004, 29 Oct. http://www.w3.org/TR/2001/WD-xquery-20041029/

31. The World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Data Model : W3C working draft / Fernandez M. et al. (eds.). 2004, 29 Oct. http://www.w3.org/TR/2001/WD-xpath-datamodel-20041029/

32. Grinev M. XQuery Optimization Based on Rewriting : Ph.D. thesis overview. 2003, Oct. http://www.ispras.ru/~grinev/mypapers/plid-short.pdf

33. Schmidt A. et al. XMark: A Benchmark for XML Data Management : Proc. 28th VLDB int. conf., Hong Kong, China, 20-23 Aug., 2002 // VLDB. Morgan Kaufinann, 2002. - pp. 974985.http://www.vldb.org/conf/2002/S30P01.pdf

34. The World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Formal Semantics : W3C working draft / Draper D. et al. (eds.). 2001, 20 Feb. http://www.w3.org/TR/2001/WD-xquery-semantics-20040220/

35. Bender J. (X)Querying XML in Scheme. 2003, 13 Jul. http://ccltic.benderweb.net/wcbit/docs/xquery-pre/

36. Fankhauser P. XQuery formal semantics state and challenges // ACM SIGMOD Record. -New York: ACM Press, 2001. Vol. 30, issue 3. - pp. 14-19. - ISSN 0103-5808. http://portal.acm.org/citation.cfm?id=G03870

37. Гарсиа-Молииа Г., Ульман Дж.Д., Уидом Дж. Системы Баз Данных. Полный курс / Пер. с англ. Варакина С.А.; под ред. Слепцова А.В. М,: Вильяме, 2003. - 1088 е.: ил. -ISBN 5-8159-0384-Х (рус.)

38. The World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Functions and Operators : W3C working draft / Malhotra A. et al. (eds.). 2001, 29 Oct. http://www.w3.org/TR/2004/WD-xpath-functions-20041029/

39. Kiselyov O. On parent pointers in SXML trees. 2003, 12 Feb. http://www.okmij.org/ftp/Sclieme/parent-pointers.txt

40. Lehti P. Design and Implementation of a Data Manipulation Processor for a XML Query Language : Ph.D. thesis. 2001, Aug. http://www.ipsi.fraunliofer.de/~lehti/

41. Kay M. XSLT and XPath Optimization : Proc. conf. XML Europe, Amsterdam, Netherlands, 18-21 Apr., 2004.http://idealliancc.org/papcrs/dxxmle04/papers/02-03-02/02-03-02.pdf

42. Gl. Mishra P., Eich M.H. Join processing in relational databases // ACM Computing Surveys. -New York: ACM Press, 1992 Vol. 24, issue 1. - pp. G3-113. - ISSN 03G0-0300. http://portal.acm.org/citation.cfm?id=1287Gl

43. G5. Кнут Д.Э. Искусство программирования, том 3. Сортировка и поиск. 2-е изд., испр. и доп. - Пер. с аигл. Тертышпыи В.Т., Красиков II.В.; под ред. Тригуб С.II. - М.: Вильяме, 2004. - 832 е.: ил. - ISBN 5-8159-0082-4 (рус).

44. G6. Stephen G.A. String Search : Technical report TR-92-gas-01. School of Electronic Engineering Science. - 1992, October, littp: //ei.es. vt .cd u/~cs5G04/f95/cs5G04cnSS/TR92.html

45. G7. Hudak P. Conception, evolution, and application of functional programming languages // ACM Computing Surveys. New York: ACM Press, 1989. - Vol. 21, issue 3. - pp. 359-411. -ISSN 03G0-0300.littp://portal. acm.org/citation.cfm?id=72554