元數(shù)據(jù)存儲庫系統(tǒng)中違背良格式約束潛在操作的推理

趙曉非　高　陽　史穎歡　史忠植

1(天津工業(yè)大學計算機科學與軟件學院　天津　300387)2(計算機軟件新技術(shù)國家重點實驗室(南京大學)　南京　210023)3(中國科學院智能信息處理重點實驗室(中國科學院計算技術(shù)研究所)　北京　100190)(zhaoxiaofei1978@hotmail.com)

元數(shù)據(jù)存儲庫系統(tǒng)中違背良格式約束潛在操作的推理

趙曉非1,2,3高陽2史穎歡2史忠植3

1(天津工業(yè)大學計算機科學與軟件學院天津300387)2(計算機軟件新技術(shù)國家重點實驗室(南京大學)南京210023)3(中國科學院智能信息處理重點實驗室(中國科學院計算技術(shù)研究所)北京100190)(zhaoxiaofei1978@hotmail.com)

摘要存儲庫系統(tǒng)的元數(shù)據(jù)組織方式呈現(xiàn)出分層、多級并且動態(tài)變化的復雜結(jié)構(gòu)；存儲庫系統(tǒng)標準對確保良格式約束規(guī)定得并不充分，上述2個原因使得確?；谠獙ο笤O(shè)施(meta object facility, MOF)建立的元數(shù)據(jù)存儲庫系統(tǒng)的狀態(tài)不違背良格式約束成為一個令人棘手的問題.提出了一種能夠自動推斷可能違背良格式約束的潛在操作的方法.首先定義了一組比MOF的構(gòu)造活動更精確和靈活的MOF內(nèi)部活動并建立了二者之間的對應關(guān)系；接著研究了如何推斷可能違背約束條件的內(nèi)部活動；最后通過比對與這些內(nèi)部活動相對應的構(gòu)造活動是否在操作規(guī)范中出現(xiàn)，研究了如何推斷違背約束條件的潛在操作,該方法可以用于約束檢測領(lǐng)域.由于可以剔除許多無關(guān)的檢測，該方法可以有效地提高良格式約束檢測的效率.此外該方法對約束設(shè)計領(lǐng)域也有一定的參考價值.

關(guān)鍵詞存儲庫系統(tǒng)；良格式約束；元對象設(shè)施；約束檢測；構(gòu)造活動；內(nèi)部活動

如今，元對象設(shè)施(meta object facility, MOF)[1]已經(jīng)成為國際上普遍接受和采用的元數(shù)據(jù)存儲庫系統(tǒng)標準.作為MOF存儲庫系統(tǒng)的重要組成部分，基于對象約束語言(object constraint lang-uage, OCL)[2]定義的良格式約束規(guī)定了系統(tǒng)所有狀態(tài)都必須遵從的條件.存儲庫系統(tǒng)的內(nèi)容會由于操作的執(zhí)行而被改變，因此必須確保操作執(zhí)行后存儲庫系統(tǒng)的狀態(tài)不違背元層次中的良格式約束.

然而2個原因的存在使得這一任務(wù)變得相當困難:1)存儲庫系統(tǒng)中元數(shù)據(jù)的組織方式呈現(xiàn)出分層、多級并且動態(tài)變化的復雜結(jié)構(gòu).不同于數(shù)據(jù)庫系統(tǒng)，存儲庫系統(tǒng)引入M3層允許用戶對M2層進行定義.在運行時刻M2，M1和M0層都可以被動態(tài)修改;2)MOF標準對確保良格式約束規(guī)定得并不充分.MOF提供了4種機制用于保證存儲庫系統(tǒng)一致性，包括：1)MOF定義了一組模型約束；2)MOF為抽象映射定義了一組閉包規(guī)則和計算語義，JMI為Jave映射定義了計算語義；3)MOF為描述領(lǐng)域規(guī)則提供了constraint模型元素；4)MOF和JMI定義了一組存儲庫界面.然而上述措施都是針對語法正確性的確保，而不是良格式約束.

針對上述問題，本文提出了一種能夠自動推斷違背良格式約束的潛在操作的方法.存儲庫操作對存儲庫系統(tǒng)的影響通?？梢酝ㄟ^一組構(gòu)造活動來指定[3-4].如果已知某個操作所涉及的所有構(gòu)造活動均不會違背特定的良格式約束，則可以斷言該操作的執(zhí)行不會違背該約束.本文的方法正是基于這種思想，該方法的基本原理是為每個約束條件找到可能違背它的構(gòu)造活動的集合，然后與操作規(guī)范進行對比，若其中的一個或多個構(gòu)造活動與操作規(guī)范相關(guān)，則可斷定該操作的執(zhí)行可能會違背該約束條件.

