大數(shù)據(jù)分區(qū)管理模型及其應(yīng)用研究

張文燚，項連志，王小芳

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

大數(shù)據(jù)分區(qū)管理模型及其應(yīng)用研究

張文燚1，項連志2，王小芳1

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

針對大數(shù)據(jù)分區(qū)管理技術(shù)缺乏普遍適用的形式化數(shù)據(jù)分區(qū)模型的問題，引入一個包含痕跡代數(shù)系統(tǒng)、結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)系統(tǒng)、多結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)系統(tǒng)的大數(shù)據(jù)范疇，作為支持大數(shù)據(jù)分區(qū)管理及其相關(guān)應(yīng)用研究的基礎(chǔ)理論模型；在此基礎(chǔ)上，給出了以滿足“本地充足”為目標(biāo)的，由基于活動場景和實體實例標(biāo)識的大數(shù)據(jù)切片規(guī)則，以及面向活動場景的切片分配規(guī)則構(gòu)成的，支持大數(shù)據(jù)分區(qū)管理和快速查詢響應(yīng)的形式化數(shù)據(jù)分區(qū)模型TSEI-PS。TSEI-PS已經(jīng)在住房和城鄉(xiāng)建設(shè)部的信息資源統(tǒng)一規(guī)劃和國家住房信息系統(tǒng)建設(shè)中得到了應(yīng)用。

大數(shù)據(jù)；形式化數(shù)據(jù)分區(qū)；本地充足；痕跡代數(shù)；結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)；多結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)；范疇

分區(qū)管理技術(shù)是大數(shù)據(jù)應(yīng)用的基礎(chǔ)性技術(shù)。與小數(shù)據(jù)所采用的記錄事物屬性的樣本數(shù)據(jù)模式不同，大數(shù)據(jù)采用全面記錄場景活動的全體數(shù)據(jù)模式［1］。大數(shù)據(jù)呈現(xiàn)出大量、多樣、生成快速的明顯特征［2］。大數(shù)據(jù)應(yīng)用對于分區(qū)管理、分類認(rèn)知和高速處理的計算技術(shù)有強(qiáng)烈的需求。普遍適用的大數(shù)據(jù)分區(qū)管理模型，對大數(shù)據(jù)應(yīng)用相關(guān)技術(shù)發(fā)展具有重要意義。

目前，已有的大數(shù)據(jù)應(yīng)用研究主要集中在2個方面［3］：Shared Nothing架構(gòu)下的大規(guī)模并行處理MPP技術(shù)和構(gòu)建在分布式文件系統(tǒng)（GFS）上的MapReduce+Bigtable技術(shù)。

MPP依賴基于關(guān)系數(shù)據(jù)庫的數(shù)據(jù)分區(qū)技術(shù)，主要的相關(guān)研究分別從冗余數(shù)據(jù)最少和檢索成本最低2個方向展開。一方面是以尋求綜合檢索成本最低的數(shù)據(jù)分區(qū)策略為目標(biāo)的研究。1983年，Sacca D等證明，基于關(guān)系數(shù)據(jù)庫的數(shù)據(jù)分區(qū)問題是一個NP難問題［4］。1990年，Shahram等通過分析查詢的資源需求、系統(tǒng)處理能力、增加額外節(jié)點用于執(zhí)行查詢的成本和搜索范圍表的成本，給出了一種為每個查詢求得合適并行度的實用分區(qū)策略HRPS［5］。該策略先測算出使查詢響應(yīng)時間最小化的每個數(shù)據(jù)分區(qū)的元組數(shù)，再依據(jù)該元組數(shù)用Range方法形成數(shù)據(jù)切片，最后使用round-robin方法將這些切片順序地分配到處理節(jié)點上。2010年，Carlo等關(guān)于事務(wù)工作負(fù)載驅(qū)動的數(shù)據(jù)分區(qū)方法的研究最終證明，使得分布處理事務(wù)數(shù)量最小的數(shù)據(jù)分區(qū)問題也是NP難問題［6］。另一方面，E.Wong等在1983年就指出，由于操作頻率不易獲取和不穩(wěn)定、成本函數(shù)不易預(yù)估，以及成本最小化策略不易獲取等因素，以檢索和更新操作成本最低為目標(biāo)的數(shù)據(jù)分區(qū)問題研究并不是特別有用［7］。E.Wong等認(rèn)為高度并行化是操作高效性的基礎(chǔ)，而本地數(shù)據(jù)資源充足和最小冗余是高度并行化中令人滿意的性質(zhì)，因此建議，數(shù)據(jù)分區(qū)應(yīng)以檢索和更新操作的快速查詢響應(yīng)（高效性）為目標(biāo)，從滿足查詢的本地數(shù)據(jù)資源充足和分區(qū)管理的數(shù)據(jù)資源最小冗余出發(fā)，研究關(guān)系數(shù)據(jù)庫的分區(qū)問題。E.Wong等給出了把數(shù)據(jù)庫語義模式圖作為可劃分森林，通過劃分森林中每一棵樹的根節(jié)點，誘導(dǎo)出其他非根節(jié)點劃分的數(shù)據(jù)分區(qū)策略。但是，E.Wong等并沒有給出一個普適性的支持本地充足和最小冗余的數(shù)據(jù)分區(qū)模型，從而限制了這種數(shù)據(jù)分區(qū)策略的推廣應(yīng)用。

