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

郭媛香

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

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

郭媛香

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

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

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

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

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

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

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

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

1.1 描述邏輯基礎(chǔ)

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

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

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

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

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

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

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

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

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

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

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

1.3 PE匹配算法

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

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

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

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

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

1.4 PE匹配推理

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

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

解釋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是知識(shí)庫(kù)К的模型，當(dāng)且僅當(dāng)I是К中包含斷言和實(shí)例斷言的模型.

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

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

證明：

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

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

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

定理2令К表示基于SH OIN（D）的知識(shí)庫(kù)，A表示SH OIN（D）的一個(gè)原子事件，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描述公理的有限集合看作一個(gè)本體知識(shí)庫(kù)，因此有關(guān)PE的語(yǔ)義匹配問(wèn)題就轉(zhuǎn)化到兩個(gè)基于描述邏輯的本體知識(shí)庫(kù)的關(guān)系問(wèn)題.令δ（К）為這樣一個(gè)轉(zhuǎn)化：把知識(shí)庫(kù)中的形如□C∈К的公理轉(zhuǎn)化為公理a：C，其中a表示一個(gè)實(shí)例的名字，C表示知識(shí)庫(kù)中的類(lèi).那么，判別一個(gè)本體知識(shí)庫(kù)蘊(yùn)含另一個(gè)本體知識(shí)庫(kù)的算法表示如表2所示.

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

2 匹配示例

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

本文將用戶的訂閱看作是概念，每一個(gè)原子事件看作是一個(gè)個(gè)體.令Sub（e）為事件斷言集，Sub（e）表示事件e匹配訂閱Sub，若要判斷事件e是否匹配訂閱Sub，就是根據(jù)描述邏輯中基于個(gè)體推理的知識(shí)庫(kù)來(lái)判斷個(gè)體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)生了一個(gè)交易事件，且該事件的St ep取值為rai l carryi ng.

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

匹配過(guò)程：

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

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

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

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

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

3 結(jié)束語(yǔ)

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