郭媛香

（晉中學(xué)院信息技術(shù)與工程學(xué)院，山西 晉中 030619）

基于動態(tài)描述邏輯的語義Web服務(wù)PE匹配算法

郭媛香

（晉中學(xué)院信息技術(shù)與工程學(xué)院，山西 晉中 030619）

將基于描述邏輯斷言構(gòu)成的PE描述公理的有限集合看作一個本體知識庫，因此有關(guān)PE的語義匹配問題就轉(zhuǎn)化到兩個基于描述邏輯的本體知識庫之間的邏輯蘊(yùn)含判定問題，然后將邏輯蘊(yùn)含推理問題轉(zhuǎn)化為本體庫的可滿足性檢測問題，并通過可判的擴(kuò)展算法解決，同時對匹配結(jié)果進(jìn)行有意義的排序及分類.所提方法與現(xiàn)有方法相當(dāng)?shù)那闆r下，具有更高的查全率，能夠更好地區(qū)分匹配結(jié)果.

語義Web服務(wù)；前提/效果；動態(tài)描述邏輯；服務(wù)匹配

W eb服務(wù)[1]是一個嶄新的分布式計(jì)算模型，是W eb上數(shù)據(jù)和信息集成的有效機(jī)制，具有自包容、自描述性的應(yīng)用模塊，可以通過W eb來發(fā)布、查詢和調(diào)用，它的出現(xiàn)及推廣將變革現(xiàn)有的W eb應(yīng)用模式.語義W eb服務(wù)擴(kuò)展了當(dāng)前的W eb服務(wù)，賦予W eb中所有信息以良好的語義，是W eb提供的一種動態(tài)服務(wù)，每一個服務(wù)可以看成一個動作.

描述邏輯（DL）是一種基于對象的形式化知識表示工具，對概念性知識的處理非常有效，它具有清晰的模型—理論語義，具有很強(qiáng)的表達(dá)能力和可判定性，能夠提供有效的可判定推理服務(wù).動態(tài)描述邏輯[2]（DDL）是描述邏輯的一種動態(tài)擴(kuò)展，支持語義W eb環(huán)境下對動作的描述和推理，該DDL清晰的語義特征能夠讓系統(tǒng)理解語義，有效地對靜態(tài)知識和動態(tài)知識進(jìn)行表示和推理.一個W eb服務(wù)的功能性描述可以抽象為一個DDL原子動作.

目前，大多數(shù)的語義匹配算法主要關(guān)注服務(wù)的IO匹配，對PE匹配算法的研究很少，但PE的描述是至關(guān)重要的.在執(zhí)行一個服務(wù)需求鏈時，沒有考慮服務(wù)PE的匹配會給整個任務(wù)帶來負(fù)面影響，因此需要設(shè)計(jì)算法解決PE的匹配.本文結(jié)合描述邏輯的知識[3]，提出一種基于動態(tài)描述邏輯的語義W eb服務(wù)PE匹配算法，以基于描述邏輯斷言構(gòu)成的知識庫對服務(wù)的PE進(jìn)行描述，將PE匹配問題轉(zhuǎn)化為描述邏輯知識庫之間的邏輯蘊(yùn)含判定問題.

1 基于動態(tài)描述邏輯的PE匹配方法

語義W eb服務(wù)功能性描述主要指服務(wù)的輸人（I）、輸出（O）、前提（P）和效果（E）的描述，W eb服務(wù)匹配實(shí)質(zhì)上是服務(wù)描述的匹配，就是利用服務(wù)的語義描述信息和動態(tài)描述邏輯對知識的推理功能，服務(wù)需求方從已經(jīng)發(fā)布的W eb服務(wù)中找到符合需求的服務(wù)的過程.從描述邏輯的定義和性質(zhì)可以看出，一個服務(wù)本質(zhì)上就是一對描述邏輯知識庫[4]，本文以描述邏輯知識庫之間的語義推導(dǎo)和邏輯蘊(yùn)含關(guān)系的一致性檢測為基礎(chǔ)，給出了基于描述邏輯知識庫一致性檢測的語義W eb服務(wù)PE匹配算法，因此有關(guān)PE的語義匹配問題就轉(zhuǎn)化到兩個基于描述邏輯的本體知識庫之間的邏輯蘊(yùn)含判定問題.

1.1 描述邏輯基礎(chǔ)

描述邏輯由語法和語義組成，語義是通過解釋I=（ΔI，·I）給出，其中，ΔI是解釋領(lǐng)域的非空集合，·I是解釋函數(shù)，能夠把每個原子概念A(yù)映射到的ΔI的子集，把每一個原子關(guān)系P映射到ΔI×ΔI的子集.ALC是最基本的描述邏輯，包括以下算子：交（∩）、并（∪）、非（┐），存在量詞（□）和全稱量詞（□）.在ALC的基礎(chǔ)上添加不同的構(gòu)造算子能構(gòu)成不同表達(dá)能力的描述邏輯.SHOIN(D)為對應(yīng)語義Web本體語言O(shè)WL DL的描述邏輯表示語言.

