Scientific journal

Fundamental research

ISSN 1812-7339

"Перечень" ВАК

ИФ РИНЦ = 1,674

На данный момент существует множество систем для создания веб-приложений с SOA-архитектурой: Microsoft.NET, IBM Lotus Notes, Oracle SOA Suite. В то же время не существует эффективных систем, способных автоматически строить интерфейсы и превращать обычные сайты старого поколения в веб-сервисы. Необходимость таких систем обусловливается проблемами реализации EAI (Enterprise Application Integration) [9]. Решить рассматриваемую задачу можно с помощью применения парадигмы основанного на онтологиях доступа к данным (OBDA)[2]. Этот подход позволяет использовать преимущества онтологий и технологий дескриптивных логик. При этом открывается возможность построения интерфейсов на базе семантической сервис-ориентированной архитектуры (SSOA), чем обеспечивается дальнейшее эффективное развитие технологии Semantic web. Для решения поставленной задачи нами разработан алгоритм SIR. В то же время разработка программы логического анализа на основе этого алгоритма для онтологий в среде Semantic Web является ресурсоемким процессом [6]. Во избежание плохих результатов после создания программы необходимо использовать явный критерий для анализа применимости алгоритма SIR до этапа разработки программы. Таким критерием может послужить вычислительная сложность алгоритмов логического вывода в онтологиях.

Цель работы: выявить эффективность алгоритма SIR посредством доказательства его невысокой вычислительной сложности и тестирование программной реализации в экспериментальных условиях.

Теоретические исследования

Алгоритм SIR является алгоритмом логического анализа онтологии. Основным критерием эффективности алгоритма логического анализа помимо выполнения задачи является невысокий показатель вычислительной сложности алгоритма [6]. Вычислительная сложность алгоритма определяет зависимость необходимого объёма памяти и времени для выполнения этого алгоритма от размера входных данных. [5] Основным понятием вычислительной сложности алгоритмов является класс вычислительной сложности задачи, которую алгоритм должен решать [5]. Далее приведены классы сложности, распространенные в области разработки алгоритмов для дескриптивных логик [3]:

LogSpace ⊆ NLogSpace ⊆ P ⊆ NP ⊆ ExpTime ⊆ NExpTime

Класс LogSpace содержит задачи, для решения которых детерминированной машине Тьюринга потребуется объем памяти, находящийся в логарифмической зависимости от входных значений.

Приставка N в названиях классов NlogSpace, NP и NexpTime означает, что эти классы содержат задачи, которые могут разрешиться за количество ресурсов, соответствующее их классу сложности с названием без приставки на недетерминированной машине Тьюринга. Так как недетерминированная машина Тьюринга – всего лишь абстрактная модель, то алгоритм этого класса вряд ли сможет разрешиться на реальном компьютере, соответствующем детерминированной машине, за то же время.

Класс P вмещает все те проблемы, решение которых детерминированной машиной Тьюринга полиномиально зависит от размера входа.

ExpTime – это класс, содержащий задачи, которые детерминированная машина Тьюринга решает за количество времени, находящееся в экспоненциальной зависимости от входных значений.

Задачи класса P считаются интуитивно простыми задачами. Задачи класса ExpTime считаются сложными. Так как не доказано, что NP = P [1], то задачи класса NP считаются сложными.

Для задач логического вывода различают три способа вычисления сложности, перечисленные далее.

1. Сложность относительно данных: сложность оценивается как функция от размера Abox.

2. Сложность относительно терминологии: сложность оценивается как функция от размера Tbox.

3. Комбинированная сложность: сложность оценивается как функция от размера Tbox и Abox.

Дискриптивная логика DL-LiteR

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

Алгоритм SIR построен для работы с онтологиями, написанными на языке веб-онтологий OWL 2 QL. Этот профиль языка OWL 2 реализует логику DL-LiteR семейства логик DL-lite[1].

Синтаксис логики DL-LiteR поддерживает:

– положительные включения С ⊑ D,

– отрицательные включения C ⊑￢ D,

где C и D – базовые концепты, представляющие собой либо атомарный концепт, либо роль R, ограниченную квантором существования и принадлежащую верхнему концепту (∃R.⏉). Кроме того, поддерживается инверсия ролей (R–). Несмотря на скудную выразительную силу приведенного синтаксиса, этого достаточно, чтобы описать основные элементы ER-модели.

