李　鑫

(重慶理工大學(xué) 會(huì)計(jì)學(xué)學(xué)院，重慶 400050)

?

一種策略沖突的消解方法

李鑫

(重慶理工大學(xué) 會(huì)計(jì)學(xué)學(xué)院，重慶 400050)

摘要：利用非單調(diào)邏輯編程技術(shù)，Chomicki等人提出了一種策略沖突消解方法.雖然該方法具有高效、可靠和良好的封裝性等優(yōu)點(diǎn)，但是它的應(yīng)用域卻受到限制.在Chomicki方法的基礎(chǔ)上，首先定義了組合沖突，它比一般策略沖突涵義更廣.其次，為消解該類沖突引入了一個(gè)優(yōu)化解—最大行動(dòng)接受集，并給出與之互補(bǔ)的最小行動(dòng)取消集的重要特性.最后，利用基于穩(wěn)定模型語(yǔ)義的權(quán)約束規(guī)則編程技術(shù)，建立消解組合沖突的邏輯程序.由于該程序始終擁有穩(wěn)定模型，所以總是能夠根據(jù)它的模型獲得優(yōu)化解.

關(guān)鍵詞：沖突；權(quán)約束規(guī)則；最大行動(dòng)接受集；最小行動(dòng)取消集；穩(wěn)定模型

隨著ECA(event-condition-action)策略在計(jì)算機(jī)管理與控制中的廣泛應(yīng)用，如分布式系統(tǒng)管理、數(shù)據(jù)庫(kù)系統(tǒng)管理、安全與訪問控制、Web服務(wù)及其組合等，有關(guān)策略沖突的研究也愈來愈受到重視[1-3].

利用基于穩(wěn)定模型語(yǔ)義的非單調(diào)邏輯編程技術(shù)[4-5](也被稱為回答集編程技術(shù)[6])，Chomicki等人[3]提出一種消解PDL(policy description language)[7]策略沖突的方法.該方法具有以下優(yōu)點(diǎn)：

1)易于實(shí)現(xiàn)PDL策略及其沖突消解的邏輯編程表示，且邏輯編程技術(shù)能夠確保沖突消解的可靠性和有效性；

2)建立的沖突消解邏輯程序具有良好的層次性和獨(dú)立性；

3)根據(jù)沖突消解邏輯程序的穩(wěn)定模型，不但能夠?qū)崿F(xiàn)沖突消解而且還可以獲得極大行動(dòng)接受集.Chomicki等人選擇PDL策略的原因是它比一般ECA策略更復(fù)雜且描述能力更強(qiáng)[7-8].

Chomicki方法并不能消解本文定義的特殊組合沖突.一方面，該方法的成功依賴于沖突消解邏輯程序語(yǔ)義模型的存在性；另一方面，當(dāng)特殊組合沖突發(fā)生時(shí)，按照該方法構(gòu)造的沖突消解邏輯程序不再擁有穩(wěn)定模型.從而導(dǎo)致失敗.其失敗的根本原因是它采用了析取邏輯編程技術(shù)[5,9]，這點(diǎn)將在3.2節(jié)詳細(xì)說明.

下文通過例1的沖突說明特殊組合沖突的普遍性.同時(shí)該例也用于闡述本文中的沖突消解方法.

例1在一個(gè)簡(jiǎn)單的會(huì)議室自動(dòng)預(yù)定系統(tǒng)中，一方面，式(1)的PDL規(guī)則構(gòu)成其策略.該規(guī)則規(guī)定當(dāng)一個(gè)用戶User的預(yù)定申請(qǐng)事件requestRes(User)發(fā)生時(shí)，為該用戶執(zhí)行預(yù)留會(huì)議室的行動(dòng)procRes(User).另一方面，為消解沖突定義式(2)的行動(dòng)約束(action constraint,ac)，以防止由于同時(shí)執(zhí)行兩個(gè)不同用戶的procRes行動(dòng)而導(dǎo)致的沖突.這里的沖突是由于同時(shí)發(fā)生了多個(gè)不同用戶的預(yù)定申請(qǐng)事件，而且他們申請(qǐng)的是同一會(huì)議室而導(dǎo)致的.另外，假設(shè)會(huì)議室的預(yù)留時(shí)間重疊.