在一定領(lǐng)域中，一個基于DL的知識庫К=＜TBox，ABox＞由TBox和ABox兩部分組成.其中，TBox是由包含概念定義及公理構(gòu)成的包含斷言的有限集合，概念A(yù)、C間包含關(guān)系的斷言表示為A?C，概念A(yù)、C引入概念名稱的過程表示為A□C，ABox是由斷言公式或其否定形式構(gòu)成的實(shí)例斷言的有限集合，形如R (a，b)、C（a）的公式分別是描述邏輯中的角色斷言、概念斷言，二者統(tǒng)稱為斷言公式，其中C是相對于TBox的簡單概念名，C（a）表示個體a滿足概念C的約束；R是一個關(guān)系，aRb，R（a，b）表示個體a的屬性R的一個取值是b，a、b為個體對象.

1.2 語義Web服務(wù)形式化定義

為了利用描述邏輯知識庫一致性檢測進(jìn)行服務(wù)的PE匹配，我們以形式化的方式定義W eb服務(wù)的前置條件P和后置條件E，并在此基礎(chǔ)上進(jìn)行分析.將具有相似功能的一類服務(wù)抽象為一個DDL原子動作，然后將蘊(yùn)含推理問題轉(zhuǎn)化為本體庫的可滿足性檢測問題[5]，并且將這些推理問題轉(zhuǎn)換為DDL SH OIN（D）中公式的可滿足性問題.為了便于說明，本文認(rèn)為服務(wù)的輸入和輸出都已經(jīng)被實(shí)例化為個體，描述只考慮了原子基礎(chǔ)服務(wù)PE.

定義1給定某個TBox，將一個原子基礎(chǔ)服務(wù)К=（P，E）看成一個原子動作.其中：К為原子動作名；P為服務(wù)前提，抽象為TBox上斷言公式或其否定式組成的有限集合，表示動作執(zhí)行前必須滿足的前提條件；E為服務(wù)效果，抽象為TBox上簡單公式組成的有限集合，表示執(zhí)行該動作后將會發(fā)生的影響.К=（P，E）包括：①一個由描述邏輯公理組成的表示前提的有限集(知識庫)；②一個由描述邏輯公理組成的表示效果的有限集（知識庫）.

一個W eb服務(wù)可用一個描述邏輯的表達(dá)式描述，用Pa、Ea表示服務(wù)提供者的PE描述信息，用Pr、Er表示服務(wù)請求者的PE描述信息，那么對于同一個TBox，請求服務(wù)Кr=（Pr，Er）和發(fā)布服務(wù)Кa=（Pa，Ea）之間的匹配可以分為以下四種定義：

Exact：如果Pr≡Pa，Er≡Ea，即Кr|=Кa和Кa|=Кr均成立，則Кr?Кa.此時服務(wù)提供者與服務(wù)請求者的描述完全等價，表明服務(wù)提供者Кr和服務(wù)請求者Кa完全匹配.

FatherContains：如果Pr□Pa，Er□Ea，即Кa|=Кr成立，但Кr|=Кa不成立，此時服務(wù)提供者的服務(wù)執(zhí)行后產(chǎn)生的效果Кa邏輯蘊(yùn)含服務(wù)請求要求的效果Кr，表明服務(wù)提供者的服務(wù)執(zhí)行后會對客觀世界產(chǎn)生額外的效果.

SubContains：如果Pr□Pa，Er□Ea，即Кr|=Кa成立，但Кa|=Кr不成立，此時服務(wù)請求者的服務(wù)Кr邏輯蘊(yùn)含服務(wù)提供者的服務(wù)Кa，表明服務(wù)請求者能夠滿足服務(wù)提供者規(guī)定的服務(wù)發(fā)生的條件.

Fail：如果Pr≠Pa，或者Er≠Ea，即Кr|=Кa和Кa|=Кr均不成立，表明Кr與Кa完全不匹配，匹配失敗.

該算法利用本體描述邏輯語言描述語義信息，并將匹配結(jié)果細(xì)化，在精確與失敗兩種匹配結(jié)果的基礎(chǔ)上添加了FatherContains匹配和SubContains匹配的情形，從而提高匹配精度.服務(wù)間的匹配程度按照匹配的強(qiáng)弱程度分為四個等級，即Exact＞FatherContains＞SubContains＞Fail.

1.3 PE匹配算法

