王 飛 錢鐵云 劉 斌 彭智勇

(武漢大學計算機學院 武漢 430072)

知識圖譜是一種重要的知識表示形式，能夠支持智能推薦[1]、智能問答[2]和知識發(fā)現(xiàn)[3]等大量的人工智能應用.隨著越來越多的知識圖譜數(shù)據(jù)陸續(xù)發(fā)布出來，知識圖譜的管理吸引了研究者的大量關注[4-8].盡管許多研究成果展示了其在知識圖譜管理方面的巨大成功，但是，帶有連續(xù)屬性的知識圖譜元知識建模管理并沒有引起太多的關注.知識圖譜自然地涵蓋知識和元知識2種陳述.一條知識就是一條陳述，而一條元知識則是一條關于知識的起源、時間、空間和置信度等信息的陳述[9].

Fig. 1 Knowledge Graph and Query Graph圖1 知識圖譜和查詢圖

由于知識圖譜包含知識和元知識2種陳述類型，因此，知識圖譜管理的一個重要任務就是進行知識和元知識的邏輯存儲建模.現(xiàn)有的邏輯存儲建模主要分為三元組框架和類三元組框架2種建模方式.三元組框架建模方式[9-11]將知識陳述抽象成句柄，通過知識句柄關聯(lián)知識陳述和元知識陳述，并統(tǒng)一表示成三元組形式.類三元組框架建模方式[12]突破了傳統(tǒng)三元組知識表示的約束，通過擴展知識維度進行公共元知識屬性的模式化存儲.由于知識圖譜是一種無模式的數(shù)據(jù)類型，因此，三元組框架和類三元組框架對知識陳述都采用泛化形式的語義表達.在進行知識和關聯(lián)元知識表示時，泛化建模方式需要同時進行數(shù)據(jù)值聲明和模式聲明，這導致了知識圖譜建模的冗余度非常高.這種類型的知識圖譜冗余不僅浪費存儲空間和I/O代價，還需要大量的連接操作來重構(gòu)知識陳述和元知識陳述，制約著知識圖譜的查詢響應效率，直接影響著知識圖譜的可用性.此外，知識和元知識可能涉及時間、地理位置以及置信度等連續(xù)型屬性，因此，面向連續(xù)型屬性的查詢已經(jīng)成為知識圖譜應用迫切需要解決的問題[13-14].現(xiàn)有的泛化知識圖譜建模方法無法有效地支持帶有連續(xù)屬性的范圍查詢.

不同于泛化建模方式，模式化建模在一定程度上固化了數(shù)據(jù)的存儲模式，在進行知識和元知識建模時只需要進行數(shù)據(jù)值聲明，而不需要進行數(shù)據(jù)模式聲明，這樣就顯著地降低了數(shù)據(jù)冗余.同時，模式化存儲也有助于實現(xiàn)對知識屬性和元知識屬性的數(shù)據(jù)類型特化，支持連續(xù)屬性的范圍查詢.為了實現(xiàn)知識圖譜的模式化存儲，就需要將無模式的知識圖譜數(shù)據(jù)轉(zhuǎn)化為模式化數(shù)據(jù).

雖然知識圖譜數(shù)據(jù)的查詢需求動態(tài)變化，但是，數(shù)據(jù)之間的固有關聯(lián)以及相關的查詢模式卻又具有一定的穩(wěn)定性[15].因此，知識圖譜數(shù)據(jù)的語義存儲建模成為知識圖譜管理提升查詢效率的一條有效途徑.一些研究者提出對知識圖譜進行謂語分組存儲來適應綁定謂語的查詢需求[16].另一些研究者采用實體形式組織存儲，根據(jù)數(shù)據(jù)組織和處理的差異性分為表上的實體存儲[17]和圖上的實體存儲[6].這種建模方式實現(xiàn)了一定程度的模式存儲，有助于減少星型查詢的關聯(lián)操作.除此之外，利用查詢?nèi)罩纠斫鈹?shù)據(jù)之間的查詢關聯(lián)，動態(tài)地調(diào)整數(shù)據(jù)的存儲組織方式也是一種建模數(shù)據(jù)語義關聯(lián)的方法[18].基于謂語分組和實體的關聯(lián)建模通常只能適應固有的數(shù)據(jù)關聯(lián)查詢，無法滿足各種應用的動態(tài)查詢需求.基于查詢?nèi)罩緞討B(tài)調(diào)整數(shù)據(jù)存儲組織方式涉及到數(shù)據(jù)的遷移與合并，通常需要較大的性能開銷.因此，我們需要設計一種輕量級的語義建模機制.這種語義建模機制不僅能夠建模數(shù)據(jù)之間的各種語義關聯(lián)，還能夠以非常低的性能代價適應查詢需求的動態(tài)變化.