(1)

(2)

此例也是文獻(xiàn)[3]中的例1.簡(jiǎn)潔起見，下文一律假設(shè)預(yù)定申請(qǐng)的是同一會(huì)議室，且申請(qǐng)事件同時(shí)發(fā)生.該例中，特殊組合沖突指由三個(gè)或三個(gè)以上不同用戶申請(qǐng)導(dǎo)致的沖突.而由兩個(gè)不同用戶申請(qǐng)導(dǎo)致的沖突，也是Chomicki方法能夠消解的，在本文歸為一般組合沖突.

為克服Chomicki方法的局限性，本文提出一種利用基于穩(wěn)定模型語(yǔ)義的權(quán)約束規(guī)則(weight constraint rule, WCR)編程技術(shù)[10-11]消解策略沖突的方法.在Chomicki方法基礎(chǔ)上，首先定義了涵義更為寬泛的組合沖突，它不僅包含了一般組合沖突，更為重要的是，特殊組合沖突也是它的一個(gè)子類.然后，為沖突消解提出一個(gè)優(yōu)化解概念，即最大行動(dòng)接受集(largest action-acceptance set, LAAS)，并給出與它互補(bǔ)的最小行動(dòng)取消集(smallest action-cancellation set,SACS)的重要性質(zhì).最后，在一個(gè)極大化處理過程的基礎(chǔ)上，利用WCR編程技術(shù)建立組合沖突消解邏輯程序.由于該程序始終擁有穩(wěn)定模型，所以總是能夠獲得LAASes.

1　背景知識(shí)

1.1　WCR編程簡(jiǎn)介

任意非單調(diào)邏輯程序是一個(gè)由形如式(3)的規(guī)則組成的有限集.其中，li(i∈{0,1，…,n})是一階正(或負(fù))文字，not是 “失敗為否定” (negation-as-failure)操作符.通常稱集合{l0,,l1,…,lk}和{lk+1,,lk+2,…,ln}分別為規(guī)則的頭和體.由于不再象Prolog程序具有唯一的最小海布南模型[12]，所以非單調(diào)邏輯程序通常按照模型語(yǔ)義解釋，即只有在一定的語(yǔ)義模型下，邏輯程序才具有明確的語(yǔ)義解釋.由M.Gelfond和V.Lifschitz開創(chuàng)的穩(wěn)定模型語(yǔ)義是至今為止被廣為接受的一種非單調(diào)邏輯程序模型語(yǔ)義.經(jīng)過二十年的發(fā)展，如今已經(jīng)開發(fā)出多種實(shí)用的穩(wěn)定模型語(yǔ)義編程系統(tǒng)，如DLV[13]、AnsProlog[14]等.

(3)

(4)

(5)

(6)

(7)

(8)

WCR編程技術(shù)是對(duì)基于穩(wěn)定模型語(yǔ)義的非單調(diào)邏輯編程技術(shù)的一種擴(kuò)展，SMODELS是它的實(shí)用編程系統(tǒng).一個(gè)WCR的基本形式為“WC0←WC1,…,WCm”，其中，式(4)表示任意權(quán)約束WCi(i∈{0,1,…,m}).WCi的語(yǔ)義定義是，S|=WCi當(dāng)且僅當(dāng)z≤w(S,WCi)≤u，其中，S為任意原子謂詞實(shí)例集，權(quán)值函數(shù)w(WCi,S)=∑ai∈Slai+∑bj?Slbj，而且，上界u、下界z以及權(quán)值目前只能為自然數(shù).關(guān)于基于穩(wěn)定模型語(yǔ)義的WCR程序，需要注意以下兩點(diǎn)：①它的模型不但符合穩(wěn)定模型語(yǔ)義解釋，而且還需要滿足權(quán)約束上的權(quán)值約束；②WCR具有靈活多樣的形式，除基本形式外，例如，式(5)的規(guī)則也是可行的.