我們的方法可以用于約束檢測領(lǐng)域，通過推斷出與給定操作無關(guān)的約束條件并將之從該操作執(zhí)行以后的約束檢測過程中剔除，該方法可以顯著提高這一過程的效率.此外，該方法也可用于約束設(shè)計領(lǐng)域.如果應用該方法后我們發(fā)現(xiàn)某個約束永遠不會被違背(即沒有操作能夠影響到它)，則可考慮刪除該約束.

1構(gòu)造活動及內(nèi)部活動

1.1存儲庫系統(tǒng)中的構(gòu)造活動

構(gòu)造活動是對實體類型(類)或關(guān)系類型(關(guān)聯(lián))進行原子的、不可再分的修改活動，如建立對象、改變對象類型、建立鏈接等.構(gòu)造活動的精確數(shù)量和定義取決于特定的存儲庫系統(tǒng)標準.在MOF標準中，構(gòu)造活動是行為規(guī)范中所有活動的子集.只有構(gòu)造活動能夠修改系統(tǒng)的內(nèi)容，因此只有它們的執(zhí)行才可能導致約束條件的違背.如果一個構(gòu)造活動的執(zhí)行可能導致某個約束條件的違背，則稱該構(gòu)造活動是該約束條件的潛在違背構(gòu)造活動，簡稱PEA(possibly violating establishment activity).

MOF存儲庫系統(tǒng)中的構(gòu)造活動有8種(詳細信息請參見文獻[1])，如表1所示:

Table 1　Establishment Activity in MOF

1.2內(nèi)部活動的提出

為了推斷OCL良格式約束的PEA集合，我們需要研究哪些構(gòu)造活動的執(zhí)行可能違背約束條件.下面我們將提出一組內(nèi)部活動并建立它們與MOF構(gòu)造活動的對應關(guān)系.在推理過程中實際參與推斷的是我們所提出的內(nèi)部活動.之所以選擇在內(nèi)部活動而不是構(gòu)造活動之上進行推理是基于2個原因：1)本文的方法借助良格式約束是OCL元模型的實例這一特性，通過建立發(fā)現(xiàn)圖實例并在其上進行推理從而實現(xiàn)PEA的推斷，因而針對可能影響OCL元模型實例的活動進行推斷是較方便的選擇，相反，構(gòu)造活動是面向MOF模型機制的，直接在其上進行推理(盡管理論上可實現(xiàn))會帶來諸多不便之處；2)目前國際上現(xiàn)存的元數(shù)據(jù)存儲庫標準有MOF，IRDS，PCTE等多種，每種標準都定義了自己框架內(nèi)的構(gòu)造活動.而我們則希望提出一種推斷PEA的通用方法，因為一旦建立了本文提出的內(nèi)部活動和其他存儲庫框架的構(gòu)造活動之間的對應關(guān)系，就可以調(diào)整本文的方法以適用于其他存儲庫框架.這將極大地提高我們所提出的方法的適用性.

下面對OCL元模型元素種類及特性進行分析.約束元模型元素包括實體類型和關(guān)系類型2類，其上分別有建立實例和刪除實例2種活動可能導致約束的違背.此外對實體類型的泛化和特化以及修改實例屬性及關(guān)聯(lián)端的活動均可能導致約束的違背，因此我們共總結(jié)出8種內(nèi)部活動.

表2列出了這些內(nèi)部活動及其與MOF構(gòu)造活動的對應關(guān)系.盡管內(nèi)部活動與MOF的構(gòu)造活動之間并不一一對應，但它們較MOF構(gòu)造活動更便于PEA的推斷并且可以通過表2的簡單映射轉(zhuǎn)換為構(gòu)造活動.例如，如果推斷出某個實例之上的內(nèi)部活動AssignObject可能違背約束條件，而該實例既不是關(guān)聯(lián)類也不是由其他實例調(diào)整所得，則需將其轉(zhuǎn)化為該實例之上的構(gòu)造活動CreateObject-Action，若該AssignObject是關(guān)聯(lián)端的變化所導致的，則還需加上該實例之上的構(gòu)造活動AddStruc-turalFeatureAction.其他內(nèi)部活動的轉(zhuǎn)換與之類似，此處不再贅述.

Table 2　Correspondence between Inner Activity and MOF Establishment Activity

2本文所使用的例子

