投入驅動的存儲與計算一體化的事務處理效率優化方法

段玉聰,邵禮旭,曹步清,孫小兵,齊連永

(1.海南大學信息科學技術學院,海南 海口 570228;2.湖南科技大學計算機科學與工程學院,湖南 湘潭 411201;3.揚州大學信息工程學院,江蘇 揚州 225127;4.曲阜師范大學信息科技與工程學院,山東 濟寧 276826)

1 引言

知識圖譜已經成為用帶有標記的有向圖的形式來表示知識，并能賦予文本信息語義的強大工具。知識圖譜是以節點的形式將項目、實體或用戶表示出來，以邊的形式將相互作用的節點鏈接起來構造的圖形，邊可以表示任何語義關系。知識庫包含一組概念、實例和關系[1]。劉嶠等[2]將知識圖譜的構建按照知識獲取的過程分為信息抽取、知識融合和知識加工三個層次，定義知識圖譜是一個具有屬性的實體通過關系鏈接而成的網狀知識庫。Cowie等[3]將信息抽取劃分為實體、關系和屬性三個層次，Sekine等[4]提出了一種包含150種實體的命名實體分類體系。Sen[5]采用主題模型作為相似度計算的依據，從維基百科中獲取了實體目錄，消除不可見文本的引用。Malin等[6]提出利用隨機漫步模型對演員合作網絡數據進行實體消歧，并取得了比基于文本相似度模型更好的消歧效果。Wu等[7]選擇維基百科作為數據源，通過自動抽取生成訓練語料，將其應用于對非結構化數據的實體屬性抽取。對于關系抽取，出現了大量基于特征向量或核函數[8]的監督學習方法、半監督學習方法[9]和弱監督學習方法[10]。Banko等[11]提出了面向開放域的信息抽取方法框架并發布了基于自監督學習方式的開放信息抽取原型系統。Chaim[12]定義了數據、信息和知識等概念，認為軟件服務系統的開發可以從數據、信息和知識的角度分為數據共享、信息傳遞和知識創造等階段[13]。Duan等[14]分別從數據、信息、知識和智慧方面闡明了知識圖譜的架構并提出通過構建數據圖譜、信息圖譜和知識圖譜的架構回答5W問題[15]。

2 資源類型及圖譜定義

從拓展現有知識圖譜(Knowledge Graph)概念的角度出發，本文提出了一種基于數據圖譜DGDIK(Data GraphDIK)、信息圖譜IGDIK(InformationDIK)和知識圖譜KGDIK(Knowledge GraphDIK)三層的可自動抽象調整的解決架構，通過對海量資源進行合理組織和存儲,達到在資源存儲空間中以最高搜索效率找到滿足用戶檢索需求資源的目標。本文對資源元素形態和圖譜的定義如下所示：

定義1(資源元素(ElementsDIK)) 資源元素包括數據資源、信息資源和知識資源三種形態。ElementsDIK:=〈DataDIK,InformationDIK,KnowledgeDIK〉。

定義2(圖譜(GraphDIK)) 本文對已有知識圖譜的概念進行拓展，將圖譜的表達分為數據圖譜、信息圖譜和知識圖譜三層。

GraphDIK:=〈(DGDIK)，(IGDIK)，(KGDIK)〉。

本文對應于DataDIK、InformationDIK、KnowledgeDIK和智慧的遞進層次在整體上澄清知識圖譜的表達，將知識圖譜劃分為DGDIK、IGDIK、KGDIK和智慧圖譜四個層面。現階段本文基于前三層架構對類型化的資源進行構建、存儲、處理和展示，在DGDIK層面上對通過直接觀察到的DataDIK進行建模，在IGDIK和KGDIK上分析自適應的自動抽象的資源優化過程，以支持兼容經驗知識的引入和高效的自動語義分析，在KGDIK上通過關系推理擴展圖譜的點密度和邊密度。表1為對DataDIK、IntormationDIK和KnowledgeDIK等形態的資源以及對應圖譜層次的介紹。

Table 1 Explanation for resource type

定義3(數據圖譜(DGDIK))

DGDIK:=collection{array,list,stack,queue,tree,graph}。