Fay Chang等以支持分區(qū)數(shù)據(jù)快速查詢響應(yīng)為目標(biāo)，在2006年提出了構(gòu)建在分布式文件系統(tǒng)之上的多維有序數(shù)據(jù)映射模型［8］，該模型通過引入未經(jīng)解釋的字節(jié)數(shù)組和由行鍵、列鍵、時間戳構(gòu)成的三維索引，給出了一種按行鍵字典序組織數(shù)據(jù)、以多個鄰行（tablet）為邏輯管理單元和組成tablet的（多個）SSTable為物理存儲單元的，統(tǒng)一支持面向結(jié)構(gòu)化、半結(jié)構(gòu)化和非結(jié)構(gòu)化數(shù)據(jù)的，數(shù)據(jù)分區(qū)管理和分布查詢策略?；诙嗑S有序數(shù)據(jù)映射模型實現(xiàn)的Bigtable，借助MapReduce技術(shù)［9］實現(xiàn)對tablets的并行處理和結(jié)果返回，借助分布式文件系統(tǒng)（GFS［10］）支持?jǐn)?shù)據(jù)及日志文件的分布式高效存取和集群式高可用性，從而形成了一個面向大數(shù)據(jù)處理的相對完整的技術(shù)架構(gòu)。但是，多維有序數(shù)據(jù)映射模型沒有給出確定tablet和SSTable形式化規(guī)則，相應(yīng)的技術(shù)體系架構(gòu)缺乏完備一致的理論支持。

顯然，以支持分區(qū)數(shù)據(jù)快速查詢響應(yīng)為目標(biāo)的大數(shù)據(jù)分區(qū)技術(shù)研究具有重要的現(xiàn)實意義，統(tǒng)一支持結(jié)構(gòu)化、半結(jié)構(gòu)化、非結(jié)構(gòu)化和多結(jié)構(gòu)化數(shù)據(jù)分區(qū)管理和快速查詢響應(yīng)的形式化數(shù)據(jù)分區(qū)模型，在大數(shù)據(jù)分區(qū)技術(shù)研究中處于基礎(chǔ)地位。本文在將大數(shù)據(jù)還原為場景活動痕跡的基礎(chǔ)上，構(gòu)造一個包含痕跡代數(shù)系統(tǒng)、結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)系統(tǒng)、多結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)系統(tǒng)的大數(shù)據(jù)范疇，作為支持大數(shù)據(jù)分區(qū)管理及其相關(guān)應(yīng)用研究的基礎(chǔ)理論模型。

1 刻畫場景活動的痕跡代數(shù)

