蔣宗華

摘要:該文提出了一種模塊化本體緩存方案,使用該方案能夠縮短本體推理的平均時(shí)間。給出了緩存的對象和緩存一致性檢查方法,通過中斷方式和增量模式傳遞知識更新信息,能夠減少通信量和提高更新的效率。

關(guān)鍵字:本體;模塊化;緩存

中圖分類號:TP311文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2010)11-2627-02

Cache Scheme in Modular Ontology

JIANG Zong-hua

(College of Information Engineering, Anhui University of Finance & Economics, Bengbu 233041, China)

Abstract: The author presents a cache scheme in modular ontology,the average ontology reasoning time can be decreased by using the scheme.The cache objects and the cache consistency checking method are described. By transmitting knowledge updating messages in interrupt mode and incremental mode, the total communication volume can be reduced and the efficiency of updating can be enhanced.

Key words: ontology; modular; cache

本體是指共享概念模型的明確的形式化規(guī)范說明,通過描述概念及概念之間的關(guān)系來描述概念的語義。本體不僅被某個(gè)應(yīng)用主體所接受,而是在各種應(yīng)用主體之間交換意見時(shí)所用到的共同語言。本體最主要的優(yōu)勢是共享和重用。

隨著對某個(gè)領(lǐng)域認(rèn)識的深入,相應(yīng)的領(lǐng)域本體也越來越大,大規(guī)模單一本體會帶來一系列問題:在大規(guī)模單一本體上進(jìn)行推理的效率低;即使只需要小部分知識也要引入整個(gè)本體,重用率低;開發(fā)者需了解整個(gè)本體,不利于分工合作和本體進(jìn)化等。模塊化是有效克服這些問題的方法,通過模塊化,本體被分成若干個(gè)功能相對獨(dú)立的模塊,而在模塊化本體中引入接口的方法,能進(jìn)一步提高模塊的獨(dú)立性。

模塊化本體中,一個(gè)本體模塊在進(jìn)行推理時(shí),可能要用到多個(gè)其它模塊的知識,甚至于這些模塊分布在網(wǎng)絡(luò)中的不同主機(jī)上。引入緩存即通過對一些概念和角色的術(shù)語和斷言進(jìn)行緩存,能夠提高本體推理的效率。為了保持本體緩存的一致性,當(dāng)相關(guān)模塊的知識變化時(shí),應(yīng)及時(shí)更新緩存的對象。

1 基于接口的模塊化本體

在基于接口的模塊化本體中,本體被定義成接口和本體模塊的集合[1],一個(gè)接口是一個(gè)概念名、角色名和關(guān)于它們的包含公理集合,而一個(gè)本體模塊是一個(gè)可以用任何描述邏輯語言表達(dá)的本體。通過引入接口的概念,將本體模塊的知識分為公有部分和私有部分。

本體表示語言的邏輯基礎(chǔ)是描述邏輯[2],描述邏輯的知識庫由ABox(斷言)和TBox(術(shù)語)兩部分組成。ABox是一個(gè)關(guān)于個(gè)體的斷言組成的有限集,形如C(a)或r(a,b),其中C是概念名而r是角色名,a、b是個(gè)體名,在本體表述中,個(gè)體指概念的實(shí)例。TBox是一個(gè)概念包含公理的有限集,形如A?哿B,其中A和B是概念表達(dá)式。

每個(gè)接口中的TBox公理構(gòu)成了本體模塊的共享段,共享段的邏輯結(jié)果會被傳播到所有其它相關(guān)模塊中,以下是接口的定義:

定義1:一個(gè)接口定義為I=其中T是接口的TBox,Cn和Rn分別是在T中用到的概念和角色的名稱集合,接口I中沒有ABox斷言。

本體模塊的斷言集和內(nèi)部TBox公理是私有的,只能通過知識查詢來訪問,私有段知識的改變只在局部知道。每個(gè)本體模塊指定它要使用的接口集和它實(shí)現(xiàn)的接口集。當(dāng)作為接口的實(shí)現(xiàn)者時(shí),該模塊將提供接口中有關(guān)概念和角色的解釋;當(dāng)作為接口的使用者時(shí),能夠集成接口實(shí)現(xiàn)者模塊的知識。以下是本體模塊的定義:

定義2:一個(gè)本體模塊定義為M=<Ψ,Ir,Iu>,其中Ψ由模塊內(nèi)的TBox公理和ABox斷言集合組成,Ir是模塊M實(shí)現(xiàn)的接口集合,Iu是模塊M使用的接口集合。