本文提出了聚簇對象代理模型(cluster object deputy model, CODM)用于知識圖譜的建模管理.CODM模型將元知識陳述關聯(lián)到相應的知識陳述，提出了基于集合編輯距離的模式聚簇算法實現(xiàn)無模式的知識圖譜到模式化數(shù)據(jù)的轉(zhuǎn)變.為了進行統(tǒng)一的建模設計，CODM模型將模式化存儲建模和關聯(lián)語義建模融合到一個統(tǒng)一的建?？蚣?引入了類-對象概念，構(gòu)建了一個由聚簇實體類和代理關系類組成的類層次系統(tǒng).基于聚簇模式構(gòu)建聚簇實體類實現(xiàn)模式化存儲，能夠更好地支持知識圖譜的星型查詢.CODM模型定義了一系列語義操作算子用于構(gòu)建代理關系類，實現(xiàn)對各種語義關聯(lián)的建模.代理關系類采用指針機制來表達數(shù)據(jù)關聯(lián)，實現(xiàn)對知識圖譜聚簇對象泛化語義關聯(lián)的輕量級物化.這種輕量級的泛化語義關聯(lián)建模機制可以將連接操作轉(zhuǎn)換為選擇操作，以此來加快復雜查詢的處理效率.

1 相關工作

以知識圖譜為代表的知識工程是進一步提升人工智能智能化水平的基石日益成為一種行業(yè)共識.越來越多的信息以知識圖譜的形式進行發(fā)布[19-20]，知識圖譜的管理引起了學術(shù)界和工業(yè)界的高度關注.知識陳述和元知識陳述組成知識圖譜.早期的知識圖譜管理主要聚焦于知識陳述的管理.隨著知識圖譜應用的逐步擴展和深化，知識圖譜管理研究開始關注元知識陳述建模和連續(xù)屬性的查詢支持[21].知識圖譜管理主要分為關聯(lián)知識陳述和元知識陳述的邏輯存儲建模和優(yōu)化查詢性能的語義存儲建模.

邏輯存儲建模主要用于構(gòu)建知識陳述和元知識陳述的邏輯關聯(lián)，依據(jù)建模的元組形式分為三元組框架和類三元組框架.三元組框架通過知識陳述的唯一意涵關聯(lián)元知識陳述，其特點是將知識和元知識整合到統(tǒng)一的三元組框架.標準增強方式(standard reified statement)[10]是資源描述框架官方推薦的帶有元知識的知識圖譜建模方式.這種建模方式將知識陳述和關聯(lián)的元知識陳述歸并為一個泛化陳述，通過泛化陳述的意涵句柄分別聲明主語、謂語、賓語以及關聯(lián)的元知識.屬性唯一方式(singleton property approach)[9]是另一種三元組框架的元知識建模方式，該方式認為知識陳述的唯一性源于主語和賓語之間謂語所代表關系的唯一性.屬性唯一方式構(gòu)建了謂語屬性類，唯一性屬性成為謂語屬性類的一個屬性情景實例，將謂語屬性情景實例作為意涵句柄進行元知識陳述的聲明.由于三元組框架進行元知識陳述建模時固有的冗余特性，類三元組框架[22]擴展了經(jīng)典的SPO三元組為SPO+X的元組框架.SPO代表經(jīng)典的主語、謂語和賓語，而X則代表擴展的元知識公共謂語集合.YAGO2增強方式(YAGO2 reified statement)[12]是一種典型的類三元組框架，保留了SPO的經(jīng)典模式，同時擴展了時間、位置以及情景等公共元知識謂語集.表1～3呈現(xiàn)了3種邏輯存儲建模方式.

Table 1 Standard Reified Statement表1 標準增強方式

Table 2 Singleton Property Approach表2 屬性唯一方式

Table 3 YAGO2 Reified Statement表3 YAGO2增強方式

語義存儲建模主要是指通過知識圖譜聚簇實施存儲來提升知識圖譜數(shù)據(jù)的查詢響應性能，依據(jù)聚簇語義的差異性分為基于謂語的聚簇、基于實體的聚簇以及基于查詢語義的聚簇等3種類型的語義存儲建模方式.基于謂語的聚簇建模[16]，也稱為列式存儲，是指依據(jù)謂語信息對知識圖譜數(shù)據(jù)進行分組，并為每一個知識圖譜集合構(gòu)建一個存儲模式，這樣有助于提升I/O操作的有效性.由于基于謂語的聚簇建模方式實施分散存儲帶來了頻繁的連接操作，因此，研究者提出了基于實體的聚簇建模.這種聚簇建模方式將具有相同主語的知識圖譜數(shù)據(jù)進行關聯(lián)，并將這些實體映射到一個統(tǒng)一的聚簇文件.基于實體的聚簇建模有2種實現(xiàn)方式:1)采用散列或者圖著色的方式將實體的謂語信息映射到一個大的關系表，構(gòu)建一種具有弱模式的映射存儲[17]；2)將實體的謂語和賓語進行綁定，生成實體的指紋編碼，再采用類似散列樹的形式構(gòu)建實體指紋編碼的層次索引結(jié)構(gòu)[20]，加速離散型知識圖譜數(shù)據(jù)的查詢處理.謂語聚簇和實體聚簇通常只能反映靜態(tài)的數(shù)據(jù)關聯(lián)，無法滿足不斷演化的知識圖譜查詢需要.基于查詢語義的聚簇建模依據(jù)查詢流和數(shù)據(jù)響應流進行數(shù)據(jù)的關聯(lián)聚簇，動態(tài)地調(diào)整數(shù)據(jù)的存儲關聯(lián)，適應當前的數(shù)據(jù)查詢需要[18].

2 聚簇對象代理模型CODM

CODM構(gòu)建了由聚簇實體類和代理關系類組成的類層次系統(tǒng).一個模式聚簇算法能夠?qū)崿F(xiàn)知識圖譜從無模式數(shù)據(jù)到強類型模式數(shù)據(jù)的轉(zhuǎn)變.基于聚簇模式生成聚簇實體類，實現(xiàn)知識圖譜的模式化邏輯存儲和屬性數(shù)據(jù)類型的特化，而代理關系類構(gòu)建各種泛化的實體語義關聯(lián)用于加快復雜語義的特化查詢.表4是本文的符號表:

Table 4 Symbol Description Table表4 符號描述表

2.1 類的層次系統(tǒng)

現(xiàn)實生活中的一個對象可能擁有多個身份，在不同的情景中扮演不同的角色.在對象代理模型(object deputy model, ODM)[23]中，基于源對象生成的代理對象主要用于表示一組對象在不同情景中的角色或者對象的特定側(cè)面.對象代理模型在源類上定義了SELECTION,JION,UNION,PROJECTION和EXTENSION等操作語義生成具有不同角色的代理類.源類和代理類分別解釋源對象和代理對象的模式信息(schema).對于一個代理類，定義在源類上的一系列操作成為生成該代理類的代理規(guī)則.同時，代理類可以迭代地作為源類生成新的代理類.雙向指針能夠?qū)崿F(xiàn)代理對象和源對象之間的雙向通信.關聯(lián)代理對象的查詢通過雙向指針可以獲取相應的數(shù)據(jù)，從而避免代價昂貴的連接操作.不同于物化視圖,對象代理模型采用雙向指針物化對象關聯(lián)能夠顯著減少維護代價.因此，本文引入對象代理模型管理知識圖譜數(shù)據(jù)以及數(shù)據(jù)之間的關聯(lián)性.

知識圖譜是無模式數(shù)據(jù)，對象代理模型通常只能管理具有固定模式的數(shù)據(jù)，因此，本文擴展對象代理模型ODM為聚簇對象代理模型CODM來解決這種模式?jīng)_突.現(xiàn)在給出聚簇實體類(聚簇實體對象)、代理關系類(代理關系對象)組成的類層次系統(tǒng)的定義.

圖2展示了聚簇對象代理模型的類層次系統(tǒng).聚簇實體類位于類層次系統(tǒng)的底層，是構(gòu)建代理關系類的基礎.聚簇實體類和下層的代理關系類可以迭代地作為源類構(gòu)建上層的代理關系類.從功能上來看，聚簇實體類主要負責知識圖譜的模式化邏輯存儲建模，而代理關系類則用于構(gòu)建加快復雜查詢的語義存儲建模.

Fig. 2 CODM hierarchical system圖2 CODM類層次系統(tǒng)

2.2 聚類和聚簇實體類

在知識圖譜的查詢處理中，星型查詢具有非常特殊意義[21].一方面，星型簡單查詢在實際應用中占據(jù)絕對的數(shù)量優(yōu)勢;另一方面，許多復雜查詢可以分解為一些塊狀的星型查詢.擁有固定存儲模式具有天然的優(yōu)勢支持知識圖譜上的星型查詢.本文提出了一種新穎的模式聚簇算法將無模式的知識圖譜數(shù)據(jù)轉(zhuǎn)換為模式數(shù)據(jù).算法的核心是定義了集合編輯距離(set editing distance)，用于衡量不同模式間的相似性，作為模式合并的依據(jù).集合編輯距離定義為

(1)

(2)

(3)

其中，D(K1,K2)表示謂語集合K1和潛在聚簇謂語集合K2之間的集合編輯距離.如果K1是K2謂語集合的子集，則D表示從K1到K2的轉(zhuǎn)換代價.否則，K1∪K2取代K2成為新的潛在聚簇謂語中心.這樣，謂語集合K1和K2都需要歸并到新的聚簇謂語中心(式(2)和式(3))，轉(zhuǎn)換代價為2個謂語集合分別轉(zhuǎn)換為聚簇謂語中心的集合編輯距離之和.

算法1.模式聚簇算法(Schema Cluster Algorithm).

輸入:三元組集合T、聚簇模式數(shù)目k;

輸出:聚簇模式集合Ψ.

① 基于相同主語歸并三元組，生成實體集合E.

② 基于實體(集合)e∈E的謂語，生成實體模式(集合)φ∈Φ.

③ 實體模式集合的最大謂語數(shù)目，記為L.

⑤ 依據(jù)聚簇初始化區(qū)域的實體模式數(shù)目為權(quán)重分配聚簇模式數(shù)目，并進行相應的初始化.

⑥ Repeat

⑦ 基于式(1)計算實體模式到每一個當前聚簇中心的集合編輯距離，將其分配給集合編輯距離最小的聚簇中心.

⑧ 更新聚簇中心的謂語集合，使得每一個新聚簇中心能夠包含其所涵蓋實體模式的所有謂語.

⑨ Until no change

⑩ 返回聚簇中心(聚簇模式Ψ).

Fig. 3 Materialization of cluster entity class圖3 物化聚簇實體類

我們將在2.3節(jié)結(jié)合物化聚簇實體類產(chǎn)生的空值現(xiàn)象討論模式聚簇算法的合理性，并給出設置超參數(shù)應當遵循的規(guī)則.

2.3 物化聚簇實體類