Алгоритмы логического анализа служат для определения совместности базы и для переписывания запросов. Так как алгоритм работает с логикой DL-LiteR и с алгоритмами переписывания запросов, для определения его эффективности необходимо знать вычислительную сложность основных задач логического вывода для DL-LiteR.

Данные о вычислительной сложности DL-LiteR [7] представлены в табл. 1.

Таблица 1

Вычислительная сложность алгоритма SIR

Входными параметрами алгоритма запросов к онтологии являются триплет запросов к базе знаний [7] < C,Q,S > .И Tbox онтологии. Выходными данными алгоритма является объединение триплетов запросов к базам данных. Далее запросы автоматически оборачиваются в стандартный код интерфейса веб-сервисов. Полученные интерфейсы размещаются на веб-сервисах исходя из содержания выходных данных алгоритма SIR.

Запрос адреса сервера и запросы адреса клиента могут содержать одинаковые элементы условий между собой. Такие параметры называются параметрами с зависимыми условиями. Для обработки параметров с зависимыми элементами используется функция DTRew.

Теорема: Пусть T – это DL-liteR TBox и C, Q, S конъюнктивные запросы к T. Время выполнения алгоритма SIR(C, Q, S, T) является полиномиально зависимым от размера T.

Доказательство:

Для доказательства теоремы выявим существование доказательства лемм, приведенных ниже.

Лемма 1. Вычислительная сложность алгоритма SIR (C, Q, S, T) для параметров без зависимых элементов не превысит полиномиальную сложность от размера Tbox.

Доказательство. Основными действиями в алгоритме SIR при входных параметрах без зависимых условий является переписывание трех запросов. С помощью методики анализа основных алгоритмических конструкций [4] получим функцию вычисления трудоемкости алгоритма:

(1)

где r – это функция переписывания запросов. Переписывание запросов (ответ на конъюнктивные запросы), согласно табл. 1, относится к классу сложности Ptime. Операция сложения относится к задачам с линейной зависимостью, входящих в класс P. Переписывание запросов в DL-Lite полиноминально зависит от размера T.

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

Лемма 2. Вычислительная сложность функции DTRew(C, uC, S, T) является полиномиально зависимой от размера Tbox.

Доказательство. Ниже представлен анализ алгоритмических конструкций [4] худшего случая для функции DTRew.

Худшим случаем для функции DTRew является тот случай, когда во все проверки условия «if» будут истинны.

Конструкция «следование» в процедурных языках программирования занимает 1 операцию [4].

Функция вычисления трудоемкости DTRew:

(2)

(3)

где C,S – количество элементов запросов; vqC, vqS – количество элементов переменных запросов (varqС, varqS); uC – количество переписанных запросов к клиенту; uC’ – количество элементов переписанного запроса к клиенту; DTSet – количество элементов коллекции зависимых переменных.

Линейная зависимость входит в класс Р. Следовательно, вычислительная сложность функции DTRew не превышает в худшем случае класс Ptime от входных параметров функции.

Лемма 3. Вычислительная сложность алгоритма SIR(C, Q, S, T) для параметров c зависимыми элементами является полиномиально зависимой от размера Tbox.

Доказательство. Функция вычисления трудоемкости алгоритма SIR(C, Q, S, T) будет рассчитана следующим образом:

(4)

где x – количество переписанных запросов в r(f2^). Согласно лемме 1, вычислительная сложность f1 относится к классу Ptime. Согласно лемме 2, f2 относится к классу Ptime. x, r(f2^) имеют линейную зависимость. Следовательно:

(5)

На основании леммы 1, леммы 2 и леммы 3 можно сказать, что время выполнения алгоритма SIR(C, Q, S, T) является полиномиально зависимым от размера T. Ч.Т.Д.

Экспериментальные исследования

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

Программный код алгоритма написан на языке программирования Java. Тестировался на ОС Windows 8, 3 гб ОЗУ, AMD Phenom(tm) II N850 Triple-Core Processor 2,20 Гц. Для тестирования использовалась онтология SAMAO. Эта онтология написана с помощью редактора онтологий Protégé на языке веб онтологий OWL 2 QL. Данные из Abox в этой реализации хранятся в СУБД MySQL. Для основных задач логического анализа онтологий использовался Hermit. Для описания интерфейса веб-сервисов использованы стандарты SOAP и WSDL. Для сравнения использовались 2 алгоритма переписывания запросов: PerfectRef [7] и Requiem [8].