本文所使用的例子如下，它包括元數(shù)據(jù)的模型結(jié)構(gòu)、位于M1層的4個OCL良格式約束以及修改存儲庫系統(tǒng)內(nèi)容的3個操作.為了簡明起見，我們忽略其他層中的約束.模型結(jié)構(gòu)如圖1所示.作為M2層元數(shù)據(jù)實例的M1層元數(shù)據(jù)描述了學校和教師的信息.教師分為全職教師和兼職教師.M1層中的4個約束條件如圖2所示，分別用于確保每個學校至少有1個60歲以上的教師(OldTeacher約束)、校長不能是兼職教師(NotHeadmasterParttimeteacher約束)、2個教師的名字不能相同(UniqueName約束)、兼職教師的周工作時間必須介于10 h和40 h之間(ValidWorkinghours約束).3個操作如圖3所示.在每個具體活動的后面我們附加了等價的MOF構(gòu)造活動.操作EmployParttimeteacher為給定的學校聘用1個新兼職教師.它建立類元Parttimeteacher的1個新對象實例，對其進行初始化賦值并將其關(guān)聯(lián)到學校.操作DismissTeacher解聘1個教師(全職或兼職)并刪除其與學校的關(guān)聯(lián).操作Delete-Association刪除1個關(guān)聯(lián)，同時刪除它的關(guān)聯(lián)端、關(guān)聯(lián)與關(guān)聯(lián)端之間的關(guān)系以及關(guān)聯(lián)端與類之間的關(guān)系.EmployParttimeteacher和DismissTeacher僅修改M0層中的內(nèi)容，而DeleteAssociation修改M1層中內(nèi)容的同時將改變傳播到M0層，即M0層中的內(nèi)容也將被修改.

因為高層次中內(nèi)容的改變必須傳播到它下面的所有層次，例如刪除1個類的同時必須刪除下面所有層次中該類的所有實例.

Fig. 1　Model structure of the metadata.圖1　元數(shù)據(jù)的模型結(jié)構(gòu)

Fig. 2Well-formedness constraints in M1.
圖2元數(shù)據(jù)M1層中的良格式約束

Fig. 3Operations that update the repository system.
圖3修改存儲庫系統(tǒng)內(nèi)容的操作

為了更好地理解1.2節(jié)中提出的內(nèi)部活動，這里為每個內(nèi)部活動給出1個例子.內(nèi)部活動AssignObject例如建立實體類型Teacher的1個實例，Teacher或Parttimeteacher之上的CreationObjectAction均可導致此活動；ModifyProperty例如1名教師年齡的修改；RomoveObject的例子是刪除1名教師；1名教師變?yōu)?名兼職教師是屬于內(nèi)部活動SubReclassify；內(nèi)部活動SuperReclassify正好與之相反；分配1名教師到1個學校是屬于內(nèi)部活動AssignLink；ModifyEnd的例子是校長的修改；內(nèi)部活動RemoveLink例如刪除1名教師與1個學校的工作關(guān)系.

3發(fā)現(xiàn)違背良格式約束的潛在操作

如引言所述，本方法的基本思想是通過推斷可能違背約束的潛在構(gòu)造活動PEA并檢查它們是否出現(xiàn)在操作規(guī)范中從而在約束的定義時刻推斷出違背它的潛在操作.之所以稱其為潛在違背構(gòu)造活動，是指它們可能會違背約束，但并不意味著這些活動的每次執(zhí)行都會違背約束(這依賴于活動執(zhí)行時刻的具體參數(shù)).為了推斷違背約束的潛在操作，我們的方法分5個步驟，分別闡述于3.1～3.5節(jié).

3.1簡化良格式約束

第1步是對定義良格式約束的OCL表達式進行等價化簡.首先使用定義在OCL標準庫[2]中的等價操作對出現(xiàn)在表達式中的操作數(shù)目進行約減，接著將表達式轉(zhuǎn)換為等價的合取范式.轉(zhuǎn)換的結(jié)果是每個約束被表示為析取項的合取.所得到的析取項的字面量包括forAll迭代子、算術(shù)比較、對象集合等價比較、布爾屬性、not操作符、oclIsTypeOf操作符以及oclIsKindOf操作符等.顯然要滿足約束條件，存儲庫系統(tǒng)必須滿足每個析取項.一個析取項被滿足需要至少它的字面量之一被滿足.

對第2節(jié)中的4個約束進行操作數(shù)目的約減之后，約束OldTeacher和UniqueName變?yōu)?其他約束保持不變)：

context School inv OldTeacher：

self.teacher->select(t|t.age>60)->size()>0

