基于描述邏輯的EER模型檢測(cè)

陳 振 慶

(賀州學(xué)院機(jī)械與電子工程學(xué)院　廣西 賀州 542899)

?

基于描述邏輯的EER模型檢測(cè)

陳 振 慶

(賀州學(xué)院機(jī)械與電子工程學(xué)院廣西 賀州 542899)

首先分析基于描述邏輯的ER模型的研究現(xiàn)狀，提出基于描述邏輯SHOIN(D)的EER模型，給出描述邏輯SHOIN(D)的語(yǔ)法和語(yǔ)義。然后研究EER模型的SHOIN(D)描述形式，以及如何將EER模型向SHOIN(D)知識(shí)庫(kù)轉(zhuǎn)化。最后給出EER模型可滿足性、冗余性判定定理，證明了這些推理問(wèn)題的正確性，并利用pellet推理機(jī)實(shí)現(xiàn)了EER模型可滿足性和冗余性推理。

描述邏輯SHOIN(D)知識(shí)庫(kù)ER模型EER模型

0　引　言

描述邏輯是一種具備很強(qiáng)表達(dá)能力和可判定性的知識(shí)表示工具，具有高效的判定算法和推理機(jī)制支撐，適合于相關(guān)推理問(wèn)題的研究。實(shí)體聯(lián)系ER模型是一種數(shù)據(jù)庫(kù)設(shè)計(jì)工具，是現(xiàn)實(shí)世界的抽象描述，在概念模型設(shè)計(jì)中得到廣泛應(yīng)用。隨著應(yīng)用環(huán)境的復(fù)雜化，為了準(zhǔn)確地模擬客觀世界，研究人員又?jǐn)U展了基本ER模型的概念，提出了增強(qiáng)實(shí)體聯(lián)系模型EER。Alex Borgida和Diego Calvanese等人分別提出了描述邏輯DLR和ALNUI，對(duì)ER模型的可滿足性、冗余性等相關(guān)問(wèn)題進(jìn)行自動(dòng)推理[1,2]。Artale 等人研究了在術(shù)語(yǔ)層和斷言層上建立了描述邏輯與面向?qū)ο髷?shù)據(jù)庫(kù)描述之間的映射關(guān)系[3]。李鑫等人利用Answer set編程表示ER模型，利用ER模型實(shí)現(xiàn)異構(gòu)數(shù)據(jù)庫(kù)之間的語(yǔ)義協(xié)作[4]，就ER模型與關(guān)系數(shù)據(jù)庫(kù)的融合進(jìn)行了理論研究。蔣運(yùn)承等人針對(duì)帶屬性依賴時(shí)序ER模型的需求和特點(diǎn),提出了時(shí)序描述邏輯A LCQI(D)US，并研究了基本時(shí)序描述邏輯ALCQI(D)US帶屬性依賴時(shí)序ER模型的自動(dòng)推理問(wèn)題[5]。上述研究都沒(méi)有擴(kuò)展到EER模型，也沒(méi)有進(jìn)行更具體的推理實(shí)現(xiàn)。Horrocks I等人研究了具有很強(qiáng)的表達(dá)能力的面向本體的描述邏輯語(yǔ)言SHOIN(D)[6]，并指出其是目前應(yīng)用最廣泛的WEB本體表示語(yǔ)言O(shè)WL DL的邏輯基礎(chǔ)。針對(duì)上述研究的不足，本文以描述邏輯SHOIN(D)為基礎(chǔ)，研究如何把EER模型正確轉(zhuǎn)化為SHOIN(D)知識(shí)庫(kù)，進(jìn)而轉(zhuǎn)化為OWL DL本體，再利用pellet推理機(jī)對(duì)OWL DL本體知識(shí)庫(kù)進(jìn)行推理，實(shí)現(xiàn)對(duì)EER模型的可滿足性、冗余性等問(wèn)題進(jìn)行檢測(cè)。

1　SHOIN(D)語(yǔ)法和語(yǔ)義

(1) 任何概念C∈NC是SHOIN(D)概念。

(2) 任何個(gè)體名O∈NO是SHOIN(D)概念。

定義2令一個(gè)解釋I=(ΔI，·I)，ΔI為解釋域，·I為解釋函數(shù)，·I函數(shù)把概念或個(gè)體映射成ΔI的子集，對(duì)于給定的解釋I，SHOIN(D)概念必須滿足以下語(yǔ)義：

