The technique of using Description Logics in the process of constructing a composite service at the functional level

Automated composition is one of the most difficult web-services tasks. It has two purposes: first is to satisfy complex client’s requirements, second is to reduce a complexity of developing web-service to satisfy complex application system. Created theoretical apparatus is the basis for developing t...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2018
Автор: Zakharova, O.V.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Інститут програмних систем НАН України 2018
Теми:
Онлайн доступ:https://pp.isofts.kiev.ua/index.php/ojs1/article/view/245
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Problems in programming
Завантажити файл: Pdf

Репозитарії

Problems in programming
id pp_isofts_kiev_ua-article-245
record_format ojs
resource_txt_mv ppisoftskievua/4d/88f7da991c50a947c534129f5f70424d.pdf
spelling pp_isofts_kiev_ua-article-2452024-04-28T11:34:16Z The technique of using Description Logics in the process of constructing a composite service at the functional level Методика применения аппарата дескриптивных логик в процессе построения композитного сервиса на функциональном уровне Методика застосування апарата дескриптивних логік у процесі побудови композитного сервісу на функціональному рівні Zakharova, O.V. semantic Web-service; description logic; composition task; service ontology; composition ontology; IOPE-model UDC 004.94 UDC 004.94 семантичний Веб-сервіс; дескриптивна логіка; задача композиції; онтологія сервісу; онтологія композиції; IOPE-модель УДК 004.94 Automated composition is one of the most difficult web-services tasks. It has two purposes: first is to satisfy complex client’s requirements, second is to reduce a complexity of developing web-service to satisfy complex application system. Created theoretical apparatus is the basis for developing the algorithms of automated solving a semantical web-services composition task. Proposed approaches are based on using description logics. It is effective and powerful tool due to its mechanisms of judgments and the possibilities of logical inference and giving semantic meaning to descriptions.Problems in programming 2018; 1: 77-91 Автоматизированная композиция – одна из самых сложных задач веб-сервисов. Вона имеет две цели: с одной стороны – удовлетворить сложные требования клиента, а с другой – снизить сложность разработки веб-сервиса, чтобы удовлетворить сложную прикладную систему. Созданный в работе теоретический аппарат является основой для разработки алгоритмов автоматизированного реше-ния задачи композиции семантических веб-сервисов. Предложенные подходы основываются на использовании аппарата дескриптивных логик, который благодаря своим механизмам суждений и возможностям логического вывода и придания описаниям семантического смысла, явля-ется эффективным и мощным инструментом.Problems in programming 2018; 1: 77-91 Автоматизована композиція – найскладніша задача веб-сервісів. Вона має дві цілі: з одного боку – задовільнити складні вимоги клієнта, а з іншого – зменшити складність розробки веб-сервісу, щоб задо-вільнити складну прикладну систему. Створений у роботі теоретичний апарат є основою для розробки алгоритмів автоматизованого вирішення задачі композиції семантичних веб-сервісів. Запропоновані підходи базуються на використанні апарата дескриптивної логіки, що завдяки своїм механізмам міркувань та можливостям логічного виводу та надання описам семантичного змісту, є ефективним та поту-жним інструментом.Problems in programming 2018; 1: 77-91 Інститут програмних систем НАН України 2018-10-09 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/245 10.15407/pp2018.01.077 PROBLEMS IN PROGRAMMING; No 1 (2018); 77-91 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2018); 77-91 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2018); 77-91 1727-4907 10.15407/pp2018.01 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/245/241 Copyright (c) 2018 PROBLEMS OF PROGRAMMING
institution Problems in programming
baseUrl_str https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date 2024-04-28T11:34:16Z
collection OJS
language Ukrainian
topic semantic Web-service
description logic
composition task
service ontology
composition ontology
IOPE-model
UDC 004.94
spellingShingle semantic Web-service
description logic
composition task
service ontology
composition ontology
IOPE-model
UDC 004.94
Zakharova, O.V.
The technique of using Description Logics in the process of constructing a composite service at the functional level
topic_facet semantic Web-service
description logic
composition task
service ontology
composition ontology
IOPE-model
UDC 004.94