context Teacher inv UniqueName:

Teacher.allInstances()->forAll(t1,t2|nott1=t2implies nott1.name=t2.name)

進一步轉(zhuǎn)換為合取范式之后，約束UniqueName變?yōu)?其他約束保持不變)：

context Teacher inv UniqueName:

Teacher.allInstances()->forAll(t1,t2|t1=t2or nott1.name=t2.name)

3.2建立發(fā)現(xiàn)圖

第2步是根據(jù)良格式約束與OCL元模型[2]之間的內(nèi)容——實例關(guān)系建立發(fā)現(xiàn)圖.發(fā)現(xiàn)圖的每個節(jié)點作為OCL元模型中元類的實例，表示OCL表達式的一個原子子集.節(jié)點的第1個后繼是OCL表達式位于該節(jié)點之前的部分.若該節(jié)點表示2元操作(如“>”，“+”等)，則節(jié)點的第2個后繼是操作的參數(shù)；若節(jié)點表示loop表達式(如forAll，select等)，則節(jié)點的第2個后繼是迭代子的體.

Fig. 4　Discovery graph for constraint OldTeacher.圖4　約束OldTeacher對應的發(fā)現(xiàn)圖

圖4給出了根據(jù)約束OldTeacher(self.teacher->select(t|t.age>60)->size()>0)建立的發(fā)現(xiàn)圖.與操作“>”相應的元類OperationCallExp的實例是初始節(jié)點，其第1個后繼是位于“>”之前的表達式(self.teacher->select(t|t.age>60)->size())而下1個后繼是操作的參數(shù)(整型常量0).初始結(jié)點的第1個后繼節(jié)點的第1個后繼節(jié)點是操作size，它只有1個孩子select.節(jié)點select的第1個后繼節(jié)點是關(guān)聯(lián)端teacher而第2個后繼節(jié)點是位于屬性age和整型常量60之間的操作“>”.

3.3標記發(fā)現(xiàn)圖

為了推斷給定約束的PEA集合，僅單獨考慮OCL表達式的每個部分是不夠的.例如為了推斷約束OldTeacher是否可能被分配教師到學?；蚪獬虒W關(guān)系2種活動所違背，不能只考慮子表達式self.teacher->select(t|t.age>60)->size().實際上這2種活動都可能改變該子表達式的值，然而由于size操作之后是“>”操作，因此只有解除教學關(guān)系才可能導致約束的違背，相反，如果size之后是“<=”操作，則只有分配教室到學校才可能導致約束的違背.上述分析表明只有綜合考慮每個OCL原子子集的上下文信息才能正確推斷出給定約束的PEA集合，因此下一步的工作是利用發(fā)現(xiàn)圖中每個節(jié)點的上下文信息對其進行標記.

為每個節(jié)點所作的標記指示出該節(jié)點與它的后繼節(jié)點之間相互影響的信息.在全面分析OCL各種結(jié)構(gòu)的基礎(chǔ)上我們歸納出4種不同類型的標記信息：1)“+”表示表達式值的增加或項目數(shù)量的增加可能導致約束的違背；2)“-”表示表達式值的減少或項目數(shù)量的減少可能導致約束的違背；3)“m”表示表達式值的改變或項目數(shù)量的改變可能導致約束的違背；4)“nr”表示該節(jié)點與其后繼節(jié)點并無相互影響.

下面對每種標記進行舉例說明.對于“+”和“-”，考慮“>”操作，要違背約束A>B有2種情況：A值的減少或B值的增加，因此節(jié)點“>”的第1個后繼節(jié)點之上應該標記為“-”，而第2個后繼節(jié)點之上應該標記為“+”.對于標記“m”，考慮select操作，不僅向待選集合增加對象或刪除對象可能影響select的結(jié)果，甚至等數(shù)量替換待選集合的某些對象也可能影響select的結(jié)果，因此節(jié)點select的后繼節(jié)點之上應該標記為“m”.對于標記“nr”，考慮and操作，由于違背AandB的活動與單獨違背A和違背B的活動相同，也就是說節(jié)點and與它的后繼節(jié)點之間不存在相互影響，因此節(jié)點and的后繼節(jié)點之上均應標記為“nr”.

Fig. 5　Marking the OldTeacher discovery graph.圖5　標記約束OldTeacher對應的發(fā)現(xiàn)圖

