基于元數(shù)據(jù)邏輯無(wú)關(guān)片斷的結(jié)構(gòu)完整性檢測(cè)方法

趙曉非 史忠植 劉建偉

1(天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 天津 300387) 2(江蘇省計(jì)算機(jī)信息處理技術(shù)重點(diǎn)實(shí)驗(yàn)室(蘇州大學(xué)) 江蘇蘇州 215006) 3(中國(guó)科學(xué)院計(jì)算技術(shù)研究所智能信息處理重點(diǎn)實(shí)驗(yàn)室 北京 100190)zhaoxiaofei1978@hotmail.com)

作為對(duì)象管理組織(object management group, OMG)提出的主要標(biāo)準(zhǔn)之一，元對(duì)象設(shè)施(meta object facility, MOF)[1]已經(jīng)成為國(guó)際主流的元數(shù)據(jù)存儲(chǔ)庫(kù)標(biāo)準(zhǔn).MOF存儲(chǔ)庫(kù)系統(tǒng)中元數(shù)據(jù)的組織方式，即元數(shù)據(jù)的結(jié)構(gòu)呈現(xiàn)出一種分層的、多級(jí)的并且動(dòng)態(tài)變化的復(fù)雜結(jié)構(gòu)，因此保持該種系統(tǒng)的一致性是一項(xiàng)重要任務(wù).MOF存儲(chǔ)庫(kù)系統(tǒng)中的一致性包括：1)操作一致性.涉及存儲(chǔ)庫(kù)應(yīng)用間的交互，與存儲(chǔ)庫(kù)事務(wù)的概念密切相關(guān)，它又分為協(xié)作原子性和并發(fā)多用戶(hù)訪(fǎng)問(wèn).2)元數(shù)據(jù)完整性.包括結(jié)構(gòu)完整性和良格式.良格式確保單一層次中元素的語(yǔ)法正確性，而結(jié)構(gòu)完整性確保1個(gè)層次中的元素符合與該層相鄰的、更高的元層次中的類(lèi)型定義[1].

結(jié)構(gòu)完整性是MOF存儲(chǔ)庫(kù)系統(tǒng)一致性的重要組成部分.如果結(jié)構(gòu)完整性得不到保證，存儲(chǔ)庫(kù)應(yīng)用就可能修改或建立Mn層中的元數(shù)據(jù)元素而與Mn+1層中它們的元類(lèi)相沖突.例如，1個(gè)操作可能會(huì)讀取某個(gè)元素的屬性，而該元素的元類(lèi)并不存在，則該操作是無(wú)效的.1個(gè)數(shù)據(jù)庫(kù)系統(tǒng)包含M0層到M2層.而為了提供可自定義、可擴(kuò)展的系統(tǒng)框架，MOF標(biāo)準(zhǔn)引入了允許用戶(hù)對(duì)M2層進(jìn)行定義的M3層，在運(yùn)行時(shí)刻M0，M1，M2層均可以被動(dòng)態(tài)修改，因而就可能導(dǎo)致相鄰層次之間的沖突問(wèn)題，即結(jié)構(gòu)完整性問(wèn)題.其他系統(tǒng)并不面臨這類(lèi)問(wèn)題，因?yàn)樗鼈兗俣ㄏ到y(tǒng)框架在運(yùn)行時(shí)刻是靜止的.