本體模塊具有局部語義和清晰接口,從而進(jìn)一步提高了模塊的獨(dú)立性。一個(gè)本體模塊使用另一個(gè)模塊時(shí),是通過使用接口實(shí)現(xiàn)的。在基于接口的模塊化本體中,模塊的進(jìn)化和接口的配置是分開的。在模塊進(jìn)化時(shí),僅確定了使用的接口而沒有確定接口由哪個(gè)模塊實(shí)現(xiàn),這樣就不必知道被使用模塊的名稱和符號;在配置時(shí),選擇模塊來實(shí)現(xiàn)接口,使得實(shí)現(xiàn)者模塊容易被替換。

2 緩存方案

2.1 緩存對象

由于在緩存方案中,對角色的處理和對概念的處理是相似的,以下僅討論對概念的處理。在基于接口的模塊化本體中,如果某模塊在推理的過程中用到其它模塊的知識,則需要向相關(guān)接口發(fā)起查詢,從接口的實(shí)現(xiàn)者模塊中查得相關(guān)概念的實(shí)例。為了盡可能地縮短本體推理的時(shí)間,每個(gè)本體模塊可以分配一個(gè)緩存空間,用來存放經(jīng)常被查詢的外部知識。文獻(xiàn)[3]提出本體模塊存儲所有用到的外部概念之間的包含公理,這在時(shí)間復(fù)雜性和空間復(fù)雜性上是難以接受的。另外文獻(xiàn)[3]沒有區(qū)分外部概念之間穩(wěn)定的和暫時(shí)的包含公理之間的區(qū)別,不能高效地更新有穩(wěn)定子集關(guān)系的相關(guān)概念。而在基于接口的模塊化本體中,模塊使用者用到的外部概念放在接口中,同時(shí)接口中的TBOX中存放這些概念間穩(wěn)定的包含公理。而對于因組合爆炸產(chǎn)生的數(shù)量巨大的暫時(shí)性包含關(guān)系則由實(shí)現(xiàn)者模塊決定,是動(dòng)態(tài)的。在實(shí)現(xiàn)者模塊中并不存儲這些暫時(shí)的包含關(guān)系,而只是解釋接口中概念,概念之間的包含公理由它們的實(shí)例決定,知識的存儲是線性的。使用者模塊可以向接口發(fā)起查詢從而獲得相關(guān)概念的實(shí)例,而被查詢概念穩(wěn)定的祖先概念可以由接口中TBOX推理出。

本方案中緩存的知識主要由兩部分構(gòu)成:ABOX緩存知識和TBOX緩存知識。ABOX存放一些經(jīng)常被查詢的概念有哪些實(shí)例,例如“直轄市”概念有北京、上海等實(shí)例。TBOX存放經(jīng)常被查詢的包含關(guān)系,假設(shè)A和B兩個(gè)概念中至少有一個(gè)是外部概念,如果經(jīng)常要查詢A和B的包含關(guān)系,查詢結(jié)果(例如是A?哿B)則被緩存。由于緩存空間的有限性,當(dāng)緩存空間將要用盡時(shí),可以采用最近最久未用法等置換算法刪除一部分緩存內(nèi)容。

采用緩存機(jī)制后,推理如果用到外部模塊的知識則先在緩存中查找,如果命中則本地的知識便能完成推理,否則再向?qū)崿F(xiàn)者模塊發(fā)起知識查詢,根據(jù)局部性原理,這樣能夠顯著縮短平均推理時(shí)間。

2.2 緩存一致性

當(dāng)一個(gè)本體模塊的相關(guān)模塊知識改變時(shí),可能會造成緩存內(nèi)容的失效。在文獻(xiàn)[1]中,一個(gè)本體模塊對相關(guān)模塊的知識集成是通過發(fā)起知識查詢來進(jìn)行的,然而如果對緩存中的概念不斷發(fā)起知識查詢,以此來判斷有無發(fā)生更改顯然是低效的,會造成模塊間通信量的劇增和相關(guān)模塊推理任務(wù)的加重。本研究中,用中斷的方式來替代查詢的方式,由發(fā)生知識改變的模塊負(fù)責(zé)發(fā)送消息給相關(guān)模塊。