由于標記發(fā)現(xiàn)圖的過程需要首先考慮當前節(jié)點之上的標記信息以及節(jié)點的類型從而確定其后繼節(jié)點之上的標記信息，因此標記的過程需要對發(fā)現(xiàn)圖進行廣度優(yōu)先遍歷.表3對各種節(jié)點類型的標記方法進行了匯總.表3的單元格中如果某個節(jié)點上的標記符號超過1個，則應分別應用每種標記以確定其后繼節(jié)點上的標記.單元格的內(nèi)容“×”表示不存在這種組合情況的約束條件.

對約束OldTeacher對應的發(fā)現(xiàn)圖進行標記的結(jié)果如圖5所示.為了簡明起見，我們略去了圖4中與標記無關(guān)的內(nèi)容.另外為每個節(jié)點添加了標記該節(jié)點所用到的表3單元格的信息，其中(X，Y)表示第X行、第Y列的單元格.

標記的過程首先從初始節(jié)點開始.由于“>”無前驅(qū)節(jié)點，因此其上無須標記.根據(jù)單元格(2，1)，初始節(jié)點的第1個后繼應標記為“-”而第2個后繼應標記為“+”，因此節(jié)點size之上為“-”.再根據(jù)單元格(11，3)，我們將節(jié)點size的后繼(節(jié)點select)標記為“-”.按照單元格(10，3)，節(jié)點select的第1個后繼節(jié)點之上的標記是“-m”而第2個后繼節(jié)點之上的標記是“nr”.再參考單元格(9，3)和(9，4)，節(jié)點teacher的后繼節(jié)點self應標記為“-m”.其他部分的標注以此類推，限于篇幅，此處不再贅述.

Table 3　Marking Information for Discovery Graph

3.4獲取內(nèi)部活動

發(fā)現(xiàn)圖標記好以后，下一步就可以據(jù)此推斷出給定約束的潛在違背內(nèi)部活動PIA(possibly violating inner activity).由于標記圖已明確標示出OCL原子子集表達式的類型以及該表達式如何變化能夠違背整個約束，因此推斷PIA的過程就是自下而上逐級推斷并匯總的過程，也就是對圖進行廣度優(yōu)先遍歷的逆過程.

表4匯總了不同節(jié)點類型和標記信息的組合所對應的PIA集合.c1+c2表示該節(jié)點的PIA集合是其后繼節(jié)點的PIA集合的并集.c1適用于該節(jié)點只有1個后繼節(jié)點的情形.空單元格意味著該節(jié)點并不影響PIA的推斷匯總.需要特別說明的是c1+X和opp(X).c1+X表示該節(jié)點向PIA集合中添加活動X.舉例來說，如果關(guān)聯(lián)端被標記為“+”，則其從屬關(guān)聯(lián)的鏈接實例的建立可能導致約束的違背，因此該節(jié)點應向PIA集合中添加AssignLink活動，即c1+AssignLink.opp(X)表示該節(jié)點的PIA是其后繼節(jié)點返回的PIA的相反活動，例如not操作.內(nèi)部活動的相反活動分別如下：opp(AssignObject)=RomoveObject，opp(ModifyProperty)=ModifyProperty，opp(RomoveObject)=AssignObject，opp(AssignLink)=RemoveLink，opp(RemoveLink)=AssignLink，opp(ModifyEnd)=ModifyEnd.

Table 4　Set of PIA for Different Nodes and Marking Information

Fig. 6　Deducing the PIA for OldTeacher.圖6　推斷約束OldTeacher的潛在違背內(nèi)部活動PIA

將表4應用于約束OldTeacher，得到的結(jié)果如圖6所示.首先處理節(jié)點self.由于節(jié)點self之上的標記是“-”和“m”，按照表4的單元格(17，3)，(17，4)可知該節(jié)點不添加任何PIA.然后參考單元格(9，3)，(9，4)處理關(guān)聯(lián)端teacher，向PIA的集合中添加活動AssignObject(School)，RemoveLink(TeachesIn)，ModifyEnd(TeachesIn-Teacher).接著處理節(jié)點select的第2個后繼(t.age>60)，它添加了活動ModifyProperty(age).在此之后處理節(jié)點select，參考單元格(10，3)，節(jié)點select的PIA集合是它的后繼節(jié)點的PIA集合的并集.隨后處理節(jié)點size、整型常量節(jié)點0并以初始節(jié)點“>”結(jié)束，它們均不添加任何活動.最終由初始節(jié)點“>”返回的PIA集合即是整個約束表達式的PIA的集合.通過這一步驟，我們可知可能違背約束OldTeacher的內(nèi)部活動有ModifyProperty(age)，ModifyEnd(TeachesIn-Teacher)，RemoveLink(TeachesIn)，AssignObject(School).