John H.Holland在復(fù)雜適應(yīng)系統(tǒng)（complex adaptive system，CAS）相關(guān)的研究中，給出了一個由適應(yīng)性主體和環(huán)境構(gòu)成的場景活動模型，用于表達(dá)復(fù)雜的自然系統(tǒng)或社會系統(tǒng)活動。場景活動的過程形式是：適應(yīng)主體的基本交互方式為通過探測器感知環(huán)境變化形成刺激消息，驅(qū)動內(nèi)部規(guī)則執(zhí)行行為決策過程，最終產(chǎn)生效應(yīng)消息激活效應(yīng)器，驅(qū)動主體行為落實［11］。這使得我們可以把全面記錄場景活動的大數(shù)據(jù)等同于CAS場景活動消息集。

注意到CAS系統(tǒng)中的適應(yīng)主體和環(huán)境對象均可視為實體存在實例，任何實體實例都可以是系統(tǒng)觀察者，于是本文稱系統(tǒng)觀察者產(chǎn)生的與實體實例關(guān)聯(lián)的狀態(tài)變化為實體實例消息，稱觀察者為實體實例消息的宿主，且任意實體實例消息中都包含有實體實例的唯一標(biāo)識。

1.1 實體實例消息的定義

定義1（有限符號分類集合空間SQ） 給定一個有限符號分類集合空間SQ＝｛S1，S2，…，Sn｝，其中Si為符號集合。

序列化的符號集是描述信息的基本單元，稱之為項，如2013-07-25，這是一個由數(shù)字和符號組成的序列。

定義3（消息m（o）） 稱形如m（o）＝（id，l，o，的四元組為消息，其中id代表消息編號，l代表消息的出生地，o代表產(chǎn)生消息的宿主，x～＝（X，f）為擴(kuò)展項，代表消息的內(nèi)容，其中：

擴(kuò)展項存在3種情況：

定義4（實體實例消息me（o））稱形如me（o）＝為實體實例的消息，其中代表實體實例標(biāo)識，其中I＝ ＜i1，i2，… ＞為名稱項腳標(biāo)序列，m（o）為消息。

當(dāng)實體實例為適應(yīng)主體時，實體實例消息可能包括主體內(nèi)部活動消息。

1.2 活動痕跡與場景

基于實體實例消息，可以形式化地定義活動場景及其痕跡。

約定：x·y代表y是x的一個分量。

定義5（活動痕跡st） 稱st＝（t，Me（O））為活動痕跡，其中t是實體實例消息的產(chǎn)生時刻，Me（O）＝是t時刻所有宿主產(chǎn)生的實體實例消息集合，O代表宿主集合，IDj代表消息編號集合，ID為消息編號全集。

當(dāng)實體實例為適應(yīng)主體時，活動痕跡可能包括主體內(nèi)部活動痕跡。

定義6（場景sT） 稱sT＝｛st1，st2，…|t1，t2，…∈T｝為場景。顯然每個時刻的活動痕跡為當(dāng)前時刻場景與上一刻場景之間的變化，即sti＝sTi-sTi-1，其中Ti＝Ti-1∪｛ti｝。

主體內(nèi)部活動痕跡構(gòu)成內(nèi)部場景，其他活動痕跡構(gòu)成外部場景，本文將內(nèi)部場景和外部場景視為統(tǒng)一場景。

1.3 痕跡代數(shù)

注意到CAS中用一個（可標(biāo)識的）效應(yīng)器組合來描述主體的活動，其過程是：先由環(huán)境通過一組感應(yīng)器將（認(rèn)知）信息以消息的形式傳遞給主體，一旦被（條件）合適的消息所激活，效應(yīng)器將（按規(guī)則）對環(huán)境中的具體（鎖定）部分落實具體行為［11］。其中，一個隱含的事實是，鎖定就意味著行為必然落實。

本文把CAS中的主體活動表達(dá)為場景中的痕跡（消息）運算組合，進(jìn)而可以把CAS表達(dá)為一個痕跡代數(shù)系統(tǒng)。這使得我們可以用痕跡代數(shù)系統(tǒng)表達(dá)復(fù)雜的自然系統(tǒng)或社會系統(tǒng)，從而真實完整地記錄自然系統(tǒng)或社會系統(tǒng)運行和演化過程的原始痕跡。