本節(jié)將介紹知識圖譜的模式存儲和屬性數(shù)據(jù)類型的特化.知識和元知識組成知識圖譜.知識圖譜的知識三元組經(jīng)過2.2節(jié)的模式聚簇生成一個聚簇模式集合.基于聚簇模式構(gòu)建聚簇實體類，聚簇模式涵蓋的實體模式關聯(lián)的所有實體稱為聚簇實體類的實例對象，即聚簇實體對象.為了進行統(tǒng)一建模，元知識作為附屬陳述與知識進行關聯(lián)，實現(xiàn)元知識的模式化存儲.聚簇實體類的每一個知識謂語連同關聯(lián)的元知識謂語集合形成一個謂語對，一個聚簇實體類的所有謂語對構(gòu)成聚簇實體類的模式信息.這樣，通過模式聚簇算法就將無模式的知識圖譜轉(zhuǎn)換成模式化數(shù)據(jù)，實現(xiàn)對象代理模型對知識圖譜的模式化建模.

聚簇實體類主要負責知識圖譜的模式化存儲建模.在聚簇實體類表中，聚簇實體類的每一個實例對象物化為對象指針(OID)進行類域范圍的唯一性指代.在聚簇代理模型的物化系統(tǒng)中，對象指針有2個突出用途：1)構(gòu)建聚簇模式主表和多值附表之間的關聯(lián);2)支持代理關系類的物化.在聚簇實體類物化時，元知識謂語取得了與關聯(lián)知識謂語相同的地位，分別占據(jù)聚簇實體類表的一個表列.元知識謂語列的一個值構(gòu)成了對知識謂語列相應知識事實的補充陳述.圖3呈現(xiàn)圖1中知識圖譜的模式化物化形式.CEC1和CEC2是聚簇實體類的2個物化模式表.在CEC1表中，元知識謂語列a2_occurIn中的1891代表了一個關于知識事實Ruth, bornIn, USA的補充陳述.

多值屬性廣泛地存在于知識圖譜.例如，一個成人可能擁有多個孩子，一個城市可能擁有多個簡稱等.聚簇實體類的每一個多值謂語關聯(lián)一個附屬表.這個附屬表的模式信息由主表對象指針、多值謂語以及相關元知識謂語集合組成.聚簇實體類的主表和多值附屬表通過對象指針實現(xiàn)了有效的關聯(lián).這樣，通過SELECTION操作而非JOIN操作就可以獲得需要的聚簇實體對象，顯著地提升星型查詢的處理效率.在圖3中，CEC2_hasChild表是主表CEC2中多值屬性hasChild謂語的附屬表.

面向知識和元知識設計強模式的物化策略能夠極大地減少數(shù)據(jù)冗余，加速星型查詢的處理效率.與此同時，這種模式化的存儲設計實際上為每一種謂語屬性(包括知識謂語和元知識謂語)分配了一個特定的表列，這客觀上創(chuàng)造了條件為每一個表列增加面向不同數(shù)據(jù)類型的索引來支持高效的范圍查詢.

一個理想的模式聚簇方法應該滿足這樣一條準則：在聚簇數(shù)目可接受的情況下，物化聚簇實體類應盡可能地減少空值現(xiàn)象.模式聚簇算法是符合這個準則的.極端情況下，將實體模式作為聚簇實體模式，無須進行實際的聚簇操作.一個實體模式設計一個存儲模式，聚簇實體類的物化不會產(chǎn)生任何空值現(xiàn)象.但是，這種情境下卻需要最大數(shù)目的聚簇模式.在聚簇模式數(shù)目(超參數(shù)k)減少時，實體模式就需要進行模式合并，這就造成了空值現(xiàn)象.隨著聚簇模式數(shù)目的逐步減少，將會有更多的實體模式合并成聚簇實體模式或者歸并進當前的聚簇實體模式，聚簇實體類的物化將會產(chǎn)生更多的空值.最后,一種極端情況是將所有的實體模式合并成一個聚簇實體模式，將造成最嚴重的空值現(xiàn)象.但是，這種情況下的聚簇模式數(shù)目又是最少的.因此，在我們提出的模式聚簇算法中，聚簇模式數(shù)目和空值數(shù)目整體上將呈現(xiàn)近似反比的函數(shù)關系.這就給我們提供了一個可操作的設置聚簇模式數(shù)目的規(guī)則：在聚簇模式數(shù)目可接受的情況下，適當?shù)卦龃缶鄞啬Ｊ綌?shù)目就可以減少物化時的空值現(xiàn)象.

2.4 物化代理關系類

知識圖譜查詢處理的瓶頸主要集中于連接操作.知識圖譜查詢通?？梢苑譃樾切筒樵?star-shaped)、鏈式查詢(chain-shaped)和雪花狀查詢(snowflake-shaped)[15]等3種查詢類型.聚簇對象代理模型的強模式存儲特性固有地支持星型查詢.為了加速鏈式和雪花狀等復雜查詢的處理效率，我們提出了采用對象代理機制將復雜對象關系變換為具有特定規(guī)則的對象序列，通過物化具有泛化語義表達能力的對象關系來加速復雜語義關系的特化查詢.

一個代理關系類表達了一種代理規(guī)則,實際上解釋了一組源對象以何種方式關聯(lián)起來展現(xiàn)一種復雜的語義關系.在聚簇對象代理模型中，對象封裝了所有的屬性和動作,由對象指針進行唯一性標識.對象之間的復雜關系可以通過對象指針進行表達，物化代理關系類的過程就是構(gòu)建起一組源類對象指針和一個代理類對象指針之間的映射關系，這樣就實現(xiàn)了輕量級的語義存儲建模.聚簇對象代理模型提供了SELECTION,JOIN和UNION三種原子操作來構(gòu)建代理關系類，這些操作的組合使用能夠表達各種復雜的實體關系.3種原子操作的定義為

