支持高效查詢檢索的大數據資源描述模型

張文燚, 項連志, 王小芳

(1. 哈爾濱工程大學 電子政務建模仿真國家工程實驗室，北京 100037； 2. 哈爾濱工程大學 計算機科學與技術學院，黑龍江哈爾濱 150001)

大數據的多樣性(Variety)決定了組成大數據各種不同來源的數據資源之間不可避免地存在著多種形式的結構差異和語義沖突[1]。因此，建立一種能夠屏蔽結構差異和語義沖突的大數據資源統一描述模型，使之以統一的查詢接口形式，支持面向完整大數據資源的高效查詢檢索，對于推動大數據查詢分析應用發展有著重要的理論貢獻和實用價值。

1994年，Gupta P等以DataJoiner的形式給出了一個面向異構分布關系數據資源的統一訪問視圖[2]，1995年，M. J. Carey等通過擴展ODMG-93對象模型，給出了一種為不同來源的異構分布數據資源，提供面向對象的統一視圖的Garlic方法[3]。DataJoiner和Garlic主要研究屏蔽結構差異的技術方法，不能有效解決語義沖突屏蔽問題。Michael Siegel等于1991年給出了一種基于規則的語義規約方法，支持協調不同來源的數據資源的語義沖突[4]，這種語義規約方法雖然具有較高的形式化水平，但它并不提供對數據資源統一描述的支持。1998年，由ORA LASSILA以語義元數據形式給出的資源描述模型RDF，可以有效地用于支持內部大規模、分布式的web數據資源統一描述和查詢導航[5]。2003年，Akiyoshi MATONO給出了一種通過抽取RDF和RDF模式的路徑表達式形成按字典排序后綴數組，支持高效數據資源檢索的索引模式[6]。2006年，YounHee Kim等進一步給出了基于結構的路徑索引和關鍵字索引等兩種RDF和RDF模式索引技術[7]，其關鍵字索引技術發展了1996年Ycmg Kyu Lee等人給出的基于k-ary的關鍵字倒排索引技術[8]，使得基于關鍵字搜索返回的是相關資源而不是整個文檔或標記，從而使大規模、分布式數據資源查詢檢索的效率大幅提高。但是，由于RDF的形式化水平不高，且它沒有給出能夠支持屏蔽結構差異和語義沖突的描述形式，因而它作為數據資源統一描述模型的普適性無法準確判定，同時也無法作為支持高效查詢檢索的大數據資源描述模型直接應用。

可見，建立一種高度形式化的大數據資源統一描述和查詢接口模型，在大數據應用技術發展中具有基礎性地位。擬基于大數據分區管理模型[9]擴展其痕跡屬性，用以構建差異化的大數據信息資源組織模式和支持差異屏蔽的大數據字典；借助由痕跡屬性表達的后綴路徑，并結合大數據字典建立支持大數據資源高效查詢檢索的倒排索引；從而建立一種支持高效查詢檢索的、完全形式化的大數據資源描述模型。

1 大數據分區管理模型及其擴展

其中，場景sT={st1,st2,...|t1,t2,...∈T}是基于活動痕跡st、實體實例消息me(o)和消息m(o)定義的。

1.1 面向場景的切片規則擴展

為了更好地表達大數據信息資源組織模式，需分別面向活動場景和實體實例標識的切片規則擴展相應的痕跡屬性。本小節借助實體實例消息的生成時間、空間和宿主等痕跡屬性，形成3種基于活動場景的切片規則，同時擴展大數據分區管理模型中的一般化子場景為時間子場景、空間子場景和宿主子場景。

2)Ti∩Tj=?，i≠j。

稱sTi={stj|tj∈Ti}為場景sT的時間子場景。

2)Li∩Lj=?，i≠j。

2)Oi∩Oj=?，i≠j。

1.2 面向實體實例標識的切片規則擴展

2)Momi∩Momj=?，i≠j。

2)Loci∩Locj=?，i≠j。

2)Timi∩Timj=?，i≠j。

2)Codi∩Codj=?，i≠j。

1.3 面向場景的分配規則擴展

2 差異化大數據信息資源組織模式

通過引入擴展項泛函刻畫差異化的大數據資源，結合擴展的大數據分區管理模型定義了差異化的大數據資源組織結構及其構造運算，并由此形成支持大數據資源差異屏蔽的大數據字典。

性質1對于擴展項泛函η，有以下等價關系：

5)η(λaj(f))=λaj(f(0))。

證明略。

定義14(屬性值r)稱形如r=(α′,x′) =(η(λaj(α)),η(λaj(x)))的二元組為差異化的屬性值(方言)，其中α′為名稱項，x′為值項，aj∈A為分配主體，A為分配主體集合。一般地，稱rs=(α,x)為標準屬性值。

在大數據資源組織結構中除了表達實體實例狀態的屬性值之外，還存在著一類刻畫資源組織結構標識的元屬性值(αm,xm)，包括：

下面就大數據資源組織結構的構造過程展開討論，該構造過程也為刻畫大數據資源檢索的析構過程提供了研究基礎。

定義19(屬性值關系≤d)設R為屬性值r的集合，≤l為字典序，≤d為R上的二元關系， ≤d定義如下：對于任意ri=(αi,xi)，rj=(αj,xj)∈R，如果滿足以下任意一個條件：

1)αi

2)αi=αj，xi≤lxj

則ri≤drj。

3 大數據資源高效檢索機制

基于差異化大數據信息資源組織模式討論大數據資源高效檢索機制。首先，定義了大數據資源檢索問題，并通過刻畫析構運算及其復合運算，給出了一般化地大數據資源檢索運算；其次，探討了兩種主要的大數據資源檢索模式：遍歷檢索模式和層次檢索模式。同時，基于大數據字典和后綴路徑形成支持大數據資源高效查詢檢索的倒排檢索模式，并將其與遍歷和層次檢索模式進行收斂速度的對比分析。最后，給出了方言模式下的統一查詢機制。