當(dāng)所有權(quán)值均為1時(shí)，WCR被稱為基數(shù)約束規(guī)則(cardinality constraint rule,CCR)，基數(shù)約束可簡(jiǎn)化為式(6)的形式.除權(quán)值始終為1外，CCR的語(yǔ)義定義與WCR一樣.WCR編程技術(shù)還提供分別形如式(7)和(8)的minimize和maximize優(yōu)化語(yǔ)句，它們的權(quán)值計(jì)算與WCR一樣.以上兩個(gè)語(yǔ)句分別完成對(duì)程序最小和最大權(quán)值模型的搜索.

1.2　Chomicki方法

1.2.1策略Prolog程序.在文獻(xiàn)[3]中，任意PDL策略P的語(yǔ)義是變換πP:Epochs(P)→ActionSet(P).其中，Epochs(P)是所有段事件集的集合，且一個(gè)段事件集是由發(fā)生在一個(gè)系統(tǒng)時(shí)間段中的所有基本事件實(shí)例(primitive event instance)組成的有限集；ActionSet(P)是一個(gè)是由所有完成填充的行動(dòng)構(gòu)成的集合，且它的一個(gè)元素被稱為行動(dòng)集.

(9)

(10)

設(shè)策略P對(duì)應(yīng)于一段事件集E的實(shí)例為P(E).通過將P(E)中每個(gè)PDL規(guī)則實(shí)例“e1&…&elcauses a if C”，用式(9)的Horn(或definite)范式捕獲，建立P對(duì)應(yīng)于E的Prolog程序∏P.在式(9)中，exec和occ是原子謂詞，條件C=t1θ1t1′，…，tmθ1tm′且任意比較謂詞θi∈{=,≠,≤,≥}(i∈{1,2,…,m}).

至此得到，對(duì)于一段事件集E而言，任意行動(dòng)a∈πP(E)當(dāng)且僅當(dāng)∏P∪OCC(E)|=exec(a)，其中，式(10)定義OCC(E).從而完成策略P的等價(jià)邏輯編程表示.

1.2.2沖突消解.Chomicki等人定義了形如“Nevera1，a2，…，amifC”的ac以捕獲一類沖突.以上ac規(guī)定在條件C被滿足的情況下，禁止同時(shí)執(zhí)行m個(gè)行動(dòng)a1，…，am，否則將導(dǎo)致沖突.AC是管理員定義的ac集合，且對(duì)應(yīng)于一個(gè)段事件集E的AC實(shí)例為AC(E).

(11)

(12)

從以上介紹也可看出，沖突消解邏輯程序具有良好的層次性且各組成部分之間相互獨(dú)立.

2　組合沖突

2.1　定義

稱被一個(gè)ac(或aci)約束的行動(dòng)個(gè)數(shù)為它的長(zhǎng)度.顯然，任意ac(或aci)的長(zhǎng)度均大于1.

2)X中所有行動(dòng)構(gòu)成的集合等于A；

3)X中的任意aci的條件C被滿足.

以上定義中，條件3排除了對(duì)aci的條件判斷，這便于沖突組合的研究.而且，由于該類條件易于判斷，所以條件3的要求是合理的.在下文中，用式(13)定義的CAC(E)表示對(duì)應(yīng)于一段事件集E的cac集合.

(13)

2.2　Chomicki方法缺陷

在下文中，用EXEC(A)={exec(a)|a∈A}、BLOCK(A)={block(a)|a∈A}分別表示行動(dòng)集A上的exec和block實(shí)例集.同時(shí)令U=OCC(E)∪EXEC(πP(E))∪BLOCK(πP(E)).

3　最大行動(dòng)接受集