1) SELECTION

其中，Cs表示執(zhí)行選擇操作的源類，sp代表選擇規(guī)則，Pdr指代從源類集合繼承的知識謂語和元知識謂語集合組成的謂語對集合.圖4(a)中的對象關系圖呈現(xiàn)了構(gòu)建在以聚簇實體類CEC2為源類的SELECTION代理類的代理規(guī)則，而圖4(a)中的物化表圖則呈現(xiàn)了基于CEC2對象指針的代理關系類的物化形式.

2) JOIN

3) UNION

需要指出的是，聚簇實體類和代理關系類都可以作為源類構(gòu)建上層的代理關系類.SELECTION代理類表達一種面向源對象的選擇規(guī)則，而JOIN代理類則表達2個源類之間存在一種關聯(lián)關系.UNION代理類通過融合多種選擇和連接規(guī)則實現(xiàn)了復雜代理關系的表達.這些原子操作的組合使用能夠支持各種復雜語義關系的建模表示.

一個查詢稱為一個代理關系類的特化查詢意味著這個查詢結(jié)果可以由代理關系類的物化結(jié)果特化生成.與此同時，這個代理關系類也稱為這個查詢的泛化類.直觀來看，一個代理關系類是一個查詢的泛化類需要至少滿足其中一個條件：1)查詢是代理關系類中知識謂語或元知識謂語的屬性實例化;2)查詢是代理關系類的知識謂語或元知識謂語的關系附加.圖5呈現(xiàn)了一個泛化類和2個特化查詢，其中，圖5(a)表示了由SELECTION和JOIN兩個原子操作組合表達的鏈式泛化類，圖5(b)和圖5(c)分別表示了屬性實例化和關系附加2種特化查詢.

Fig. 4 Materialization of deputy relation class圖4 物化代理關系類

Fig. 5 A generalized class and two specialized queries圖5 泛化類和特化查詢

3 實驗與結(jié)果

在本節(jié)中，我們介紹數(shù)據(jù)集和評價指標等實驗設置，采用本文提出的技術(shù)進行知識圖譜的管理，并報告聚簇對象代理模型在減少數(shù)據(jù)冗余和支持范圍查詢方面的有效性.

3.1 實驗設置

3.1.1 數(shù)據(jù)集

我們選擇YAGO2s[12]和LUBM[24]2個數(shù)據(jù)集作為實驗評估的測試數(shù)據(jù).YAGO2s是一個大規(guī)模事實型知識圖譜，主要涵蓋從Wikipedia抽取的各類事實，并整合了WordNet和GeoNames等相關的實體信息.由于YAGO2s是一個真實的知識圖譜數(shù)據(jù)，因而能夠如實地反應生產(chǎn)場景中知識圖譜的各種存儲需求.LUBM是一個大學領域的人工合成型本體庫，廣泛地應用于評估知識型知識圖譜管理系統(tǒng)[5-7,25].LUBM的一個顯著特征是能夠根據(jù)評估需要生成任意大小的知識圖譜，可驗證知識圖譜管理方法的伸縮性.

YAGO2s是由知識陳述和元知識陳述組成的知識圖譜，包含時間、高度以及地理經(jīng)緯度等大量連續(xù)屬性.由于LUBM是一個知識型知識圖譜，因此，我們針對特定的知識陳述進行連續(xù)型元知識陳述的擴展，使其滿足帶有元知識知識圖譜建模的各種評估需要.這些擴展的連續(xù)元知識屬性基于給定的取值范圍隨機生成.表5給出了LUBM連續(xù)元知識屬性的取值范圍.

Table 5 Range of Metadata Expansion表5 元知識擴展范圍

由于YAGO2s沒有提供任何的測試查詢用例，因此，本文采用LUBM提供的查詢用例進行檢索性能的有效性驗證.文獻[24,26]分別給出了設計在LUBM測試集上的評估查詢用例.從這些查詢中選擇至少包含表5中一個謂語的測試用例，移除重復和相似查詢項，剩余查詢組成本文實驗的評估查詢用例.根據(jù)查詢的復雜程度，將這些測試用例分為星型查詢(sq)和復雜查詢(cq)2個類別.最后，對這些評估查詢語句進行元知識屬性的擴展，例如，查詢添加“Year>2005 and Confidence<0.8”的過濾條件.表6呈現(xiàn)了評估查詢語句的分類情況，并給出了新查詢用例和原查詢用例的編號對應關系，其中，lq*和mq*分別表示查詢來自文獻[24]和文獻[26]，而*則表示當前查詢在原查詢用例集的編號.

Table 6 Type of Evaluated Query表6 評估查詢的類別

3.1.2 評估設置

在邏輯存儲建模方面，我們選擇Standard Reified Statement(SRS)[10],Singleton Property Approach(SPA)[9]和YAGO2 Reified Statement(YRS)[12]等3種經(jīng)典的建模方法用于知識圖譜元知識建模的實驗評估.最近一些研究工作通過理論和實驗反復驗證了SRS,SPA以及YRS等方法在知識圖譜建模方面的有效性[27-29].SRS和SPA將知識圖譜建模成三元組，而YRS和CODM則分別采用元組和對象形式進行知識圖譜建模.在語義存儲建模方面，SW-Store[16]和gStore[6]分別是基于謂語建模和基于實體建模的典型代表，而基于查詢的語義存儲建模還沒有發(fā)布支持帶有連續(xù)屬性的知識圖譜建模管理方法.由于gStore已經(jīng)展示了對于SW-Store的壓倒性優(yōu)勢，因此，我們主要以gStore作為語義存儲建模的對比評估方法.