Web服務(wù)匹配包含了兩個功能：一個是發(fā)布服務(wù)，一個是從服務(wù)的描述數(shù)據(jù)庫中查詢服務(wù).服務(wù)提供者將服務(wù)的描述發(fā)布在匹配器的服務(wù)注冊中心，用戶則通過提交查詢來獲取所需服務(wù)的信息.為了判斷服務(wù)發(fā)布者是否提供了用戶需求的功能，基于描述邏輯的服務(wù)本體為匹配模型提供了描述信息.Web服務(wù)匹配過程如圖1所示.

在服務(wù)匹配的過程中，查詢語句和每一個存放在注冊中心的服務(wù)描述進(jìn)行匹配.在進(jìn)行匹配時，需求服務(wù)和服務(wù)描述的所有前置條件和后置條件都要進(jìn)行匹配，每當(dāng)一個服務(wù)和用戶需求匹配成功就將其記錄到查詢結(jié)果的列表中，并將它與其他匹配成功的服務(wù)進(jìn)行匹配度的排序.

圖1 基于描述邏輯的語義Web匹配的流程圖

在PE匹配中，結(jié)合描述邏輯的知識，用ABox概念斷言描述服務(wù)發(fā)布和服務(wù)請求的前提條件和效果，用TBox描述推理依賴的領(lǐng)域知識，給出一個能夠通過兩個服務(wù)的PE描述信息計(jì)算出匹配結(jié)果的算法1.在匹配結(jié)果中也可能存在多個服務(wù)發(fā)布與服務(wù)請求相匹配，該算法并對它們的匹配結(jié)果集進(jìn)行排序，該算法的偽代碼形式化表示如表1所示.

表1 判別匹配結(jié)果精確分類的算法

1.4 PE匹配推理

W eb服務(wù)推理對保障知識庫的一致性非常重要.基本推理主要有：概念可滿足性檢測，一致性檢測，包含檢測，實(shí)例檢測等.其中概念可滿足性檢測推理、一個知識庫可滿足性檢測問題都能被簡化成關(guān)于術(shù)語的概念可滿足性問題.

定義2可滿足性：對于給定的TBox Τ，ABox Α，如果存在術(shù)語庫Τ的一個解釋I及概念C，使得CI≠Ф，那么概念C是關(guān)于Τ可滿足的.此時，我們說I是C的一個模型.

解釋I是包含斷言C?D的模型，當(dāng)且僅當(dāng)CI?DI.

解釋I是概念斷言C（a）的模型，當(dāng)且僅當(dāng)a∈CI.

解釋I是角色斷言R（a，b）的模型，當(dāng)且僅當(dāng)（a，b）∈RI.

解釋I是知識庫К的模型，當(dāng)且僅當(dāng)I是К中包含斷言和實(shí)例斷言的模型.

若К有模型，則К是可滿足的.

定理1概念C是可滿足的?形如{C（a）}的斷言關(guān)于TBox是一致的.

證明：

充分性.若C是可滿足的，假設(shè){C（a）}是不一致的，則必有TBox Τ的一個模型I，使得

而CI≠ CI，這與C是可滿足的矛盾.

必要性.若{C（a）}是一致的，對所有的I∈Int（L），C∈Τ有CI=CI，即I|=Τ，所以C是可滿足的.

定理2令К表示基于SH OIN（D）的知識庫，A表示SH OIN（D）的一個原子事件，G（A）表示事件斷言集，則：

К|=A當(dāng)且僅當(dāng)К與{G（A）}是一致的；К與{G（A）}是一致的當(dāng)且僅當(dāng)К∪{┐G（A）}是不一致的.

當(dāng)且僅當(dāng)（A∈К1）∩(К1|=К2)成立，則К1|=К2.

當(dāng)且僅當(dāng)（К1|=К2）∩(К2|=К1)成立，則К1?К2.

本文將PE描述公理的有限集合看作一個本體知識庫，因此有關(guān)PE的語義匹配問題就轉(zhuǎn)化到兩個基于描述邏輯的本體知識庫的關(guān)系問題.令δ（К）為這樣一個轉(zhuǎn)化：把知識庫中的形如□C∈К的公理轉(zhuǎn)化為公理a：C，其中a表示一個實(shí)例的名字，C表示知識庫中的類.那么，判別一個本體知識庫蘊(yùn)含另一個本體知識庫的算法表示如表2所示.

表2 判別本體知識庫蘊(yùn)含關(guān)系的算法描述

2 匹配示例

本文以物流領(lǐng)域信息服務(wù)中的發(fā)布/訂閱系統(tǒng)為例來說明匹配過程.關(guān)注產(chǎn)品流通的用戶向產(chǎn)品流通環(huán)節(jié)發(fā)布的信息中請求消息訂閱服務(wù)，訂閱自己感興趣的產(chǎn)品流通信息，根據(jù)業(yè)務(wù)語義來進(jìn)行事件與訂閱的匹配分析，如果該業(yè)務(wù)事件符合用戶的訂閱要求，該物流環(huán)節(jié)上的信息服務(wù)提供者就會自動通知該用戶，從而達(dá)到用戶請求服務(wù)與實(shí)時發(fā)布服務(wù)的匹配.