對(duì)于AC(E)中的單個(gè)aci，只需要取消被它約束的一個(gè)行動(dòng)，不但能夠滿足該aci(即實(shí)現(xiàn)沖突消解)，而且還確保了行動(dòng)接受集的極大性.但為滿足AC(E)的一個(gè)子集或AC(E)本身，同時(shí)又要確保行動(dòng)接受集的極大性，卻是復(fù)雜的.

定義2對(duì)應(yīng)于一段事件集E的行動(dòng)全集始終是πP(E).設(shè)一個(gè)aci集合X?AC(E).如果一個(gè)行動(dòng)集X?πP(E)同時(shí)滿足：

1)πP(E)X滿足X中的任意aci；

2)任意X′?X，πP(E)X′至少不能滿足X中的一個(gè)aci.

則稱X是X的一個(gè)極小行動(dòng)取消集(minimal action-cancellation set, MACS)，記為ΔX.稱πP(E)ΔX是與ΔX對(duì)應(yīng)的 MAAS.顯然，一個(gè)ΔX同與之對(duì)應(yīng)的MAAS構(gòu)成互補(bǔ)關(guān)系.一個(gè)MAAS等價(jià)于文獻(xiàn)[3]中定義的繁瑣的“P的極大AC監(jiān)控行動(dòng)取消(maximal action-cancellation AC-monitor of P)”.

假設(shè)ΔAC(E)∩A<|A|-k+1成立.由以上證明，易得πP(E)ΔAC(E)不能滿足α，所以ΔAC(E)不是AC(E)的一個(gè)MACS.

命題1不但適合特殊組合沖突，同樣適合一般組合沖突.

在實(shí)際應(yīng)用中，往往要求被接受的行動(dòng)愈多愈好.但是，由于一個(gè)MAAS并不一定是對(duì)應(yīng)的AC(E)所有MAASes中基數(shù)最大的集合，所以依靠AC(E)的一個(gè)MAAS并不能確保被接受的行動(dòng)最多.

由命題1可知，此時(shí)任意ΔAC(E)至少包含A1(或A2)的2個(gè)元素.在AC(E)的所有MAASes中，一方面，由于ΔAC(E)={a1,a2}在AC(E)所有的MACSes中基數(shù)最小，所以對(duì)應(yīng)的MAAS(即{a3,a4,a5,a6})基數(shù)最大，從而確保了被接受的行動(dòng)最多；另一方面，由于ΔAC(E)={a3,a4,a5,a6}的基數(shù)最大，所以對(duì)應(yīng)的MAAS(即{a1,a2})擁有最小基數(shù)，從而被接受的行動(dòng)最少.

定義3設(shè)一個(gè)aci集合X?AC(E).在X的所有MACSes中，基數(shù)最小的集合被稱為X的一個(gè)SACS，記為ΞX.類似MAAS的定義，稱πP(E)ΞX是與一個(gè)ΞX對(duì)應(yīng)的LAAS.

顯然，aci集X的一個(gè)SACS必然是它的一個(gè)MACS，但反之并不成立.這同樣適合X的LAAS和MAAS.所以，SACS/LAAS是對(duì)MACS/MAAS的進(jìn)一步優(yōu)化.另外，X的SACS或LAAS并不是唯一的.

證明由命題1直接可得.

4　組合沖突消解

4.1　極大化

在利用WCR編程技術(shù)消解組合沖突之前，有必要剔出CAC(E)中的冗余元素.首先定義一個(gè)CAC(E)上的偏序關(guān)系≤.然后在此關(guān)系基礎(chǔ)上，利用一個(gè)簡(jiǎn)單的極大化過程剔出CAC(E)中的冗余元素.

可獲得如下關(guān)于偏序集〈CAC(E),≤〉的性質(zhì).

命題3設(shè)兩個(gè)cacsαi,αj∈CAC(E)、Ξαj是αj的一個(gè)SACS.如果αi≤αj，則αi至少存在的一個(gè)SACS(Ξαi)，滿足Ξαi?Ξαj.而且，如果αi=αj，則αi的一個(gè)SACS必然是αj的一個(gè)SACS，反之也成立.