為了評估知識圖譜建模方法對查詢性能的影響，我們需要為不同的建模方法選擇相應的管理系統(tǒng).在邏輯存儲建模方面，現(xiàn)有的RDF3X[4],gStore[6]和Virtuoso[30]等都能夠支持三元組框架的知識圖譜建模管理.但是，由于RDF3X不支持連續(xù)屬性的查詢，因此，選擇gStore和Virtuoso用于SRS和SPA建模的知識圖譜管理.YAGO2[12]推薦了一種基于對象關系型數(shù)據(jù)庫Postgresql的知識圖譜管理方法.由于對象建模的需要,我們選擇Postgresql作為CODM建模的知識圖譜管理系統(tǒng).在語義存儲建模方面，gStore提供了一種在有向圖上進行實體建模的原型系統(tǒng).

在本文實驗中，我們選擇gStore,Virtuoso Open Source 7.2.5以及Postgresql 10.4等版本的知識圖譜管理系統(tǒng).這些管理系統(tǒng)運行在16G內(nèi)存的Ubuntu Desktop 14.04.3操作系統(tǒng)上進行實驗性能的評估.

3.2 空間有效性

基于LUBM數(shù)據(jù)生成器獲得了10 M條的知識陳述，并結(jié)合3.1節(jié)策略補充了相應的元知識陳述，形成了LUBM10M數(shù)據(jù)集.我們分別按照SRS,SPA,YRS以及CODM將LUBM10M和YAGO2s兩個評估測試集轉(zhuǎn)換成相應的知識圖譜邏輯存儲建模表示形式.由于這4種方法采用三元組、元組以及對象等不同形式進行建模，因此，我們以元素數(shù)目取代三元組數(shù)目進行數(shù)據(jù)冗余的評估.一條三元組含有3個元素，而一個對象(元組)的元素數(shù)目則對應于屬性(屬性列)的數(shù)目.類似于文獻[9]，我們將不同知識圖譜建模方法的元素劃分為知識元素、控制元素以及元知識元素3種類別.這種劃分方法有助于評估不同知識圖譜建模方法的哪些具體因素影響知識圖譜建模的數(shù)據(jù)冗余.

1) 知識元素(knowledge element).知識陳述和元知識陳述組成知識圖譜,而知識元素是由知識陳述分解而來.傳統(tǒng)的資源描述框架是知識陳述的主流表達形式，因此，知識元素由知識圖譜中知識陳述的主語、謂語和賓語組成.這樣，一條知識三元組蘊含3個知識元素.

Fig. 6 Space effectiveness of four modelings for logical storage圖6 4種邏輯存儲建模方法的空間有效性

2) 控制元素(handler element).在知識圖譜建模時，控制元素的主要任務是將一條知識陳述轉(zhuǎn)換為一個獨立的知識句柄，用于知識陳述關聯(lián)元知識的陳述聲明.一條知識陳述只有轉(zhuǎn)換成知識句柄才能進行元知識的陳述聲明.不同的知識圖譜建模方法擁有不同的知識句柄化方式.在三元組框架中，SRS需要4條三元組陳述12個控制元素，而SPA則需要2條三元組陳述6個控制元素將一條知識陳述轉(zhuǎn)換成一個知識句柄.在類三元組框架中，YRS需要一個元組陳述ID,Subject,Predicate,Object，4個控制元素句柄化一個知識陳述.由于模式化存儲的緣故，CODM只需要一個對象陳述OID,Subject,Object，3個控制元素建模一個知識陳述.在有n條知識陳述共享一個主語的情況下，CODM的表現(xiàn)更加突出，只需要n+2個控制元素就可以實現(xiàn)這些知識陳述的句柄化.

3) 元知識元素(metadata element).在邏輯存儲建模時，元知識通?；谥R句柄進行陳述聲明.在三元組框架內(nèi)，SRS和SPA分別以知識增強句柄,元知識謂語,元知識賓語和屬性唯一句柄,元知識謂語,元知識賓語的形式關聯(lián)一條元知識陳述.YRS有2種元知識陳述聲明情景.如果存儲模式含有元知識謂語(例如時間、位置和情景)，YRS只需要一個元知識元素聲明一條元知識陳述.否則，YRS則至少需要4個元知識元素來聲明一條元知識陳述.CODM將元知識陳述作為知識陳述的附屬，實現(xiàn)了元知識陳述的模式化存儲.因此，CODM只需要一個元知識元素就可以聲明一條元知識陳述.