定義3令一個(gè)解釋I=(ΔI，·I)，ΔI為解釋域，·I為解釋函數(shù)，·I函數(shù)把角色映射成ΔI×ΔI的子集，對(duì)于給定的解釋I，SHOIN(D)角色必須滿足以下語(yǔ)義：

(1) RI=ΔI×ΔI。

(2)(┐R )I=ΔI×ΔIRI。

(3) (R -)I={(b,a)∈ΔI×ΔI|(a,b)∈ΔI×ΔI}}。

(4) (R1R2)I={R1，R2∈RI|(R1IR2I)∈RI}。

(5) (R1R2)I={R1，R2∈RI|(R1IR2I)∈RI}。

2　基于SHOIN (D)的EER模型

2.1EER模型

定義4令X和Y是兩個(gè)有限域，T為X→Y的函數(shù)，如果X與Y滿足：對(duì)于任意的Xi∈X有T(Xi)=Yi且Yi∈Y，則稱T為Y上 X標(biāo)記的元組，記作T(X，Y)或T=[X1:Y1,X2:Y2，…，Xi:Yi]，1≤i≤n。

定義5EER模型S為一個(gè)九元組MS=(LS，ATT，REL，KEY，CARD，WEAK，ISA，DISJ，COVER)，滿足如下說(shuō)明：

(3)REL為關(guān)系函數(shù)，REL(R)=[U1:E1,U2:E2，…，Ui:Ei], 對(duì)于任意的R∈RS，函數(shù)值為ES上US標(biāo)記的元組。

宴姝的家鄉(xiāng)江蘇省南通市建有中國(guó)最早的博物館——南通博物館，幼時(shí)那便是宴姝走進(jìn)歷史、看向世界的窗口。后來(lái)，每去一處旅游，宴姝的父親都不惜花上半天的時(shí)間排隊(duì)，帶她去當(dāng)?shù)氐牟┪镳^看一看。

2.2EER模型的SHOIN(D)描述

定義7給定EER模型MS向SHOIN(D) 知識(shí)庫(kù)KB轉(zhuǎn)化是通過(guò)一個(gè)轉(zhuǎn)化函數(shù)φ(MS)來(lái)完成。

φ(MS)的概念公理Tbox由以下元素組成：

φ(MS)的概念公理Abox由以下元素組成：

2.3EER模型的描述邏輯推理

EER模型MS向SHOIN(D) 知識(shí)庫(kù)轉(zhuǎn)化都要考慮知識(shí)庫(kù)的可滿足性和冗余性，可滿足性要求知識(shí)庫(kù)邏輯上不能出現(xiàn)空集，否則是無(wú)意義的。冗余性則指兩個(gè)實(shí)體或關(guān)系之間的邏輯描述不存在蘊(yùn)含或等價(jià)關(guān)系。

定義8給定一個(gè)SHOIN(D)知識(shí)庫(kù)K，KF為術(shù)語(yǔ)公理，當(dāng)且僅當(dāng)K的每一個(gè)解釋I滿足KF，稱K蘊(yùn)含KF，記作KKF。

定理1可滿足性判定定理

給定一個(gè)EER模型MS，φ(MS)是EER模型MS轉(zhuǎn)化得到的SHOIN(D)知識(shí)庫(kù)，MS是可滿足的，當(dāng)且僅當(dāng)φ(MS)滿足以下條件：φ(MS)φ(A)?；φ(MS)φ(P)?；φ(MS)φ(E)?；φ(MS)φ(R)?。

下面僅對(duì)φ(MS)φ(A)?進(jìn)行證明，其他條件證明同理。

再證明?。因?yàn)棣?MS)φ(A)?成立，則有φ(MS)φ(A)?，φ(A)?，由定義8可得φ(MS)φ(A)，由定義7得知φ(A)是由原子概念轉(zhuǎn)化得到的對(duì)應(yīng)SHOIN(D)知識(shí)庫(kù)，所以A?。根據(jù)定義2得知存在一個(gè)解釋I=(ΔI，·I)，使得AIΔI成立，所以A是可滿足的， 從而得MS是可滿足的，證畢。

定理2冗余性判定定理