根據(jù)命題2，可得到如下三個(gè)結(jié)論：①如果αi=αj，易得任意行動(dòng)集是αi的一個(gè)SACS當(dāng)且僅當(dāng)它是αj的一個(gè)SACS；②如果Ai?Aj且kj=ki，假設(shè)Ξαj∩Ai=|Ai|-ki，即Ξαj只包含|Ai|-ki個(gè)Ai的元素.然而這是不可能的，因?yàn)榇藭r(shí)Ξαj∩(AjAi)=|AjAi|+1成立，即Ξαj需要包含|AjAi|+1個(gè)AjAi的元素；③如果Ai=Aj且kj

基于偏序集〈CAC(E),≤〉，用于剔出CAC(E)中冗余元素的極大化過程為：

1)初始CACm(E)為?.

2)如果CAC(E)≠?，從〈CAC(E),≤〉中選擇一個(gè)極大元素α，將之添加到CACm(E).然后刪除〈CAC(E),≤〉中任何滿足α′≤α的元素α′.

3)循環(huán)執(zhí)行步驟2，直到CAC(E)=?.

下文用CACm(E)取代CAC(E).

4.2　沖突消解邏輯程序

易得A1是AC(E)的一個(gè)SACS.

(14)

(15)

(16)

(17)

由于πP(E)=?使得沖突消解沒有必要，所以，下文中均假設(shè)πP(E)≠?.

由以上定理證明也可知，式(14)可簡(jiǎn)化為論據(jù)(fact) “n-k+1≤{block(a1)，…，block(an)}≤n←”.需要說明的是，即使一個(gè)WCR程序擁有多個(gè)優(yōu)化模型，如多個(gè)相同最小基數(shù)模型，但是當(dāng)前的SMODELS只為用戶提供其中的一個(gè)優(yōu)化模型.

再根據(jù)定理2和定義3，得AM(E)是AC(E)的一個(gè)LAAS.

5　結(jié)語(yǔ)

析取邏輯編程技術(shù)使得Chomicki方法在消解組合沖突時(shí)并不可靠.而本文利用WCR編程技術(shù)不但完成沖突消解，特別是能夠完成一種特殊沖突的消解，即組合沖突的消解，同時(shí)能夠獲得沖突的優(yōu)化解.本文方法成功的根本原因是，WCR編程技術(shù)不僅提供了優(yōu)化機(jī)制，更重要的是，其程序的穩(wěn)定模型能夠包含一個(gè)規(guī)則頭中的多個(gè)原子謂詞實(shí)例.

參考文獻(xiàn):

[1]Lupu E,Sloman M.Conflicts in Policy-Based Distributed Systems Management[J]. IEEE Transaction on Software Engineering，Nov/Dec，1999，25(6)：852-869.

[2]Turner K, Blair L.Policies and Conflicts in Call Control[J]. The International Journal of Computer and Telecommunications Networking，Elsevier，2006，51(2)：496-514.

[3]Chomicki J,Lobo J, Naqvi S. Conflict Resolution Using Logic Programming[J].IEEE Transactions on Knowledge and Data Engineering，Jan/Feb，2003，15(1)：244-249.

[4]Gelfond M, Lifschitz V. The Stable Model Semantics for Logic Programming[M].The MIT Press: R. Kowalski, K. Bowen (eds.), In Proc the 5th International Conference on logic programming,1988：1070-1080.

[5]Gelfond M,Lifschitz V.Classical Negation in Logic Programs and Disjunctive Databases[J].New Generation Computing，1991，9(3/4)：365-386.

[6]Gelfond M, Leone N. Logic Programming and Knowledge Representation—The A-Prolog Perspective[J]. Artificial Intelligence，Elsevier，2002，138：3-38.

[7]Lobo J, Bhatia R, Naqvi S. A Policy Description Language[C]// In Proc the 16th National Conference on Artificial Intelligence (AAAI-99), July,1999：291-298.