DGDIK是各種數據結構包括數組、鏈表、棧、隊列、樹和圖等的集合。DGDIK上未對DataDIK的準確性進行分析，可能出現不同名稱的DataDIK但表達相同含義，即冗余。DGDIK只能對圖譜上表示的DataDIK進行靜態分析，無法分析和預測DataDIK的動態變化。DataDIK是通過觀察獲得的數字或其他類型信息的基本個體項目，在沒有上下文語境的情況下，DataDIK沒有意義。

定義4(信息圖譜(IGDIK))

IGDIK:=combination{relatedDataDIK}。

IGDIK是相互關聯的DataDIK的組合，InformationDIK是通過DataDIK和DataDIK組合之后的上下文傳達的，經過概念映射和相關關系組合之后的適合分析和解釋的信息。在IGDIK上可進行數據清洗，消除冗余數據。

定義5(知識圖譜(KGDIK))

KGDIK:=collection{StatisticRules}。

KGDIK實質是語義網絡，包括由InformationDIK總結出的統計規則的集合。KGDIK蘊含豐富的語義關系，在KGDIK上通過信息推理和實體鏈接可提高KGDIK的邊密度和節點密度，KGDIK的無結構特性使得其自身可以無縫鏈接。信息推理需要有相關關系規則的支持，這些規則可以由人手動構建，但往往耗時費力，得到復雜關系中的所有推理規則更加困難。使用路徑排序算法將每個不同的關系路徑作為一維特征，通過在KGDIK中構建關系路徑來構建關系分類的特征向量和關系分類器提取關系。

3 面向事務處理的時空效率優化方法

3.1 問題的輸入

首先，給出本文所討論的問題的輸入。

定義6(事務性搜索目標資源集合) 本文將事務性搜索目標資源集合定義為TSR:={TSRD,TSRI,TSRK}，TSR的類型集合為TTSR={ttsrD,ttsrI,ttsrK}，每種資源的規模為ATSR={atsrD,atsrI,atsrK}。

定義7(資源存儲空間(RSS)) 本文將資源存儲空間定義為RSS:={RSSD,RSSI,RSSK}，RSS的類型集合為TRSS={trssD,trssI,trssK}，每種資源的規模為ARSS={arssD,arssI,arssK}。

圖1展示了事務資源的元模型，對資源處理框架的構建和資源建模可提供資源共享、個性化推薦等服務。在建模過程中，資源類型轉換是有必要的，資源類型轉換與目標類型和資源轉換的規模有關，并取決于用戶期望投入。

Figure 1 Meta model of transaction resources圖1 事務型資源元模型

(1)DataDIK到InformationDIK的轉換。

在沒有上下文背景的情況下DataDIK沒有語義，通過概念映射和聚類對直接觀察得到的DataDIK進行處理，將DataDIK進行重組和分類，重組后的DataDIK集合對應不同的類或者概念，由此得到InformationDIK。

(2)InformationDIK到KnowledgeDIK的轉換。

InformationDIK用來表達實體之間的交互和協作，通過分類和抽象交互記錄或行為記錄得到有關實體動態行為的統計規則，即KnowledgeDIK。KnowledgeDIK可以從已知資源中推斷得出，推斷過程中缺乏的必要信息可通過適當的研究技術來收集，例如實驗、調查等。

(3)DataDIK到KnowledgeDIK的轉換。

DataDIK可以從標準的模式中繼承語義關系，被有效地集成并被其他應用重用，海量的DataDIK在集成融合過程中會存在冗余、不一致等現象，在DataDIK向KnowledgeDIK的轉換過程中，通過鏈接數據來源以及納入語義約束識別出最可靠的DataDIK進行融合得到KnowledgeDIK。

圖2給出了由DataDIK轉換成KnowledgeDIK的例子，不同來源的DataDIK(來源1的DataDIK和來源2的DataDIK)在集成融合過程中發生沖突，此時通過引入額外的語義約束“專利類型包括發明專利和實用新型專利”，排除錯誤DataDIK“A機構專利數量為100”。

Figure 2 An example of conversion from DataDIK to KnowledgeDIK 圖2 DataDIK向KnowledgeDIK轉換示例

(4)InformationDIK到DataDIK的轉換。

InformationDIK到DataDIK的轉換過程是從概念集合到資源實例的轉換。InformationDIK表達了實體之間的動態交互和協作，觀察實體對象在某一時刻的靜態狀態得到DataDIK。

