張文燚，項連志，王小芳

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1 實體實例消息的定義

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

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

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

擴展項存在3種情況：

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

當實體實例為適應主體時，實體實例消息可能包括主體內部活動消息。

1.2 活動痕跡與場景

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

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

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

當實體實例為適應主體時，活動痕跡可能包括主體內部活動痕跡。

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

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

1.3 痕跡代數(shù)

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

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

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

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

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

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

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

其中：

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

其中：

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

其中：

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

其中：

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

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

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

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

2.1 結構化狀態(tài)關系代數(shù)

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

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

定理2 設 Ωt為結構化狀態(tài)關系集合，則為一個代數(shù)，本文稱之為結

2.2 多結構化狀態(tài)關系代數(shù)

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

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

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

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

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

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

證明略。

定理5 設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ù)范疇態(tài)射圖Fig.1 Big data category morphism figure

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

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

證明略。

證明略。

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

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

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

4.1 結構化狀態(tài)關系形式化數(shù)據(jù)分區(qū)模型

設結構化狀態(tài)關系Rt的集合為Ωt，其對應的場景活動痕跡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是結構化狀態(tài)關系Rt基于子場景的一個數(shù)據(jù)切片，如果滿足以下條件：

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

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

對于任意結構化狀態(tài)關系Rt，給定由上述切片規(guī)則生成的數(shù)據(jù)切片集合，j＝1，2，…，m，i＝1，2，…，n，和與場景對應的處理節(jié)點j，j＝1，2，…，m，令，則有序對為面向子場景的一個分配，那么切片集合 PP1?2面向子場景，j＝1，2，…，m的切片分配規(guī)則為

4.2 多結構化狀態(tài)關系形式化數(shù)據(jù)分區(qū)模型

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

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

5 應用

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

其中：

其中：

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

其中：

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

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

6 結論

首先，本文基于對 CAS場景活動痕跡的刻畫，以及對經典關系代數(shù)系統(tǒng)的擴展和改造，建立了由痕跡代數(shù)系統(tǒng)S，結構化狀態(tài)關系代數(shù)系統(tǒng)Ω和多結構化狀態(tài)關系代數(shù)Ω三個對象，以及從S到Ω的態(tài)射g：S→Ω，從S到Ω的態(tài)射g-：S→Ω和從Ω到Ω的態(tài)射h：Ω→Ω構成的大數(shù)據(jù)范疇，作為支持大數(shù)據(jù)分區(qū)管理及其相關應用研究的基礎理論模型。其次，本文給出了以滿足“本地充足”為目標的，基于活動場景和實體實例標識的大數(shù)據(jù)切片規(guī)則的形式化表達，以及面向活動場景的切片分配規(guī)則的形式化表達，并由此形成了一種支持大數(shù)據(jù)分區(qū)管理和快速查詢響應的形式化數(shù)據(jù)分區(qū)模型 TSEI-PS。最后，本文把TSEI-PS應用于文獻［7］提出的基于語義模型的數(shù)據(jù)分區(qū)討論，有效地降低了數(shù)據(jù)分區(qū)討論的復雜度，并且使數(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·霍蘭.隱秩序——適應性造就復雜性［M］.上海：上?？萍冀逃霭嫔纾?000.

［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］.北京：科學出版社，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. 網絡出版時間：2014-3-21 14：11：50

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

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