Тестовые данные, на которых анализировался алгоритм, состоят из онтологий, написанных или адаптированных под язык OWL 2 QL для тестирования алгоритмов логического анализа. Далее приведено описание тестовых онотологий[8].

VICODI – онтология, содержащая информацию о Европейской истории, разработанной Европейским проектом Евросоюза. VICODI обозначена в табл. 2 буквой V.

StockExchange – онтология содержит информацию о финансовом институте Евросоюза. Разработана для архитектуры OBDA. StockExchange обозначена в табл. 2 буквой S.

LUMB6 – DLlite версия онтологии для тестирования, разработанной Легигским университетом для тестирования алгоритмов логического анализа. Онтология содержит данные об организационной структуре университета. LUMB6 – обозначена в табл. 2 буквой L.

SAMAO – Онтология государственных и муниципальных учреждений, разработанная специально для системы авто построения интерфейсов взаимодействия веб-сервисов. Набор аксиом(Tbox) онтологии SAMAO содержит данные о ведомствах и их территориальном расположении. Набор утверждений(Abox) онтологии SAMAO содержит данные об адресах веб-сервисов и данные, предоставляемые веб-сервисами. SAMAO – обозначена буквами SM в табл. 2. Ниже представлен отрывок из онтологии SAMAO.

TypeOfEstablishment ⊑ Think

Education ⊑ TypeOfEstablishment

GOUVPO ⊑ Education

GeneralEducationEstablishment ⊑ Education

PreschoolEducationEstablishment ⊑ Education

HighSchool ⊑ GeneralEducationEstablishment

…

Входные параметры алгоритма SIR(C,Q,S,T) для тестовых онтологий выбирались из тестов запросов к онтологиям[8]. SIR(C = Q2, Q = Q4, S = Q3, T = Tbox онтологии).

Входные параметры алгоритма SIR(C,Q,S,T) для онтологии SAMAO приведены ниже.

Параметры без зависимых условий.

C(x1, x2) ← EducationPortal(x1), RyazanCity(x2)

Q(x3) ← Phone(x3)

S(x4, x5) ← Education(x4), RyazanArea(x5)

Параметры с зависимыми условиями.

C(x1, x2, x3) ← EducationPortal(x1), CentralRegion(x2), City(x3)

Q(x4) ← Phone(x4)

S(x5, x3) ← Education(x5), City(x3)

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

(6)

где t(q), t(s), t(c) – это время срабатывания алгоритма переписывания соответствующих запросов.

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

(7)

где t(q), t(s) – это время срабатывания алгоритма переписывания соответствующих запросов. t(uk) – время срабатывания алгоритма переписывания для массива, порожденного функцией DTRew, t(d) – время работы функции DTRew.

При работе алгоритма порождаются новые запросы к базам данных. Порожденные запросы сохраняются в текстовом формате. Для вычисления занимаемой памяти результатов работы алгоритма следует подсчитать количество порожденных запросов. Количество порожденных запросов было подсчитано по формуле, идентичной формуле расчета времени работы алгоритма, с той лишь разницей, что вместо функции подсчета времени t(x) использовалась функция подсчета количества порожденных запросов.

Результаты тестирования приведены в табл. 2.

Таблица 2

Заключение

Результаты тестирования показали, что выполнение SIR алгоритма требует сравнительно небольшого количество процессорного времени и оперативной памяти. Эти выводы сходятся с тем, что вычислительная сложность алгоритма SIR входит в класс P, являющийся классом быстрых алгоритмов. Более того, для онтологии, разработанной специально для системы на базе SIR, алгоритм выполняется быстрее, чем для произвольных онтологий (см. SM в табл. 2).

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

Рецензенты:

Овечкин Г.В., д.т.н., профессор, заведующий кафедрой ВПМ Рязанского государственного радиотехнического университета, г. Рязань;

Пылькин А.Н., д.т.н., профессор кафедры ВПМ Рязанского государственного радиотехнического университета, г. Рязань.

Работа поступила в редакцию 11.04.2013.