UDC 004.94
семантичний Веб-сервіс
дескриптивна логіка
задача композиції
онтологія сервісу
онтологія композиції
IOPE-модель
УДК 004.94
format Article
author Zakharova, O.V.
author_facet Zakharova, O.V.
author_sort Zakharova, O.V.
title The technique of using Description Logics in the process of constructing a composite service at the functional level
title_short The technique of using Description Logics in the process of constructing a composite service at the functional level
title_full The technique of using Description Logics in the process of constructing a composite service at the functional level
title_fullStr The technique of using Description Logics in the process of constructing a composite service at the functional level
title_full_unstemmed The technique of using Description Logics in the process of constructing a composite service at the functional level
title_sort technique of using description logics in the process of constructing a composite service at the functional level
title_alt Методика применения аппарата дескриптивных логик в процессе построения композитного сервиса на функциональном уровне
Методика застосування апарата дескриптивних логік у процесі побудови композитного сервісу на функціональному рівні
description Automated composition is one of the most difficult web-services tasks. It has two purposes: first is to satisfy complex client’s requirements, second is to reduce a complexity of developing web-service to satisfy complex application system. Created theoretical apparatus is the basis for developing the algorithms of automated solving a semantical web-services composition task. Proposed approaches are based on using description logics. It is effective and powerful tool due to its mechanisms of judgments and the possibilities of logical inference and giving semantic meaning to descriptions.Problems in programming 2018; 1: 77-91
publisher Інститут програмних систем НАН України
publishDate 2018
url https://pp.isofts.kiev.ua/index.php/ojs1/article/view/245
work_keys_str_mv AT zakharovaov thetechniqueofusingdescriptionlogicsintheprocessofconstructingacompositeserviceatthefunctionallevel
AT zakharovaov metodikaprimeneniâapparatadeskriptivnyhlogikvprocessepostroeniâkompozitnogoservisanafunkcionalʹnomurovne
AT zakharovaov metodikazastosuvannâaparatadeskriptivnihlogíkuprocesípobudovikompozitnogoservísunafunkcíonalʹnomurívní
AT zakharovaov techniqueofusingdescriptionlogicsintheprocessofconstructingacompositeserviceatthefunctionallevel
first_indexed 2024-09-16T04:07:38Z
last_indexed 2024-09-16T04:07:38Z
_version_ 1818568196341366784
fulltext Моделі та засоби систем баз даних і знань © О. Захарова, 2018 ISSN 1727-4907. Проблеми програмування. 2018. № 1 77 УДК 004.94 О. Захарова МЕТОДИКА ЗАСТОСУВАННЯ АПАРАТА ДЕСКРИПТИВНИХ ЛОГІК У ПРОЦЕСІ ПОБУДОВИ КОМПОЗИТНОГО СЕРВІСУ НА ФУНКЦІОНАЛЬНОМУ РІВНІ Автоматизована композиція – найскладніша задача веб-сервісів. Вона має дві цілі: з одного боку – за- довільнити складні вимоги клієнта, а з іншого – зменшити складність розробки веб-сервісу, щоб задо- вільнити складну прикладну систему. Створений у роботі теоретичний апарат є основою для розробки алгоритмів автоматизованого вирішення задачі композиції семантичних веб-сервісів. Запропоновані підходи базуються на використанні апарата дескриптивної логіки, що завдяки своїм механізмам мірку- вань та можливостям логічного виводу та надання описам семантичного змісту, є ефективним та поту- жним інструментом. Ключові слова: семантичний Веб-сервіс, дескриптивна логіка, задача композиції, онтологія сервісу, он- тологія композиції, IOPE-модель. Вступ Композиція Веб-сервісів являє со- бою комбінування та координування мно- жини сервісів з метою досягнення фун- кціональності, що не може бути реалізова- на існуючими сервісами. Тобто, це можли- вість забезпечити нову функціональність, отриману з комбінації різних сервісів, що надаються різними провайдерами. Для отримання такого композитного сервісу необхідно вміти знаходити найбільш від- повідні Веб-сервіси для композиції та мати автоматичний інструмент для їх компо- зиції. Зрозуміло, що бажано, щоб ство- рення такого сервісу здійснювалося авто- матизованим чином. Ефективність вирі- шення цих та інших супутніх задач та ви- бору алгоритмів для їх вирішення, перш за все, залежить від обраної моделі фор- малізації сервісу. В даній роботі будемо розглядати семантизовані сервіси, що представлені функціональною IOPE моделлю, та для формального представлення яких викорис- товується дескриптивна логіка (ДЛ). Зада- ча композиції породжує багато супутніх задач на всіх етапах життєвого циклу сер- вісів: від їх формалізації, формалізації по- шукового запиту, виявлення та інші. Під- ходи до формалізації семантичних веб- сервісів та пошукового запиту засобами дескриптивної логіки та виявлення потріб- них веб-сервісів шляхом співставлення сервісів та пошукового запиту бути дета- льно розглянуті в [1]. Предметом розгляду цієї статті є побудова композитного серві- су на базі відібраної множини існуючих сервісів, що представлені IOPE моделлю. При цьому використовуються підходи встановлення відповідності за виходами – входами та ефектами – передумови серві- сів, що композуються. Моделі представлення сервісу на функціональному рівні Залежно від повноти опису функ- ціональних можливостей сервісу розріз- няють різні формальні моделі представ- лення. Так, в IO моделі сервіс описується лише наборами вхідних та вихідних пара- метрів. PE модель має на увазі представ- лення сервісу його передумовами та ефек- тами. У загальному випадку, опис фун- кціональних можливостей сервісу визна- чається його входами, виходами, перед- умовами та ефектами – IOPE моделлю. Іноді IOPE модель розширюється пост- умовами, або/та об’єктами ефектів. Наоч- но, IO (входи, виходи) надають синтакси- чну інформацію про веб-сервіси, тоді як PE (передумови та ефекти) – відобража- ють їх семантику. Методи, які ви- користовуються у співставленні виходів- входів відрізняються від тих, що викорис- Моделі та засоби систем баз даних і знань 78 товуються для передумов та ефектів. Та семантики, які відображаються входами- виходами й передумовами та ефектами також різні. На сьогодні досягнуто знач- них результатів у співставленні веб- сервісів за входами-виходами, але відсут- ній ефективний підхід щодо спів- ставлення передумов та ефектів. У роботі [2] наводиться алгоритм PE співставлен- ня, на основі формалізма ДЛ SHOIN+(D). В даній роботі розглядаються IO та IOPE моделі, що для формального опису входів, виходів, передумов та ефектів ви- користовують апарат дескриптивної логі- ки (ДЛ). Безперечна доцільність викорис- тання апарата ДЛ для вирішення багатьох задач Веб-сервісів обумовлена тим, що системи ДЛ забезпечують користувачів різними механізмами виводу, які виводять неявні знання з тих, що явно представле- ні, та більше того, на сьогодні існує вже чимало реалізованих механізмів мірку- вань (резонерів) ДЛ, що готові до вико- ристання. Але, варто пам’ятати, що окре- мою складною задачею залишається вибір такої ДЛ, що є компромісним рішенням між її виразністю та розв’язуваністю. При визначені формального опису веб-сервісу на функціональному рівні за- собами ДЛ описується онтологія домена. Зрозуміло, що онтологія домена – специ- фічна для кожної предметної області, але при вирішенні задач веб-сервісів вона має бути єдина (або інтегрованою) для всіх сервісів, що прийматимуть у цьому уч- асть. Анотації входів, виходів, передумов та ефектів веб-сервісів є аксіомами визна- чення або аксіомами включення ДЛ з по- силаннями на онтологію домена. Але, перш за все, для вирішення задач веб-сервісів доцільно мати онтоло- гію сервісу вищого рівня, що надаватиме загальне визначення веб-сервісів. На цей опис будуть спиратися описи конкретних веб-сервісів, що використовуватимуться при вирішенні задач. Онтологія сервісу має відображати визначення його моделі, тому її TBox залежить від обраної функ- ціональної моделі. Для IOPE моделі онто- логію сервісу ServiceOntology можна ви- значити наступним чином. TBox Service, InputParameter, OutputParameter, PreCondition, PostCondition, Parameter, Name, Value, Type Service ⊑ has.InputParameter; /* I – складова сервісу Service ⊑ has.OutputParameter /* O – складова сервісу Service ⊑ has.PreCondition; /* P – складова сервісу PreCondition ⊑ Condition PostCondition ⊑ Condition; Condition ⊑ hasValue.Boolean Service ⊑ has.PostCondition; /* E – складова сервісу InputParameter ⊑ Parameter OutputParameter ⊑ Parameter; Parameter ⊑ has.Name Parameter ⊑ has.Value; Name ⊑ String; Value ⊑ has.Type Визначення онтологій конкретних сервісів та онтології домена буде розгля- нуто далі на конкретному прикладі засто- сування методології, що пропонується в роботі для вирішення задачі композиції. Огляд існуючих підходів до композиції веб-сервісів Мета задачі композиції – побудова складного сервісу, який реалізує постав- лену бізнес-задачу. Задача композиції ви- ражається запитом на композицію, що являє собою опис сервісу, який потрібно отримати. Результуючий композитний сервіс має відповідати запиту на компо- зицію, або іншими словами, «покривати» цей запит. Одним з підходів для формування такого сервісу є використання задачі зна- ходження найкращого покриття запиту [3, 4], що з технічної точки зору належить Моделі та засоби систем баз даних і знань 79 до загальної структури для рерайтингу (перезапису) [6, 7], використовуючи тер- мінологію з [5]. Знаходження найкращого покриття За умови представлення сервісів за- собами ДЛ, кожний елемент визначення сервісу та запиту є концептом (класом), визначенням якого є його опис. Семантики описів концептів визна- чаються в термінах інтерпретації 𝒥= =(∆𝒥,.𝒥), що складається з непустої мно- жини ∆𝒥 – інтерпретації домена та функції інтерпретації .𝒥, яка зв’язує з кожним іме- нем концепта P ∈ C підмножину P𝒥 of ∆𝒥 та з кожним іменем ролі R ∈ 𝓡 бінарне відношення 𝑅𝒥 ⊆ ∆𝒥×∆𝒥. На основі цих семантик визнача- ються subsumption (включення), еквівален- тність та поняття найменшого загального включення [3], що є основою для отри- мання найкращого покриття. Нехай С , C1,...,Cn та D – описи концептів: – C включається в (subsumed by) D ( С ⊑ D ), якщо 𝐶𝒥 ⊆ 𝐷𝒥 для всіх інтерпре- тацій 𝒥. – C еквівалентно D ( С ≡ D ), якщо 𝐶𝒥 = 𝐷𝒥 для всіх інтерпретацій 𝒥. – D – найменше загальне включен- ня концептів n1 C,...,С ( D = lcs( n1 C,...,С )), якщо: - iС ⊑ D для всіх ni 1 , та - D найменший опис концепта, що має таку властивість, тобто, якщо D’ – опис концепта, що задовільняє iС ⊑ D для всіх ni 1 , тоді D ⊑D’ [3]. Таким чином, найменше загальне включення множини концептів відповідає найбільш специфічному опису, що містить всі концепти з множини. Більш детально питання побудови найменшого загального включення висвітлюється в [4]. Процес виявлення сервісів можна розглядати як процес перезапису (re- writing), в якому запит Q перезаписується найближчим до нього описом E, який ви- ражається кон’юнкцією Веб-сервісів зада- ної онтології 𝓣, на базі якої визначаються сервіси та запит. Такий опис і є найкращим покриттям запиту. Представлення сервісів та запиту як концептів ДЛ дозволяє також використо- вувати операцію різності на описах серві- сів, що забезпечує гнучкий механізм спів- ставлення сервісів та запиту або входів та виходів сервісів. У роботі [8] різність за- дається як найменше загальне включення двох концептів. Зрозуміло, що є малоймовірним знайти покриття яке повністю відповідає запиту, тобто не містить зайвої інформації або/та не має відсутньої інформації. Тому, найкраще покриття – це покриття, яке, по-перше, має найменшу решту, по-друге – найменшу частину відсутньої ін- формації. Задача найкращого покриття – це задача обчислення всіх найкращих по- криттів запиту 𝓠, використовуючи термі- нологію задану 𝓣. Мінімізація залишку та нестачі інформації і є критерієм оптималь- ності при вирішенні даної задачі. Слід зазначити, що знаходження по- криття з нуля для кожного запиту це до- сить трудомістка задача. Окрім цього, сер- віси, що утворюють це покриття необхідно впорядкувати в ланцюжки, щоб вони утво- рили ефективну композицію. Тому, доці- льно було б визначати та зберігати за- лежності між серсвісами у реєстрі. Визна- чення всіх залежностей між усіма серві- сами утворює, так званий, граф залежно- стей [9]. Будь-який ланцюжок, що є його підмножиною, утворює складний сервіс. Таким чином, для побудови композитного сервісу, що реалізовуватиме поставлену бізнес-задачу, треба знайти такий ланцю- жок в графі залежностей, що на вході прийматиме вхідні параметри та перед- умови, визначені в запиті на композицію, а за досягненням кінцевого вузла забезпе- чувати необхідні виходи та ефекти. Най- частіше пошук такого ланцюжка здійсню- ється саме з кінця, тобто з сервіс-вузла, що забезпечує виходи запита. У такому ви- падку, кажуть, що сервіс будують знизу вгору. Тобто, починаючи з кінцевого атом- ного сервісу, підіймаються по ланцюжку вгору аж доки не будуть досягнуті не- Моделі та засоби систем баз даних і знань 80 обхідні входи запиту на композицію. Зро- зуміло, що для побудови графа залежно- стей (та композиції сервісів) необхідно враховувати та вміти визначати зв’язки між різними Web-сервісами, що викорис- товуються в композиції. Ці відношення можна класифікувати. Класифікація залежностей між веб-сервісами Визначення 1 [10]. Нехай 𝓣 – ацик- лічний Tbox, 𝓐 - ABox, та сервіси iS та jS є підсервісами композитного сервіса S, тоді як сервіс iS забезпечує інший тип сер- віса, ніж сервіс jS . Зв’язок R між підсерві- сами iS та jS може бути визначений на- ступним чином: Незалежність: ijji SSSS  – кожний підсервіс – вільно незалежний від іншого та порядок їх виконання не впливає на результат.  Ідентичність: ji SS  – два сервіси забезпечують одну й ту саму пос- лугу, але вони мають деякі різні атрибути.  Умовна ідентичність: iS ≅ ≅ ij SS  може забезпечувати ту саму фун- кцію, що й jS у деякій ситуації.  Підстановка (Substitute): iS ≺ jS – сервіс iS може заміщуватися сервісом jS у будь-якому випадку. Анало- гічно, jS ≺ iS .  Умовна підстановка: iS ≼ jS – сервіс iS може бути заміщений сервісом jS в деякій ситуації. Аналогічно, iS ≽ jS .  Перекриття: iS ⊗ jS – існує частина перекриття між цими двома серві- сами. Для створення цього відношення, має бути виключена частина, що є пере- криттям.  Передумова: iS → jS – один сервіс має завершитися до початку друго- го. Сервіс iS має завершитися до того, як почнеться сервіс jS . Для визначених відношень серві- сів, можна сформулювати наступні теоре- ми [11]. Теорема 1. Якщо iS та jS є викону- ваними в 𝓐 відносно 𝓣, то ℐ ⇒𝑆𝑖 𝒯,𝒜 𝓘’, ℐ ⇒𝑆𝑗 𝒯,𝒜 𝓘’’, у всіх моделях 𝓘 ABox 𝓐 від- носно 𝓣, якщо виконується 𝓘’ ≡ 𝓘’’, то iS ≅ jS у випадку ABox 𝓐 відносно 𝓣. Теорема 2. Якщо iS та jS є вико- нуваними в 𝓐 відносно 𝓣, то ℐ ⇒𝑆𝑖 𝒯,𝒜 𝓘’, ℐ ⇒𝑆𝑗 𝒯,𝒜 𝓘’’, у всіх моделях 𝓘 ABox 𝓐 від- носно 𝓣, якщо виконується 𝓘’ ≪ 𝓘’’, то iS ≽ jS у випадку ABox 𝓐 відносно 𝓣. Відповідно до визначення відно- шення незалежності, можна визначити па- ралельні сервіси. Паралельний сервіс [10] S – це сер- віс, який досягається відношенням неза- лежності. S = 1S | 2S |···| kS , де ...21  SS kS... еквівалентно ik SS  +··· 1S . Це означає, що сервіси-кандидати у сервісі S можуть виконуватися незалежно. Сервіс S = 1S | 2S |···| kS є виконува- ним в 𝓐 відносно 𝓣 лише тоді, якщо кож- ний сервіс в S є виконуваним. Згідно визначенню відношення передумови, можна вивести множину сервісів, що утворює послідовний сервіс. Послідовний сервіс S [10] – це сер- віс, що досягається відношенням перед- умови, а саме 21 SS  ;··· ; kk SS 1 . Сервіс kSSSS ;...;; 21 є виконува- ним в 𝓐 відносно 𝓣, лише тоді, якщо нас- тупні умови правильні у всіх моделях 𝓘 ABox 𝓐 та TBox 𝓣:  𝓘 ⊨ 1P та  для всіх i з ki 1 та всіх інтерпре- тацій 𝓘’ з 𝓘 ⇒S1;S2;···;Si 𝒯 𝓘’, маємо 𝓘’ ⊨ P(i+1) та  𝓘 ⇒S 𝒯 𝓘’, 𝓘’ не має конфліктів. Моделі та засоби систем баз даних і знань 81 Підходи до побудови композитного сервісу, що засновані на графах Композиція сервісів – це процес виявлення кандидатів Веб-сервісів, які можна скомбінувати у складний ланцюг, та визначення порядку виконання для цих сервісів. Формально, задачу композиції мож- на описати кортежем < 𝓣, 𝓐, G , S > [10], де:  𝓣 описує словник прикладного домена (чи Tbox онтології домена);  𝓐 містить твердження про іме- новані індивіди в термінах цього словника, а також позначають вихідний стан Світу (ABox онтології домена);  G – множина тверджень, яка пред- ставляє ціль, якої намагаються досягти;  S – множина сервісів. Можливі різні підходи для побудо- ви композитного сервісу, але вони мають спільні складові, а саме: використання за- питу, як цілі композиції, фільтрація серві- сів репозиторію для виявлення відповідних сервісів, співставлення сервісів за вхо- дами/виходами, передумовами та ефек- тами для побудови результуючого лан- цюжка. Підходи, що використовують на- правлені ациклічні графи для представ- лення композитного сервісу, відносяться до групи підходів з доведеною ефективні- стю. Причому алгоритм побудови можли- вий у двох напрямках: 1) виходячи від де- композиції цілі, тобто аналогічно до під- ходів AI-планування, 2) пошук всіх мож- ливих графів з сервісів репозиторію, що відповідатимуть запиту. Щоб для побудови композитного сервісу застосувати підходи та алгоритми на основі методів AI планування, необхід- но визначити діаграму станів, щоб пред- ставити план та алгоритм для знаходження відповідних кандидатів сервісів, модель для представлення задачі декомпозиції та шляхи виконання плану. Діаграма станів будується із станів та переходів. Діаграма переходів із стану в стан позначається ста- нами, умовами та операціями. Стани мо- жуть бути простими або складними. Прос- тий стан позначається одним ком- понентним сервісом – дією. Складний стан – це стан, який має графічну декомпо- зицію, яка може бути OR та AND-станами. OR-стани використовують механізм гру- пування з метою модульності, тоді як AND-стан містить декілька областей, що призначені для одночасного виконання. Кожне твердження G можна транслювати в діаграми, які заміщують вузел задачі. Таким чином, плани в діаграмі ста- нів визначаються наступним чином. Декомпозиція задачі композиції сервісів [10] – це послідовність декомпози- цій ],...,,[ 21 nTTT , така що 1T – вихідна під- задача, nT – кінцева підзадача, та для кож- ного стану iT ( ni 1 ):  iT – безпосередній успішний результат підзадач ],...,[ 11 iTT та не є без- посереднім успішним результатом будь- яких інших станів в ],...,[ 1 ni TT  .   jT ],,...,[ 11 iTT де jT та iT належать OR-станам діаграми.  Якщо виконується вихідна за- дача однієї з конкурентних областей AND-стану, то виконуються всі інші гілки цього AND-стану. Виходячи з цього, можна зробити наступні висновки щодо транслювання різ- них типів сервісів у стани діаграми: згідно визначенням паралельні сервіси можна транслювати в AND-стани; послідовні сер- віси можна зв’язати один з одним; сервіси ідентичних відношень можна транслювати в OR-стани. Якщо діаграма містить OR- стани, вона має декілька шляхів з вихідно- го стану в кінцевий. Кожний шлях – це ок- ремий план для завершення виконання складного сервіса. Структурування та під- тримка шляху виконання відіграють клю- чову роль у підтримці ефективного плану- вання. Ациклічний направлений граф (DAG), у даному випадку, є ефективним інструментом представлення множини пов’язаних дій. DAG [12] – це граф, реб- рам якого присвоєне направлення, та який не містить циклів, тобто таких шляхів, що Моделі та засоби систем баз даних і знань 82 починаються та закінчуються в одній і тій самій вершині. DAG забезпечує топологіч- ний пошук, який надає допустимий (за- гальний) порядок для виконання базових дій по одному. Діаграма станів перетворю- ється у план виконання, що представлений DAG ),( EVGG  , де },...,{ 1 nvvV  – мно- жина сервісів та E – множина зважених направлених дуг, які ідентифікують залеж- ності. Для кожної задачі iT у діаграмі ста- нів існує множина сервісів-кандидатів, які можуть досягати цільового стану iT . Формально, DAG шляху досягнення задачі визначається наступним чином. Визначення [10]. Задана діаграма станів декомпозиції задачі ],...,,[ 21 nTTT , DAG ),( EVGG  -представлення плану:  DAG має щонайменше два вузли Start та Finish.  ),...,,( 21 itiii SSSS  – множина кандидатів сервісів для задачі iT в ST та ii TE  .  DAG містить один вузел для ко- жного сервіса ),...,,( 21 nSSS .  DAG містить ребро від сервіса iS до дії jS , лише тоді, якщо jT – прямий по- слідовник iT . Додатково, можуть бути визначені операції об’єднання та перетину. Визначення (сформульовано на базі операцій об’єднання та перетину, що вве- дені в [10]). Якщо задані два шляхи вико- нання, які представлені в DAG, ),( 1111 EVGG  та ),( 2222 EVGG  , та кін- цевий вузел 1G є начальним вузлом 2G , тоді об’єднання 1G та 2G ( 21 GG  ) – це також шлях виконання DAG. Нехай ),( 333 EVG  – це 21 GG  , що створюється згідно наступним крокам: 1) всі вузли в 1G та 2G розгляда- ються як атомні вузли 213 VVV  ; 2) якщо вузел 21 VVVc  , то DAG 3G розширюється cV та всіма ребра- ми, що відповідають cV ; 3) якщо вузел 21 VVVc  , тоді порівнюються ребра сE1 , що відповідають cV в 1G , з ребрами сE2 , що відповідають cV в 2G , тоді обираємо оптимальні ребра, щоб розгорнути 3G . Якщо задані два шляхи виконання, які представлені в DAG, ),( 1111 EVGG  та ),( 2222 EVGG  , й кінцевий вузел 1G спів- падає з кінцевим вузлом 2G , та ( 1V ⊓ 2V )−({first,finish}) ≠∅, тоді перетин 1G та 2G ( 21 GG  ) – також є шляхом ви- конання DAG. Нехай ),( 333 EVG  – 21 GG  створюється згідно наступним крокам: 1) всі вузли в 1G та 2G розгляда- ються як атомні вузли, нехай 213 EEE  та 3V – множина, яка складається з вузлів, які примикають до кожного з ребер в 3E ; 2) якщо вузел 21 VVVc  , та 3VVc  , тоді додамо cV та пов’язані дуги, щоб розгорнути 3G . Використовуючи ці дві операції, можна інтегрувати дрібно-деталізований план в крупно-деталізований або розділити задачу великого плану на декілька дрібно- деталізованих компонент. Зв’язки між веб-сервісами можна визначати й за ходом виконання компози- ції (без попередньої декомпозиції цілі). Наприклад, для визначення залежностей сервісів можна використовувати графову модель. Використання графової моделі для автоматичної композиції сервісів. В даному випадку, поведінка наявних веб- сервісів представляється в термінах їх ін- формації входів-виходів та семантичної інформації про веб-дані. Граф залежностей [9] є набором вершин або «вузлів» та ре- бер, що з’єднують пари вершин. Граф мо- же бути неорієнтовний, це означає, що не- має ніякої різниці між двома вершинами, пов’язаних з кожним ребром, або його реб- ра можуть бути спрямовані від однієї вер- шини до іншої. Зважений граф являє со- Моделі та засоби систем баз даних і знань 83 бою граф, де кожне ребро має вагу (деяке дійсне число), що з ним пов’язана. В по- шуці композитного сервісу використову- ється граф залежностей, який виконує да- ний запит. Більшість заснованих на графах ме- тодів композиції будують графи залежно- стей веб-сервісів під час виконання. Вони використовують алгоритм пошуку для об- ходу графів залежностей для того, щоб композувати сервіси. Основна відмінність між такими методами полягає в тому, як вони шукають граф залежностей: пряма побудова ланцюжка, зворотна побудова ланцюжка, двонаправлені алгоритми по- шуку тощо. В роботі [13] визначається задача узагальненої композиції, як підхід, що по- лягає в автоматичному знаходженні у ре- позиторії орієнтованого ациклічного графа сервісів, які можуть бути компоновані для отримання сервісу, заданого запитом. Фо- рмально, необхідно в репозиторії R знай- ти орієнтований ациклічний граф ),( EVG  сервісів відповідно до запиту на композицію Q , де V – набір вершин і E – набір ребер графа. Сервіс у IOPE моделі являє собою кортеж з 4 елементів ) , , ,( = СОOICIS , де CI – список перед- умов, I – список входів, O – список ви- ходів і СО – список післяумов (або ефек- тів). Перед- та післяумови являють собою заземлені логічні предикати (ground logical predicates). Аналогічно, запит на сервіс визначається як ) , , ,( = ОСOIICQ  , де IC  – список передумов, I  – список вхо- дів, O – список виходів, ОС  – список пост-умов. Кожен вузол у графі є або сер- вісом, що бере участь в композиції, або пост-умовою безпосереднього поперед- нього сервісу в графі, результат якого мо- же бути визначений тільки після виконан- ня сервісу. Кожне вихідне ребро вузла (сервіс) представляє виходи і післяумови, вироблені сервісом. Кожне вхідне ребро вузла представляє входи і передумови сер- вісу. На вузлах графа мають виконуватись умови: 1. i ,VSi  де iS має рівно одне вхідне ребро, яке представляє входи запи- ту і передумови, I  i iI , IC    i iCI . 2. i ,VSi  де iS має рівно одне вихідне ребро, яке представляє виходи за- питу і пост-умови, О′ i iO , ОС    i iСО . 3. i ,VSi  де iS є сервісом і має, щонайменше, одне вхідне ребро. Нехай imii SSS ,...,, 21 будуть вузли такі, що існує спрямоване ребро від кожного з цих вузлів до iS . Тоді . 4. i ,VSi  де iS представляє умову, яка обчислюється під час виконан- ня, і має рівно одне вхідне ребро, нехай jS буде його безпосереднім вузлом- попередником, таким, що існує спрямова- не ребро від jS до iS . У такому разі, для входів та передумов у вузлі iS виконуєть- ся: IOI ji  , ji COСI  . Вихідні ребра з iS представляють виходи, які співпадають з входами ,iI та пост-умови, що є резуль- татом умови, обчисленої під час виконан- ня, які є передумовами для iS . У даному випадку, є відношен- ням включення, а  - відношенням імплі- кації. Іншими словами, сервіс на будь-яко- му етапі в композиції може потенційно ма- ти як свої входи всі виходи від своїх попе- редників, а також входи запиту. Сервіси на першому етапі композиції можуть викори- стовувати тільки входи запиту. Об’єднання виходів, вироблених сервісами, на остан- ній стадії композиції, має містити всі ви- ходи, які визначені у запиті. Постумови сервісів на будь-якому етапі композиції мають означати передумови сервісів на наступному етапі. Не завжди при виконан- ні можна визначити, чи має місце імпліка- ція між постумовами та передумовами на- ступного сервісу. В такому випадку, в гра- фі створюється умовний вузол. Вихідні ребра умовного вузла представляють мож- Моделі та засоби систем баз даних і знань 84 ливі умови, які будуть обчислюватися під час виконання. Залежно від умови, що є іс- тиною, виконуються відповідні сервіси. Тобто, якщо підсервіс 1S композований з під-сервісом 2S , то пост-умови 1CO по- винні імплікувати передумови 2CI з 2S . Під час виконання обчислюються наступні умови: if ( 1CO  2CI ) then execute 1S ; else if ( 1CO  2CI ) then no-op; else if ( 2CI ) then execute 1S . Зазначені формалізми дозволяють визначити ітераційний алгоритм компози- ції [13], де пошук та фільтрація відповід- них сервісів відбувається на основі множи- ни вхідних параметрів та передумов, що формується ітераційно на кожному кроці. Композитний сервіс є графом. Щоб його отримати, перш за все необхідно від- фільтрувати сервіси репозиторію, що не є корисними для композиції на декількох етапах (рис. 1). Якщо процедура композиції здій- снюється згори донизу, то вона починаєть- ся з вхідних параметрів запиту. Алгоритм знаходить всі сервіси з репозиторію, які як вхідні потребують підмножину вхідних параметрів запиту. На рис. 2 ICI , є передумови та вхі- дні параметри, визначені в запиті. 1S і 2S – сервіси, знайдені після першого кроку – фільтрації за вхідними параметрами запи- ту. 1O є об’єднання всіх виходів, виробле- них сервісами на першому етапі. На нас- тупному етапі, доступні входи – це вхідні параметри запиту та всі виходи, що отри- мані на попередньому етапі, тобто IOI  12 . Саме 2I й використовується для пошуку сервісів на наступному кроці, тобто всі ті сервіси, які потребують підм- ножину 2I як вхідні параметри. Щоб алго- ритм не зациклився, отримуються лише ті сервіси, які вимагають щонайменше один параметр з виходів, отриманих на поперед- ньому етапі. Така фільтрація триває, поки не будуть вироблені всі вихідні параметри запиту. Після цього здійснюється ще один прохід у зворотному напрямку, щоб вида- лити надлишкові сервіси, які прямо або по- бічно не сприяють вихідним параметрам запиту. В даному випадку, треба починати з вихідних параметрів та рухатися у зворо- тному напрямку. Рис. 1. Композитний сервіс, побудований з п’яти сервісів, як орієнтований ациклічний граф Рис. 2. Алгоритм узагальненої композиції Моделі та засоби систем баз даних і знань 85 Кожен композиційний сервіс, по- роджений наведеним алгоритмом, є дійс- но сервісом, що відповідає всім вимогам запиту і, отже, є правильним. Окрім цьо- го, для заданого запиту алгоритм генерує всі можливі композитні сервіси, тобто, є повним. Але, очевидно, що на кожному кро- ці може бути декілька можливих шляхів у графі, та, як слідство, декілька результу- ючих композиційних сервісів. Тому, неод- мінно виникає питання знаходження най- коротшого шляху в графі. Визначення ваги для всіх ребер графа дозволило б оптимізувати композицію шляхом обчис- лення найкоротших шляхів. Одним з підходів визначення найко- ротшого шляху у зваженому ациклічному графі є використання матриці найкорот- шого попередника. В даному випадку всі результати виконання алгоритму пошуку зберігаються в матриці, а потім ця матриця використовується для реконструкції най- коротшого шляху, який відповідає опти- мальній автоматизованій композиції серві- сів. Граф та матриця мають оновлюватися кожного разу, коли до репозиторію дода- ються нові сервіси або існуючі сервіси змінюються, або видаляються з репозито- рію. Це дозволяє уникнути побудови графа і застосування алгоритму пошуку графа кожного разу, коли здійснюється запит на композицію сервісів. Під час виконання композиції і при обробці кожного запиту, визначаються лише початкові й кінцеві веб-сервіси в графі. А потім з матриці ви- тягується відповідний найкоротший шлях між початковою та кінцевою вершиною. Ключовим моментом такого підходу є ва- га, так як вона впливає на вибір шляхів композиції. Існують різні підходи до ви- значення ваги. У роботі [14] пропонується алгоритм зважування, при якому в відпо- відність всім ребрам у графі ставиться ва- га, розрахована з використанням значення S семантичної подібності між вхідними і вихідними параметрами, і функції f(QoS) нефункціональних властивостей сервісів, як, наприклад, вартість, час виконання, надійність, доступність і т. д. Так, наприклад, з урахуванням трьох параметрів, а саме: вартості, часу і наявності, f(QoS) для ребра i можна об- числити наступним чином: ())(( iVQOSf *cost ()  *execution time ()  *availability ) , (1) де  ,  і  – це відносні фактори, які можуть бути визначені системним адмініс- тратором. Тоді, вагу ijW даного ребра ji VV  можна обчислити наступним чи- ном: ,))(( ijiij SVQoSfW  (2) де ijS – значення семантичної подібності між вхідними параметрами jV і вихідними параметрами iV , та приймає одно з чо- тирьох значень (Exact, Plug-in, Subsumes, Fail). Початкові та цільові вершини в графі для кожного запиту визначаються також, на основі семантичних подібностей, але між вхідними і вихідними параметра- ми запиту та вершинами графу. Одним з найпростіших у реалізації алгоритмів обчислення найкоротших шля- хів [15] є алгоритм Флойда – Воршалла [16]. Його часова складність займає )( 3N , де N – кількість вершин. Одне виконання алгоритму забезпечить довжи- ни (сумарні ваги) найкоротших шляхів між усіма парами вершин, хоча це не по- верне деталі про самі шляхи. Тому, у [13] автори описують зміни до алгоритму, які дозволили створити метод для реконстру- кції фактичного найкоротшого шляху між будь-якими двома кінцевими вершинами. Реконструкція шляху в цьому методі про- ходить в )(N і, таким чином, не впливає на складність алгоритму. Методичні підходи до побудови композитного сервісу Проведені дослідження дозволили визначити методичні підходи до побудови композитного сервісу, на основі функціо- нальної IOPE моделі сервісу. Моделі та засоби систем баз даних і знань 86 1. Запит – абстрактний опис серві- су, що реалізує необхідну функціональ- ність. Таким чином, композитними харак- теристиками результуючого сервісу мають бути саме параметри запиту, або множина параметрів, що максимально наближена до вимог запиту. 2. Методика базується на викорис- танні ДЛ як для представлення предметної області задачі (онтологія домена), так і для вирішення безпосередньо задач веб- сервісів, шляхом представлення сервісів та запиту за допомогою онтологій, де в якості мови опису онтологій обрано дескриптив- ну логіку. 3. Семантичні описи веб-сервісу являють собою твердження або аксіоми ДЛ. Задачі, що виникають при вирішенні задач веб-сервісів, зводяться до задач ви- конуваності ДЛ. 4. Кожен сервіс представляється ДЛ-онтологією на основі загальної онто- логії сервісу верхнього рівня. Кожна онто- логія конкретного сервісу базується на базі знань інтегрованої ДЛ-онтології домену. 5. Враховуючі, що опис профілей семантичних веб-сервісів, що зберігаються в реєстрі, є WSDL документ, який допов- нений семантичними анотаціями, тобто – звичайний XML, можливий автоматичний розбір цього XML-визначення та побудова онтології конкретного сервісу на основі онтології сервісу верхнього рівня, що ви- значена вище. 6. Алгоритм співставлення на ос- нові ДЛ, що представлений в [1] може бу- ти застосований для співставлення сервісів при композиції. 7. Існуючі резонери ДЛ дозволять здійснювати автоматичне співставлення запиту та сервісів, сервісів один з одним за входами виходами. Це стандартні задачі виводу ДЛ. Відношення між концептами та індивідами, що представлятимуть вхід- ну та вихідну інформацію запиту, визна- чають ступінь відповідності сервісів, що співставляються та ранжувати їх за цим показником. 8. В ході вирішення задач вияв- лення та композиції сервісів ймовірно ви- никає необхідність розширення онтології домену, уточнення онтологій сервісів чи описів сервісів. Резонери ДЛ дозволять перевірити отриманий опис на відсутність протиріч – стандартна задача розв’я- зуваності ДЛ. 9. Відповідність за виходами є пріорітетнішою ніж відповідність за входа- ми. Тому, пошук сервісів та побудову лан- цюжка доцільніше все ж таки проводити знизу-вгору – від виходів запиту. 10. Ітераційний покроковий алго- ритм побудови ланцюжка: a) пошук у реєстрі всіх сервісів, що відповідають вихідним параметрам та ефектам запиту, та ранжування їх за сту- пенем відповідності. Відповідно до крите- рія виявлення, найбільшу ступінь від- повідності (Exact) мають сервіси, виходи та ефекти яких еквівалентні виходам та ефектам запиту. Наступну ступінь відпо- відності мають сервіси, виходи та ефекти яких включають (subsumes) виходи та ефе- кти запиту. Але розглядаються також сер- віси, вихідні характеристики яких вклю- чають хоча б один вихід запиту (sub- sumed); b) якщо знайдено сервіс з Exact або Subsumes відповідністю за виходами, то це єдиний кінцевий сервіс ланцюжка; c) якщо існує декілька сервісів з Exact або Subsumes відповідністю за вихо- дами, аналізуються їх вхідні характерис- тики (вхідні параметри та передумови), та обирається сервіс, найближчий до запиту за входами; d) якщо існують сервіси тільки з Subsumed відповідністю виходів до запиту, обираємо сервіс, що має найбільший пере- тин за виходами із запитом; e) виходами результуючого ком- позитного сервісу буде об’єднання без по- вторень всіх виходів сервісів, що прий- матимуть участь у ланцюжку; f) сервіси кандидати-поперед- ники шукаються за критерієм: їх виходи співставляються з множиною, що є об’єднанням виходів запиту та входів на- ступного сервісу. Аналогічно, постумови (ефекти) сервісу, що шукається, мають Моделі та засоби систем баз даних і знань 87 бути пов’язані імплікацією з передумова- ми наступного сервісу або постумовами запиту. Сервіси ранжуються за ступенем відповідності. Після чого аналізуються входи відібраних сервісів, які переві- ряються на відповідність вхідним параме- трам запиту, а передумови повинні бути імплікацією передумов запиту. Якщо це не виконується, але є відповідність за ви- ходами, сервіси вбудовуються у ланцю- жок, але продовжується ітеративний про- цес пошуку сервісів – попередників, доки не будуть максимально задоволені всі вимоги запиту. 11. Підхід, що пропонується, поля- гає у застосуванні апарату ДЛ для реаліза- ції описаної методики. При цьому, сама задача композиції описується також за до- помогою апарата ДЛ. При такій постанов- ці, задача відповідності двох сервісів зво- диться до вирішення стандартної задачі розв’язуваності ДЛ, для чого може бути використаний будь-який з існуючих резо- нерів. Продемонструємо підхід на просто- му прикладі. Приклад побудови композитного сервісу Як приклад розглянемо просту зада- чу, а саме – задачу побудови композитного сервісу для вирішення задачі знаходження S площі трикутника, що заданий трьома векторами �̅�, �̅�, �̅�. Так як поставлена задача є геомет- ричною, то онтологія домену спирається на онтологію геометрії. TBox онтології домену POGeometry Vertex ⊑ has.XCoordinate Vertex ⊑ has.YCoordinate XCoordinate ⊑ Coordinate YCoordinate ⊑ Coordinate Coordinate ⊑ hasValue.NUMBER Verterx ⊑ has.VerterxLength Verterx ⊑ has.VerterxAngle VerterxLength ⊑ hasType.NUMBER VerterxAngle ⊑ hasType.NUMBER Height ⊑ hasType.NUMBER LenthAB ⊑ hasType.NUMBER … Triangle ⊑ GeometricFigure Triangle ⊑ =3has.Vertex Triangle ⊑ =3has.Vector Triangle ⊑ =3has.Height Square ⊑ hasType.NUMBER Triangle ⊑ has.Square Онтології запиту та сервісів спира- тимуться на онтологію сервісу вищого сер- вісу ServiceOntology та онтологію домена POGeometry. Онтологію запиту можна предста- вити наступним чином: TBox Q ⊑ Service /* зв’язок з ServiceOntology Q ⊑ =3has.InputParameter Q ⊑ =1has.OutputParameter IQ ⊑ InputParameter OQ ⊑ OutputParameter ABox a : I; b : I; c : I ; S: O a : Verterx, b : Verterx, c : Verterx /* зв’язок з онтологією POGeometry S : Square Припустимо, що в реєстрі нема сер- вісу, що задовільняє вимогам запиту, але ми знайшли сервіс 4S з вхідними парамет- рами: 𝒶 – NUMBER, 𝒽 – NUMBER, та ви- хідним параметром 𝓢 – NUMBER. Семан- тичні анотації сервісу вказують, що 𝒶 – довжина однієї з сторін трикутника, 𝒽 – його висота, що опущена на цю сторону, 𝓢 – площа цього трикутника. А саме, онтологія цього сервісу S4Ontology має наступний TBox: Моделі та засоби систем баз даних і знань 88 TBox 4S ⊑ Service 4S ⊑ =2has.InputParameter 4S ⊑ =1has.OutputParameter 4SI ⊑ InputParameter 4SO ⊑ OutputParameter ABox L : 4SI ; H : 4SI ; S : 4SO ; S : Square; L : Verterx; H : Height Тобто цей сервіс має Exact [1] від- повідність запиту за виходами, але взагалі не відповідає запиту за входами. Подальший пошук дозволив вияви- ти ще два сервіси 3S та 2S . Сервіс 2S має три вхідних парамет- ри, кожний з яких є вершиною трикутника, що задається своїми координатами, а ви- ходом є висота трикутника, яка опущена на одну з сторін. TBox для S2Ontology може мати ви- гляд: TBox 2S ⊑ Service 2S ⊑ =3has.InputParameter 2S ⊑ =1has.OutputParameter 2SI ⊑ InputParameter 2SO ⊑ OutputParameter ABox А : 2SI ; B : 2SI C ⊑ 2SI ; hC ⊑ 2SO A : Vertex, B: Vertex, C: Vertex /* Зв‘язок з онтологією POGeometry hC : Height Сервіс 3S має два вхідних параме- три, кожний з яких – це точка на площі, що задається своїми координатами, а виходом є довжина відрізку між ними. TBox для S3Ontology може мати вигляд: TBox 3S ⊑ Service 3S ⊑ =2has.InputParameter 3S ⊑ =1has.OutputParameter 3SI ⊑ InputParameter 3SO ⊑ OutputParameter ABox А : 3SI ; B : 3SI ; lAB : 3SO A: Vertex, B:Vertex /* Зв’язок з он- тологією POGeometry lAB : LenthAB Тобто об’єднання виходів цих двох сервісів – це точна відповідність входу сервісу 4S 4SI ≡ 3SO ⊔ 2SO . Але їх входи досі не забезпечують- ся запитом. Тобто не виконується умова: 2SI ⊔ 3SI ⊔ 4SI ⊑ QI . Таким чином, треба знайти сервіс S такий, що 2SI ⊔ 3SI ⊑ SO та SI ⊑ QI . Нарешті, виявляємо сервіс 1S із вхідними параметрами cba ,, – це векто- ри, та вихідні параметри CBA ,, , що є вершинами трикутника. Тобто сервіс, який виконує перетворення з представлення трикутника трьома векторами, у представ- лення вершинами. TBox для 1S Ontology може мати ви- гляд: 1S ⊑ Service 1S ⊑ =3has.InputParameter 1S ⊑ =3has.OutputParameter 1SI ⊑ InputParameter Моделі та засоби систем баз даних і знань 89 1SO ⊑ OutputParameter ABox a : 1SI b : 1SI c : 1SI A : 1SO , B : 1SO , C : 1SO A : Vertex, B: Vertex, C: Vertex /* Зв‘язок з онтологією POGeometry a : Vector, b:Vector, c:Vector При чому: QI ⊑ 1SI 2SI ⊔ 3SI ⊑ 1SO та 1SO ⊑ 2SI ⊔ 3SI Тобто графічно можна представити ланцюжок, який показано на рис. 3. Рис. 3. Ланцюжок побудови композитного сервісу знаходження площі трикутника Онтологія композиції Визначимо загальну онтологію композиції сервісів CompTaskOntology: Q ⊑ Service InputService ⊑ Service OutputService ⊑ Service ServiceComposition ⊑ (hasInput.InputService ⊔ hasInput.Q) ⊓ (hasOutput.OutputService) MatchingXY(S1,S2) ⊑ ∃𝒙. 𝑶𝒔𝟏, ∃𝒚. 𝑰𝒔𝟐: (C1(x) ⊓ C2(y) ⊓ ((C1⊑C2)⊓(C2⊑C1))⊔ (C1⊑C2)) Тоді ComposedServices(S1,S2) ⊑ ServiceComposition ⊓ MatchingXY(S1,S2) Слід зазначити, що всі наведені ви- ще постановки задач та алгоритми їх вирі- шення припускають, що сервіси репозито- рію та запит мають схоже представлення та посилаються на єдине представлення моделі домена чи онтологію. Але у загаль- ному випадку це досить суворе обмежен- ня, яке суттєво звужує область пошуку. В дійсності існує проблема гетерогенності представлення, як множини сервісів, так і запитів. Запропонована методологія зво- дить вирішення задачі гетерогенності до задачі інтеграції онтологій, а задачі вияв- лення та композиції сервісів до класичних алгоритмів ДЛ. Висновки Без побудови теоретично обґрунто- ваної семантичної моделі веб-сервісу та розробки на її основі формалізованих ме- тодів та підходів до вирішення основних задач веб-сервісів неможливе подальше ефективне автоматизоване вирішення складних бізнес-задач. В цілому, створе- ний теоретичний апарат є основою для розробки алгоритмів автоматизованого ви- рішення задач виявлення та композиції се- мантичних веб-сервісів. Специфіка запропонованих підходів полягає у тому, що для формального пред- ставлення веб-сервісів пропонується вико- ристовувати дескриптивну логіку. Доціль- ність використання дескриптивної логіки обумовлюється тим, що це формалізм, який забезпечує хороше семантичне ано- тування сервісів. Так як сервіси можуть Моделі та засоби систем баз даних і знань 90 створювати змінення у світі, точне пред- ставлення їх функціональності повинно мати справу з динамічним аспектом (пове- дінкою). Це також є одним з ключових аспектів, що робить очевидною доціль- ність використання ДЛ для описання сер- вісів, так як їх забезпечує можливість мір- кувань для сервісів, і таким чином дозво- ляє описати ДЛ динамічний аспект. Але дослідження сервісів на рівні їх поведінко- вої, або процесної моделі, є напрямком подальших досліджень. Наявність механі- змів міркувань ДЛ забезпечує також мож- ливість автоматизованого виявлення від- повідних сервісів та побудови складного сервіса, який реалізує конкретний бізнес- процес. Формалізація таких загальних по- нять як веб-сервіс, задача виявлення, ком- позиція за допомогою ДЛ онтолгій є осно- вою вирішення всієї низки задач веб-серві- сів на всіх етапах їх життєвого циклу. На основі цих базових визначень побудовані запропоновані методичні підходи, що фак- тично визначають покроковий ітераційний алгоритм побудови композитного сервісу на функціональному рівні. Література 1. Захарова О. Визначення та вирішення за- дачі виявлення Веб-сервісів за допомогою апарату дескриптивних логік. Проблеми програмування. 2017. № 4. С. 66–78. 2. Hai Wang, Zengzhi Li. A Semantic Matchmaking Method of Web Services Based On SHOIN+(D). Institute of Computer System Structure and Networks School of Electronics & Information Engineering, Xi’an Jiaotong University, Xi’an Shaanxi 710049, PR China hwang@mailst.xjtu.edu.cn, lzz@mail.xjtu.edu.cn 3. Baader F., Ku¨sters R., and Molitor R. Computing Least Common Subsumer in Description Logics with Existential Restrictions. In T. Dean, editor, Proc. of the 16th Int. Joint Conf. on AI. P. 96–101. M.K, 1999. 4. Franz Baader, Ralf Kiisters, and Ralf Molitor LuFg Theoretische Informatik, RWTH Aachen. Computing Least Common Subsumers in Description Logics with Existential. 5. Franz Baader, Ralf Ku¨sters, and Ralf Molitor. Rewriting Concepts Using Terminologies. In Proc. of the Int. Conf.KRColorado. USA. P. 297–308, Apr. 2000. 6. Beeri C., Levy A.Y., and Rousset M-C. Rewriting Queries Using Views in Description Logics. In L. Yuan, editor, Proc. of the ACM PODS , New York, USA. P. 99–108, Apr. 1997. 7. Alon Y. Halevy. Answering queries using views: A survey. VLDB Journal, 10(4):270 – 294, 2001. 8. Teege G. Making the difference: A subtraction operation for description log- ics. In J. Doyle, E. Sandewall, and P. Torasso, editors, KR’94, San Francisco, CA, 1994. Morgan Kaufmann. 9. AND/OR Graph and Search Algorithm for Discovering Composite Web Services. Qianhui Althea Lang, Singapore Management University, Stanley Y.W. Su, University of Florida, USA/ http://citeseerx.ist.psu.edu/viewdoc/summary? doi=10.1.1.131.1053 10. Semantic Web Services Composition Using AI planning of Description Logics. Lirong Qiu*" Fen Lin*" Changlin Wan*" Zhongzhi Shi* *Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, 100080, Beijing, China "Graduate School of the Chinese Academy of Sciences, 100039, Beijing, China {qiulr, linf, wancl, shizz}@ics.ict.ac.cn 11. D2.4.6 A Theoretical Integration of Web Service Discovery and Composition. Roberti Pierluigi (ITC-IRST) Marco Pistore (University of Trento) with contributions from: Walter Binder (EPFL), Ion Constantinescu (EPFL) Axel Polleres (UIBK), Holger Lausen (UIBK), Paolo Traverso (ITC- IRST), Michal Zaremba (NUIG). 2005. KWEB/2005/D2.4.6A/v1.0 12. http://life- prog.ru/view_zam2.php?id=204&cat=5&page =13 13. Srividya Kona, Ajay Bansal, M. Brian Blake, Gopal Gupta. Generalized Semantics-based Service Composition. / http://ieeexplore.ieee.org/abstract/document/4 670179 14. Paolucci M. et al., Semantic Matching of Web Services Capabilities, In First International Semantic Web Conference, Sardinia, Italy. 2002. P. 333–347. mailto:lzz@mail.xjtu.edu.cn mailto:shizz%7d@ics.ict.ac.cn http://life-prog.ru/view_zam2.php?id=204&cat=5&page=13 http://life-prog.ru/view_zam2.php?id=204&cat=5&page=13 http://life-prog.ru/view_zam2.php?id=204&cat=5&page=13 http://ieeexplore.ieee.org/abstract/document/4670179 http://ieeexplore.ieee.org/abstract/document/4670179 Моделі та засоби систем баз даних і знань 91 15. https://vo.homelinux.org/wiki/code/FloydWar shall. 16. Cormen T.H. et al. Introduction to Algorithms, MIT Press, 1990. References 1. Zakharova O. Defining and resolving Web- services discovery problems using description logics formalism. Problems in programming. 2017. N 4. P. 66–78. 2. Hai Wang, Zengzhi Li. A Semantic Matchmaking Method of Web Services Based On SHOIN+(D). Institute of Computer System Structure and Networks School of Electronics & Information Engineering, Xi’an Jiaotong University, Xi’an Shaanxi 710049, PR China hwang@mailst.xjtu.edu.cn, lzz@mail.xjtu.edu.cn 3. Baader F., Ku¨sters R., and Molitor R. Computing Least Common Subsumer in Description Logics with Existential Restrictions. In T. Dean, editor, Proc. of the 16th Int. Joint Conf. on AI. P. 96–101. M.K, 1999. 4. Franz Baader, Ralf Kiisters, and Ralf Molitor LuFg Theoretische Informatik, RWTH Aachen. Computing Least Common Subsumers in Description Logics with Existential. 5. Franz Baader, Ralf Ku¨sters, and Ralf Molitor. Rewriting Concepts Using Terminologies. In Proc. of the Int. Conf.KRColorado. USA. P. 297–308, Apr. 2000. 6. Beeri C., Levy A.Y., and Rousset M-C. Rewriting Queries Using Views in Description Logics. In L. Yuan, editor, Proc. of the ACM PODS , New York, USA. P. 99–108, Apr. 1997. 7. Alon Y. Halevy. Answering queries using views: A survey. VLDB Journal, 10(4):270 – 294, 2001. 8. Teege G. Making the difference: A subtraction operation for description log- ics. In J. Doyle, E. Sandewall, and P. Torasso, editors, KR’94, San Francisco, CA, 1994. Morgan Kaufmann. 9. AND/OR Graph and Search Algorithm for Discovering Composite Web Services. Qianhui Althea Lang, Singapore Management University, Stanley Y.W. Su, University of Florida, USA/ http://citeseerx.ist.psu.edu/viewdoc/summary? doi=10.1.1.131.1053 10. Semantic Web Services Composition Using AI planning of Description Logics. Lirong Qiu*" Fen Lin*" Changlin Wan*" Zhongzhi Shi* *Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, 100080, Beijing, China "Graduate School of the Chinese Academy of Sciences, 100039, Beijing, China {qiulr, linf, wancl, shizz}@ics.ict.ac.cn 11. D2.4.6 A Theoretical Integration of Web Service Discovery and Composition. Roberti Pierluigi (ITC-IRST) Marco Pistore (University of Trento) with contributions from: Walter Binder (EPFL), Ion Constantinescu (EPFL) Axel Polleres (UIBK), Holger Lausen (UIBK), Paolo Traverso (ITC- IRST), Michal Zaremba (NUIG). 2005. KWEB/2005/D2.4.6A/v1.0 12. http://life- prog.ru/view_zam2.php?id=204&cat=5&page =13 13. Srividya Kona, Ajay Bansal, M. Brian Blake, Gopal Gupta. Generalized Semantics-based Service Composition. / http://ieeexplore.ieee.org/abstract/document/4 670179 14. Paolucci M. et al., Semantic Matching of Web Services Capabilities, In First International Semantic Web Conference, Sardinia, Italy. 2002. P. 333–347. 15. https://vo.homelinux.org/wiki/code/FloydWar shall. 16. Cormen T.H. et al. Introduction to Algorithms, MIT Press, 1990. Одержано 12.09.2017 Про автора: Захарова Ольга Вікторівна, кандидат технічних наук, старший науковий співробітник. Кількість наукових публікацій в українських виданнях – 26. http://orcid.org/0000-0002-9579-2973. Місце роботи автора: Інститут програмних систем НАН України, проспект Академіка Глушкова, 40. Тел.: 526 5139. E-mail: ozakharova68@gmail.com. https://vo.homelinux.org/wiki/code/FloydWarshall https://vo.homelinux.org/wiki/code/FloydWarshall mailto:lzz@mail.xjtu.edu.cn mailto:shizz%7d@ics.ict.ac.cn http://life-prog.ru/view_zam2.php?id=204&cat=5&page=13 http://life-prog.ru/view_zam2.php?id=204&cat=5&page=13 http://life-prog.ru/view_zam2.php?id=204&cat=5&page=13 http://ieeexplore.ieee.org/abstract/document/4670179 http://ieeexplore.ieee.org/abstract/document/4670179 https://vo.homelinux.org/wiki/code/FloydWarshall https://vo.homelinux.org/wiki/code/FloydWarshall