3.5發(fā)現(xiàn)違背約束的潛在操作

如引言所述，存儲庫系統(tǒng)操作可以表示為構(gòu)造活動的集合.如果給定約束的1個或多個PEA在存儲庫系統(tǒng)操作規(guī)范中出現(xiàn)，我們就可以斷定該操作的執(zhí)行有可能導致該約束被違背，因此按照上述步驟推斷出每個約束條件的PIA集合以后，需要將其轉(zhuǎn)換為對應的PEA的集合，并檢查它們是否在操作規(guī)范中出現(xiàn).轉(zhuǎn)換過程按照1.2節(jié)中所述的對應規(guī)則進行.以O(shè)ldTeacher為例，ModifyEnd(TeachesIn-Teacher)直接轉(zhuǎn)化為關(guān)聯(lián)端teacher之上的Add-StructuralFeatureAction，ModifyProperty(age)直接轉(zhuǎn)化為屬性age之上的AddStructuralFeatureAction，RemoveLink(TeachesIn)轉(zhuǎn)化為關(guān)聯(lián)TeachesIn之上的DestroyLinkAction，對于AssighObject(School)，由于School既不是關(guān)聯(lián)類也不是由其他實例調(diào)整所得，而且AssignObject不是由關(guān)聯(lián)端的變化所導致，因此只需將其轉(zhuǎn)化為School之上的Create-ObjectAction.

應用于第2節(jié)中的整個例子，我們得到如下結(jié)果.

1) 每個約束的PIA集合

① OldTeacher—ModifyProperty(age)，ModifyEnd(TeachesIn-Teacher)，RemoveLink(TeachesIn)，AssignObject(School)；

② NotHeadmasterParttimeteacher—SubReclassify(Parttimeteacher)，AssignLink(Manages)，ModifyEnd(Manages-Headmaster)；

③ UniqueName—AssignObject(Teacher)，ModifyProperty(Name-Teacher)；

④ ValidWorkinghours—AssignObject(Parttime-teacher)，ModifyProperty(workinghours).

2) 轉(zhuǎn)換為MOF標準的構(gòu)造活動所得的PEA集合

① OldTeacher—屬性age之上的AddStruc-turalFeatureAction，關(guān)聯(lián)端teacher之上的Add-StructuralFeatureAction，關(guān)聯(lián)TeachesIn之上的DestroyLinkAction，School之上的CreateObject-Action；

② NotHeadmasterParttimeteacher—將全職教師所屬類元修改為Parttimeteacher的Reclassify-ObjectAction，Manages之上的CreateLinkAction，關(guān)聯(lián)端headmaster之上的AddStructuralFeature-Action；

③ UniqueName—Teacher之上的CreateObject-Action，Parttimeteacher之上的CreateObjectAction，屬性name之上的AddStructuralFeatureAction；

④ ValidWorkinghours—Parttimeteacher之上的CreateObjectAction，屬性workinghours之上的AddStructuralFeatureAction.

3) 最后根據(jù)上述信息可得出每個操作可能違背的約束

① EmployParttimeteacher可能違背Valid-Workinghours和UniqueName，其他2個約束則不會違背；

② DismissTeacher只可能違背OldTeacher；

③ DeleteAssociation只可能違背OldTeacher.

利用上述推斷出的知識，在每個操作執(zhí)行完以后就無需檢測所有4個約束條件了，執(zhí)行Employ-Parttimeteacher以后只需檢測2個約束而執(zhí)行DismissTeacher和DeleteAssociation以后只需檢測1個約束.可以看到我們的方法能夠大大提高良格式約束檢測的效率.

4相關(guān)工作

Petrov等人[5]論述了基于MOF的元數(shù)據(jù)存儲庫系統(tǒng)中各種一致性的概念并提出了策略和算法用于增強操作執(zhí)行以后的系統(tǒng)狀態(tài)和良格式約束之間的一致性.然而在此過程中他們對所有約束條件進行檢測，從而使得檢測過程效率不高.類似的局限性也出現(xiàn)于Paria等人[6]的研究工作中.相比之下，由于在檢測過程中只需考慮實際可能被違背的約束，不相關(guān)的約束將被略去，我們的方法可以顯著提高該過程的效率.Takeshi等人[7]在解決元數(shù)據(jù)交換問題時也將元數(shù)據(jù)組織到不同的層次中.與本文針對的MOF框架不同的是，他們的元數(shù)據(jù)層次不是按照元數(shù)據(jù)的語義級別而是按照不同的元數(shù)據(jù)的內(nèi)容及相關(guān)程度進行組織的，各層次之間并無語義關(guān)聯(lián).操作對存儲庫內(nèi)容的修改不會影響到下面的層次使得約束的確保相對簡單,但該框架難以適用于動態(tài)變化的復雜元數(shù)據(jù)結(jié)構(gòu).文獻[8]所提出的元數(shù)據(jù)框架也具有類似問題.