為了自動(dòng)地執(zhí)行結(jié)構(gòu)完整性檢測(cè)，不同的方法被相繼提出，其中影響比較大的有3種:1)Muzaffar等人[2-3]為MOF存儲(chǔ)庫(kù)系統(tǒng)的形式化、查詢(xún)和結(jié)構(gòu)完整性檢測(cè)提出了一種統(tǒng)一的框架OMLM.該框架采用F邏輯作為形式化機(jī)制.在文獻(xiàn)[2]中他們利用F邏輯的開(kāi)源實(shí)現(xiàn)Flora-2對(duì)各層次元數(shù)據(jù)進(jìn)行描述并利用推理機(jī)MULLER執(zhí)行結(jié)構(gòu)完整性檢測(cè).他們?cè)谖墨I(xiàn)[3]進(jìn)一步提出了Realization維度的概念并據(jù)此建立了MOF框架與Flora-2之間的映射，隨后采用模型轉(zhuǎn)換技術(shù)(MTT)開(kāi)發(fā)了到Flora-2的轉(zhuǎn)換工具，從而實(shí)現(xiàn)了形式化描述的自動(dòng)生成.利用F邏輯形式化MOF框架并進(jìn)行推理檢測(cè)的還有Bernd等人[4]的工作.2)Liliana等人[5]采用了基于代數(shù)的形式化機(jī)制，他們首先針對(duì)MOF的層次結(jié)構(gòu)提出了一種基于代數(shù)演算的形式化元建模語(yǔ)言NEREUS并為之開(kāi)發(fā)了推理接口.NEREUS利用Instantiation-算子來(lái)建模相鄰層次之間的類(lèi)型-實(shí)例關(guān)系.NEREUS不僅可以實(shí)現(xiàn)結(jié)構(gòu)完整性檢測(cè)，也可以實(shí)現(xiàn)良格式約束的檢測(cè).3)Esther等人[6-7]提出了一種對(duì)MOF框架的相鄰層次進(jìn)行壓扁(flattening)處理以檢測(cè)結(jié)構(gòu)完整性的方法并實(shí)現(xiàn)了原型工具metaDepth.他們提取出元層次中與結(jié)構(gòu)完整性約束有關(guān)的特性(如元素之間的引用關(guān)系、屬性的類(lèi)型以及多重性等)，然后與相鄰的下層元數(shù)據(jù)進(jìn)行合并從而得到單層的元數(shù)據(jù)知識(shí)庫(kù)，而后采用良設(shè)計(jì)的算法實(shí)現(xiàn)檢測(cè).

1 存儲(chǔ)庫(kù)元數(shù)據(jù)的形式化

1.1 Mn+1層的形式化

1) 元類(lèi)及元屬性

2) 元-關(guān)聯(lián)類(lèi)

元層次中的元-關(guān)聯(lián)類(lèi)如圖1所示.每個(gè)元-關(guān)聯(lián)類(lèi)都包含2個(gè)存在多重性約束的關(guān)聯(lián)端.與元屬性不同的是，在MOF框架中元-關(guān)聯(lián)類(lèi)的名字是唯一的.

Fig. 1 Meta-association class in level Mn+1圖1 Mn+1層中的元-關(guān)聯(lián)類(lèi)

由于每個(gè)關(guān)聯(lián)端表示相應(yīng)端的元類(lèi)與元-關(guān)聯(lián)類(lèi)之間的2元關(guān)系(即該元類(lèi)以何種身份參與元-關(guān)聯(lián)類(lèi))，我們將元類(lèi)C和C′之間的元-關(guān)聯(lián)類(lèi)A(關(guān)聯(lián)端分別為r1和r2)形式化為1個(gè)概念A(yù)和2個(gè)角色r1和r2，其中r1和r2分別對(duì)應(yīng)于關(guān)聯(lián)端r1和r2，r1以C和A作為第1和第2個(gè)要素，而r2以C′和A作為第1和第2個(gè)要素，因此r1端和r2端的取值限定被形式化為

C?r1.A；
C′?r2.A；
A

C(≥i1r1.A)(≤j1r1.A)；
C′(≥i2r2.A)(≤j2r2.A).

3) 元關(guān)聯(lián)

Fig. 2 Meta-association in level Mn+1圖2 Mn+1層中的元關(guān)聯(lián)

元關(guān)聯(lián)如圖2所示，用于表明2個(gè)元類(lèi)的實(shí)例之間的2元關(guān)系.例如元關(guān)聯(lián)R描述了元類(lèi)StructuralFeature和UniqueKey之間2元關(guān)系.R的多重性描述了每個(gè)UniqueKey的實(shí)例至少和1個(gè)StructuralFeature的實(shí)例相關(guān)聯(lián).

由于元關(guān)聯(lián)本質(zhì)上是一種2元關(guān)系，因此我們將元類(lèi)C和C′之間的元關(guān)聯(lián)R形式化為1個(gè)角色R并用下述斷言描述R的取值限定：

C?R.C′；
C′?R-.C.

C的多重性i1..j1和C′的多重性i2..j2則分別被形式化為

C(≥i1R.C′)(≤j1R.C′)；
C′(≥i2R.C)(≤j2R.C).