定義7（主體a） 稱形如a＝（tag，P，R，L，B）的五元組為主體，其中：

1）tag代表標(biāo)識，標(biāo)識是 n元項 tag＝｛tag1，tag2，…，tagn｝，其中tagi是項，本文稱之為標(biāo)識項。

4）稱形如?＝（f?，L）的二元組為鎖定?，其中f?∈F為被鎖定對象的消息結(jié)構(gòu)，F(xiàn)為結(jié)構(gòu)集合，L＝｛αk，k＝1，2，…｝為被鎖定的名稱項集合。 記所有鎖定?的集合為L。

5）稱形如b＝（fb，Δ）的二元組為行為落實b，其中fb∈F為行為落實對象的消息結(jié)構(gòu)，F(xiàn)為結(jié)構(gòu)集合，為行為落實對象的狀態(tài)變化，變化后所達(dá)到的值項和編碼。記所有行為落實b的集合為B。

定義8（認(rèn)知運算opp） 設(shè)sT為場景，st∈sT為活動痕跡，opp為sT上的一元運算，p＝（fp，c＾），認(rèn)知運算定義如下：

其中：

定義9（規(guī)則運算opr） 設(shè)sT為場景，給定任意st1，st2∈sT為活動痕跡，opr為sT上的二元運算，，規(guī)則運算定義如下：

其中：

定義10（鎖定運算op?） 設(shè)sT為場景，st∈sT為活動痕跡，op?為sT上的一元運算，?＝（f?，L），鎖定運算定義如下：

其中：

定義11（行為落實運算opb） 設(shè)sT為場景，st∈sT為活動痕跡，opb為 sT上的一元運算，b＝，行為落實運算定為

其中：

定理1（痕跡代數(shù)） 設(shè)sT為場景，則S＝＜sT，opp，opr，op?，opb＞是一個代數(shù)，本文稱之為痕跡代數(shù)。

證：顯然，opp，opr，op?，opb為sT上的運算，則S是痕跡代數(shù)。

2 狀態(tài)關(guān)系代數(shù)

上節(jié)中，大數(shù)據(jù)是以原始痕跡記錄的形式存在的，這種形式能夠充分完整地表達(dá)大數(shù)據(jù)所包含的語義，但不方便對大數(shù)據(jù)進(jìn)行管理。本節(jié)通過在關(guān)系代數(shù)［12］上引入時間元素表達(dá)屬性狀態(tài)，擴(kuò)展構(gòu)造狀態(tài)關(guān)系代數(shù)，以支持建立大數(shù)據(jù)管理形式化模型。

2.1 結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)

定義12（結(jié)構(gòu)化狀態(tài)關(guān)系Rt） 稱形如Rt＝的集合為結(jié)構(gòu)化狀態(tài)關(guān)系，其中idk為結(jié)構(gòu)化狀態(tài)關(guān)系元組標(biāo)識，為結(jié)構(gòu)化狀態(tài)關(guān)系元組的誕生時刻，為結(jié)構(gòu)化狀態(tài)關(guān)系元組的記錄時刻，τk＝｛（Ai，vki），i＝1，2，…｝是結(jié)構(gòu)化狀態(tài)關(guān)系元組，Ai為屬性名，vki為屬性值，與的消息擴(kuò)展項中的αi和xi相對應(yīng)。 記attr（Rt）＝｛Ai，i＝1，2，…｝為結(jié)構(gòu)化狀態(tài)關(guān)系屬性集。

注釋idk可以是由一組屬性值按指定順序連接而成，即，其中I＝＜ i1，i2，… ＞ 為屬性腳標(biāo)序列。

定理2 設(shè) Ωt為結(jié)構(gòu)化狀態(tài)關(guān)系集合，則為一個代數(shù)，本文稱之為結(jié)

2.2 多結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)