據(jù)我們所知，在基于MOF的元數(shù)據(jù)存儲庫系統(tǒng)中推斷出給定約束的確切PEA集合的問題在國際上還未有相關(guān)研究.類似的研究存在于演繹數(shù)據(jù)庫和關(guān)系數(shù)據(jù)庫領(lǐng)域，所采用的解決方法主要是將OCL約束轉(zhuǎn)換為邏輯表達式或SQL表達式[9-14]，而后在此基礎(chǔ)上設(shè)計算法用以推斷給定約束的確切PEA集合.不幸的是，由于OCL約束包括了諸如否定、遞歸、包語義、聚合操作等很多復雜結(jié)構(gòu)，所提出的算法的處理能力很難涵蓋OCL約束的所有機制，如文獻[15].盡管有的算法對此進行了改進以支持OCL約束的所有機制，但處理邏輯的高復雜性又導致了算法的效率不高(關(guān)于它們的局限性參見文獻[16]).基于上述原因，我們認為不進行轉(zhuǎn)換、而在定義良格式約束的OCL表達式上直接進行推導是解決該問題的最佳途徑.

5結(jié)論及未來工作

確保MOF存儲庫系統(tǒng)的狀態(tài)不違背良格式約束是一個令人棘手的問題.本文提出的方法可以推斷操作的執(zhí)行是否可能違背良格式約束.由于可以剔除許多無關(guān)的檢測，因此該方法可以顯著提高約束檢測的效率，另外該方法對約束設(shè)計領(lǐng)域也有一定的參考價值.

有效的約束檢測至少要解決2方面的問題：1)本文中闡述的問題；2)當我們知道操作的執(zhí)行可能違背某個約束條件時，如何設(shè)計高效的算法去檢測它，而這正是我們下一步要進行的工作.

參考文獻

[1]Object Management Group. Meta Object Facility Core Specification, Version 2.4.2 [S]. Needham, Massachusetts: Object Management Group, 2014

[2]Object Management Group. Object Constraint Language Specification, Version 2.4[S]. Needham, Massachusetts: Object Management Group, 2014

[3]Olive A. Time and change in conceptual modeling of information systems[G]Information Systems Engineering: State of the Art and Research Themes. Berlin: Springer, 2000: 289-304

[4]Wieringa R. A survey of structured and object-oriented software specification methods and techniques[J]. ACM Computing Surveys, 2008, 30(4): 459-527

[5]Petrov I, Jablonski S, Holze M. On the notion of consistency in metadata repository systems[G]LNCS 3520: Proc of the 16th Int Conf on Advanced Information Systems Engineering. Berlin: Springer, 2004: 90-104

[6]Paria M, Kamada A, Luciano L, et al. Metadata repository support for legacy knowledge discovery in public administrations[C]Proc of the 5th IFIP Int Working Conf on Knowledge Management in Electronic Government. Piscataway, NJ: IEEE, 2010: 157-165

[7]Takeshi A, Mitsuo E, Masanori A, et al. Metabolonote: A wiki-based database for managing hierarchical metadata of metabolome analyses[J]. Frontiers in Bioinformatics and Computational Biology, 2015, 15(38): 1-12

[8]Wang F, Vergara-Niedermayr C, Liu P. Metadata based management and sharing of distributed biomedical data[J]. International Journal of Metadata, Semantics and Ontologies, 2014, 9(1): 42-57

[9]Duboisset M, Pinet F, Kang M A, et al. Integrating the calculus-based method into OCL: Study of expressiveness and code generation[C]Proc of the 18th Int Workshop on Database and Expert Systems Applications. Piscataway, NJ: IEEE, 2007: 502-506

[10]Yuan Chun, Chen Yiyun. Weakest and incremental preconditions for constraint checking[J]. Journal of Computer Research and Development, 2003, 40(7): 1088-1094 (in Chinese)(袁春, 陳意云. 約束檢查的最弱及增量前條件方法. 計算機研究與發(fā)展, 2003, 40(7): 1088-1094)

[11]Pinet F, Duboisset M, Demuth B, et al. Constraints modeling in agricultural databases[G]Advances in Modeling Agricultural Systems. Berlin: Springer, 2009: 55-65