[8]Son T C, Lobo J. Reasoning about Policies Using Logic Programs[C]//In Proc the AAAI Spring Symposium on Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning, March,2001：210-216.

[9]Przymusinski T. Stable Semantics for Disjunctive Programs[J]. New Generation Computing，1991，9(3/4)：401-424.

[10]Niemel? I, Simons P， Soininen T. Stable Model Semantics of Weight Constraint Rules[C]// In Proc. the 5th International Conference on Logic Programming and Nonmonotonic Reasoning, Texas，USA，Dec，1999：317-331.

[11]Simons P, Niemel? I, Soininen T. Extending and Implementing the Stable Model Semantics[J]. Artificial Intelligence，Elsevier，2002，138：181-234.

[12]Emden M, Kowalski R. The Semantics of Predicate Logic as a Programming Language[J]. Journal of ACM，1976，23(4)：733-742.

[13]Leone N, Pfeifer G, Faber W, et al. The DLV System for Knowledge Representation and Reasoning[J]. ACM Transactions on Computational Logic，2006，7(3)：499-562.

[14]Baral C. Knowledge Representation, Reasoning, and Declaring Problem Solving with Answer sets[M].Cambridge University Press，2003.

[15]Leone N, Rullo P, Scarcello F. Disjunctive Stable Models: Unfounded Sets, Fixpoint Semantics, and Computation[J]. Information and Computation，1997，135(2)：69-112.

[16]Lifschitz V, Turner H. Splitting a Logic Program[C] / / In Proc the 11th International Conference on Logic Programming, 1994：23-37.

[17]盧開澄,盧華明.組合數(shù)學(xué)[M].3版.北京：清華大學(xué)出版社，2002.

責(zé)任編輯：時(shí)凌

A Method of Policy Conflict Resolution

LI Xin

(School of Accounting,Chongqing University of Technology,Chongqing 400050,China)

Abstract：By using the nonmonotonic logic programming technology, Chomicki et al. proposed an approach to resolve policy conflict. Although the approach is efficient, reliable, and has good encapsulation, its application domain is limited. On the base of Chomicki’s approach, we firstly define combination conflict that is more general than common policy conflict. Then, we introduce an optimal solution for combination conflict resolution, i.e., the largest action-acceptance set, and show the important property of the smallest action-cancellation set as the complement of the solution. Lastly, the logic program for combination conflict resolution is constructed by using weight constraint rule programming technology with the stable model semantics. Because the logic program always has at least one stable mode, it is reliable to obtain an optimal solution according to a stable model of this program.

Key words：conflict；weight constraint rule；largest action-acceptance set；smallest action-cancellation set；stable model

作者簡(jiǎn)介：郭黎(1978- )，女，博士，副教授，主要從事視頻圖像處理與識(shí)別信息顯示的研究. 何恬(1988- )，女，碩士生，主要從事國(guó)土資源調(diào)查、評(píng)價(jià)與規(guī)劃開發(fā)的研究;*:宋鄂平(1971- )，男，高級(jí)實(shí)驗(yàn)師，博士，主要從事林業(yè)、旅游、地質(zhì)學(xué)的研究.

DOI:10.13501/j.cnki.42-1569/n.2015.06.028 10.13501/j.cnki.42-1569/n.2015.06.020

文章編號(hào)：1008-8423(2015)02-0230-05 1008-8423(2015)02-0193-04

通信作者

基金項(xiàng)目：教育部人文社會(huì)科學(xué)青年基金項(xiàng)目(12YJC630306). 國(guó)家自然科學(xué)基金項(xiàng)目(61263030,61463014)；湖北省自然科學(xué)基金資助項(xiàng)目(2014CFB612)；湖北民族學(xué)院博士啟動(dòng)基金(MY2014B018).

收稿日期：2015-03-31. 2014-12-01.

中圖分類號(hào)：TP181；TP182

文獻(xiàn)標(biāo)志碼：A