下面進(jìn)行具體證明：先證明?。假設(shè)(1)φ(MS)E1E2和φ(MS)E2E1或(2)φ(MS)R1R2和φ(MS)R2R1成立，由定義8得知存在一個(gè)解釋I=(ΔI，·I)，使得E1IE2I和E2IE1I成立，或者R1IR2I和R2IR1I成立，那么就有(E1E2)?和(E2E1)?，或者(R1R2)?和(R2R1)?，所以E1E2和E2E1，或者R1R2和R2R1是可滿足的，顯然MS是存在冗余性的，證畢。

3　EER模型推理實(shí)現(xiàn)

OWL是W3C推薦的Web本體語(yǔ)言標(biāo)準(zhǔn)，英國(guó)牛津大學(xué)IHorrocks教授已經(jīng)證明了OWLDL與描述邏輯SHOIN(D)等價(jià)。Pellet是美國(guó)馬里蘭大學(xué)MindSwap實(shí)驗(yàn)室開(kāi)發(fā)的開(kāi)源描述邏輯本體推理機(jī)[7]，支持OWLDL所有構(gòu)造元素，基于Tableau算法實(shí)現(xiàn)了對(duì)OWLDL本體進(jìn)行推理機(jī)。文獻(xiàn)[8]研究了描述邏輯對(duì)應(yīng)的OWL本體表示形式，從而給EER模型推理提供了技術(shù)支持。本文的EER模型推理實(shí)驗(yàn)硬件采用處理機(jī)Intel(R)core(TM)i5-4210uCPU@2.40GHz，內(nèi)存4.0GB，Widows8.1中文版64位操作系統(tǒng)，軟件使用Pellet2.2.2推理機(jī)，系統(tǒng)架構(gòu)如圖1所示。

圖1　EER模型推理框架

圖2為教學(xué)管理系統(tǒng)的局部EER模型圖，根據(jù)定義7得知該EER模型圖對(duì)應(yīng)的SHOIN(D)知識(shí)庫(kù)是通過(guò)一個(gè)轉(zhuǎn)換函數(shù)φ轉(zhuǎn)換得到，所以對(duì)應(yīng)的SHOIN(D)知識(shí)庫(kù)不可能為空，由定理1知該EER模型圖及其對(duì)應(yīng)的SHOIN(D)知識(shí)庫(kù)都是可滿足的。但在“教師與學(xué)生之間的授課聯(lián)系”中，由“授課”和“選修”這兩個(gè)聯(lián)系可以導(dǎo)出“教師與課程之間的任教聯(lián)系”，出現(xiàn)了冗余性，從而導(dǎo)致模型存在不一致性。下面介紹EER模型可滿足性和冗余性的推理過(guò)程，根據(jù)圖1 的EER模型推理框架，首先通過(guò)轉(zhuǎn)換函數(shù)把EER模型圖轉(zhuǎn)換為OWL DL本體，然后利用Pellet推理機(jī)進(jìn)行推理[9]，可滿足性推理結(jié)果如圖3所示，冗余性推理結(jié)果如圖4所示。

圖2　教學(xué)管理系統(tǒng)局部EER模型

圖3　EER模型可滿足性推理結(jié)果

圖4　EER模型一致性推理結(jié)果

從圖3、圖4可以看出，Pellet推理機(jī)成功實(shí)現(xiàn)了對(duì)EER模型本體知識(shí)庫(kù)的可滿足性和冗余性進(jìn)行推理，其中可滿足性推理主函數(shù)運(yùn)行用時(shí)640 ms，本體裝載用時(shí)406 ms，一致性檢測(cè)用時(shí)16 ms，可滿足性推理用時(shí)15 ms，最終沒(méi)有發(fā)現(xiàn)不可滿足的概念。冗余性推理主函數(shù)運(yùn)行用時(shí)672 ms，本體裝載用時(shí)438 ms，一致性檢測(cè)用時(shí)16 ms，結(jié)果顯示學(xué)生與課程之間產(chǎn)生了冗余，本體知識(shí)庫(kù)是不一致的。

4　相關(guān)工作