(5)KnowledgeDIK到DataDIK的轉換。

根據知識推理，對抽取出的KnowledgeDIK集合建立相關實例，知識節點之間的關系以屬性的方式與實例相關聯，得到DataDIK。

(6)KnowledgeDIK到InformationDIK的轉換。

由已知的KnowledgeDIK通過邏輯推理挖掘隱式存在的資源，知識圖譜的無結構特征使得其可以鏈接和利用更豐富的知識庫幫助用戶做決策，從知識檢索到知識創造的過程中得到InformationDIK。

3.2 問題形式化描述

如圖3所示，其特征在于以計算來決定存儲，以存儲來服務搜索，將以DataDIK、InformationDIK和KnowledgeDIK等形態存在的資源根據在DGDIK、IGDIK和KGDIK上搜索的代價進行存儲，發現資源搜索和存儲的最優方案，優化資源處理和存儲的時空效率。

Figure 3 Resource type combination scheme圖3 資源類型組合方案

3.2.1 資源類型轉移代價計算

問題假定1：假定TSR中資源已在RSS中以任意一種方式存儲完畢。

對TSR中資源的類型集合TTSR的每個元素依次取ElementsDIK中的值，形成組合情形TTSR={ttsrD,ttsrI,ttsrK}，TSR中單位資源向ElementsDIK中定義的資源類型轉換的原子代價如表2所示，則TSR中所有的資源向賦值后對應類型資源轉移的代價(CostMT1)可根據公式(1)來計算：

*ARRS

(1)

Table 2 Atomic cost for conversionof unit resource type in TSR

*ARSS

(2)

Table 3 Atomic cost for conversion ofunit resource type in RSS

3.2.2 處理TSR中資源的計算代價

綜合考慮存儲代價和搜索代價的計算，在不超過用戶投入的方案中選擇綜合代價最低的方案對資源搜索機制和資源存儲方案進行調整，根據公式(3)計算在RSS中搜索TSR中資源所要花費的計算代價(Costc)：

αARSS*SCost+βARSS′

(3)

其中,α和β分別表示圖譜規模和資源類型轉換代價占Costc的權重，均可通過數據訓練得出，ARSS′表示進行類型轉換之后的資源規模。RSS中搜索單位資源TSR的原子代價如表4所示。

Table 4 Atomic cost for searchingunit TSR resource in RSS

3.2.3 存儲與計算協同調整的總代價計算

本文假定已提前獲取到用戶的預期投入(Inve0)和用戶所能接受的最大總代價(Total_Cost0)。根據CostMT1、CostMT2和Costc，計算TSR資源從當前狀態向TTSR中資源類型轉移的代價和TRSS中資源向RSS中資源狀態轉移的代價以及計算代價的總和(Total_Cost)，計算方式如公式(4)所示：

Total_Cost=CostMT1+CostMT2+Costc

(4)

將不同情形下Total_Cost的值與Total_Cost0進行比較，并將與計算所得的Total_Cost對應的方案所需用戶投入(Inve)和Inve0作比較，判斷是否滿足條件“Total_CostTotal_Cost0時，執行下一步操作；用戶投入計算方法如公式(5)所示：

Inve=γ*Total_Cost0-Total_Cost

(5)

其中，γ表示單位代價所需投入，可通過數據訓練得出。

抓培訓，干部隊伍素質進一步提升。林芝市局領導班子高度重視干部培訓工作，積極組織干部赴成都、北京、拉薩、廣東、福建等地參加“四品一械”相關培訓，自主舉辦食品安全、食品藥品抽樣、食品藥品安全協管員培訓班等各類培訓16期，參訓人數共計2000余人次。

算法1計算資源類型不同組合情形下的總代價

輸入：TSR，RSS，ElementsDIK，TotalCost0，Inve0。

輸出：TSR和RSS中資源類型組合的最小總代價。

FOR eachttsrDo

Assign value fromElementsDIK;

ComputeCostMT1;

FOR eachtrssDo

Assign value fromElementsDIK;

ComputeCostMT2,Total_Cost;