4) 泛化

MOF框架中的泛化關(guān)系表明子類(lèi)的每個(gè)實(shí)例也是父類(lèi)的實(shí)例.因此子類(lèi)的實(shí)例繼承了父類(lèi)的屬性，此外它們還可以定義自己的屬性.

1.2 Mn層的形式化

1) 若Mn層元素c是其元層次中元類(lèi)C的實(shí)例，則將其形式化為C(c)；

2) 若Mn層元素c關(guān)聯(lián)了c′，相應(yīng)的元類(lèi)C(或其祖先)通過(guò)元關(guān)聯(lián)R與元類(lèi)C′(或其祖先)相聯(lián)系，元關(guān)聯(lián)R被形式化為T(mén)box中的角色R，則將c和c′之間的關(guān)系形式化為R(c，c′)；

3) 若Mn層元素c關(guān)聯(lián)了c′，相應(yīng)的元類(lèi)C(或其祖先)通過(guò)元-關(guān)聯(lián)類(lèi)A與元類(lèi)C′(或其祖先)相聯(lián)系，而元-關(guān)聯(lián)類(lèi)被形式化為概念A(yù)和角色r1，r2，則將c和c′之間的關(guān)系形式化為3個(gè)斷言A(a)，r1(c，a)，r2(c′，a).

2 元數(shù)據(jù)邏輯無(wú)關(guān)片斷的抽取

2.1 基本思路

我們的目標(biāo)是劃分出精確的元數(shù)據(jù)片斷，該片斷僅包含對(duì)給定簽名必不可少的斷言，從而使得產(chǎn)生的片斷在保持信息完備性的同時(shí)具有最小的規(guī)模.簡(jiǎn)單地說(shuō)，要使得斷言對(duì)于給定簽名S必不可少，它們必須能夠影響S中任意元數(shù)據(jù)元素的邏輯結(jié)論，為了區(qū)分這種斷言，我們給出定義4：

證畢.

通過(guò)定理1可知，由于簽名S中每個(gè)元素的邏輯無(wú)關(guān)片斷的并集即為S的邏輯無(wú)關(guān)片斷，因此我們僅需為S中單個(gè)元數(shù)據(jù)元素的邏輯無(wú)關(guān)片斷的計(jì)算提出算法即可.

由第2種斷言我們得到:

其中C1是b的類(lèi)屬概念.

其中C3是將元素a作為要素的所有其他角色斷言的限定性概念的合取.

2.4 邏輯無(wú)關(guān)片斷的抽取算法

證畢.

3 基于邏輯無(wú)關(guān)片斷的結(jié)構(gòu)完整性檢測(cè)

根據(jù)結(jié)構(gòu)完整性約束，如果某個(gè)操作修改了元層次中某元屬性的類(lèi)型，若新類(lèi)型不是原有類(lèi)型的超類(lèi)且原有類(lèi)型是元層次中已存在的元類(lèi)，而下級(jí)層次中該元屬性的相應(yīng)實(shí)例沒(méi)有被修改則會(huì)產(chǎn)生結(jié)構(gòu)完整性沖突之一——屬性類(lèi)型沖突.該類(lèi)沖突可以通過(guò)定義函數(shù)1來(lái)檢測(cè)(假定元類(lèi)Property的元屬性referencedType的類(lèi)型由StructuredType變?yōu)镾impleType，而非DataType等超類(lèi)型，如圖3所示)：

Fig. 3 An example for property type inconsistency圖3 屬性類(lèi)型沖突示例

if (count1>count2)

print(“Property type inconsistency: some fillers do not belong to the type #.”,referencedType).)

下例是多重性沖突的檢測(cè).根據(jù)結(jié)構(gòu)完整性約束，如果某個(gè)操作修改了元層次中的關(guān)聯(lián)端的多重性，而下級(jí)層次中的元素沒(méi)有被相應(yīng)修改,則可能會(huì)導(dǎo)致相應(yīng)實(shí)例數(shù)目與修改后的多重性發(fā)生沖突.可以通過(guò)定義函數(shù)2來(lái)檢測(cè)該類(lèi)沖突(假定Association和AssociationEnd間的元關(guān)聯(lián)在AssociationEnd端的多重性由1改為2)：

count1=|ans(associationEnd)←body

association,associationEnd))|;