結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)充分表達(dá)了大數(shù)據(jù)中的結(jié)構(gòu)化數(shù)據(jù)，但未能支持半結(jié)構(gòu)化和非結(jié)構(gòu)化數(shù)據(jù)的表達(dá)。本節(jié)通過引入符號序列組成的項表達(dá)多種結(jié)構(gòu)，改造結(jié)構(gòu)化狀態(tài)關(guān)系，以支持建立結(jié)構(gòu)化、半結(jié)構(gòu)化和非結(jié)構(gòu)化的多結(jié)構(gòu)化數(shù)據(jù)管理形式化模型。

定理3 設(shè)Ωt為多結(jié)構(gòu)化狀態(tài)關(guān)系的集合，則是一個代數(shù)，本文稱之為多結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)。

3 大數(shù)據(jù)范疇

本文將以痕跡代數(shù)系統(tǒng)S，結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)系統(tǒng)Ω和多結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)系統(tǒng)三個對象，以及從S到Ω的態(tài)射g：S→Ω，從S到的態(tài)射和從Ω到的態(tài)射h：建立大數(shù)據(jù)范疇。閱讀本節(jié)內(nèi)容需要了解相關(guān)的代數(shù)和范疇的基礎(chǔ)理論知識，未說明的相關(guān)概念和理論請參考文獻(xiàn)［13-15］。

定理4（大數(shù)據(jù)范疇C） C由以下內(nèi)容組成（見圖1）：

那么C為范疇［15］，稱之為大數(shù)據(jù)范疇。

證明略。

定理5 設(shè)C為大數(shù)據(jù)范疇，對于對象S和Ω，態(tài)射g：S→Ω，有：

1）對任意ξ＝｛st|st∈sT，me∈st，me·m·id∈IDq｝，，必然存在，使得

2）對任意ξ＝｛st|st∈sT，me∈st，me·m·id∈ID1∪ID2｝，，必然存在使得

3）對任意ξ＝｛st|st∈sT，me∈st，me·m·id∈ IDq｝，? ＝ （f?，L?），必然存在，使得

證明略。

圖1 大數(shù)據(jù)范疇?wèi)B(tài)射圖Fig.1 Big data category morphism figure

上述定理證明了痕跡代數(shù)中的認(rèn)知、規(guī)則、鎖定與狀態(tài)關(guān)系代數(shù)中的約束、關(guān)聯(lián)、投影的運算可保持性，說明了認(rèn)知、規(guī)則、鎖定構(gòu)成的運算模式可態(tài)射為結(jié)構(gòu)化狀態(tài)關(guān)系中的約束、關(guān)聯(lián)、投影構(gòu)成的運算模式。盡管痕跡代數(shù)的行為落實運算沒有與狀態(tài)關(guān)系保持運算，但鎖定意味著行為必然落實，說明了在發(fā)生鎖定時，場景中必然會存在行為落實運算的結(jié)果，因此，行為落實運算對于其他3個運算并無影響。

對任意ξ＝ ｛st|st∈sT，me∈st，me·m·id∈，必然存在使得

證明略。

證明略。

痕跡代數(shù)到結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)，痕跡代數(shù)到多結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)，以及結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)到多結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)的態(tài)射的運算可保持性，說明了痕跡代數(shù)與狀態(tài)關(guān)系代數(shù)的數(shù)據(jù)域是可對應(yīng)的，即痕跡代數(shù)中的實體實例消息可對應(yīng)到狀態(tài)關(guān)系中的元組。

4 數(shù)據(jù)分區(qū)管理

注意到對于單變量類的語義查詢，橫向數(shù)據(jù)分區(qū)總是能夠滿足本地充足的要求［7］，故假設(shè)每個結(jié)構(gòu)化／多結(jié)構(gòu)化狀態(tài)關(guān)系都進(jìn)行橫向劃分。則接下來的問題是在結(jié)構(gòu)化／多結(jié)構(gòu)化狀態(tài)關(guān)系數(shù)據(jù)庫上如何實施數(shù)據(jù)橫向分區(qū)：本文采取基于實體實例標(biāo)識和場景的數(shù)據(jù)切片規(guī)則，和面向?qū)嶋H場景的切片分配規(guī)則，即對于給定的子場景集合，首先確定結(jié)構(gòu)化／多結(jié)構(gòu)化狀態(tài)關(guān)系中每一個結(jié)構(gòu)化／多結(jié)構(gòu)化狀態(tài)關(guān)系元組對應(yīng)的實體實例消息，及實體實例消息的實體實例標(biāo)識和所在子場景，然后基于場景和實體實例標(biāo)識進(jìn)行兩級數(shù)據(jù)劃分形成數(shù)據(jù)切片；按子場景將切片匯聚成切片集合，并分配到處理節(jié)點上，本文稱這種方法為TSEI-PS（trace-scene and entityinstance based partitioning strategy）。