IF (Total_Cost

Total_Cost0=Total_Cost;

事務處理效率優化方法的流程如圖4所示。

Figure 4 Process of the collaborative storage and computation adaptation 圖4 存儲與計算一體化方法流程

算法1描述了TSR和RSS中資源不同類型的組合情況，計算每種情況下TSR中資源向TTSR中資源類型轉移的代價，TRSS中資源狀態向RSS轉移的代價，以及每種組合情況下在RSS中搜索TSR中資源的計算代價，找出不超過用戶投入且具有最小Total_Cost的方案作為協同調整資源的最優方案。

4 資源類型轉換效果示意

本文將提出的優化方法應用于以下場景：資源庫中有一個用戶訂單表，并關聯了用戶信息表，訂單表中有1 000萬條用戶記錄信息，用戶信息表中有100萬條用戶采購記錄信息。依據用戶的訂單記錄給用戶推薦合適的產品時，傳統方法是從這1 000萬條記錄中查找出對應用戶id的記錄然后通過分庫、分表等操作進行查詢，然而要在一臺服務器的基礎上不做分庫、分表，就要從這100萬個用戶數據關聯的1 000萬個訂單記錄中，提取出用戶消費相關產品的知識體系，例如按年齡劃分等，依據知識來給用戶進行推薦。本文構建的知識體系形成了新的表，這些新的包含知識的表比原有記錄表的規模小很多，時間是查詢某個用戶id訂單記錄的時間和通過知識推理得出的時間。如圖5所示，本文將不轉換資源類型(方案0)推薦結果準確度設為1，通過比較不同方案向用戶推薦的產品的相似度來衡量用戶滿意度。

Figure 5 Accuracy comparison of resource type conversion results圖5 資源類型轉換結果準確度比較

本文將用戶訂單表關聯的用戶根據年齡進行劃分，再結合采購記錄，建立不同年齡段對商品的偏好體系，例如15～20歲用戶常買學習用品，20～40歲用戶常買服裝個護用品，40～55歲用戶常買生活用品。同時為500個用戶進行商品推薦，方案1～方案4分別是為100個、200個、300個、400個用戶按推理出的商品采購偏好知識體系進行推薦，剩余用戶按分庫分表進行查詢，根據查詢結果進行相似商品推薦。不同方案之間資源類型轉換的目標類型和轉換規模不同，隨著用戶采購商品的記錄數量增多，推薦商品一致性與傳統方法的相似度逐漸升高。知識體系是經過抽象后的可推理的規則，在提取知識體系的過程中所消耗的計算資源和存儲資源都會降低，通過計算未轉換資源類型和轉換資源類型后不同方案的代價差異，選擇在用戶投入范圍內具有最大效益比的方案對優化資源存儲和計算。

5 相關工作

Mccarthy等[16]使用決策樹來學習如何在商業合資企業領域分類不同短語的系統，解決共指消解問題。本體被用作語義網中的知識表示的標準形式[17]，微軟發布的Probase利用統計機器學習算法以數據驅動的方法構建本體[18]。MongoDB作為一種基于分布式文件存儲的數據庫，不適用于高度事務性的系統，基于DGDIK、IGDIK和KGDIK三層架構對資源進行建模，以節點和邊的形式存儲資源，圖譜對自然語言的映射更完整，可以表達實體間任意的語義關系及與或非等邏輯關系。Wang 等[19]通過概念注釋來促進跨語言知識鏈接，促進不同語言的知識共享。潘偉豐等[20]提出服務分類方法并用于服務注冊管理系統中，為服務提供分類信息，提高服務發現、檢索以及服務資源管理的效率。

6 結束語

本文的貢獻在于將以數據、信息和知識等形態的資源根據資源的存儲代價和搜索代價綜合考慮來協同調整資源的搜索機制和存儲方案，優化時空效率。基于DGDIK、IGDIK和KGDIK建立資源處理框架，對不同的資源需求在最匹配的資源層面上進行查找，有效提高查找效率。合理地處理系統中的類型化資源，通過分析和抽象事務處理中海量的DataDIK、InformationDIK和KnowledgeDIK等形態的資源，消除概念歧義，剔除冗余和錯誤概念，提高DataDIK、InformationDIK和KnowledgeDIK等資源的質量。當前工作在各個環節進行了實例討論，下一步將擴大數據規模進行驗證。