支持高效查詢檢索的大數(shù)據(jù)資源描述模型

張文燚, 項(xiàng)連志, 王小芳

(1. 哈爾濱工程大學(xué) 電子政務(wù)建模仿真國家工程實(shí)驗(yàn)室，北京 100037； 2. 哈爾濱工程大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱 150001)

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

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

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

1 大數(shù)據(jù)分區(qū)管理模型及其擴(kuò)展

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

1.1 面向場景的切片規(guī)則擴(kuò)展

為了更好地表達(dá)大數(shù)據(jù)信息資源組織模式，需分別面向活動場景和實(shí)體實(shí)例標(biāo)識的切片規(guī)則擴(kuò)展相應(yīng)的痕跡屬性。本小節(jié)借助實(shí)體實(shí)例消息的生成時間、空間和宿主等痕跡屬性，形成3種基于活動場景的切片規(guī)則，同時擴(kuò)展大數(shù)據(jù)分區(qū)管理模型中的一般化子場景為時間子場景、空間子場景和宿主子場景。

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

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

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

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

1.2 面向?qū)嶓w實(shí)例標(biāo)識的切片規(guī)則擴(kuò)展

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

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

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

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

1.3 面向場景的分配規(guī)則擴(kuò)展

2 差異化大數(shù)據(jù)信息資源組織模式

通過引入擴(kuò)展項(xiàng)泛函刻畫差異化的大數(shù)據(jù)資源，結(jié)合擴(kuò)展的大數(shù)據(jù)分區(qū)管理模型定義了差異化的大數(shù)據(jù)資源組織結(jié)構(gòu)及其構(gòu)造運(yùn)算，并由此形成支持大數(shù)據(jù)資源差異屏蔽的大數(shù)據(jù)字典。

性質(zhì)1對于擴(kuò)展項(xiàng)泛函η，有以下等價關(guān)系：

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

證明略。

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

在大數(shù)據(jù)資源組織結(jié)構(gòu)中除了表達(dá)實(shí)體實(shí)例狀態(tài)的屬性值之外，還存在著一類刻畫資源組織結(jié)構(gòu)標(biāo)識的元屬性值(αm,xm)，包括：

下面就大數(shù)據(jù)資源組織結(jié)構(gòu)的構(gòu)造過程展開討論，該構(gòu)造過程也為刻畫大數(shù)據(jù)資源檢索的析構(gòu)過程提供了研究基礎(chǔ)。

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

1)αi

2)αi=αj，xi≤lxj

則ri≤drj。

3 大數(shù)據(jù)資源高效檢索機(jī)制

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

3.1 大數(shù)據(jù)資源檢索問題和檢索運(yùn)算

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

索引項(xiàng)等關(guān)系≈在不同索引類型下為不同的關(guān)系，當(dāng)cδ為屬性值或多結(jié)構(gòu)化狀態(tài)關(guān)系標(biāo)識索引時，≈為取值=；當(dāng)cδ為場景標(biāo)識或切片標(biāo)識索引時，≈為條件等關(guān)系。

3.2 大數(shù)據(jù)資源檢索模式

顯然，析構(gòu)索引是影響析構(gòu)運(yùn)算收斂速度的關(guān)鍵要素，依據(jù)析構(gòu)運(yùn)算各級索引的不同，一般有以下2種檢索模式：

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

定義29(檢索運(yùn)算成本ρ(φ))設(shè)φ(R,Λ)為檢索運(yùn)算，R為大數(shù)據(jù)資源組織結(jié)構(gòu)，Λ為檢索輸入，則檢索成本ρ(φ)=ρ*(φ)+ρ⊙(φ)，其中ρ*(φ)為索引匹配成本，ρ⊙(φ)為遍歷成本。

不重點(diǎn)討論由于索引匹配算法導(dǎo)致的成本差異，假設(shè)所有索引匹配均采用二分查找匹配的方法完成。在實(shí)際過程中，可通過算法優(yōu)化使得索引匹配產(chǎn)生不低于二分查找匹配的收斂效率。

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

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

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

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

4 應(yīng)用

本小節(jié)把大數(shù)據(jù)資源描述模型應(yīng)用于國家住房信息系統(tǒng)，并基于大數(shù)據(jù)分區(qū)管理模型，給出了其差異化的大數(shù)據(jù)資源組織結(jié)構(gòu)和支持資源高效檢索的大數(shù)據(jù)資源倒排索引，以及方言模式下的統(tǒng)一查詢機(jī)制。國家住房信息系統(tǒng)要統(tǒng)一管理全國近300個城市的個人或企事業(yè)單位的房產(chǎn)信息，并提供全國房產(chǎn)信息的查詢檢索服務(wù)。

5 結(jié)束語

1)基于大數(shù)據(jù)分區(qū)管理模型，面向活動場景，擴(kuò)展實(shí)體實(shí)例消息的生成時間、空間、宿主等痕跡屬性用于表達(dá)切片規(guī)則；面向?qū)嶓w實(shí)例標(biāo)識，擴(kuò)展實(shí)體實(shí)例的產(chǎn)出母體、產(chǎn)出地點(diǎn)、產(chǎn)出時間、批量編碼等痕跡屬性用于表達(dá)切片規(guī)則；基于擴(kuò)展后切片規(guī)則形成的大數(shù)據(jù)切片集和分配主體集，擴(kuò)展了分配規(guī)則，從而形成了支持大數(shù)據(jù)資源分布式定位描述的基礎(chǔ)。

2)通過引入擴(kuò)展項(xiàng)泛函刻畫了由分配主體導(dǎo)致的差異化大數(shù)據(jù)資源，并結(jié)合擴(kuò)展的大數(shù)據(jù)分區(qū)管理模型，給出了差異化大數(shù)據(jù)信息資源組織模式和支持差異屏蔽的大數(shù)據(jù)字典。

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

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

參考文獻(xiàn)：

[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]張文燚, 項(xiàng)連志, 王小芳. 大數(shù)據(jù)分區(qū)管理模型及其應(yīng)用研究[J]. 哈爾濱工程大學(xué)學(xué)報, 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.