Alex Borgida等人提出了基于描述邏輯DLR的ER模型，研究了ER模型的DLR表示形式，并把ER模型轉(zhuǎn)化為DLR知識(shí)庫(kù)，借助描述邏輯的推理機(jī)制實(shí)現(xiàn)對(duì)知識(shí)庫(kù)進(jìn)行推理[1]。Diego Calvanese等人提出描述邏輯ALNUI，研究了ALNUI知識(shí)庫(kù)可滿足性、冗余性自動(dòng)推理問(wèn)題[2]。他們主要是從理論層面進(jìn)行了相關(guān)研究，若要推廣到EER模型并進(jìn)行更具體的推理實(shí)現(xiàn)，必須尋找一種具有強(qiáng)大表達(dá)能力，且有成熟軟件支持的描述邏輯。描述邏輯SHOIN(D)作為OWL DL的邏輯基礎(chǔ)，具有更強(qiáng)的語(yǔ)義表達(dá)能力，能夠滿足EER模型形式化的需要。Horrocks I等人也證明了SHOIN(D)和OWL DL是等價(jià)的[6]，可知SHOIN(D)與 OWL DL存在邏輯上的對(duì)應(yīng)性，為SHOIN(D)知識(shí)庫(kù)能夠正確向OWL DL本體知識(shí)庫(kù)轉(zhuǎn)化提供了理論依據(jù)。而成熟的Pellet描述邏輯本體推理機(jī)支持OWL DL的所有元素，為基于描述邏輯的EER模型檢測(cè)提供了全面的技術(shù)支持，強(qiáng)有力地支持了本文的研究。

5　結(jié)　語(yǔ)

本文給出了描述邏輯SHOIN(D)語(yǔ)法和語(yǔ)義，研究了基于描述邏輯SHOIN(D)的EER模型及其推理問(wèn)題，并利用Pellet推理機(jī)對(duì)EER模型進(jìn)行了可滿足性、冗余性推理。實(shí)驗(yàn)結(jié)果表明，基于描述邏輯的EER模型檢測(cè)方案切實(shí)可行。

[1] Borgida A,Lenzerini M Rosati.Description logics[C]//The Description Logic Handbook,ACM，2003：472-494.

[2] Calvanese D, Giacomo G D, Nardi D, et al. Reasoning in expressive description logics[C]//Handbook of Automated Reasoning.Milan:Elsevier Science Publishers, 2001：1581-1634.

[3] Artale A, Franconi E, Mandreoli F.Description logics for modeling dynamic information[C]//Logics for Emerging Applications of Databases. Berlin:Springer-Verlag, 2003：239-275.

[4] 李鑫，李凡，劉啟和. ER模型的邏輯表示途徑[J].電子科技大學(xué)學(xué)報(bào)，2010，39(3):435-439.

[5] 蔣運(yùn)承，湯庸，王駒，等.基于描述邏輯的帶屬性依賴時(shí)序 ER模型[J].計(jì)算機(jī)研究與發(fā)展，2007，44(10):1765-1773.

[6] Horrocks I, Pate1 Schneider PF, van Harmelen F. From SHIQ and RDF to OWL: The Making of a Web Ontology Language[J].Journal of Web Semantics, 2003,1(1):7-26.

[7] 歐陽(yáng)柳波，尹勝臺(tái).層疊推理機(jī)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與軟件，2014，31(10):161-166.

[8] 陳振慶，羅蘭花.基于OWL本體的UML類圖推理[J].計(jì)算機(jī)應(yīng)用與軟件，2011，28(8):190-192,243.

[9] 柯昌博，黃志球.云計(jì)算環(huán)境下隱私需求的描述與檢測(cè)方法[J].計(jì)算機(jī)研究與發(fā)展，2015，52(4):879-888.

EER MODEL CHECKING BASED ON DESCRIPTION LOGIC

Chen Zhenqing

(DepartmentofMechanicsandElectronicsEngineering,HezhouUniversity,Hezhou542899,Guangxi,China)

We first analysed current status of description logic-based ER model researches, and presented the description logic SHOIN(D)-based EER model, as well as put forward the syntax and semantics of description logic SHOIN(D). Then we studied the describing form of SHOIN(D) in EER model, and the way of how to translate EER model into description logic SHOIN(D) knowledge bases. Finally we gave the judgement theorem of the satisfiability and redundancy of EER model, proved the correctness of these reasoning problems, and employed the pellet’s inference mechanism to achieve the reasoning of satisfiability and redundancy in EER model.

Description logic SHOIN(D)Knowledge basesER modelEER model

2015-04-27。廣西自然科學(xué)基金項(xiàng)目(2014GXNSF BA118278)。陳振慶，副教授，主研領(lǐng)域：語(yǔ)義網(wǎng)，描述邏輯，軟件工程。

TP182

A

10.3969/j.issn.1000-386x.2016.08.009