4.1 結(jié)構(gòu)化狀態(tài)關(guān)系形式化數(shù)據(jù)分區(qū)模型

設(shè)結(jié)構(gòu)化狀態(tài)關(guān)系Rt的集合為Ωt，其對應(yīng)的場景活動痕跡st的集合為sT，即g（sT）＝Ωt，由態(tài)射g：S→Ω的定義可知，對Rt中任意的元組τk，存在實體實例消息（｛（αi，xi，ci）｝，f））），使得g me·m( )＝τk。

記 Lj＝ {lj1，lj2，…，ljnj}為實體實例消息的出生地的集合，j＝1，2，…，m，k＝ 1，2，…，nj。所有實體實例消息me（o）出生地的集合記為L L。

對于任意實體實例消息me∈sT，若me·m·l∈ Lj，則

定義19 稱 PP1j是結(jié)構(gòu)化狀態(tài)關(guān)系Rt基于子場景的一個數(shù)據(jù)切片，如果滿足以下條件：

定義20 給定結(jié)構(gòu)化狀態(tài)關(guān)系Rt，和基于結(jié)構(gòu)化狀態(tài)關(guān)系元組標(biāo)識的約束條件，稱是 Rt關(guān)于的一個數(shù)據(jù)切片。

對任意結(jié)構(gòu)化狀態(tài)關(guān)系Rt，給定子場景1，2，…，m，基于實體實例標(biāo)識的約束條件1，2，…，n，且，那么Rt的數(shù)據(jù)切片規(guī)則為：

對于任意結(jié)構(gòu)化狀態(tài)關(guān)系Rt，給定由上述切片規(guī)則生成的數(shù)據(jù)切片集合，j＝1，2，…，m，i＝1，2，…，n，和與場景對應(yīng)的處理節(jié)點j，j＝1，2，…，m，令，則有序?qū)槊嫦蜃訄鼍暗囊粋€分配，那么切片集合 PP1?2面向子場景，j＝1，2，…，m的切片分配規(guī)則為

4.2 多結(jié)構(gòu)化狀態(tài)關(guān)系形式化數(shù)據(jù)分區(qū)模型

與結(jié)構(gòu)化狀態(tài)關(guān)系數(shù)據(jù)分區(qū)類似，多結(jié)構(gòu)化狀態(tài)關(guān)系同樣采用基于場景和實體實例標(biāo)識的切片規(guī)則，以及面向場景的切片分配規(guī)則。類似地可以給出多結(jié)構(gòu)化狀態(tài)關(guān)系的數(shù)據(jù)切片規(guī)則和切片分配規(guī)則。

下面對結(jié)構(gòu)化／多結(jié)構(gòu)化狀態(tài)關(guān)系數(shù)據(jù)分區(qū)是否滿足本地充足的問題進(jìn)行討論。E.Wong定義數(shù)據(jù)分區(qū)（物化）M的本地充足是指處理給定的語義查詢類Q中的每一個查詢都無需在處理節(jié)點之間移動數(shù)據(jù)［7］。自然語義查詢是場景中用戶為完成活動目標(biāo)，在狀態(tài)關(guān)系數(shù)據(jù)庫上發(fā)起的數(shù)據(jù)訪問操作，則該自然語義查詢類等價于場景活動，而每一個結(jié)構(gòu)化／多結(jié)構(gòu)化狀態(tài)關(guān)系分區(qū)是按場景匯聚的，顯然自然語義查詢所涉及的數(shù)據(jù)資源包含在結(jié)構(gòu)化／多結(jié)構(gòu)化狀態(tài)關(guān)系分區(qū)之內(nèi)，那么結(jié)構(gòu)化／多結(jié)構(gòu)化狀態(tài)關(guān)系分區(qū)關(guān)于自然語義查詢類是本地充足的。另外，由于存儲等硬件設(shè)施的快速發(fā)展，實際應(yīng)用技術(shù)對數(shù)據(jù)冗余的約束不強(qiáng)，故本文忽略該因素。