本文將用戶的訂閱看作是概念，每一個原子事件看作是一個個體.令Sub（e）為事件斷言集，Sub（e）表示事件e匹配訂閱Sub，若要判斷事件e是否匹配訂閱Sub，就是根據(jù)描述邏輯中基于個體推理的知識庫來判斷個體e是否滿足概念Sub的約束.物流領(lǐng)域的業(yè)務(wù)狀態(tài)如圖2所示.

用戶的訂閱需求：貨物的業(yè)務(wù)狀態(tài)變?yōu)閠 ransport i ng→通知用戶.

圖2 物流領(lǐng)域業(yè)務(wù)狀態(tài)圖

用戶的訂閱表達(dá)式：Sub=Transact i onEvent∩□St ep.Transport i ng.

條件：系統(tǒng)中產(chǎn)生了一個交易事件，且該事件的St ep取值為rai l carryi ng.

目標(biāo)：判斷該事件是否匹配訂閱Sub.

匹配過程：

（1）斷言知識庫К={Transact i onEvent(e),St ep（e,rai l Canrryi ng）}

（2）計(jì)算S={КU{┐Sub(e)}}的完全形式：

（3）判斷S的不一致性：

S中的第一個集合元素是不一致的，因?yàn)樵摷显匕琓ransact i onEvent（e）和┐Transact i onEvent（e）；由于S中的第二個集合元素包含┐l andCarryi ng（rai l Carryi ng），顯然也是不一致的，因而S是不一致的，所以由定理2可知事件e匹配訂閱Sub.

由此可知，對于原子訂閱的匹配算法，算法的主要工作集中在判斷知識庫完全形式的一致性上.充分利用DL推理機(jī)的強(qiáng)大推理功能，實(shí)現(xiàn)了本文提出的基于描述邏輯的W eb服務(wù)匹配算法.將W eb服務(wù)的功能抽象為DDL動作后，從DDL具有動態(tài)語義模型出發(fā)，通過推理由前提條件的動作產(chǎn)生的效果來實(shí)現(xiàn)W eb服務(wù)的匹配.

3 結(jié)束語

針對語義W eb服務(wù)的前提/效果匹配問題，本文提出了一種基于動態(tài)描述邏輯的方法來實(shí)現(xiàn)W eb服務(wù)功能性層面上的自動匹配.將基于描述邏輯斷言構(gòu)成的PE描述公理的有限集合抽象為一個本體知識庫，然后提出一種基于描述邏輯知識庫一致性檢測的PE匹配算法，并對該算法的合理性進(jìn)行了實(shí)例分析.由于本文提出的匹配算法僅針對原子基礎(chǔ)服務(wù)，還未能在更多的實(shí)際應(yīng)用中表達(dá)復(fù)雜的業(yè)務(wù)邏輯，接下來的工作方向是擴(kuò)展DDL使得它支持復(fù)合服務(wù)的匹配，在兼顧匹配效率的情況下來提高描述語言的表達(dá)能力，并在實(shí)踐中進(jìn)行檢驗(yàn).

［1］Jai deep R,Anupam a.R.Underst andi ngW eb servi ces［C］//IT Prof essi onal，Vol um e3.W ashi ngt on：IEEE Com put erSoci et y，2001.

［2］BaadeF，Cal vaneseD，eta1.TheDescri pt i on Logi c H andboo K：Theory Im pl em ent at i on and Appl i cat i ons［M］.Cam bri dge Uni versi t yPress.2003：47～100．

［3］石蓮，孫吉貴.描述邏輯［J］.計(jì)算機(jī)科學(xué)，2006，33（1）：194～198.

［4］BADER F，LUTZ C，M ILICIC M，eta1.A descri pt i on l ogi cbased approach t oreasoni ngaboutW eb servi ces［C］//Proceedi ngsoft he W W W 2005 W orkshop on W eb Servi ceSem ant i csNew York：USA：ACM 2005.

［5］吳強(qiáng)，劉宗田，強(qiáng)宇.基于本體的知識庫推理研究［J］.計(jì)算機(jī)應(yīng)用研究，2005（1）：51～53.

（編輯 張瑛）

TP311

A

1673-1808（2014）03-0064-05

2013-12-23

郭媛香（1963-），女，山西榆社人，晉中學(xué)院信息技術(shù)與工程學(xué)院，副教授，研究方向：計(jì)算機(jī)技術(shù)與應(yīng)用、數(shù)據(jù)挖掘.