count2=get-min-cardinality((get-conceptAssociation)(get-relationAssociation-AssociationEnd));

if (count1

print(“AssociationEnd multiplicity inconsistency:#associates#elements,at least # is needed.”,association,count1,count2).)

4 方法有效性評(píng)測(cè)

為了評(píng)測(cè)本文方法的有效性，我們進(jìn)行了大量實(shí)驗(yàn)，重點(diǎn)測(cè)試了抽取元數(shù)據(jù)片斷對(duì)結(jié)構(gòu)完整性檢測(cè)效率的提升，并對(duì)本方法與前述3種主要方法(OMLM，NEREUS，metaDepth)的檢測(cè)時(shí)間性能進(jìn)行對(duì)比.所有實(shí)驗(yàn)是在Intel i5-8265U、8 GB內(nèi)存和Windows 10操作系統(tǒng)的環(huán)境下執(zhí)行的.實(shí)驗(yàn)采用基于MOF 2.5.1框架的元數(shù)據(jù)集ReMoDD[14]作為測(cè)試集，我們隨機(jī)地選擇4個(gè)檢測(cè)任務(wù)：ColumnSet的屬性類(lèi)型沖突、Dimension的屬性類(lèi)型沖突、TableOwning的多重性沖突以及SchemaOwning的多重性沖突并分別使用2種推理機(jī)HermiT和FaCT++執(zhí)行檢測(cè).測(cè)試結(jié)果如表1和圖4所示.

從實(shí)驗(yàn)結(jié)果來(lái)看，無(wú)論采用何種推理機(jī)，本文的方法在4種檢測(cè)任務(wù)上的表現(xiàn)均大幅優(yōu)于NEREUS方法.值得注意的是，在采用HermiT推理機(jī)時(shí)，我們的方法執(zhí)行2個(gè)多重性沖突檢測(cè)任務(wù)的平均時(shí)間508.20 s不如OMLM方法的444.67 s，這一差距在FaCT++的情況下(596.66 s)甚至更大，即便如此，由于本方法在屬性類(lèi)型沖突檢測(cè)中的優(yōu)勢(shì)，4種任務(wù)的平均執(zhí)行時(shí)間509.45 s(HermiT)和520.88 s(FaCT++)仍略?xún)?yōu)于OMLM方法的531.16 s.這一結(jié)果在與metaDepth方法(611.60 s)的對(duì)比中同樣得以反應(yīng).綜合來(lái)看，在實(shí)驗(yàn)元數(shù)據(jù)集上，我們的方法取得了顯著優(yōu)于NEREUS方法但略?xún)?yōu)于OMLM和metaDepth方法的結(jié)果.

Table 1 Experimental Results for Extracting Logically Independent Fragment表1 抽取邏輯無(wú)關(guān)片斷的實(shí)驗(yàn)結(jié)果

Fig. 4 Time performance comparison with related approaches圖4 與相關(guān)方法的時(shí)間性能比較

5 結(jié) 論

通過(guò)在抽取出的元數(shù)據(jù)片斷上進(jìn)行查詢(xún)推理，本文提出了一種高效、自動(dòng)地檢測(cè)MOF存儲(chǔ)庫(kù)系統(tǒng)的結(jié)構(gòu)完整性的方法.我們研究了將層次化的元數(shù)據(jù)轉(zhuǎn)化為描述邏輯知識(shí)庫(kù)的方法；最小邏輯無(wú)關(guān)片斷的獲取方法以及基于該片斷的結(jié)構(gòu)完整性檢測(cè)方法.為了證明方法的正確性，我們給出了嚴(yán)格的形式化證明.由于抽取出的元數(shù)據(jù)子集是原始集合的邏輯蘊(yùn)含的閉包，因此待查詢(xún)?cè)氐乃羞壿嫿Y(jié)論均得以保留從而使得本方法在不改變檢測(cè)結(jié)果的前提下具有較高的效率.實(shí)驗(yàn)過(guò)程組合了不同的推理機(jī)和檢測(cè)任務(wù)，結(jié)果表明邏輯無(wú)關(guān)片斷的抽取可以顯著地提高檢測(cè)的效率以及本方法具有優(yōu)于相關(guān)方法的時(shí)間性能.