若某模塊的知識發(fā)生變化時(shí),首先確定該知識變化所影響的概念,如果相關(guān)的概念都未在接口中出現(xiàn),則說明對接口的解釋沒有改變,只是發(fā)生和接口使用者無關(guān)的局部語義改變,不必發(fā)送更新消息。否則,將發(fā)生改變的概念的實(shí)例發(fā)送給接口的使用者模塊。發(fā)生改變的概念如果在接口中有祖先概念,勢必也會引起祖先概念實(shí)例的改變,但此時(shí)只發(fā)送最底層概念和它的實(shí)例,這是因?yàn)榻涌诘腡BOX知識能傳播到使用者模塊從而能夠推理出祖先概念。由于接口的使用者模塊的緩存對象是它的局部信息,接口的實(shí)現(xiàn)者模塊并不知道該信息,無法判斷發(fā)生語義改變的概念出現(xiàn)在哪些使用者模塊的緩存中,所以知識更新消息將發(fā)給所有使用者模塊。

發(fā)生改變的概念實(shí)例采用增量的模式發(fā)送,在消息中指出哪個(gè)概念增加(或減少)了哪些實(shí)例。只向相關(guān)模塊定向發(fā)送和采用增量模式,可以減少通信量。使用者模塊收到消息后,結(jié)合自身的知識和相關(guān)接口的TBOX,推理出發(fā)生改變的概念所有祖先概念,加上該概念自身得到一個(gè)概念集。由于接口中的TBOX知識已被加入到使用者模塊的本地知識庫,故這一步的推理是在本地進(jìn)行的。如果該概念集中的所有概念均未在使用者模塊的緩存中出現(xiàn),使用者模塊將丟棄收到的更新消息。如果在緩存的ABOX部分找到了概念集中的某個(gè)概念,則更新ABOX緩存知識。下一步是查找該概念集中的概念有無在緩存的TBOX部分中出現(xiàn),假設(shè)該概念集中的某概念出現(xiàn)在緩存中一條形如A?哿B的包含公理中,則分為下述幾種情況決定該包含公理是否失效,對失效的公理將從緩存中刪除。

1)A的實(shí)例減少或不變而B的實(shí)例不變或增加。這種情況下該條包含公理仍有效。

2)A的實(shí)例增加。這種情況下則首先查詢緩存ABOX知識中有無概念B,若沒有則要向概念B的實(shí)現(xiàn)者模塊發(fā)送知識查詢信息,得到概念B的實(shí)例集。令A(yù)1表示A增加實(shí)例的集合,如果A1?哿B,則該條包含公理仍有效,否則該條包含公理失效。

3)B的實(shí)例減少。這種情況下則首先查詢緩存ABOX知識中有無概念A(yù),若沒有則要向概念A(yù)的實(shí)現(xiàn)者模塊發(fā)送知識查詢信息,得到概念A(yù)的實(shí)例集。令B1表示B減少實(shí)例的集合,如果B1∩A=?覫,則該條包含公理仍有效,否則該條包含公理失效。

如果實(shí)現(xiàn)者模塊重新定義了一個(gè)概念,造成一個(gè)概念的實(shí)例大規(guī)模變化,使得發(fā)送概念增量實(shí)例可能比發(fā)送概念實(shí)例通信量更大,這種情況下也可以直接發(fā)送概念實(shí)例。由于使用者模塊的緩存中可能沒有該概念,為了減少通信量,在知識更新消息中僅發(fā)送該概念的名稱和一個(gè)特殊標(biāo)志指出當(dāng)前工作在非增量模式。該概念和它的祖先概念構(gòu)成一個(gè)概念集,如果該概念集的某個(gè)概念出現(xiàn)在使用者模塊緩存中一條形如A?哿B的包含公理中,則不論位置如何,都要重新判斷該條包含公理的有效性。通過向相關(guān)實(shí)現(xiàn)者模塊發(fā)起知識查詢,得到A和B的實(shí)例集,再判斷A?哿B的有效性。非增量模式下緩存ABOX檢查是類似的。

3 結(jié)束語

為了提高模塊化本體推理的效率,本研究提出了模塊化本體緩存方案,給出了緩存的對象和緩存一致性檢查方法。進(jìn)一步的研究是將該方案應(yīng)用到具體的系統(tǒng)中并進(jìn)行驗(yàn)證。

參考文獻(xiàn):

[1] Ensan F.Formalizing Ontology Modularization through the Notion of Interfaces[C].Acitrezza,Catania,Italy:Proc. of the 16th International Conference on Knowledge Engineering and Knowledge Management,2008:74-82.

[2] Borgida A,Serafini L.Distributed Description Logics:Assimilating Information from Peer Sources[J].Journal of Data Semantics,2003,1(1):153-184.

[3] Stuckenschmidt H,Klein M.Reasoning and Change Management in Modular Ontologies[J].Data and Knowledge Engineering,2007,63(2):200-223.