5 應(yīng)用

作為TSEI-PS的應(yīng)用描述，本節(jié)簡要討論文獻(xiàn)［7］中對于給定的語義查詢類，如何劃分“公司”數(shù)據(jù)庫使其滿足本地充足的數(shù)據(jù)分區(qū)問題。“公司”狀態(tài)關(guān)系數(shù)據(jù)庫包含雇員（emp），部門（dept），工作（job），授權(quán)（qualified）和經(jīng)理（mgr）等結(jié)構(gòu)化狀態(tài)關(guān)系，具體描述如下：

其中：

其中：

設(shè)該結(jié)構(gòu)化狀態(tài)關(guān)系數(shù)據(jù)庫對應(yīng)的場景sT為一個帶有分公司的全國性公司，分布在全國m個城市，與結(jié)構(gòu)化狀態(tài)關(guān)系元組對應(yīng)的實體實例消息可描述如下：

其中：

對于給定的m個與城市場景對應(yīng)的處理節(jié)點j，j＝1，2，…，m，則雇員的切片分配規(guī)則為，其中，為面向城市j場景的切片集合，并被分配到節(jié)點j上。

其余結(jié)構(gòu)化狀態(tài)關(guān)系的數(shù)據(jù)分區(qū)方法與雇員的類似，這里不再重復(fù)論述。顯然，數(shù)據(jù)分區(qū)關(guān)于單變量的語義查詢是本地充足的。此外，一個城市場景中的雇員（emp），部門（dept），工作（job），授權(quán)（qualified）和經(jīng)理（mgr）等結(jié)構(gòu)化狀態(tài)關(guān)系均分布在相同的城市場景處理節(jié)點上，因此對作用于結(jié)構(gòu)化狀態(tài)關(guān)系雇員與部門、雇員與經(jīng)理、部門與經(jīng)理，及經(jīng)理與雇員之上的關(guān)聯(lián)操作都是在同一個城市的狀態(tài)關(guān)系分區(qū)上進(jìn)行的。因此全國性公司形成的數(shù)據(jù)分區(qū)關(guān)于自然語義查詢是本地充足的。

6 結(jié)論

首先，本文基于對 CAS場景活動痕跡的刻畫，以及對經(jīng)典關(guān)系代數(shù)系統(tǒng)的擴(kuò)展和改造，建立了由痕跡代數(shù)系統(tǒng)S，結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)系統(tǒng)Ω和多結(jié)構(gòu)化狀態(tài)關(guān)系代數(shù)Ω三個對象，以及從S到Ω的態(tài)射g：S→Ω，從S到Ω的態(tài)射g-：S→Ω和從Ω到Ω的態(tài)射h：Ω→Ω構(gòu)成的大數(shù)據(jù)范疇，作為支持大數(shù)據(jù)分區(qū)管理及其相關(guān)應(yīng)用研究的基礎(chǔ)理論模型。其次，本文給出了以滿足“本地充足”為目標(biāo)的，基于活動場景和實體實例標(biāo)識的大數(shù)據(jù)切片規(guī)則的形式化表達(dá)，以及面向活動場景的切片分配規(guī)則的形式化表達(dá)，并由此形成了一種支持大數(shù)據(jù)分區(qū)管理和快速查詢響應(yīng)的形式化數(shù)據(jù)分區(qū)模型 TSEI-PS。最后，本文把TSEI-PS應(yīng)用于文獻(xiàn)［7］提出的基于語義模型的數(shù)據(jù)分區(qū)討論，有效地降低了數(shù)據(jù)分區(qū)討論的復(fù)雜度，并且使數(shù)據(jù)分區(qū)討論更具有形式一般性和普適可操作性。