我們以LUBM10M和YAGO2s作為評估知識圖譜邏輯存儲建模的數(shù)據(jù)集.在評估空間有效性時，將空值以及標識(YRS的ID和CODM的OID)都作為元素進行統(tǒng)計.圖6展示了4種知識圖譜建模方法的空間存儲情況.在CODM模型中，超參數(shù)代表最終聚簇實體模式的數(shù)目，影響哪些實體模式的實體對象存儲到同一張聚簇模式表.LUBM是一個模擬的知識圖譜數(shù)據(jù)集，擁有12個實體模式，而YAGO2s則是一個真實的知識圖譜數(shù)據(jù)集，實體關系非常復雜，擁有超過2萬多個實體模式.LUBM和YAGO2s都很好地驗證了2.3節(jié)的結(jié)論，即隨著聚簇實體模式的逐步增大，控制元素和元知識元素的空值數(shù)量逐漸減少.從圖6(a)(c)可以看出，隨著聚簇模式數(shù)目的逐漸增加，超參數(shù)對于減少空值的邊際效益是逐步降低的.這種現(xiàn)象表明，只需要設置一個少量的聚簇中心數(shù)目就可以取得令人滿意的聚簇結(jié)果，例如YAGO2s和LUBM10M的超參數(shù)可以設置為1 000和4.

圖6(b)(d)分別呈現(xiàn)了4種邏輯存儲建模方法在2個數(shù)據(jù)集上的建模結(jié)果，其中，CODM在LUBM10M和YAGO2s上的超參數(shù)分別設置為4和10.從橫向比較來看，SRS,SPA和YRS這3種建模方法的控制元素數(shù)量都明顯高于知識元素，而CODM建模的控制元素數(shù)量和知識元素數(shù)目基本保持一致.在元知識建模方面，CODM建模的元知識元素數(shù)量大致保持在SRS和SPA建模的40%～70%之間.YRS和CODM都采用了模式化方法進行元知識建模.但是，由于YRS的存儲模式只涵蓋公有謂語，這樣就造成了大量的空值情況.因此，YRS建模的元知識元素數(shù)量達到了CODM建模的2倍(YAGO2s)到4倍(LUBM10M).總體來看，CODM進行知識圖譜建模能夠極大地減少數(shù)據(jù)冗余，取得了最好的空間存儲優(yōu)勢.

3.3 時間有效性

在3.3節(jié)，我們將從查詢響應時間、數(shù)據(jù)的可伸縮性以及代理機制加速復雜查詢等方面驗證CODM支持范圍查詢的有效性.

知識圖譜建模主要分為邏輯存儲建模和語義存儲建模.邏輯存儲建模構(gòu)建知識陳述和元知識陳述的邏輯關系，其存儲方式則依據(jù)建模方式的不同而有所差異.三元組框架的直接存儲方式就是構(gòu)建三列表分別用于主語、謂語和賓語的存儲，因此，我們在Virtuoso系統(tǒng)上構(gòu)建三列表來存儲標準增強方式(SRS_Virtuoso)和屬性唯一方式(SPA_Virtuoso)生成的知識圖譜數(shù)據(jù).類三元組框架采用YAGO2推薦的存儲方法(YRS_PG)，而聚簇對象代理模型則構(gòu)建模式化存儲(CODM_PG).在語義存儲建模方面，gStore是基于實體聚簇存儲在圖結(jié)構(gòu)上的一種實現(xiàn)方式.由于gStore并不支持屬性唯一方式的元知識邏輯表示，因此，語義存儲建模主要采用標準增強方式進行知識陳述和元知識陳述的邏輯建模表示(SRS_gStore)

聚簇對象代理模型有2個顯著特性.一個是模式化存儲減少數(shù)據(jù)冗余和JOIN操作.以低冗余方式進行知識圖譜建模能夠減少I/O代價，而更少的JOIN操作則能夠縮小查詢的響應時間.另一個特性則是數(shù)據(jù)類型的特化支持，可以構(gòu)建面向特定數(shù)據(jù)類型的索引加速，提升連續(xù)屬性查詢的響應效率.圖7呈現(xiàn)了知識圖譜建模方法的時間有效性.由于系統(tǒng)設計的完備性問題，gStore無法支持BIND語法操作，因此，SRS_gStore沒有sq3的響應時間.

Fig. 7 Time effectiveness of knowledge graph modelings (LUBM10M)圖7 知識圖譜建模方法的時間有效性(LUBM10M)

從邏輯存儲建模角度來看，CODM建模方法取得了最好的查詢響應時間，在所有查詢上均大幅度地領先于其他類型查詢.在三元組框架內(nèi)，標準增強方式(SRS_Virtuoso)在進行知識陳述句柄化過程中產(chǎn)生的控制元素遠遠高于屬性唯一方式(SPA_Virtuoso).因此，不管是星型查詢，還是復雜查詢，標準增強方式需要更多的I/O和JOIN操作，其查詢響應時間也明顯高于屬性唯一方式.三元組框架知識陳述句柄化產(chǎn)生的控制元素數(shù)目多于類三元組框架，但是，三元組框架建模的元知識元素數(shù)量通常少于類三元組框架，因此，這2種建模方法的實際查詢響應時間依賴于具體的連接條件.

從語義存儲建模角度來看，YAGO2(YRS_PG)實現(xiàn)了公共元知識的模式化存儲，而聚簇對象代理模型(CODM_PG)則實現(xiàn)了知識陳述和元知識陳述的完全模式化存儲.因此，這2種存儲建模方式實現(xiàn)了不同程度的實體聚簇，屬于基于實體聚簇的存儲建模方式.從圖7可以看出，CODM_PG和YRS_PG的查詢性能明顯優(yōu)于SRS_gStore的查詢性能.這主要是因為gStore構(gòu)建的類哈希樹索引結(jié)構(gòu)在離散字符型數(shù)據(jù)上擁有非常優(yōu)越的查詢性能，但是，當數(shù)據(jù)含有大量連續(xù)性屬性，特別是涉及范圍查詢時，這種索引結(jié)構(gòu)的性能就表現(xiàn)的不是非常突出.與YRS的部分屬性模式化相比，CODM實現(xiàn)了完全的模式化存儲，不僅避免了大量的連接操作，更重要的是能夠以非常低的代價構(gòu)建面向數(shù)據(jù)類型支持的各種索引結(jié)構(gòu)，自然具有更加優(yōu)秀的查詢性能.