[12]Donald C, Narayanaswamy K. Using first-order logic to query heterogeneous internet data sources[G]Procedia Computer Science 62: Proc of the 2015 Int Conf on Soft Computing and Software Engineering. New York: Academic Press, 2015: 170-177

[13]Demuth B, Hussmann H, Loecher S. OCL as a specification language for business rules in database applications[G]LNCS 2185: Proc of the 4th Conf on UML. Berlin: Springer, 2006: 104-117

[14]Chen Lianggang, Xu Guihong, Wang Yujun, et al. ISQL: An interval constraint database query language[J]. Journal of Computer Research and Development, 2000, 37(6): 677-683 (in Chinese)(陳良剛, 徐貴紅, 王宇君, 等. 區(qū)間約束數(shù)據(jù)庫查詢語言: ISQL. 計算機研究與發(fā)展, 2000, 37(6): 677-683)

[15]Behrend A, Manthey R. A transformation-based approach to view updating in stratifiable deductive databases[G]LNCS 4932: Proc of the 5th Int Conf on Foundations of Information and Knowledge Systems. Berlin: Springer, 2008: 253-271

[16]Siva S, Chu J, Parekh O, et al. Constraint processing in relational database systems: From theory to implementation[C]Proc of the 25th ACM Symp on Applied Computing. New York: ACM, 2010: 2066-2070

Zhao Xiaofei, born in 1978. PhD. His main research interests include semantic Web, data integration, description logics and artificial intelligence.

Gao Yang, born in 1972. PhD, professor and PhD supervisor. His main research interests include artificial intelligence and machine learning (gaoy@nju.edu.cn).

Shi Yinghuan, born in 1987. PhD. His main research interests include artificial intelligence and machine learning (syh@nju.edu.cn).

Shi Zhongzhi, born in 1941. Professor and PhD supervisor. Senior member of China Computer Federation. His main research interests include artificial intelligence, machine learning and data mining (shizz@ics.ict.ac.cn).

Reasoning on Constraints for Incoherent Operations in Metadata Repository Systems

Zhao Xiaofei1,2,3, Gao Yang2, Shi Yinghuan2, and Shi Zhongzhi3

1(SchoolofComputerScienceandSoftwareEngineering,TianjinPolytechnicUniversity,Tianjin300387)2(StateKeyLaboratoryforNovelSoftwareTechnology(NanjingUniversity),Nanjing210023)3(KeyLaboratoryofIntelligentInformationProcessing,ChineseAcademyofSciences(InstituteofComputingTechnology,ChineseAcademyofSciences),Beijing100190)

AbstractThe architecture of the repository system metadata is hierarchical, multi-layer, dynamically changed and complicated; the prevailing repository system specifications provide insufficiently support for validating well-formedness constraints, so how to check well-formedness constraints for MOF (meta object facility) metadata repository systems becomes a difficult problem. This paper presents an approach which can reasoning on the well-formedness constraints in the different layers, thus the operations that may violate the constraints can be determined automatically. Firstly, a group of inner activities which are more accurate and adaptable than establishment activities provided by MOF are proposed. We define the correspondence between inner activities and establishment activities. Then we research how to reasoning on the constraints directly so that the incoherent inner activities can be detected. At last, we research how to deduce potentially incoherent operations by determining the establishment activities that potentially violate the constraints and testing whether these activities are included in the operations. Our approach can improve the efficiency of well-formedness constraint checking because the precise set of constraints that will be violated by operations can be reduced in the actual checking process. In addition, our method also helps to the constraint design process since we can discard the constraint if we find it can never be violated by any operations.

Key wordsrepository system; well-formedness constraint; meta object facility (MOF); constraint checking; establishment activity; inner activity

收稿日期：2014-12-31；修回日期：2015-08-20

基金項目：國家自然科學基金項目(61035003,61072085,51378350)；國家“九七三”重點基礎(chǔ)研究發(fā)展計劃基金項目(2013CB329502)；計算機軟件新技術(shù)國家重點實驗室(南京大學)開放課題項目(KFKT2014B16)；天津市科技特派員項目(15JCTPJC58100)

中圖法分類號TP311.13

This work was supported by the National Natural Science Foundation of China (61035003,61072085,51378350), the National Basic Research Program of China (973 Program) (2013CB329502), the Foundation of State Key Laboratory for Novel Software Technology (Nanjing University) (KFKT2014B16), and the Science and Technology Commissioner Project of Tianjin (15JCTPJC58100).