［1］維克托·邁爾-舍恩伯格，肯尼思·庫克.大數(shù)據(jù)時代——生活、工作與思維的大變革［M］.杭州：浙江人民出版社，2012：30-37.

［2］DUMBILL E.Planning for big data［M］.Sebastopol：O’Reilly Media，Inc.，2012：9-16.

［3］MADDEN S.From databases to big data［J］.IEEE Internet Computing，2012，16（3）：4-6.

［4］SACCA D，WIEDERHOLD G.Database partitioning in a cluster of processors［J］.VLDB，1983：242-247.

［5］GHANDEHARIZADEH S，DEWITT D J.Hybrid-range partitioning strategy：a new declustering strategy for multiprocessor database machines［C］／／Proceedings of the 16th International Conference on Very Large Data Bases.San Francisco：Morgan Kaufmann Publishers Inc.，1990：481-492.

［6］CURINO C，JONES E，ZHANG Y，et al.Schism：a workload-driven approach to database replication and partitioning［J］.VLDB Endowment，2010，3（1／2）：48-57.

［7］WONG E，KATZ R H.Distributing a database for parallelism［J］.ACM SIGMOD Record，1983，13（4）：23-29.

［8］CHANG F，JEFFREY D，GHEMAWAT S，et al.Bigtable：a distributed structured data storage system［C］／／7th OSDI.Berkeley：USENIX Association，2006：305-314.

［9］DEAN J，GHEMAWAT S.MapReduce：simplified data processing on large clusters［J］.Communications of the ACM，2008，51（1）：107-113.

［10］GHEMAWAT S，GOBIOFF H，LEUNG S T.The Google file system［J］.ACM SIGOPS Operating Systems Review，2003，37（5）：29-43.

［11］約翰·H·霍蘭.隱秩序——適應(yīng)性造就復(fù)雜性［M］.上海：上海科技教育出版社，2000.

［12］CODD E F.A relational model of data for large shared data banks［J］.Communications of the ACM，1970，13（6）：377-387.

［13］賀偉.范疇論［M］.北京：科學(xué)出版社，2006：1-22.

［14］ASPERTI A，LONGO G.Categories，types，and structures［M］.Cambridge：MIT Press，1991：1-9.

［15］AWODEY S.Category theory［M］.2nd ed.New York：Oxford University Press，2010：1-28.

Big data partition management model and its application research

ZHANG Wenyi1，XIANG Lianzhi2，WANG Xiaofang1

（1.Modeling and Emulation in E-government National Engineering Laboratory，Harbin Engineering University，Beijing 100037，China；2.College of Computer Science and Technology，Harbin Engineering University，Harbin 150001，China）

Because of the big data partition management technique＇s lack of a universally applicable formalized data partition model，this paper introduces a big data category that contains a trace algebra system，structural state relational algebra system and multi-structural state relational algebra system，as the basic theoretical model for supporting partition management and its application research.On this basis，this paper details a formalized data partition model known as trace-scene and entity-instance based partitioning strategy（TESI-PS）that supports big data partition management and rapid query response，with the goal of meeting＂local sufficiency＂.It is made up of the big data partitioning rules based on the activity-scenes and the identification of entity instances and the activity-scene-oriented partition allocating rules.So far，TSEI-PS has achieved success with unified information resource planning and national housing information system construction of the Ministry of Housing and Urban-Rural Development.

big data；formalized data partition；local sufficiency；trace algebra；structural state relational algebra；multi-structural state relational algebra；category

10.3969／j.issn.1006-7043.201312105

TP311.5

A

1006-7043（2014）03-0353-08

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.10067043.201312105.html

2013-12-30. 網(wǎng)絡(luò)出版時間：2014-3-21 14：11：50

張文燚（1968-），男，教授，博士生導(dǎo)師；項連志（1983-），男，講師，博士研究生.

項連志，E-mail：xlz_work＠126.com.