在評估圖7的時間有效性時，聚簇實體類采用了超參數(shù)為4的LUBM10M數(shù)據(jù)集的模式聚簇結(jié)果.超參數(shù)的調(diào)整影響聚簇模式，決定哪些實體存儲到同一個磁盤文件，進而造成了不同的數(shù)據(jù)冗余.由于聚簇對象代理模型實現(xiàn)了面向數(shù)據(jù)類型的索引支持，所有的查詢字面值都是先走索引再讀取磁盤數(shù)據(jù)，因此，超參數(shù)的設置對于查詢響應的影響主要體現(xiàn)在不同數(shù)量的磁盤I/O.由于超參數(shù)的設置對于數(shù)據(jù)冗余和磁盤I/O的影響是類似的，這樣，超參數(shù)對于查詢性能的影響可以參照圖6中超參數(shù)對于數(shù)據(jù)冗余的影響分析得到.因此，本節(jié)不再給出模式聚簇算法的超參數(shù)對于查詢性能的影響.

為了驗證CODM模型的可伸縮性，我們利用LUBM數(shù)據(jù)生成器分別生成10 M,30 M,50 M,70 M以及100 M等5個不同三元組數(shù)量規(guī)模的評估測試集.圖8呈現(xiàn)了8個評估查詢在5個測試評估集上的運行結(jié)果.得益于CODM的模式化邏輯存儲建模和數(shù)據(jù)類型特化，絕大多數(shù)查詢處理的響應時間并沒有隨著數(shù)據(jù)規(guī)模的增大而明顯的擴大，始終維持在500 ms以下，這就很好地驗證了CODM模型能夠有效地支持大規(guī)模知識圖譜的查詢應用.需要指出的是，模式化存儲無法避免非星型查詢之間的連接操作.在數(shù)據(jù)規(guī)模增大時，需要執(zhí)行連接操作的中間結(jié)果也會隨之增大，導致了數(shù)據(jù)規(guī)模對復雜查詢cq2和cq3的響應時間影響比較明顯，這就給驗證代理機制的有效性提供了機會.

Fig. 8 Scalability of CODM圖8 CODM的可伸縮性

Fig. 9 Effectiveness of deputy mechanism圖9 代理機制的有效性

許多實體之間可能存在一些固有的關聯(lián)，例如學術(shù)會議和研究主題.由于知識圖譜主要面向互聯(lián)網(wǎng)用戶，一些特定的歷史事件可能導致相關查詢的急劇增長.對象代理機制可用于建模實體之間的復雜語義關聯(lián)，通過物化固有的泛化對象關系來縮短復雜查詢的響應時間.由于復雜查詢cq2和cq3分別呈現(xiàn)了實體不規(guī)則形狀的固有關系，因此，我們可以分別為這2個查詢創(chuàng)建泛化的代理關系類來物化這2類固有實體關聯(lián).圖9呈現(xiàn)了構(gòu)建在代理機制上的查詢性能，響應時間從原來的幾十秒迅速回落到幾毫秒.因此，通過代理關系類的物化結(jié)果來特化查詢結(jié)果，代理機制能夠極大地降低復雜查詢的響應時間.聚簇實體類構(gòu)建了實體的內(nèi)部關聯(lián)，而代理關系類則構(gòu)建了實體的外部關聯(lián).實驗結(jié)果證明了兩者的配合使用，能夠極大地提升復雜查詢的處理能力.

4 總 結(jié)

本文提出了一種支持范圍查詢的低冗余知識圖譜建模方法-聚簇對象代理模型(CODM).我們設計了集合編輯距離用于知識圖譜聚簇，將無模式的知識圖譜數(shù)據(jù)轉(zhuǎn)換為模式化數(shù)據(jù).在邏輯存儲建模方面，CODM將元知識陳述作為知識陳述的附屬，基于聚簇模式實現(xiàn)知識陳述和元知識陳述的模式化存儲和數(shù)據(jù)類型特化，減少了數(shù)據(jù)冗余，支持了連續(xù)屬性的范圍查詢.在語義存儲建模方面，CODM通過代理機制實現(xiàn)知識圖譜固有關聯(lián)的輕量級語義建模，能夠有效地適應不斷演化的知識圖譜查詢，提升復雜查詢的處理能力.實驗結(jié)果驗證了CODM模型在減少數(shù)據(jù)冗余和支持范圍查詢方面的有效性.

模式聚簇算法的超參數(shù)在一定程度上影響CODM模型的有效性，超參數(shù)的設定與知識圖譜數(shù)據(jù)本身的特性存在很強的關聯(lián)性.此外，CODM模型在實際應用場景中的性能表現(xiàn)依然存在一些不確定因素.因此，CODM模型在現(xiàn)實場景中應用和基于知識圖譜數(shù)據(jù)特征來優(yōu)化超參數(shù)設計將作為下一階段的研究工作.