3.1 大數據資源檢索問題和檢索運算

定義22(索引匹配∝cδ)設cδ為索引，對于給定的索引項γ=(αc,xc)，若存在(γk,Sk)∈cδ，使得γ≈γk，≈為索引項等關系，則稱γ在索引cδ上匹配Sk，記為γγcδSk。

索引項等關系≈在不同索引類型下為不同的關系，當cδ為屬性值或多結構化狀態關系標識索引時，≈為取值=；當cδ為場景標識或切片標識索引時，≈為條件等關系。

3.2 大數據資源檢索模式

顯然，析構索引是影響析構運算收斂速度的關鍵要素，依據析構運算各級索引的不同，一般有以下2種檢索模式：

上述檢索模式是逐級析構展開的，下面討論基于倒排索引的一維倒排檢索模式。倒排索引是通過引入類似于RDF路徑表達式后綴數組[6]的后綴路徑，并結合大數據字典形成的。

定義29(檢索運算成本ρ(φ))設φ(R,Λ)為檢索運算，R為大數據資源組織結構，Λ為檢索輸入，則檢索成本ρ(φ)=ρ*(φ)+ρ⊙(φ)，其中ρ*(φ)為索引匹配成本，ρ⊙(φ)為遍歷成本。

不重點討論由于索引匹配算法導致的成本差異，假設所有索引匹配均采用二分查找匹配的方法完成。在實際過程中，可通過算法優化使得索引匹配產生不低于二分查找匹配的收斂效率。

定理1 對于大數據資源檢索問題Q(Λ)，大數據資源倒排檢索運算φcδ su(R,Λ)比φ(R,Λ)更高效地支持大數據資源檢索。

情形1：當φ(R,Λ)為遍歷運算時，檢索成本ρ1(φ)>ρ(φcδ su)。

情形2：當φ(R,Λ)為層次檢索運算時，檢索成本ρ2(φ)>ρ(φcδ su)。

由此可知，遍歷檢索的收斂階為1/nSe，層次檢索的收斂階為1/nSe，倒排檢索的收斂階為1/lb(nSe)，顯然，基于倒排索引的倒排檢索模式要遠優于遍歷檢索模式和層次檢索模式。

4 應用

本小節把大數據資源描述模型應用于國家住房信息系統，并基于大數據分區管理模型，給出了其差異化的大數據資源組織結構和支持資源高效檢索的大數據資源倒排索引，以及方言模式下的統一查詢機制。國家住房信息系統要統一管理全國近300個城市的個人或企事業單位的房產信息，并提供全國房產信息的查詢檢索服務。

5 結束語

1)基于大數據分區管理模型，面向活動場景，擴展實體實例消息的生成時間、空間、宿主等痕跡屬性用于表達切片規則；面向實體實例標識，擴展實體實例的產出母體、產出地點、產出時間、批量編碼等痕跡屬性用于表達切片規則；基于擴展后切片規則形成的大數據切片集和分配主體集，擴展了分配規則，從而形成了支持大數據資源分布式定位描述的基礎。

2)通過引入擴展項泛函刻畫了由分配主體導致的差異化大數據資源，并結合擴展的大數據分區管理模型，給出了差異化大數據信息資源組織模式和支持差異屏蔽的大數據字典。

3)基于差異化信息資源組織模式，給出了大數據資源倒排檢索模式，并證明了其遠比遍歷檢索模式和層次檢索模式高效。

4)把大數據資源描述模型應用于國家住房信息系統，說明了大數據資源描述模型對大數據資源差異屏蔽、高效檢索和方言模式下統一查詢的有效支持。

參考文獻：

[1]DUMBILL E. Planning for big data [M]. Sebastopol：O' Reilly Media, Inc.，2012：9-16.

[2]GUPTA P, LIN E. Datajoiner: a practical approach to multi-database access[C]//Proceedings of the Third International Conference on Parallel and Distributed Information Systems. Austin, USA, 1994: 264.

[3]CAREY M J, HAAS L M, SCHWARZ P M, et al. Towards heterogeneous multimedia information systems: the garlic approach[C]//Fifth International Workshop on Research Issues in Data Engineering. Taipei, 1995: 124-131.

[4]SIEGEL M D, MADNICK S E. A metadata approach to resolving semantic conflicts[C]//Proceedings of the 17th International Conference on Very Large Database Systems. Barcelona, Spain, 1991: 133-145.

[5]LASSILA O, SWICK R R.WD-rdf-syntax-19980216, Resource Description Framework (RDF) model and syntax specification [S]. Boston：W3C,1998.

[6]MATONO A, AMAGASA T, YOSHIKAWA M, et al. An indexing scheme for RDF and RDF schema based on suffix arrays[C]//SWDB. Berlin, Germany, 2003: 151-168.

[7]KIM Y H, KIM B G, LIM H C. The index organizations for RDF and RDF schema[C]//The 8th International Conference of Advanced Communication Technology . Dublin, Ireland , 2006, 3: 1871-1874.

[8]LEE Y K, YOO S J, Yoon K, et al. Index structures for structured documents[C]//Proceedings of the First ACM International Conference on Digital Libraries. Bethesda,USA, 1996: 91-99.

[9]張文燚, 項連志, 王小芳. 大數據分區管理模型及其應用研究[J]. 哈爾濱工程大學學報, 2014,35(3):353-360.

ZHANG Wenyi, XIANG Lianzhi, WANG Xiaofang. Big data partition management model and its application research[J].Journal of Harbin Engineering University, 2014,35(3):353-360.