Approach to determination of completeness of composition of Semantic Web-services

A Basic task of the service oriented paradigm/SOA is facilitation the automated composition of services motivated by scenarios developed in electronic commerce and e-science. The problem of the automated composition is begun with the specification of "goal" service and set of acces...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2026
1. Verfasser:	Deretsky, V.A.
Format:	Artikel
Sprache:	Russisch
Veröffentlicht:	PROBLEMS IN PROGRAMMING 2026
Schlagworte:	UDC 681.3
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/987
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming
Завантажити файл:

Institution

Problems in programming

_version_	1867750851777396736
author	Deretsky, V.A.
author_facet	Deretsky, V.A.
author_institution_txt_mv	[ { "author": "V.A. Deretsky", "institution": "Institute of Software Systems NAS of Ukraine" } ]
author_sort	Deretsky, V.A.
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
collection	OJS
datestamp_date	2026-06-11T11:30:31Z
description	A Basic task of the service oriented paradigm/SOA is facilitation the automated composition of services motivated by scenarios developed in electronic commerce and e-science. The problem of the automated composition is begun with the specification of "goal" service and set of accessible for a search existing services. Composition depends on finding out the proper services on semantic level, mainly, through the entry/exit conditions, and assembling them in a "application" as a purpose service. Basedon this framework, we study in this paper a tightening problemwhich strengthens service discovery queries formulatedfrom conditions in the goal service. A tighter condition canfind more relevant services while a looser one may excludethe possibility of assembling a goal realization. The tighteningproblem is studied for conditions is studied in different logical languages, in this case, ones given for both integers and real numbers constraints.Problems in programming 2009; 3: 30-39
first_indexed	2026-06-12T01:00:16Z
format	Article
fulltext	Програмування для комп’ютерних мереж та Інтернет 30 УДК 681.3 В. Дерецкий ПОДХОД К ОПРЕДЕЛЕНИЮ ПОЛНОТЫ КОМПОЗИЦИИ СЕМАНТИЧЕСКИХ ВЕБ-СЕРВИСОВ Основная задача сервис-ориентированной парадигмы – это облегчение автоматизированной композиции сервисов мотивирована сценариями, развиваемыми в электронной коммерции и e-science. Проблема автоматизированной композиции начинается со спецификации цели “goal” сервиса и набора доступных для поиска сервисов. Композиция зависит от обнаружения соответствующих сервисов на семантическом уровне, в основном, через входные и выходные условия активностей, и сборки их в “приложение” целевого сервиса. Мы исследуем проблему полноты композиции, путем усиления запросов поиска сервисов, начиная от условий целевого сервиса. Более сильное условие может найти более релевантный сервис, без которого сборка целевого сервиса может быть невозможной. Проблема усиления условий изучается в различных логических языках, в данном случае, используются условия с порядковыми ограничениями. Введение Веб-сервисы описываются функ- циональными и нефункциональными свой- ствами и могут быть размещены и доступны через стандартизированные ин- терфейсы [1]. Композиция веб-сервисов обеспечивает механизм связывания много- разовых сервисов с целью формирования нового сервиса, который порождает новые значения. Автоматизированная компози- ция сервисов важна для приложений многих областей, в частности, таких как электронная коммерция, e-science и других. Фундаментальной проблемой ком- позиции сервисов является поиск сер- висов. В результате поиска могут быть найдены сервисы, релевантные условиям поиска, реализующие целевой сервис. Целевой сервис представлен действиями или активностями, которые связаны в цепочку потока данных. Каждая актив- ность в целевом сервисе содержит семантические описания. Проблема специ- фикации целевого сервиса состоит в назначении каждой активности в целевом сервисе существующих сервисов из реестра. Композиция, основанная на модели целевого сервиса, представляет собой естественный подход, развиваемый от интерактивной композиции сервисов на основе бизнес модели приложения [2–4] и моделей потока данных научных прило- жений [5, 6]. Предлагаемый подход раз- вивает задачи композиции как в части усиления поиска сервисов на основе семантической спецификации входных и выходных условий, так и исследований, связанных с принципиальной возмож- ностью реализации целевого сервиса с учетом условий и окружения, в отличии от подходов к композиции, при которых сервисы заранее известны и отсутствует семантика в их спецификации. Модель целевого сервиса предста- вляется в виде ациклического графа с потоком данных, соответствующем вход- ным и выходным условиям. Семантика активностей выражается в их условиях. Подход напоминает работы [7–10], в которых OWL-S расширялся семанти- ческими описаниями. Для каждой актив- ности формируется запрос к сервису в соответствии с входными и выходными условиями активности. Осуществляется семантическое согласование запросов с условиями существующих сервисов в реестре. Поиск сервисов на основе семан- тики исследовался в различных работах © В. Дерецкий, 2009 ISSN 1727-4907. Проблеми програмування. 2009. № 3 Програмування для комп’ютерних мереж та Інтернет 31 [10–13]. В данной работе предлагается подход, при котором поиск сервисов осуществляется с использованием семан- тики в модели целевого сервиса, при котором результаты запроса поиска одного сервиса используются в запросах поиска следующих сервисов в модели. Форми- рование поискового запроса на основе семантических условий целевого сервиса влияет на условия в соответствии с которыми сервис может быть найден. Учитывая входные условия в целевом сервисе можно значительно уменьшить число сервисов-кандидатов, реализующих заданную активность целевого сервиса, тем самым повысить производительность системы. В данной работе исследуется подход, основанный на усилении условий целевого сервиса. Условия формально выводятся из условий предшествующих активностей для усиления условий теку- щей активности. Условия предшествую- щей активности называются пост-усло- виями активности. Заданные входные условия и существующие условия актив- ности определяют задачу усиления или уплотнения пост-условий активности. Алгоритм уплотнения, рассмотрен- ный в данной работе, может использовать различные логические языки. В частности нами исследовалась возможность исполь- зования языка COLOG и исчисление ситуаций [14]. 1. Композиция сервисов на основе семантических спецификаций Автоматизированная композиция сервисов – основная задача парадигмы сервисов, которая обеспечивает и облег- чает такие возможности сервисов как публикацию, поиск, повторное исполь- зование. Проблема композиции в целом имеет три составляющих: спецификация цели, сбор доступных сервисов, и «склеивание» найденных сервисов в один сервис. Кратко опишем модель ком- позиции сервисов и метод усиления условий активностей, на основе которого реализуется композиция сервисов. Проблема композиции сервисов исследуется во многих работах, в которых исследуются теоретические модели. В частности Латинская модель [15, 16], модели, основанные на переговорах [17, 18], модели потока данных [19–21], модели, основанные на внутренних сос- тояниях сервисов [22, 23], модели плани- рования искусственного интеллекта [24, 25], и недавно, модели Коломбо [26]. Мы исследуем модель композиции сервисов, основанную на спецификациях целевого сервиса. Подход использует спецификации цели, используемый в модели WSMO [27, 28]. Целевой сервис состоит из актив- ностей, которые связаны потоком упра- вления и данных. Каждая активность представляет сервис, который должен быть найден, чтобы реализовать эту актив- ность. Активность описывается своими входными и выходными дугами и соответствующими входными и выход- ными условиями. Дуги представляют контейнеры данных, вытекающие от одной активности к следующей. Если удовлетворяется на- чальное условие (истина), то активность может быть выполненной, и порождает образец выходной дуги, которая является входом для следующей активности. После выполнения активности, фиксируется условие выхода для пары входной и выходной дуг. Целевой сервис такого вида соответствует сервисным приложениям e-business, например, amazon.com, opentable.com, научным технологическим процессам Workflow [20, 21] и другим приложениям. Ключевая характеристика таких приложений ориентированная на потоки данных логика вычислений, которая управляет композицией сервисов. Модель композиции – пример парадигмы, положенной в основу WSMO [28, 29], в которой целевой сервис семантически описан пред- и пост- условиями, предпо- ложениями и результатами. Входные и выходные условия в нашей модели сосредоточиваются на ограничениях входов и выходов активностей. Композиция сервисов, ориентиро- ванная на целевой сервис также расширяет естественный подход, используемый в диалоговой композиции [15, 26]. Исполь- зование целевого сервиса в форме модели Програмування для комп’ютерних мереж та Інтернет 32 потока данных для композиции иссле- дуется в [20, 23]. В работе [23], композиция сервисов использует нефунк- циональные свойства, например, условия входа и выхода. Семантическое расши- рение спецификации Веб-сервисов иссле- довалась в моделях OWL-S [30], WSDL-S [31], SWSO [27] и WSMO [28]. Атомарные процессы в OWL-S и SWSO используют входные условия и результаты. 1.1. Пред- и пост-условия активностей. Модель целевого сервиса представим в виде направленного графа (Q, M), где Q – представляет множество активностей, M – множество дуг, которые отображают потоки данных, произво- димые одной активностью и используемые другими как входные. В общем случае, для одной активности может быть более одной входной дуги и более одной выходной дуги. Для того чтобы рассмотреть алгоритм уплотнения условий, мы рассмотрим более простую модель, в которой целевой сервис представлен в виде “линейной” схемы, в которых активность имеет один вход и один выход. Вход каждой активности связан с начальными условиями, а выход, – с вы- ходными условиями. Отметим, что дуги активности представляют кортеж пере- менных. Входные и выходные условия представляют собой логические формулы на некотором логическом языке над переменными активностей. Мы рассма- триваем логический язык L, который содержит арифметические неравенства для выражения порядковых ограничений, как в области целых, так и реальных чисел. Определение 1. Входным условием дуги является конъюнктивная формула в L над переменными дуги. r- ым покрытием выходных условий над входной дугой [x1, ..., xn] и выходной дугой [y1, ..., ym] является r-кортеж формул в L следующего вида: ),...(),...,( 111 lni zzxx ψϕ → … ),...(),...,( 11 lrnr zzxx ψϕ → , где iirk ψϕ ,,1,0 ≥≥ – конъюнктивные формулы в L такие, что iϕ – парные дизъюнкции и ii ϕ∨ – повторения, такие, что {z1, ..., zl} ⊆ {x1, ..., xn} ∪ {y1, ..., ym}, и мощность {z1, ..., zl} – { y1, ..., ym} является k. Выходные условия являются орто- гональными, если существует 0-покрытие и входные/выходные дуги не разделяют общих переменных. На рис. 1 в соответствии с опре- делением, дуга е1 = [x1,…xn] c входными условиями ),...,( 11 nxxϕ . Дуга е2 = [y1,…,ym] с входными условиями 2ϕ . Выходные условия Р(е1, е2): if ),...,( 1 ni xxϕ then ),...( 11 lzzψ ; M if ),...,( 1 nr xxϕ then ),...( 1 lr zzψ ; Рис. 1. Дуги, входные и выходные условия активностей линейного целевого сервиса Очевидно, что входные условия должны удовлетворять результатам выпол- нения активности, которая выполнилась ранее. На рис. 1 показаны входные и выходные условия для активности q1. Отметим, что выходная дуга q1 является также входной дугой для последующей активности q2. Выходное условие P(e1, e2) имеет структуру в виде операторов выбора (если, то): Если )1( rii ≤≤ϕ истинна, тогда iψ получается после выполнения активности q1. Каждая пара iϕ и jϕ , ji ≠ не пересекается, таким образом, ),...(),...(... 111 njnin xxxxxx ϕϕ ∧∃¬∃ всегда истинна. После реализации активности, хотя бы один случай в выходном условии должен быть истинным. Рассмотрим пример, в котором активность имеет входную дугу [x1, x2] и выходную дугу [y1]. Входное условие – )90( 22 ≤∧≤ xx , выходное условие – ( 11211121 3,23 xyxxyxxx <→<−<→−≤ ). Отметим, что условия 213 xx −≤ и q1 q2 e1 e1 e1 Програмування для комп’ютерних мереж та Інтернет 33 321 <− xx взаимоисключающие, и их дизъюнкция всегда истинна. Определение. Пусть [x1, ..., xn], [y1, ..., ym] – входные и выходные дуги для активности q, ),...,( 1 nxxϕ и ),...,,,...,( 11 mn yyxxψ – входные и выходные условия соответственно. Пост-условием для q является формула ),...,( 1 myyξ в дизъюнктивной нормальной форме в L над выходными дугами, такими, что имеет место следующее: )(...... 11 ξψϕ →∧∀∀∀∀ mn yyxx . Пост-условие ξ1 является уплот- нением другого пост-условия ξ2, если )(...... 2111 ξξψϕ →→∧∀∀∀∀ mn yyxx . Самым плотным пост-условием активности q является самое уплотненное пост-условие из пост-условий активности q. Например, пусть [x1] и [y1] – входные и выходные дуги. Входным условием является 3 < x1 и выходным – x1 < y1. Пост-условие может быть пред- ставлено как 0 < y1, но самое сильное уплотнение условия – 3 < y1. Пусть задан целевой сервис, процедура уплотнения генерирует уплот- нение пост-условий для усиления входных условий последующей активности. Процедура выполняется последовательно от первой активности к следующей и на каждом шаге вычисляются самые уплотненные пост-условия. Отметим, что пост-условия пред- ставляются в дизъюнктивной нормальной форме вместо того, чтобы быть пред- ставленным в конъюнктивной форме. Это следует из факта, что не всегда возможно осуществить уплотнение пост-условий. Рассмотрим следующий пример. Пусть [x1] и [y1] – переменные входной и выходной дуг активности. Входное условие является истинным и выходные условия – 111111 0,0 xyxyxx <→<<→≤ . Самое плотное пост-условие – ( 00 11 <∨< yy ), которое представлено в дизъюнктивной нормальной форме. На рис. 1, входным условием является φ1 в конъюнктивной форме, и выходное условие – P(e1, e2). Самое плотное условие для q1 – формула в DNF, а именно )),((... 2111 eePtt s ∧∃∃ ϕ , где ts представляет все переменные в e1, но не в e2. Уплотнением начальных условий для q2 является конъюнкцией из самого плотного пост-условия с φ2. 2. Подход к поиску семантических Web-сервисов с использованием пред- и пост-условий Рассмотрим свойство “полноты” композиции целевого сервиса. Под полнотой, мы подразумеваем нахождение выполнимой реализации целевого сервиса, если она существует. Понятие полноты “схемы” композиции измеряет возмож- ность поиска выполнимых реализаций для алгоритма композиции схемы. В данном случае учитываются только семантические характеристики целевой схемы и сервисов в реестре. Алгоритмы композиции направ- лены на реализацию целевого сервиса на основе реализации активностей целевого сервиса. Информация о сервисах, связан- ных с активностями, существует в описаниях сервисов. Мы показываем, что стратегия уплотнения “вширину” пол- ностью использует описание сервисов, в том смысле, что алгоритм композиции схемы с первой стратегией уплотнения является полной схемой. Определение. Композиция серви- сов является полной, если для целевого сервиса и сервисов из реестра существует выполнимая реализация. На рис. 2 представлен пример, который показывает целевой сервис с тремя активностями. S11 и S12 – два сервиса в реестре для активностей q1, S21, S22, и S23 – три сервиса для активности q2, S31 и S32 – два сервиса для активности q3. Таким образом, целевой сервис имеет выполнимые реализации. Например, схема L(q1 → S11, q2 → S21, q3 → S31), является выполнимой реализацией с пред- условиями, S31 гарантируются пост- условиями S21 и S11. Другие выполнимые Програмування для комп’ютерних мереж та Інтернет 34 Рис. 2. Иллюстрация полноты композиции реализации включают L1(q1→ S11, q2→ S22, q3 → S31), L2(q1 → S11, q2 → S22, q3 → S32) и т.п. Алгоритм полной схемы композиции сформирует одну из выполнимых реали- заций. Для того чтобы найти выполнимую реализацию, алгоритму композиции нужно усилить условия с целью нахождения сервисов-кандидатов для каждой актив- ности. Эти условия включают начальные условия предыдущих активностей, и пост- условия отобранных сервисов. Все агре- гированные условия получаются из опи- саний сервисов. Рассмотрим два алгоритма (две стратегии) на основе поиска «вглубину» и поиска «вширину», которые обеспечивают полноту схемы. Также рассмотрим эффек- тивность алгоритма в терминах избы- точных вычислений. Алгоритм композиции использует первую стратегию уплотнения условий, которая должна обеспечить полноту схемы. На рис. 3 показано поисковое пространство алгоритма композиции сервисов с первой стратегией уплотнения, рассмотренной на примере (рис.2). Каж- дый путь в области поиска является вы- полнимой реализацией целевого сервиса. Рис. 3. Пространство поиска для стратегии уплотнения пост-условий q1 q2 s11 s12 s21 s22 s32 s23 s31 s31 s21 s31 s23 s31 s31 q3 q1 g2 = true e1() q3 q2 s11 Q: 3<x<9 s12 Q:0<x<9 s21 s22 s31 s32 s23 e1() g1= true e1() e2(x) g3 = true e3(y) P: 0<x<9 P: 3<x<13 P: 0<x<13 Q: 0<y<3 Q: 3<y<7 Q: 2<y<9 P: 3<x<9 P: 3<x<9 and 0<y<9 and 2<y<7 Програмування для комп’ютерних мереж та Інтернет 35 Если для активности q1 выбирается сервис S11, то пост- условие S11 (3 < x < 9) используется для уплотнения входного условия активности q2, в результате чего могут быть найдены сервисы S21, S22 и S23. Если для активности q2 выбран сервис S21, уплотняется входное условие q2 (3 < x < 9) вместе с пост-условиями S21 (0 < y < 3), которые толкают активность q3. Уплот- нение входных условий q3 (3 < x < 9 ^ 0 < < y < 3) определяет S31 сервисом-канди- датом. При таких условиях S32 не является сервисом-кандидатом, потому что для сервисов S11 и S21, агрегированные условия не могут гарантировать предусловия S32 которые должны быть истинными. В алгоритме композиции сервиса со стратегией уплотнения сервис выбирается для каждой активности. Для конкретного алгоритма композиции поиск выполнимой реализации состоит в выполнении поиска «вглубину» или поиска «вширину». Например, на рис. 3 поиск «вглубину» начинается от первой активности q1 и первого сервиса-кандидата S11, затем пер- вому кандидату сервиса S21 активности q2 после того, как для q1 назначен S11, поиск переходит к следующим сервисам, вчастности S31 для активности q3, и выполнимая реализация найдена. В случае если сервисы для активности не могут быть найдены, осуществляется возврат к предыдущей активности и осуществляется попытка найти следующий сервис-кан- дидат на предыдущем уровне (S22 или S23). Утверждение 1. Алгоритм поиска «вглубину» порождает полную схему. Грубое доказательство этого утвер- ждения состоит в том, что, поиск «вглубину» проверяет все пути в прос- транстве поиска. На примере исследуется область поиска слева направо, пока не будет найдена выполнимая реализация. Поиск «вглубину» осуществляет полный перебор, для того чтобы гарантировать полноту схемы. В наихудшем случае, исследуется вся область поиска. Скорость поискового процесса для алгоритма поиска «вглубину» может быть увеличена путем сокращения области поиска. Например (рис. 3), все подветви S12 также являются подветвями S11. Ветвь, начинающаяся с вершины S12 на рис. 3 может быть удалена из области поиска. Сокращение области поиска не изменяет свойство полноты схемы поиска «вглу- бину» потому что, если существует выпол- нимая реализация в ветви (S12), то должна быть выполнимая реализация в одном из путей, начинающихся от S11. Если мы рассмотрим уплотнение начальных усло- вий q2 после того как выбран S11 или S12, то очевидно, что уплотнение условия q2 после S11 и S12 является С1 = 3 < x < 9, и C2 = 0 < x < 9. C1 сильнее, чем C2 (т. е. C1 > > C2), таким образом, все сервисы, найденные для C2, нашлись бы в C1. Таким образом, ветвь (S12) становится избы- точной и может быть удалена. Ветвь (S11) на рис. 3 также может быть удалена по той же причине, условие после S11 и S22 сильнее, чем после S11 и S23. Если путь (S11, S23, S31) является выполнимой реализацией, то путь (S11, S22, S31) – также выполнимая реализация. Алгоритм композиции с сокра- щением области поиска может быть описан следующим образом. Основная идея подхода горизонтального поиска «вширину» состоит в том, что для всех сервисов-кандидатов активности, если существует отношение между условиями по двум путям, заканчивающихся на одной активности, путь с более слабым условием может быть удален. Поисковый процесс начинается от первой активности целевого сервиса. Для каждой активности qi за исключением последней, вначале нахо- дятся все сервисы-кандидаты по всем возможным комбинациям сервисов. Затем проверяются любые два пути, которые заканчиваются на активности qi. Если есть отношение между двумя агрегированными условиями в обоих путях, тогда путь с более слабым условием удаляется. Этот алгоритм называется поиском «вширину» с сокращением. Рассмотрим целевой сервис и область поиска, показанную на рис. 3. Поиск «вширину» с сокращением начи- нается от активности q1, и находит сервисы S11, S12, как сервисы-кандидаты. Програмування для комп’ютерних мереж та Інтернет 36 Поскольку агрегированное условие пути после (S11) (3 < x < 9) является сильнее, чем условие пути после (S12) (0 < x < 9), то путь (S12) удаляется, т. е. ветвь (S12) обре- зается в пространстве поиска. Поиск «вширину» с сокращением переходит к следующей активности q2. Для активности q2 по пути (S11), найдены сервисы S21, S22 и S23. Агрегированное условие пути (S11, S22) составляет 3 < x < 9 ^ 3 < y < 7, а агрегированное условие пути (S11, S23) составляет 5 < x < 10 ^ 3 < y < 10. Первое условие является более сильным, следо- вательно путь (S11, S23) удаляется. Ветвь удаляется из поискового пространства. Утверждение 2. Алгоритм поиска «вширину» с сокращением обеспечивает полную схему композиции. Основная идея доказательства сос- тоит в том, что для каждой выполнимой реализации, найденной посредством поис- ка «вглубину» или вертикального поиска можно найти выполнимую реализацию поиска «вширину» с сокращением. Пос- кольку поиск «вглубину» – полная схема, то поиск «вширину» с сокращением также является полной схемой. Алгоритм поиска «вширину» с сокращением ограничивает область поис- ка. Фактически устраняются избыточные пути в области поиска. Пути являются избыточными, если алгоритм может все еще находить выполнимую реализацию, если она существует после того как была уже найдена. Для того, что бы гаран- тировать полноту схемы линейного целе- вого сервиса и произвольного реестра сервисов, не существует алгоритма, кото- рый может обеспечить меньшее прос- транство поиска, чем алгоритм поиска «вширину» с сокращением. Утверждение 3. Пусть задан линейный целевой сервис и регистр сервисов, алгоритм поиска «вширину» с сокращением пространства поиска не порождает избыточных путей в области поиска. Основная идея доказательства состоит в том, что мы удаляем путь из области поиска «вширину» с сокраще- нием. Мы можем всегда конструировать ситуацию, в которой этим путем является только выполнимая реализация. Например, если (S11, S21) удаляется из области поиска, мы конструируем регистр сервисов, в котором существует только один сервис S31, который соответствует активности q3. И пред-условие S31 является агреги- рованным условием C в пути (S11, S21), если выбраны S11 и S21, то может быть найден S31. Условия C не можно отнести к категории агрегированных условий на пути (S11, S22). Иначе путь (S11, S21) удаляется из области поиска «вширину» с сокращением. Поэтому, только пути (S11, S21, S31) являются выполнимой реали- зацией для целевого сервиса. Если удаляется путь (S11, S21), то схема становится неполной. 3. Алгоритм композиции на основе формирования полноты образца Полнота схемы, измеряет полноту алгоритмов формирования схемы компо- зиции. В данном случае семантические характеристики, используемые для алго- ритмов композиции, заданы в специ- фикациях целевого сервиса и в реестре сервисов при описании каждого сервиса. Но существуют ситуации, в которых семантические характеристики могут быть определены только после выполнения сервиса. Для таких ситуаций, мы определяем понятие “полнота образца”. Отметим, что полнота образца допускает выполнимые реализации в случаях, когда: 1) для уплотнения условий должны исполь- зоваться параметры, получаемые в результате выполнения сервиса; 2) в процессе композиции возможен запуск на выполнение отобранных сервисов. Рассмотрим способ, при котором алгоритм формирования образца вызывает на выполнение сервисы-кандидаты для активностей, которые инициируют другие активности, в соответствии с целевым сервисом. Алгоритм композиции образца со стратегией уплотнения «вглубину» является полным. Такое определение полноты, возможно, слишком сильное, в том смысле, что с практической точки Програмування для комп’ютерних мереж та Інтернет 37 зрения не целесообразно осуществлять запуск все возможных сервисов. Определение. Алгоритм компо- зиции обеспечивает полноту образца, если для заданного реестра сервисов, соответ- ствующему целевому сервису, и реали- зации целевого сервиса, алгоритм воз- вращает выполнимую реализацию каждый раз, когда целевой сервис имеет выпол- нимую реализацию для запускаемых сер- висов из реестра. Алгоритм композиции полного образца в худшем случае должен осущест- вить полный перебор, который вызывает почти все сервисы-кандидаты. Рассмотрим целевой сервис и реестр сервисов (рис. 4). Для любого алгоритма композиции, который не вызы- вает сервис-кандидат S13 для q1 не обеспечивается полнота образца. На рис. 4 целевой сервис содержит три активности q1, q2 и q3, q1 имеет три сервиса-кандидата, а q2 и q3 имеют по два. Для каждого сервиса значение x или y в круглых скобках связаны со значениями, получаемыми после выполнения сервиса. Без вызова сервиса для q1 не может быть найдена выполнимая реализация, потому что ни для одного из входных пред- условий S21 и S22 не может следовать пост- условия S11, S12 и S13. Однако если сервис S13 выполнен, то определяется пост- условие S11, которое становится x = 3, и которое делает S22 сервисом-кандидатом для q2. Фактически, только (S13, S22, S32) является выполнимой реализацией. Если алгоритм запустит только сервисы S11 и S12, он не найдет выполнимую реали- зацию. Утверждение. Алгоритм компо- зиции полного образца в наихудшем случае должен запускать все сервисы- кандидаты для активностей кроме конеч- ных активностей. Алгоритм композиции полного образца использует стратегию вертикаль- ного поиска («вглубину») или горизон- тального («вширину»), вызывая на выпол- нение все сервисы из реестра. Очевидно, что он не эффективный. Можно улучшить его через использование похожего алго- ритма со стратегией уплотнения «вши- рину», выше представленной. Рис. 4. Иллюстрация полноты образца На рис. 5 показан пример, в котором целевой сервис имеет линейную структуру. Общий алгоритм композиции образца является полным, если развернута стратегия уплотнения – поиск «вширину». Сервис-кандидат для каждой активности qi находится с уплотненным начальным условием. Путь в пространстве поиска будет неполным, если отсутствующий сервис не может быть найден следующей q1 g2 = true e1() q3 q2 s11 Q: 5<x<10 s12 Q:0<x<7 s21 s22 s31 s32 s13 e1() g1= true e1() e2(x) g3 = true e3(y) P: 3<x<8 P: 0<x<5 Q: 3<y<15 Q: 3<y<10 Q: 5<x<10 P: 0<y<5 P: 3<y<8 x=5 x=6 x=3 x=5 y=10 y=5 Целевой сервис Сервис из реестра Програмування для комп’ютерних мереж та Інтернет 38 активностью. Выполнимая реализация представляется полным путем в пространстве поиска, если каждой активности в целевом сервисе назначен сервис из реестра. Рис. 5. Пространство поиска для компози- ции со стратегией горизонтального уплотнения Вторая стратегия уплотнения запус- кает выбранные сервисы, связывая свой- ства в выходных дугах со значениями, полученными в результате выполнения сервиса и уплотнения выходных условий. Эти условия инициируют уплотнение начальных условий для последующей активности. На рис. 5, если для активности q1 выбрать S13, то значение после выпол- нения S13 связывается с ограничением (x = = 3) и добавляется к пост-условиям q1. Обновление пост-условий используется для уплотнения входных условий актив- ности q2 таким образом, что для q2 может быть найден сервис S22. Алгоритмы композиции со второй стратегией уплотнения могут достигать полноты образца в процессе запуска сервисов и связывания значения ограни- чений, которые обеспечивают уплотнение начальных условий для последующих активностей. Однако, чтобы достичь полноты образца, требуется сделать полный перебор и таким образом вызывать на выполнение все связанные сервисы. Алгоритмы композиции, которые обеспечивают полноту образца через вызов сервисов-кандидатов, не практич- ны. Проблема состоит в избыточности использования ресурсов и масштаби- руемости. Если композитный сервис осно- ван на транзакциях и, если текущий путь не успешный, то алгоритму нужно верну- ться на предыдущий уровень. На практике, возможно, выполнить несколько сервисов выборочно. Понятие полноты образца может служить мерой качества QоS для алгоритмов поиска композиции. Заключение Автоматизированная композиция Web-сервисов, использующая поиск сервисов – важная практическая проблема. Через формулировку проблемы компо- зиции, мы рассматриваем много связанных ее вопросов. Одно направление – развитие алгоритмов эффективности композиции, которые могут использовать семантичес- кие свойства предметных областей. На общем уровне, важно рассмотреть, как процесс поиска может использоваться совместно с запуском сервисов. 1. Hull R., Su J. Tools for composite web services: A short overview // SIGMOD Record. − 2005. − N 34(2). − Р. 86–95. 2. Berardi D., Calvanese D., De Giacomo G. et al. Automatic composition of transition-based semantic web services with messaging // In Proc. 31st Int. Conf. on Very Large Data Bases (VLDB).− 2005.− Р. 613–624. 3. Berardi D., Calvanese D., De Giacomo G., et al. Automatic composition of e-services that export their behavior // In Proc. 1st Int. Conf. on Service Oriented Computing (ICSOC).− 2003.− Р. 43–58. 4. Gerede C., Hull R., Ibarra O., Su J. Automated composition of e-services: Lookaheads // In Proc. 2nd Int. Conf. onService-Oriented Computing (ICSOC). − 2004. 5. Ludaescher B., Altintas I., Berkley C., et al. Scientific workflow management and the kepler system // J. of Concurrency and Computation: Practice & Experience. Special Issue on Scientific Workflows. 6. Андон П., Дерецкий В. Проблемы пос- троения сервис-ориентированных прик- ладных информационных систем в Semantic web среде на основе агентного подхода // Проблемы программирования. − 2006. − № 2-3, − C. 493–502. 7. Rao J., Su X. A survey of automated web- service composition methods // In Proc. of the 1st Int.Workshop on Semantic Web Services and Web Process Composition. − 2004. q1 q2 s11 s13 s21 s12 s21 s22 s32 q3 Програмування для комп’ютерних мереж та Інтернет 39 8. Elgedawy I., Tari Z., Winikoff M. Exact functional context matching for web services // In Proc. Int. Conf. on ServiceOriented Computing (ICSOC).− 2004.− P. 143–152. 9. Andon Ph., Deretsky V. Control Oriented Ontology and Process Description for Cooperation Agents in Information Retrieval // Sixth International Scientific Conference „Electronic Computers and Informatics ECI’2004”. Х Kosice – Herlany, Slovakia September 22-24.− 2004.− P. 14–18. 10. Дерецкий В. Подход к композиции Веб- сервисов на основе специификации функ- циональной семантики // Проблемы прог- раммирования. − 2009. − № 2. − C. 30–39. 11. Bernstein A. and Klein M. Discovering services: Towards high precision service retrieval // In Proc. of the CaiSE workshop on Web Services, e-Business, and the Semantic Web. – 2002. 12. Cardoso J. and Sheth A. Semantic e-workflow composition // Jnl. of Intelligent Info. Systems. – 2003. – N 21(3). – P. 191–225. 13. Lu S. Semantic Correctness of Transactions and Workflows // PhD thesis, SUNY at Stony Brook. –2002. – P. 8–18. 14. McIlraith S. and Son T.C. Adapting Colog for Composition of Semantic Web Services // In Proc. KRR. − 2002. − P. 482–493. 15. Berardi D., Calvanese D., Giacomo G.D., Lenzerini M. and Mecella M. Automatic composition of e-services that export their behavior. ICSOC. – 2003. 16. Gerede C., Hul lR., Ibarra O., Su J. Automated composition of e-services: Lookaheads // In Proc. 2nd Int. Conf. onService-Oriented Computing (ICSOC). − 2004. 17. Fu X. Bultan T. and Su J. Conversation pro- tocols: A formalism for specification and verification of reactive electronic services // Theoretical Computer Science. − 2004. – N 328 (1-2). 18. Fu X., T. Bultan, and Su J. Realizability of conversation protocols with message contents. // International Journal of Web Services Research. – 2005.– N 2. – P. 68–93. 19. W. M. P. van der Aalst. On the automatic generation of Workflow processes based on product structures // Computer in Industry. – 1999. – Vol. 39. N.2. – P. 97 – 111. 20. Tsalgatidou A., Athanasopoulos G. and et al. Developing scientific WorkFlows from heterogeneous services // ACM Sigmod Record. – 2006. – N 2. – P. 22–28; 1999. – N 39(2). – P. 97–111. 21. Ludaescher, Altintas I., Berkley C. and et al. Scientific Workflow management and the kepler system // J. of Concurrency and Computation. Practice & Experience. Special Issue on Scientific Workflows. http://users. sdsc.edu/ ~ludaesch/Paper/kepler-swf.pdf 22. Benatallah B., Dumas M., and et al. Declarative composition and peer-to-peer provisioning of dynamic web services. ICDE. – 2002. 23. Zeng L., Benatallah B. and et al. Qos-aware middleware for web services composition // IEEE Transactions on Software Engineering. – 2004. – N 30(5). – P. 311–327. 24. Narayanan S. and McIlraith S. Simulation, verification and automated composition of web services. http://www2002.org/presenta- tions/narayanan.pdf. 25. Narayanan S. and McIlraith S. Analysis and simulation of web services // Computer Networkds. – 2003. – N 42. – P. 675–693. 26. Berardi D., Calvanese D., Giacomo G. D. and et al. Automatic composition of transition- based semantic Web services with messaging. VLDB . – 2005. 27. Semantic Web Services Ontology (SWSO) 1.0. – 2005. September. http://www.w3.org/ Submission/SWSF-SWSO/. 28. Web Service Modeling Ontology. http://www.wsmo.org/. 29. Rao J. and Su X. A survey of automated Web service composition methods // In Proc. of the 1st Int.Workshop on SemanticWeb Services and Web Process Composition. – 2004. 30. OWL-S 1.1 Release.– 2004. November. http://www.daml.org/services/ OWL-S/1.1/ 31. W3C. Web services semantics – WSDL-S 1.0. – 2005. Nov. http://www.w3.org/Submission/ WSDL-/ Получено 08.05.2009 Об авторе: Дерецкий Валентин Александрович, кандидат физико-математических наук, ведущий научный сотрудник. Место работы автора: Институт программных систем НАН Украины. 03187, Киев-187, проспект Академика Глушкова, 40. Тел.: 38 044 526 4342. e-mail: dva@isofts.kiev.ua.
id	pp_isofts_kiev_ua-article-987
institution	Problems in programming
keywords_txt_mv	keywords
language	Russian
last_indexed	2026-06-12T01:00:16Z
publishDate	2026
publisher	PROBLEMS IN PROGRAMMING
record_format	ojs
resource_txt_mv	ppisoftskievua/fa/0368c2398049478adb49a371dc34fafa.pdf
spelling	pp_isofts_kiev_ua-article-9872026-06-11T11:30:31Z Approach to determination of completeness of composition of Semantic Web-services Подход к определению полноты композиции семантических Веб–сервисов Підхід до визначення повноти композиції семантичних Веб-сервісів Deretsky, V.A. UDC 681.3 УДК 681.3 УДК 681.3 A Basic task of the service oriented paradigm/SOA is facilitation the automated composition of services motivated by scenarios developed in electronic commerce and e-science. The problem of the automated composition is begun with the specification of "goal" service and set of accessible for a search existing services. Composition depends on finding out the proper services on semantic level, mainly, through the entry/exit conditions, and assembling them in a "application" as a purpose service. Basedon this framework, we study in this paper a tightening problemwhich strengthens service discovery queries formulatedfrom conditions in the goal service. A tighter condition canfind more relevant services while a looser one may excludethe possibility of assembling a goal realization. The tighteningproblem is studied for conditions is studied in different logical languages, in this case, ones given for both integers and real numbers constraints.Problems in programming 2009; 3: 30-39 Основная задача сервис-ориентированной парадигмы – это облегчение автоматизи-рованной композиции сервисов мотивирована сценариями, развиваемыми в электронной коммерции и e-science. Проблема автоматизированной композиции начинается со спецификации цели "goal" сервиса и набора доступных для поиска сервисов. Композиция зависит от обнаружения соответствующих сервисов на семантическом уровне, в основном, через входные и выходные условия активностей, и сборки их в "приложение" целевого сервиса. Мы исследуем проблему полноты композиции, путем усиления запросов поиска сервисов, начиная от условий целевого сервиса. Более сильное условие может найти более релевантный сервис, без которого сборка целевого сервиса может быть невозможной. Проблема усиления условий изучается в различных логических языках, в данном случае, используются условия с порядковыми ограничениями.Problems in programming 2009; 3: 30-39 Основне завдання сервіс-орієнтированої парадигми полягає у полегшенні автоматизованої композиції сервісів яке мотивоване сценаріями, що розвиваються в електронній комерції і e-science. Проблема автоматизованої композиції починається із специфікації мети "goal" сервісу і визначення набору доступних сервісів для пошуку. Композиція залежить від виявлення відповідних сервісів на семантичному рівні, в основному, через вхідні і вихідні умови активностей, і збірки їх в "застосування" цільового сервісу. Ми досліджуємо проблему повноти композиції, шляхом посилення запитів пошуку сервісів, починаючи від умов цільового сервісу. Сильніша умова може знайти більш релевантний сервіс, без якого збірка цільового сервісу може бути неможливою. Проблема посилення умов вивчається в різних логічних мовах, у даному випадку, використовуються умови з порядковими обмеженнями.Problems in programming 2009; 3: 30-39 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2026-06-11 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/987 PROBLEMS IN PROGRAMMING; No 3 (2009); 30-39 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2009); 30-39 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2009); 30-39 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/987/1055 Copyright (c) 2026 PROBLEMS IN PROGRAMMING
spellingShingle	UDC 681.3 Deretsky, V.A. Approach to determination of completeness of composition of Semantic Web-services
title	Approach to determination of completeness of composition of Semantic Web-services
title_alt	Подход к определению полноты композиции семантических Веб–сервисов Підхід до визначення повноти композиції семантичних Веб-сервісів
title_full	Approach to determination of completeness of composition of Semantic Web-services
title_fullStr	Approach to determination of completeness of composition of Semantic Web-services
title_full_unstemmed	Approach to determination of completeness of composition of Semantic Web-services
title_short	Approach to determination of completeness of composition of Semantic Web-services
title_sort	approach to determination of completeness of composition of semantic web-services
topic	UDC 681.3
topic_facet	UDC 681.3 УДК 681.3 УДК 681.3
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/987
work_keys_str_mv	AT deretskyva approachtodeterminationofcompletenessofcompositionofsemanticwebservices AT deretskyva podhodkopredeleniûpolnotykompoziciisemantičeskihvebservisov AT deretskyva pídhíddoviznačennâpovnotikompozicíísemantičnihvebservísív

Approach to determination of completeness of composition of Semantic Web-services

Institution

Ähnliche Einträge