信俊昌,王國仁,李國徽,高云君,張志強

1(東北大學(xué) 計算機科學(xué)與工程學(xué)院,遼寧 沈陽 110819)

2(北京理工大學(xué) 計算機學(xué)院,北京 100081)

3(華中科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,湖北 武漢 430074)

4(浙江大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,浙江 杭州 310058)

5(浙江財經(jīng)大學(xué) 信息管理與工程學(xué)院,浙江 杭州 310018)

在信息化社會,數(shù)據(jù)庫技術(shù)是管理信息系統(tǒng)、辦公自動化系統(tǒng)、決策支持系統(tǒng)等各類信息系統(tǒng)的核心部分,是進行科學(xué)研究和決策管理的重要技術(shù)手段.數(shù)據(jù)庫技術(shù)從誕生到現(xiàn)在,在不到半個世紀的時間里,形成了堅實的理論基礎(chǔ)、成熟的商業(yè)產(chǎn)品和廣泛的應(yīng)用領(lǐng)域,吸引了越來越多的研究者加入.數(shù)據(jù)庫的誕生和發(fā)展,給計算機信息管理帶來了一場巨大的革命[1].幾十年來,國內(nèi)外已經(jīng)開發(fā)建設(shè)了成千上萬個數(shù)據(jù)庫,它已成為企業(yè)、部門乃至個人日常工作、生產(chǎn)和生活的基礎(chǔ)設(shè)施.同時,隨著應(yīng)用的擴展與深入,數(shù)據(jù)庫的數(shù)量和規(guī)模越來越大,數(shù)據(jù)庫的研究領(lǐng)域也已經(jīng)大大地拓廣和深化了.自1966年計算機圖靈獎設(shè)立以來,數(shù)據(jù)庫領(lǐng)域共獲得了4次該獎項(1973年C.W.Bachman1,1983年E.F.Codd,1998年J.Gray和2014年M.Stonebraker),更加充分地說明了數(shù)據(jù)庫是一個充滿活力和創(chuàng)新精神的領(lǐng)域.

數(shù)據(jù)模型是數(shù)據(jù)庫中數(shù)據(jù)的存儲方式和操作方式,是數(shù)據(jù)庫系統(tǒng)的基礎(chǔ).現(xiàn)實世界中客觀存在的事物之間存在著多種聯(lián)系,數(shù)據(jù)模型是將不同的聯(lián)系通過篩選、歸納、總結(jié)、命名等抽象過程產(chǎn)生出概念模型,用以表示對現(xiàn)實世界的描述,然后轉(zhuǎn)換成真實、容易被人們理解和便于計算機處理的數(shù)據(jù)表現(xiàn)形式.也可以說,數(shù)據(jù)模型用于表達現(xiàn)實世界中的對象,也就是將現(xiàn)實世界中雜亂的信息,用一種規(guī)范而形象化的方式表達出來.

根據(jù)不同模型的應(yīng)用層次,可以將數(shù)據(jù)模型分為概念數(shù)據(jù)模型、邏輯數(shù)據(jù)模型和物理數(shù)據(jù)模型:概念數(shù)據(jù)模型中最常用的有E-R模型和面向?qū)ο竽Ｐ偷?主要用來描述世界的概念化結(jié)構(gòu),它使數(shù)據(jù)庫的設(shè)計人員在設(shè)計的初始階段,集中精力分析數(shù)據(jù)以及數(shù)據(jù)之間的聯(lián)系;邏輯數(shù)據(jù)模型反映的是系統(tǒng)分析設(shè)計人員對數(shù)據(jù)存儲的觀點,是對概念數(shù)據(jù)模型進一步的分解和細化,其中最常用的是層次模型、網(wǎng)狀模型、關(guān)系模型和大數(shù)據(jù)模型等;物理數(shù)據(jù)模型描述了數(shù)據(jù)在儲存介質(zhì)上的組織結(jié)構(gòu),是在邏輯數(shù)據(jù)模型的基礎(chǔ)上,考慮各種具體的技術(shù)實現(xiàn)因素,進行數(shù)據(jù)庫體系結(jié)構(gòu)設(shè)計,真正實現(xiàn)數(shù)據(jù)在數(shù)據(jù)庫中的存放.根據(jù)不同模型的語義關(guān)系,可以將數(shù)據(jù)模型分為XML、RDF模型和超模型等:XML模型是一種分層自描述模型;RDF是一種基于XML(可擴展標記語言)編寫的元數(shù)據(jù)(描述數(shù)據(jù)的數(shù)據(jù)),用于描述Web資源的標記語言;超模型是一組超實體以及定義在它們上面的關(guān)系和約束組成,為復(fù)雜的實體模型建模提供了快捷的方法.根據(jù)不同模型的應(yīng)用場景,可以將數(shù)據(jù)模型分為離線模型、在線模型和近線模型:離線模型的主要代表為OLAP模型;在線模型可以可靠地處理無限的數(shù)據(jù)流,像 Hadoop批量處理大數(shù)據(jù)一樣,實時處理數(shù)據(jù),主要代表為 Storm等;近線模型定位于在線存儲和離線存儲之間,是指將那些并不是經(jīng)常用到或者說數(shù)據(jù)的訪問量并不大的數(shù)據(jù)加以存儲,但要求對這些數(shù)據(jù)尋址要迅速、傳輸率要高.目前,近線模型很多是基于 Hadoop分布式文件系統(tǒng)構(gòu)建起來的.根據(jù)數(shù)據(jù)模型的發(fā)展歷程,按時間段將數(shù)據(jù)模型分為結(jié)構(gòu)化模型、半結(jié)構(gòu)化模型、OLAP分析模型和大數(shù)據(jù)模型,其發(fā)展過程如圖1所示.20世紀60年代中后期,出現(xiàn)了結(jié)構(gòu)化模型,主要包括層次模型、網(wǎng)狀模型、關(guān)系模型和面向?qū)ο竽Ｐ偷?20世紀80年代以前主要研究關(guān)系模型,關(guān)系模型為數(shù)據(jù)庫系統(tǒng)和產(chǎn)業(yè)的發(fā)展奠定了堅實的基礎(chǔ).20世紀70年代后期產(chǎn)生了ER模型,80年代中期開始出現(xiàn)面向?qū)ο竽Ｐ?到20世紀 90年代初期,面向?qū)ο竽Ｐ瓦_到一個頂峰.20世紀90代末期,隨著互聯(lián)網(wǎng)應(yīng)用和科學(xué)計算等復(fù)雜應(yīng)用的快速發(fā)展,開始出現(xiàn)半結(jié)構(gòu)化模型,包括XML模型、JSON模型、RDF模型、圖模型和超模型等.XML模型是一種分層自描述模型;JSON使用文本表示一個JS對象的信息,支持字符串、數(shù)字、對象、數(shù)組等各種類型;圖模型應(yīng)用圖論存儲實體間關(guān)系.進入21世紀,隨著電子商務(wù)、商業(yè)智能等應(yīng)用的不斷發(fā)展,數(shù)據(jù)分析模型成為研究熱點,主要包括ROLAP模型、MOLAP模型和Storm模型等.ROLAP模型主要研究事實表和維表的組織表示及其變種,包括星型模型、雪花模型等;MOLAP模型主要研究數(shù)據(jù)立方及其優(yōu)化計算算法.2010年以來,隨著大數(shù)據(jù)工業(yè)應(yīng)用的快速發(fā)展,以NoSQL和NewSQL數(shù)據(jù)庫系統(tǒng)為代表的大數(shù)據(jù)模型成為新的研究熱點,主要包括key-value模型、key-column模型和key-document模型等.本文對上述數(shù)據(jù)模型進行了綜述,并選取每個模型的典型數(shù)據(jù)庫系統(tǒng)進行了性能的分析.

因此,根據(jù)數(shù)據(jù)模型的發(fā)展歷程,本文第 1節(jié)和第 2節(jié)分別綜述結(jié)構(gòu)化模型和半結(jié)構(gòu)化模型.第 3節(jié)綜述OLAP分析模型.第4節(jié)綜述大數(shù)據(jù)模型.第5節(jié)選取每個模型的典型數(shù)據(jù)庫系統(tǒng)進行性能的分析.第6節(jié)進行總結(jié).

Fig.1 Timeline for the development of data models圖1 數(shù)據(jù)模型的發(fā)展時間軸

1 結(jié)構(gòu)化模型

結(jié)構(gòu)化模型是最早被提出來的數(shù)據(jù)模型,是數(shù)據(jù)模型中最基礎(chǔ)的模型之一.結(jié)構(gòu)化模型主要包括層次模型、網(wǎng)狀模型、關(guān)系模型和面向?qū)ο竽Ｐ偷?20世紀60年代中后期,出現(xiàn)了以IBM公司的IMS系統(tǒng)[2]為代表的層次模型、DBTG[3]提出的網(wǎng)狀模型和 Codd[4,5]提出的關(guān)系模型.關(guān)系型數(shù)據(jù)庫是目前最為流行的數(shù)據(jù)庫,同時也是被普遍使用的數(shù)據(jù)庫.20世紀70年代后期產(chǎn)生了E-R模型,通過E-R圖,計算機專業(yè)人員與非計算機人員可以進行交流合作,以真實、合理地模擬一個單位,作為進一步設(shè)計數(shù)據(jù)庫的基礎(chǔ).20世紀 80年代以前主要研究關(guān)系模型,關(guān)系模型為數(shù)據(jù)庫系統(tǒng)和產(chǎn)業(yè)的發(fā)展奠定了堅實基礎(chǔ).20世紀80年代中期開始出現(xiàn)面向?qū)ο竽Ｐ?到20世紀90年代初期,面向?qū)ο竽Ｐ瓦_到一個頂峰.面向?qū)ο髷?shù)據(jù)模型是一種可擴充的數(shù)據(jù)模型,它吸收了語義數(shù)據(jù)模型和知識表示模型的一些基本概念,同時又借鑒了面向?qū)ο蟪绦蛟O(shè)計和抽象數(shù)據(jù)類型的一些思想.面向?qū)ο髷?shù)據(jù)模型不是一開始就有明確的定義,而是在發(fā)展中逐步形成的.直到 1991年,美國國家標準協(xié)會(ANSI)的一個面向?qū)ο髷?shù)據(jù)庫工作組才提出第一個標準化的報告.

結(jié)構(gòu)化模型可以分為傳統(tǒng)數(shù)據(jù)模型和非傳統(tǒng)數(shù)據(jù)模型,如圖2所示.傳統(tǒng)數(shù)據(jù)模型主要包括層次模型、網(wǎng)狀模型和關(guān)系模型;非傳統(tǒng)數(shù)據(jù)模型主要包括E-R模型和面向?qū)ο竽Ｐ偷?

Fig.2 Classification of structured models圖2 結(jié)構(gòu)化模型類別

1.1 層次模型

層次模型采用樹形結(jié)構(gòu)來表示各類實體以及實體間的聯(lián)系,具有數(shù)據(jù)結(jié)構(gòu)比較簡單清晰、數(shù)據(jù)庫的查詢效率高等優(yōu)點.然而,現(xiàn)實世界中很多聯(lián)系是非層次性的,而層次數(shù)據(jù)庫系統(tǒng)只能處理一對多的實體聯(lián)系;其次,由于層次模型查詢子女節(jié)點必須通過雙親節(jié)點,查詢效率較低.

在采用層次模型的典型數(shù)據(jù)庫系統(tǒng)中,最著名的是IBM公司于1968年研制的IMS(information management system)[2].在IMS數(shù)據(jù)庫管理系統(tǒng)中,數(shù)據(jù)被分層處理,層與層之間的數(shù)據(jù)彼此獨立.這樣使得數(shù)據(jù)保持彼此的獨立完整,優(yōu)化了數(shù)據(jù)的存儲和獲取進程.由于IBM公司具有強大的競爭力并且IMS是最早的大型數(shù)據(jù)庫管理系統(tǒng),因此該系統(tǒng)在公開之后被廣泛應(yīng)用.

1.2 網(wǎng)狀模型

由于層次數(shù)據(jù)庫系統(tǒng)只能處理一對多的實體聯(lián)系,對現(xiàn)實世界的描述比較局限,因此出現(xiàn)了網(wǎng)狀模型.網(wǎng)狀模型的主要特點是子女節(jié)點與雙親節(jié)點的聯(lián)系可以不唯一.

網(wǎng)狀模型具有更好的性能和較高的存取效率,但網(wǎng)狀模型結(jié)構(gòu)、數(shù)據(jù)定義語言和數(shù)據(jù)操作語言比較復(fù)雜,用戶不容易掌握和使用;其次,由于網(wǎng)狀模型記錄之間的聯(lián)系是通過存取路徑實現(xiàn)的,應(yīng)用程序在訪問數(shù)據(jù)時必須選擇適當?shù)拇嫒÷窂?因此用戶必須了解系統(tǒng)結(jié)構(gòu)的細節(jié),加重了編寫應(yīng)用程序的負擔.在采用網(wǎng)狀模型的典型數(shù)據(jù)庫系統(tǒng)中,最具代表性的是 20世紀 70年數(shù)據(jù)系統(tǒng)語言研究會 CODASYL(Conf.on Data Systems Language)下屬的數(shù)據(jù)庫任務(wù)組(Data Base Task Group)提出的DBTG系統(tǒng)[3],亦稱CODASYL系統(tǒng).DBTG在數(shù)據(jù)定義語言中提供了數(shù)據(jù)庫完整性的若干概念和語句.現(xiàn)有的網(wǎng)狀數(shù)據(jù)庫系統(tǒng)大都采用DBTG方案.

1.3 關(guān)系模型

由于層次模型和網(wǎng)狀模型缺乏充實的理論基礎(chǔ),于是人們開始尋求具有較充實理論基礎(chǔ)的數(shù)據(jù)模型.IBM公司的E.F.Codd從1970年～1974年發(fā)表了一系列有關(guān)關(guān)系模型的論文[4,5],從而奠定了關(guān)系數(shù)據(jù)庫的設(shè)計基礎(chǔ).關(guān)系數(shù)據(jù)模型使用二維表表示實體和實體之間的關(guān)系,其數(shù)學(xué)定義如下.

(1) 域:具有相同的數(shù)據(jù)類型值的集合,語義上通常是指某一對象的取值范圍;

(2)笛卡爾積:設(shè)D1,D2,…,Dn是n個域,則它們的笛卡爾積為D1×D2×…×Dn={(d1,d2,…,dn)|di∈Di,i=1,2,…,n},其中每一個元素稱為一個n元組,簡稱元組;元組中的每個值di稱為一個分量;

(3)關(guān)系:笛卡爾積D1×D2×…×Dn的子集合,記作R(D1,D2,…,Dn).其中,R稱為關(guān)系名,n為關(guān)系的目或度.

關(guān)系型數(shù)據(jù)庫管理系統(tǒng)的特征如下.

(1) 無論是實體、還是實體之間的聯(lián)系都被映射成一張二維表;

(2) 借助關(guān)系表,表示實體之間的多對多的關(guān)系;

(3) 關(guān)系中的每個屬性是不可分割的實體.

圖3是學(xué)生選課系統(tǒng)的關(guān)系模型.從圖中可以看到,學(xué)生與課程之間的聯(lián)系以及教師和課程之間的多對多聯(lián)系都被映射成了表格.其中,選課表中的sut_id和cour_id分別是引用學(xué)生表和課程表的cour_id的外鍵;教課表也是如此.

Fig.3 Relationship model instance of student圖3 學(xué)生關(guān)系模型實例

關(guān)系模型是一些表格的框架,實體的屬性是表格中列的條目,實體之間的關(guān)系也是通過表格的公共屬性來表示,結(jié)構(gòu)簡單明了;其次,存取路徑對用戶而言是完全隱蔽的,程序和數(shù)據(jù)具有高度的獨立性;再次,關(guān)系數(shù)據(jù)模型操作方便,在模型中操作的基本對象是集合而不是某一個元組數(shù)據(jù).但是關(guān)系數(shù)據(jù)模型查詢時只需指明數(shù)據(jù)存在的表和需要的數(shù)據(jù)所在的列,不用指明具體的查找路徑,因而加大了系統(tǒng)的負擔,查詢效率較低.關(guān)系型數(shù)據(jù)庫是目前最流行的數(shù)據(jù)庫,同時也是被普遍使用的數(shù)據(jù)庫.在采用關(guān)系模型的典型數(shù)據(jù)庫系統(tǒng)中,目前業(yè)界普遍使用的有 MySQL[6]、PostgreSQL[7]、DB2[8]、Oracle[9]以及 SQL Server[10]等系統(tǒng):MySQL 數(shù)據(jù)庫是由瑞典MySQL AB公司1994年開始研發(fā)的一個開源數(shù)據(jù)庫系統(tǒng),因其具備處理速度快、可靠性高和適應(yīng)性強等特點而備受關(guān)注;PostgreSQL是由加州大學(xué)伯克利分校計算機系開發(fā)的POSTGRES系統(tǒng)發(fā)展而來,支持處理豐富的數(shù)據(jù)類型;DB2是由IBM公司開發(fā),采用多進程、多線索體系結(jié)構(gòu),可以運行于多種操作系統(tǒng)之上的關(guān)系型數(shù)據(jù)庫管理系統(tǒng);Oracle關(guān)系數(shù)據(jù)庫管理系統(tǒng)是由甲骨文公司研發(fā)的一種高效率、高可靠性并適應(yīng)高吞吐量的數(shù)據(jù)庫解決方案;SQL Server是Microsoft公司推出的關(guān)系型數(shù)據(jù)庫管理系統(tǒng),具有使用方便、可伸縮性好與相關(guān)軟件集成程度高等優(yōu)點.

1.4 E-R模型

傳統(tǒng)數(shù)據(jù)模型以記錄為基礎(chǔ),不能很好地面向用戶和應(yīng)用[11].因為人們對現(xiàn)實世界的認識往往通過實體來實現(xiàn),而現(xiàn)實中實體不一定與模型中的記錄相對應(yīng),一個記錄可能包含多個實體,一個實體可能分在多個記錄中描述,有些實體也可能僅僅作為某個記錄中的屬性出現(xiàn);其次,用戶很難從傳統(tǒng)數(shù)據(jù)模式看出實體間的全面聯(lián)系,現(xiàn)實世界中的實體聯(lián)系被淹沒在關(guān)系和屬性之中;再次,傳統(tǒng)數(shù)據(jù)模型語義貧乏,支持的數(shù)據(jù)類型較少.因此從20世紀70年代后期開始,出現(xiàn)了第一種非傳統(tǒng)的數(shù)據(jù)模型——E-R模型.E-R模型不同于傳統(tǒng)數(shù)據(jù)模型面向數(shù)據(jù)庫的實現(xiàn),而是面向現(xiàn)實世界.E-R模型(entity-relationship model)即實體聯(lián)系模型,是非傳統(tǒng)數(shù)據(jù)模型之一,于1976年由P.Chen提出[12].其主要有3個抽象概念.

(1) 實體:一般認為,客觀上可以相互區(qū)分的事物就是實體,實體可以是具體的人和物,也可以是抽象的概念與聯(lián)系,關(guān)鍵在于一個實體可與另一個實體相區(qū)別.用實體名及其屬性名的集合來抽象和刻畫同類實體;

(2) 屬性:實體所具有的某一特性,一個實體可由若干個屬性來刻畫.屬性不能脫離實體,屬性是相對實體而言的;

(3) 聯(lián)系,也稱關(guān)系,信息世界中反映實體內(nèi)部或?qū)嶓w之間的關(guān)聯(lián).實體內(nèi)部的聯(lián)系通常是指組成實體的各屬性之間的聯(lián)系;實體之間的聯(lián)系通常是指不同實體集之間的聯(lián)系.

E-R模型實例如圖4所示.由于E-R圖直觀易懂,在概念上表示了一個數(shù)據(jù)庫的信息組織情況,所以若能畫出E-R圖,意味著徹底搞清了問題,此后就可以根據(jù)E-R圖,結(jié)合具體DBMS的類型,把它演變?yōu)镈BMS所能支持的數(shù)據(jù)模型.這種逐步推進的方法已經(jīng)普遍用于數(shù)據(jù)庫的設(shè)計中,成為數(shù)據(jù)庫設(shè)計的一個重要步驟.

Fig.4 E-R model instance圖4 E-R模型實例

通過E-R圖,計算機專業(yè)人員與非計算機人員可以進行交流合作,以真實、合理地模擬一個單位,作為進一步設(shè)計數(shù)據(jù)庫的基礎(chǔ).在 E-R圖中:實體用矩形表示,矩形框內(nèi)寫明實體名,如果是弱實體的話,在矩形外面再套實線矩形;屬性用橢圓形表示,并用無向邊將其與相應(yīng)的實體連接起來;聯(lián)系用菱形表示,菱形框內(nèi)寫明聯(lián)系名,并用無向邊分別與有關(guān)實體連接起來,同時在無向邊旁標上聯(lián)系的類型(1:1,1:n或m:n).比如,老師給學(xué)生授課存在授課關(guān)系,學(xué)生選課存在選課關(guān)系.

1.5 面向?qū)ο竽Ｐ?/h3>

基于面向?qū)ο竽Ｐ偷臄?shù)據(jù)庫屬于非傳統(tǒng)的數(shù)據(jù)庫.與傳統(tǒng)的數(shù)據(jù)庫和 E-R模型相比,面向?qū)ο髷?shù)據(jù)庫適合存儲不同類型的數(shù)據(jù),如圖片、聲音、視頻、文本、數(shù)字等.因為,其結(jié)合了面向?qū)ο蟪绦蛟O(shè)計與數(shù)據(jù)庫技術(shù),提供了一個集成應(yīng)用開發(fā)系統(tǒng).

基于對象定義語言描述的面向?qū)ο竽Ｐ驮试S使用以下數(shù)據(jù)類型.

(1) 原子類型:包含整型、浮點型、字符型、字符串、布爾型和枚舉型,定義方式與C語言類同;

(2) 結(jié)構(gòu)類型:用StructN{T1F2,T2F2,…,TNFN}表示,其中,Struct是關(guān)鍵字;N是結(jié)構(gòu)名;T1,T2,…,TN是類型,一般是原子類型;Fl,F2,…,FN是域名;第i個域名是Fi,類型是Ti;

(3) 聚集類型:一般由類型相同的原子類型或結(jié)構(gòu)類型的元素聚集而成,包含集合、包、列表和數(shù)組;

(4) 接口類型:即類類型,面向?qū)ο竽Ｐ投x的類型.

面向?qū)ο竽Ｐ蜎]有準確的定義,因為該名稱已經(jīng)應(yīng)用到很多不同的產(chǎn)品和原型中,而這些產(chǎn)品和原型考慮的方面可能不一樣,所以很難提供一個準確的定義來說明面向?qū)ο驞BMS應(yīng)建成什么樣.

面向?qū)ο竽Ｐ偷臄?shù)據(jù)結(jié)構(gòu)是非常容易變化的.與傳統(tǒng)的數(shù)據(jù)庫(如層次、網(wǎng)狀或關(guān)系)不同,面向?qū)ο竽Ｐ蜎]有單一固定的數(shù)據(jù)結(jié)構(gòu).編程人員可以給對象類型定義任何有用的結(jié)構(gòu),如鏈表、集合、數(shù)組等.此外,對象可以包含可變的復(fù)雜度,利用多重類型和多重結(jié)構(gòu).面向?qū)ο髷?shù)據(jù)模型的實例如圖5所示.

Fig.5 Object-Oriented model instance圖5 面向?qū)ο竽Ｐ蛯嵗?/p>

面向?qū)ο髷?shù)據(jù)模型提供強大的特性,如繼承、多態(tài)和動態(tài)綁定,允許用戶不用編寫特定對象的代碼即可構(gòu)成對象并提供解決方案,提高了數(shù)據(jù)庫應(yīng)用程序開發(fā)人員的開發(fā)效率;其次,面向?qū)ο髷?shù)據(jù)模型明確地表示聯(lián)系,支持導(dǎo)航式和關(guān)聯(lián)式兩種方式的信息訪問,比基于關(guān)系值的聯(lián)系更能提高數(shù)據(jù)訪問性能;再次,面向?qū)ο髷?shù)據(jù)模型適合于需要管理數(shù)據(jù)對象之間存在復(fù)雜關(guān)系的應(yīng)用,特別適合特定的應(yīng)用,如工程、電子商務(wù)、醫(yī)療等.

但是隨著組織信息需求的改變,對象的定義也要求改變,并且需移植現(xiàn)有數(shù)據(jù)庫,以完成新對象的定義,面向?qū)ο髷?shù)據(jù)模型維護困難;其次,面向?qū)ο髷?shù)據(jù)模型并不適合所有應(yīng)用,當其被用于某些應(yīng)用時,其性能將會降低.在采用面向?qū)ο竽Ｐ偷臄?shù)據(jù)庫系統(tǒng)中,典型的有 Gemstone[13]、Ontos[14]、O2[15]、Itasca[16]等:GemStone Systems于1982年3月1日成立,名為Servio Logic,于1995年6月更名為GemStone Systems,Gemstone系統(tǒng)是第一個作為面向?qū)ο蟮臄?shù)據(jù)庫;Ontos系統(tǒng)是美國Ontologic公司用C++語言開發(fā)的,采用多C/S體系結(jié)構(gòu),每個用戶進程處理一個邏輯數(shù)據(jù)庫;O2是法國Altair公司研制開發(fā)的,其設(shè)計目標是集成面向?qū)ο蟪绦蚣夹g(shù)和數(shù)據(jù)庫技術(shù),支持CAM、CAD等高級應(yīng)用;Itasca系統(tǒng)是Itasca公司在ORION系統(tǒng)基礎(chǔ)上研發(fā)的商業(yè)化系統(tǒng),采用基于對象服務(wù)器的多服務(wù)器多客戶的分布式體系結(jié)構(gòu),支持復(fù)合對象和版本管理.

2 半結(jié)構(gòu)化模型

結(jié)構(gòu)化模型雖然可以很好地表達現(xiàn)實世界實體之間的關(guān)系,但對于諸如文本文件、超鏈接、HTML文檔等半結(jié)構(gòu)化數(shù)據(jù)缺乏有效的支持.不同于結(jié)構(gòu)化模型,半結(jié)構(gòu)化模型的特點主要有隱含的模式信息、結(jié)構(gòu)不規(guī)則、缺乏嚴格的類型約束等[17].半結(jié)構(gòu)化模型包括XML模型、RDF模型、JSON模型、圖模型和超模型等.

2.1 XML模型

可擴展標記語言(extensible markup language,簡稱XML)是一種標記語言被作為互聯(lián)網(wǎng)信息交換的標準[18],XML是一種分層自描述模型,具有良好的語義和可擴展性,可以靈活地表示和組織數(shù)據(jù),并提供高效的查詢方法,例如 XPath[19]、XQuery[20]、關(guān)鍵字查詢[21,22]、子樹匹配[23,24]等.此外,XML模型在數(shù)學(xué)(MathML[25])、化學(xué)(CML[26])、地理(GML[27])等領(lǐng)域也被廣泛應(yīng)用.

XML模型是由若干帶有標簽的節(jié)點組成的有向樹,具體定義如下.

(1) 元素節(jié)點:該類型的節(jié)點為XML樹中的標簽;

(2) 屬性節(jié)點:該類型的節(jié)點為 XML樹中標簽相關(guān)的屬性.不同于元素節(jié)點,屬性節(jié)點不是嵌套的,即,屬性節(jié)點不能有任何子元素.相同的屬性節(jié)點不能嵌套在同一個元素節(jié)點中,并且屬性節(jié)點是無序的;

(3) 值節(jié)點(葉子節(jié)點):該類型的節(jié)點為標簽的值;

(4) 有向邊描述了各類型節(jié)點之間的關(guān)系.

此外,XML圖模型允許用戶引入 ID/IDREF屬性來對樹模型進行擴展,其中,ID屬性唯一地標示了某個元素;IDREF引用其他被ID屬性標示的元素,構(gòu)成一個有向無環(huán)圖.

XML模型如圖6所示.

Fig.6 XML model instance圖6 XML模型實例

在圖6(a)所示的XML樹模型中,book節(jié)點表示一個元素,title節(jié)點表示book的一個屬性,而Database節(jié)點表示book的值.在圖6(b)所示的XML圖模型中,author=“Jim”的節(jié)點通過ID屬性指向了他的friend節(jié)點(author=“Tom”).

基于XML模型的數(shù)據(jù)庫有BaseX[28]、eXist[29]、MarkLogic Server[30]等:BaseX是一個開源的輕量級的XML數(shù)據(jù)管理系統(tǒng),提供XQuery查詢,常用于XML數(shù)據(jù)的存儲、查詢和可視化等.同樣,eXist也是一個開源的XML源生數(shù)據(jù)庫,除了支持XML數(shù)據(jù),還支持JSON、HTML以及二進制文檔的存儲和管理;MarkLogic Server是一個面向?qū)ο蟮腦ML數(shù)據(jù)庫,支持多維模型,支持JSON和RDF數(shù)據(jù).

2.2 RDF模型

RDF(resource description framework)模型又稱為資源描述框架,本質(zhì)上是一個數(shù)據(jù)模型,它提供了一個統(tǒng)一的標準來描述Web上的資源,所謂的資源可以是指類(class)、屬性(property)、實例(Instance)等等.RDF在形式上表示為一個三元組,即主語s(subject)、謂詞p(predicate)、賓語o(object),以描述具體的事物及關(guān)系.RDF也可以表示為一張帶有標記的有向圖,圖中有節(jié)點和邊,節(jié)點對應(yīng)實體,邊對應(yīng)關(guān)系或者屬性,關(guān)系指的是實體之間、實體與屬性之間的關(guān)系,其形式化描述如下.

RDF三元組:給定一個URI集合R、空節(jié)點集合B、文字描述集合L,一個RDF三元組t是形如(s,p,o)的三元組,其中,s∈R∪B,p∈R,o∈R∪B∪L.這里的s通常稱為主語(subject)、資源(resource)或主體,p稱為謂詞(predicate)或?qū)傩?property),o稱為賓語(object)、屬性值(value)或客體.例如,知識圖譜中的一條知識:“人工智能之父是圖靈”,其中,“人工智能”是主語,“之父是”是謂語,“圖靈”是賓語.

RDF模型以三元組的形式描述資源,簡潔明了,并且令使用元數(shù)據(jù)的軟件可以更容易和快速地制造.同時,索引是基于元數(shù)據(jù)而不是從正文得來,搜索者將得到更精確的搜索結(jié)果.在應(yīng)用中,RDF模型可以用來表示W(wǎng)eb上的任何被標識的信息,并且使得它可以在應(yīng)用程序之間交換而不喪失語義信息.因此,RDF模型成為語義數(shù)據(jù)描述的標準,被廣泛應(yīng)用于元數(shù)據(jù)的描述、本體及語義網(wǎng)中很多機構(gòu)和項目,如Wikipedia、DBLP等都用RDF表達它們的元數(shù)據(jù).

2.3 JSON模型

雖然XML模型有統(tǒng)一的格式和標準、可提供多種復(fù)雜查詢方法等優(yōu)點,但數(shù)據(jù)文件較大,格式較復(fù)雜,不利于互聯(lián)網(wǎng)上的數(shù)據(jù)傳輸.JSON(JavaScript object notation)是一種易于讀寫的輕量級數(shù)據(jù)表示格式,可以被快速、高效地解析[31,32].JSON使用文本來表示JavaScript對象的信息,支持字符串、數(shù)字、對象、數(shù)組等各種類型,并且提供快速讀取數(shù)據(jù)的方法,被廣泛用在數(shù)據(jù)采集[33]、數(shù)據(jù)挖掘[34]中.

JSON模型中有兩種結(jié)構(gòu).

(1) 對象:一個對象包含一系列非排序的鍵-值對,一個對象以“{”開始,并以“}”結(jié)束.每個鍵-值對之間使用“:”區(qū)分;

(2)數(shù)組:一個數(shù)組是若干值的集合,一個數(shù)組以“[”開始,并以“]”結(jié)束.數(shù)組成員之間使用“,”區(qū)分.

例如,在圖7(a)所示的 JSON 模型中,“address”表示了一個數(shù)組,存儲了若干鍵-值對,即“streetAddress”:“21 2nd Street”,“city”:“New York”等.此外,JSON 模型可以與 XML 模型進行相互轉(zhuǎn)換[35],例如,圖7(a)所示的 JSON文檔可以轉(zhuǎn)換成圖7(b)所示的XML模型.

雖然JSON和XML都可以完整地表示數(shù)據(jù),并且可以相互轉(zhuǎn)換,但它們之間存在以下不同之處.

· 首先,XML是一種標記語言,而JSON是由若干鍵/值對組成的集合,這使得應(yīng)用程序在讀取XML時需要更多的時間開銷;

· 其次,XML的設(shè)計理念與JSON不同.XML利用標記語言的特性提供了良好的延展性(如XPath),并且提供高級檢索,包括關(guān)鍵字查詢、滿足特定語義(如SLCA)查詢等操作;而JSON相比于XML更加輕量級,可以被快速解析,使其更適用于互聯(lián)網(wǎng)中的數(shù)據(jù)傳輸.

JSON模型多用于大數(shù)據(jù)的存儲,支持JSON模型的數(shù)據(jù)庫主要有MongoDB、CouchDB等.

Fig.7 JSON and XML conversion examples圖7 JSON和XML相互轉(zhuǎn)換舉例

2.4 圖模型

雖然 JSON模型可以有效地解決互聯(lián)網(wǎng)中的數(shù)據(jù)傳輸問題,但在表示復(fù)雜實體關(guān)系時的可讀性較差.針對這一問題,研究人員基于圖論提出了圖模型來存儲和表示實體間關(guān)系[36,37].圖模型是一種良好的數(shù)據(jù)表現(xiàn)形式,并提供多種查詢方法,例如最短路徑查詢[38]、子圖同構(gòu)[39]等.圖模型的應(yīng)用十分廣泛,如社交網(wǎng)絡(luò)、知識圖譜、時序數(shù)據(jù)管理等.基本的圖模型可以分為無向圖模型和有向圖模型.隨著研究的進展,圖模型又細分為不確定圖模型[40-43]、超圖模型[44-48]、時序圖模型[49-52].

(1) 圖G=(V,E,∑),其中,V是節(jié)點集合,E是邊集合,表示節(jié)點之間的關(guān)系,∑表示標簽集合.更進一步地,如果圖中的邊是沒有方向的,如圖8(a)所示,則稱為無向圖;否則,稱為有向圖,如圖8(b)所示;

(2) 不確定圖G′=(G,P),其中,G表示一個有向圖.對于任意邊e∈E,P(e)→(0,1]表示e存在的概率.特別地,P(e)=1表示邊e確定存在.不確定圖模型如圖8(c)所示;

(3) 時序圖是一種隨時間而變化的圖模型,一般是有向的.時序圖可以被看作是一組有向圖序列TG=,其中,Gtx表示在時間點tx時的圖G,時序圖模型如圖8(d)所示;

(4) 超圖H=(X,E),其中,X表示一個有限集合S,S中的元素稱為節(jié)點e;E是X的一個非空子集,稱為超邊或連接.超圖模型如圖8(e)所示.

Fig.8 Graph model example圖8 圖模型舉例

基于圖模型的數(shù)據(jù)庫有AllegroGraph[53]、DEX[54]、HyperGraphDB[55]、Neo4j[56]等.AllegroGraph是一個商業(yè)型的數(shù)據(jù)庫,提供圖模型存儲數(shù)據(jù),提供多種語言的API接口,并支持SQL語言.DEX是一個輕量級的、可擴展的、高性能的圖數(shù)據(jù)庫,支持多種操作系統(tǒng).HyperGraphDB是一種通用的開源數(shù)據(jù)存儲機制,提供高效的數(shù)據(jù)管理方式.Neo4j是最常用的圖數(shù)據(jù)管理系統(tǒng),具有原生圖存儲機制,并支持ACID事務(wù).

2.5 超模型

超模型與其他數(shù)據(jù)模型一樣,超模型由一組超實體以及定義在它們上面的關(guān)系和約束組成,其差別是超模型必須由一個或多個模型來實現(xiàn).其中,超實體被定義為實體或超實體類型的集合.超實體像實體一樣,除試圖捕獲更高級的信息以外,它還可以有屬性、協(xié)議以及參加各種關(guān)系等.超模型為復(fù)雜的實體模型建模提供了快捷的方法,其形式表示如圖9所示.

Fig.9 Super entity representation圖9 超實體表示形式

以某集團公司為例,超實體集團公司是公司、產(chǎn)品、市場等實體(或超實體)類型的抽象,它還可以定義一些有意義的屬性,如利潤、稅金等,我們給出的定義如圖10所示.

Fig.10 Instance of super entity圖10 超實體實例

3 數(shù)據(jù)分析模型

3.1 OLAP模型

隨著電子商務(wù)、商業(yè)智能等應(yīng)用的不斷發(fā)展,關(guān)系數(shù)據(jù)庫之父E.F.Codd[57]于1993年提出了聯(lián)機分析處理(on line transaction processing,簡稱OLAP)的概念.Codd認為,聯(lián)機事務(wù)處理(on-line transaction processing,簡稱OLTP)[58]已不能滿足終端用戶對數(shù)據(jù)庫查詢分析的需要,SQL對數(shù)據(jù)庫進行的簡單查詢也不能滿足用戶分析的需求,故提出了多維數(shù)據(jù)庫和多維分析的概念.數(shù)據(jù)分析模型主要包括關(guān)系型 ROLAP和多維型 MOLAP[59]:ROLAP模型主要研究事實表和維表的組織表示及其變種,包括星型模型、雪花模型等;MOLAP模型主要研究數(shù)據(jù)立方及其優(yōu)化計算算法.

為了嚴謹?shù)鼐C述OLAP模型[60],下面我們對一些OLAP模型用到的定義給出形式化描述.

(1) 度量:度量u是一個獨立變量,它們參照每個維的某一維值,并作為OLAP的分析對象.度量的粒度是度量參照的維值所在的維級別,最細粒度的度量參照每一維d中的最低維級別的某一維值.設(shè)u參照維集合D={d1,d2,…,dn},?d∈D,即集合D可以確定度量u,記作D→u,則滿足D→u??!v∈md(lmd)?v→u(d有m個維級別),其中,v→u是指維值v可以確定度量u;

(2) 單元格:在邏輯視圖中,單元格是由若干不同的度量組成的原子單元,這些度量都參照相同的維值.對于維集合D而言,單元格可以表示為度量的集合,記作{u|D→u};

(3) 數(shù)據(jù)立方:根據(jù)定義1～定義3,數(shù)據(jù)立方是OLAP中的多維數(shù)據(jù)結(jié)構(gòu),簡稱立方;

(4) 塊:塊是數(shù)據(jù)立方的邏輯劃分,一個數(shù)據(jù)立方可以根據(jù)維的取值分成多個塊.

3.2 ROLAP模型

ROLAP(relational OLAP)[61,62]是基于關(guān)系數(shù)據(jù)庫的 OLAP技術(shù).ROLAP以關(guān)系型結(jié)構(gòu)進行多維數(shù)據(jù)的表示和存儲.ROLAP將多維數(shù)據(jù)庫的多維結(jié)構(gòu)劃分為兩類表:一類是事實表,用來存儲數(shù)據(jù)和維關(guān)鍵字;另一類是維表,即對每個維度使用一個或多個表來存放層次、成員類別等維度的描述信息.ROLAP模型主要包括星型模型、雪花模型.

星型數(shù)據(jù)模型是數(shù)據(jù)倉庫和聯(lián)機分析處理使用的最基本、最常用的數(shù)據(jù)模型,它能準確、簡潔地描述出實體之間的邏輯關(guān)系.一個典型的星型模型包括一個大型的事實表和一組邏輯上圍繞這個事實表的維度表.事實表是星型模型的核心,其中存放的大量數(shù)據(jù),是同主題密切相關(guān)的、用戶最關(guān)心的度量數(shù)據(jù).維度是觀察事實、分析主題的角度.維度表的集合是構(gòu)建數(shù)據(jù)倉庫數(shù)據(jù)模式的關(guān)鍵.維度表通過主鍵與事實表相連.用戶依賴維表中的維度屬性,從事實表中獲取支持決策的數(shù)據(jù).

圖11所示為一個酒店經(jīng)營數(shù)據(jù)倉庫星型數(shù)據(jù)模型,記載了每位客人的消費形式、消費價格、促銷方式、促銷折扣、消費金額、成本、利潤等度量數(shù)據(jù).圍繞經(jīng)營主題,酒店經(jīng)營數(shù)據(jù)倉庫建立了客戶維、消費項目維、時間維和促銷維這4個維度.

當有一個或多個維表沒有直接連接到事實表上,而是通過其他維表連接到事實表上時,其圖解就像多個雪花連接在一起,故稱雪花模型.雪花模型是對星型模型的擴展,它對星型模型的維表進一步層次化,原有的各維表可能被擴展為小的事實表,形成一些局部的“層次”區(qū)域,這些被分解的表都連接到主維度表而不是事實表.如圖12所示,對消費項目維度的餐飲種類進行劃分、對促銷維度打折程度進行劃分等.雪花型數(shù)據(jù)模型通過最大限度地減少數(shù)據(jù)存儲量以及聯(lián)合較小的維表來改善查詢性能,除了數(shù)據(jù)冗余.

Fig.11 Star data model instance圖11 星型數(shù)據(jù)模型實例

Fig.12 Snowflake data model instance圖12 雪花型數(shù)據(jù)模型實例

微軟Access的數(shù)據(jù)透視表(pivot table)[63]就是采用ROLAP數(shù)據(jù)模型的一個例子.Pivot Table是一種交互式的表,可以根據(jù)數(shù)據(jù)在數(shù)據(jù)透視表中的排列進行求和與計數(shù)等操作.同時,數(shù)據(jù)透視表可以動態(tài)地改變它們的版面布置,以便按照不同方式分析數(shù)據(jù),也可以重新安排行號和頁字段.當每一次改變版面布置時,數(shù)據(jù)透視表會立即按照新的布置重新計算數(shù)據(jù).

3.3 MOLAP模型

ROLAP是將用戶的OLAP操作轉(zhuǎn)換成SQL語句提交到數(shù)據(jù)庫中執(zhí)行,并且提供聚集導(dǎo)航功能,根據(jù)用戶操作的維度和度量,將SQL查詢定位到最粗粒度的事實表上.ROLAP提供了更大的靈活度,但響應(yīng)速度較慢,因此提出了MOLAP(multidimensional OLAP)[64,65],這是一種基于多維數(shù)據(jù)組織的OLAP技術(shù).

MOLAP將OLAP分析所用到的多維數(shù)據(jù)以多維數(shù)組的形式存儲,形成“立方體”的結(jié)構(gòu).MOLAP事先將匯總數(shù)據(jù)計算好,存放在自己特定的多維數(shù)據(jù)庫中,用戶的OLAP操作可以直接映射到多維數(shù)據(jù)庫的訪問,不通過SQL訪問,加快了響應(yīng)速度.

圖13所示為某一超市連鎖店的銷售數(shù)據(jù)立方體,其中,用戶關(guān)心的是銷售量,并習(xí)慣從時間、地點和商品這3個角度來分析銷售數(shù)據(jù).在這里,銷售量稱為度量,時間、地點和商品稱為維度.如圖13所示,時間維、地點維和商品維的層次分別是年、城市和商品種類.這3個維層次以及由維到度量的映射關(guān)系決定的度量數(shù)據(jù)構(gòu)成了一個數(shù)據(jù)立方體實例.

Fig.13 Data cube instance based on time,place,product圖13 基于時間、地點、商品的數(shù)據(jù)立方體實例

采用MOLAP模型的數(shù)據(jù)庫系統(tǒng)的代表產(chǎn)品有Hyperion(原Arbor Software) Essbase[66]等.Hyperion Essbase平臺是全球領(lǐng)先的企業(yè)績效管理(business performance management,簡稱BPM)解決方案提供商.借助此平臺,企業(yè)可以制定戰(zhàn)略方針、構(gòu)建業(yè)務(wù)模型,并有效規(guī)劃企業(yè)資源.業(yè)務(wù)智能平臺同時可以監(jiān)控由上述因素所推動的業(yè)務(wù)改進流程,并提供詳細報表.這樣不僅可以分析出推動企業(yè)成長的主要動力,還可以預(yù)測核心業(yè)務(wù)的前景.

3.4 Storm模型

Storm[67,68]是一個免費并開源的分布式實時計算系統(tǒng),利用 Storm,可以很容易做到可靠地處理無限的數(shù)據(jù)流.像Hadoop批量處理大數(shù)據(jù)一樣,Storm可以實時處理數(shù)據(jù).Storm操作簡單,可以使用任何編程語言.

Storm實現(xiàn)了一個數(shù)據(jù)流(data flow)的模型,在這個模型中,數(shù)據(jù)持續(xù)不斷地流經(jīng)一個由很多轉(zhuǎn)換實體構(gòu)成的網(wǎng)絡(luò).一個數(shù)據(jù)流的抽象叫作流(stream),流是無限的元組(tuple)序列.元組就像一個可以表示標準數(shù)據(jù)類型(例如int、float和byte數(shù)組)和用戶自定義類型(需要額外序列化代碼的)的數(shù)據(jù)結(jié)構(gòu).每個數(shù)據(jù)流由一個唯一的ID來標示,這個ID可以用來構(gòu)建拓撲中各個組件的數(shù)據(jù)源.

Storm[69]模型對數(shù)據(jù)輸入的來源和輸出數(shù)據(jù)的去向沒有作任何限制.像 Hadoop,是需要把數(shù)據(jù)放到自己的文件系統(tǒng)HDFS里的.在Storm里,可以使用任意來源的數(shù)據(jù)輸入和任意的數(shù)據(jù)輸出,只要實現(xiàn)對應(yīng)的代碼來獲取/寫入這些數(shù)據(jù)即可.

Storm模型具有編程簡單、低延遲、可擴展性強、容錯性高和消息不易丟失等優(yōu)點.Storm模型提供的編程原語與 Hadoop類似,也很簡單,開發(fā)人員只需要關(guān)注應(yīng)用邏輯;Storm 模型可以分布式處理,輕松應(yīng)對數(shù)據(jù)量大、單機搞不定的場景;并且隨著業(yè)務(wù)的發(fā)展,數(shù)據(jù)量和計算量越來越大,Storm模型可以水平擴展.

4 大數(shù)據(jù)模型

隨著互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、社交網(wǎng)絡(luò)等技術(shù)的飛速發(fā)展,傳統(tǒng)的數(shù)據(jù)模型已經(jīng)無法應(yīng)對數(shù)據(jù)量的爆炸式增長.為了解決因這些海量數(shù)據(jù)造成的存儲瓶頸以及管理復(fù)雜性等問題,以NoSQL和NewSQL數(shù)據(jù)庫系統(tǒng)為代表的大數(shù)據(jù)模型逐漸成為新的研究熱點.

4.1 NoSQL模型

NoSQL模型是指非關(guān)系型、不遵循 ACID原則的存儲模型[70,71].NoSQL模型遵循CAP理論[72]和BASE原則[73].CAP理論指出:任何分布式系統(tǒng)無法同時滿足一致性(consistency)、可用性(availability)和分區(qū)容錯性(partition tolerance),最多只能滿足其中的兩個.而 BASE指出,分布式系統(tǒng)在設(shè)計時需要考慮基本可用性(basically available)、軟狀態(tài)(soft state)和最終一致性(eventually consistent).

NoSQL模型主要有3類,即Key-Value模型、Key-Column模型、Key-Document模型.

4.1.1 Key-Value模型

Key-Value模型的主要思想主要來自于哈希表.Key-Value模型由一個鍵-值映射的字典構(gòu)成.Key-Value不僅支持字符串類型,還支持字符串列表、無序(或有序)不重復(fù)的字符串集合、鍵-值哈希表.Key-Value通常將數(shù)據(jù)存儲在內(nèi)存中,從而提高運算速度.此外,Key-Value模型又可以細分為臨時性和永久性兩種類型.臨時性Key-Value模型中所有操作都在內(nèi)存中進行,這樣做的好處是讀取和寫入的速度非?？?但一旦數(shù)據(jù)庫實例關(guān)閉后,將會丟失所有數(shù)據(jù).臨時性 Key-Value模型的數(shù)據(jù)庫通常作為高效緩存技術(shù)應(yīng)用在高并發(fā)場景.而永久性Key-Value模型會將數(shù)據(jù)寫入到硬盤上,這個過程中會造成I/O開銷,導(dǎo)致性能較差,但數(shù)據(jù)不會丟失.

圖14給出了一個Key-Value模型舉例,其中,鍵k1對應(yīng)的值value={11,22,33},鍵k2對應(yīng)的值是一個字符串數(shù)組{Name:Jim,Tel:1234}.綜上可以看出,Key-Value模型支持任意格式的值存儲.

Fig.14 Key-Value model example圖14 Key-Value模型舉例

基于 Key-Value模型的數(shù)據(jù)庫實例主要有 Memcached[74]、Redis[75]、LevelDB[76]等:Memcached是一個通用的分布式內(nèi)存緩存系統(tǒng),通常用于緩存數(shù)據(jù)和對象,以減少讀取外部數(shù)據(jù)源(如數(shù)據(jù)庫或API)的次數(shù);Redis是一款開源內(nèi)存數(shù)據(jù)庫項目,實現(xiàn)了分布式內(nèi)存鍵-值存儲和可選持久性,提供字符串、列表、位圖和空間索引;LevelDB是一個開源的Key-Value數(shù)據(jù)庫,實現(xiàn)了快速讀、寫機制,并提供鍵-值之間的有序映射.

4.1.2 Key-Document模型

雖然Key-Document模型可以快速地訪問數(shù)據(jù),但當數(shù)據(jù)規(guī)模較大、無固定模式時,讀寫的效率會明顯降低.Key-Document模型的核心思想是“數(shù)據(jù)用文檔(如JSON)來表示”,JSON文檔的靈活性使得Key-Document模型數(shù)據(jù)適合存儲海量數(shù)據(jù).

Key-Document模型如圖15所示,Key-Document模型是“面向集合”的,即數(shù)據(jù)被分組存儲在數(shù)據(jù)集中,這個數(shù)據(jù)集稱為集合(collection).每個集合都有一個唯一標識,并且存儲在集合中的文檔沒有數(shù)量限制.Key-Document模型中的集合類似于關(guān)系型數(shù)據(jù)庫中的表結(jié)構(gòu).所不同的是,Key-Document模型中無需定義模式(schema).

Fig.15 Key-Document model example圖15 Key-Document模型舉例

基于Key-Document模型的數(shù)據(jù)庫實例主要有MongoDB[77]、CouchDB[78]等.MongoDB是開源的、跨平臺、面向文檔的數(shù)據(jù)庫,使用JSON文檔和模式存儲數(shù)據(jù).CouchDB是開源的、基于Key-Document模型的數(shù)據(jù)庫,專注于易用性和可擴展的體系結(jié)構(gòu),它使用JSON來存儲數(shù)據(jù).

4.1.3 Key-Column模型

雖然Key-Value模型和Key-Document模型在特定的場景下得到了廣泛的應(yīng)用,但它們對范圍查詢、掃描等操作的效率較低.Key-Column模型是一個稀疏的、分布式的、持久化的多維排序圖,并通過字典順序來組織數(shù)據(jù),支持動態(tài)擴展,以達到負載均衡.存儲在Key-Column模型中的數(shù)據(jù)可以通過行鍵(row key)、列鍵(column鍵)和時間戳(timestamp)進行檢索.其中,列族(column family)是最基本的訪問單位,存放在相同列族下的數(shù)據(jù)擁有相同的列屬性,并使用時間戳來索引不同版本的數(shù)據(jù),以避免數(shù)據(jù)的版本沖突問題.同時,用戶可以通過指定時間戳來獲得不同版本的數(shù)據(jù).

圖16給出了通過Key-Column模型來存儲網(wǎng)頁的示例.

Fig.16 Key-Column model example圖16 Key-Column模型舉例

可以看出:不同于關(guān)系型數(shù)據(jù)庫中的表結(jié)構(gòu),Key-Column模型中的表是一個“多維Map”結(jié)構(gòu).每個行都代表了一個對象,由一個行鍵,如“com.baidu.www”,和一個或多個列組成,如“contents”.相關(guān)的行鍵標識的行對象存儲在相鄰的位置.每個列由列族和列標示符組成,并用“:”隔開,例如 anchor:cnnsi.com.單元格是行、列族和列標識符的組合,并且包含了一個值和一個時間戳來標示數(shù)據(jù)的版本,如t2.

基于 Key-Column模型的數(shù)據(jù)庫實例主要有 BigTable[79]、HBase[80]、Cassandra[81]等:BigTable是 Google公司推出的一種高擴展性的分布式數(shù)據(jù)庫,提供列壓縮等功能,被用于存儲海量數(shù)據(jù);HBase是BigTable的開源實現(xiàn),提供了壓縮算法、內(nèi)存操作和布魯姆過濾器等功能;Cassandra最初是由 Facebook開發(fā)的一款開源的Key-Column模型數(shù)據(jù)庫,支持海量數(shù)據(jù)的讀、寫,擁有較高的可擴展性,并提供類SQL語言來操作數(shù)據(jù).

4.2 NewSQL模型

NewSQL被稱作“下一代可擴展關(guān)系型數(shù)據(jù)庫”,為傳統(tǒng)數(shù)據(jù)庫系統(tǒng)提供了接近 NoSQL的處理性能,使用SQL語言作為應(yīng)用之間交互的主要機制,并且遵循ACID特性[82,83].值得一提的是:NewSQL并沒有提出新的數(shù)據(jù)模型,而是將傳統(tǒng)的關(guān)系型模型和NoSQL模型的優(yōu)點相結(jié)合.NewSQL使用“無鎖”的并發(fā)控制機制,使得應(yīng)用程序在實時讀取數(shù)據(jù)時不會被阻塞.此外,部署了NewSQL的分布式集群中的每個節(jié)點都可以處理請求,從而提高了效率,且高于傳統(tǒng)RDBMS解決方案.NewSQL使用了無共享的架構(gòu),可以方便地部署在海量節(jié)點中,并提供了良好的水平擴展性,從而使得系統(tǒng)不受性能瓶頸的影響[84,85].

為了更好地比較RDBMS、NoSQL和NewSQL的特點,表1從不同的角度分析了三者之間的優(yōu)劣.通過比較結(jié)果可以看出:NewSQL結(jié)合了傳統(tǒng)關(guān)系型數(shù)據(jù)庫和 NoSQL數(shù)據(jù)庫的優(yōu)點,提供了管理海量數(shù)據(jù)的新方法,這也是未來的一個重要研究方向.

Table 1 Comparison of RDBMS,NoSQL,and NewSQL features表1 RDBMS、NoSQL和NewSQL特點比較

基于NewSQL模型的數(shù)據(jù)庫主要有H-Store[86]、S-Store[87]、Spanner[88]、VoltDB[89]等:H-Store是一款內(nèi)存并行數(shù)據(jù)庫管理系統(tǒng),是一個高度分布的基于行存儲的關(guān)系數(shù)據(jù)庫,運行在無共享的群集上;S-Store是一個全球化的流式 OLTP引擎,將在線事務(wù)處理和實時數(shù)據(jù)流處理相結(jié)合,并支持事務(wù)的 ACID特性和事務(wù)的有序性;Spanner是Google公司推出的全球化的基于BigTable模型的NewSQL數(shù)據(jù)庫,在原有BigTable模型的基礎(chǔ)上實現(xiàn)了事務(wù)的ACID特性;VoltDB是一個橫向可擴展的NewSQL關(guān)系數(shù)據(jù)庫,支持SQL訪問和事務(wù)的ACID特性,并基于連續(xù)快照和命令日志記錄的組合實現(xiàn)數(shù)據(jù)持久性.

5 數(shù)據(jù)庫實例的分析與比較

本節(jié)選取每個模型的典型實例分析特點[90],并通過實驗對比了大數(shù)據(jù)模型實例的效率.

5.1 結(jié)構(gòu)化模型

在結(jié)構(gòu)化模型中,選取開源關(guān)系型數(shù)據(jù)庫實例(MySQL和 PostgreSQL)和商業(yè)型關(guān)系型數(shù)據(jù)庫(Oracle和SQL Server)作為分析對象.

表2給出了開源的關(guān)系型數(shù)據(jù)庫MySQL和PostgreSQL的分析結(jié)果:相比于MySQL,PostgreSQL允許對象模型的存儲,具有良好的可擴展性,可擴展到多節(jié)點中進行部署;而 MySQL不支持物化視圖和對象存儲.這兩種數(shù)據(jù)庫都支持GUI接口,都支持多種操作系統(tǒng)環(huán)境,也都提供臨時表.

Table 2 Comparison between MySQL and PostgreSQL表2 MySQL和PostgreSQL對比

表3給出了商業(yè)的關(guān)系型數(shù)據(jù)庫Oracle和SQL Server的分析結(jié)果.

· 首先,這兩種關(guān)系型數(shù)據(jù)庫所使用的查詢語言不同.Oracle使用PL/SQL,SQL Server使用T-SQL;

· 其次,這兩種關(guān)系型數(shù)據(jù)庫中的事務(wù)提交方式不同.在 Oracle中,事務(wù)的提交依賴于管理員(DBA)發(fā)出Commit命令,如果沒有Commit命令,則事務(wù)無法提交;而在SQL Server中,即使沒有確切的Commit命令,事務(wù)中的命令也可以被獨立地運行;

· 在 Oracle中,所有的數(shù)據(jù)庫在用戶之間是共享的,Oracle通過權(quán)限管理來限制用戶的訪問權(quán)限;而在SQL Server中,數(shù)據(jù)庫是私有的,無法在多個用戶之間共享;

· Oracle支持多種操作系統(tǒng);而SQL Server只能運行在Windows或Linux上,通用性較差.

Table 3 Comparison of Oracle and SQL Server表3 Oracle和SQL Server對比

5.2 半結(jié)構(gòu)化模型

在半結(jié)構(gòu)化模型中,選取XML模型實例(MarkLogic和BaseX)和圖模型實例(Neo4j和HyperGraphDB)作為分析對象,結(jié)果見表4.如前所述,由于JSON模型常用于大數(shù)據(jù)的存儲,這里沒有給出JSON模型實例分析結(jié)果.

在XML模型實例分析中,MarkLogic支持SQL查詢語言,支持數(shù)據(jù)劃分策略并提供數(shù)據(jù)副本存儲方法.在這些方面要優(yōu)于BaseX;同時,在MarkLogic中的事務(wù)支持ACID特性,而在BaseX中支持并發(fā)讀數(shù)據(jù),但支持單進程寫數(shù)據(jù);最后,MarkLogic對內(nèi)存計算有良好的支持,并提供范圍索引.

在圖模型實例分析中,Neo4j不支持SQL查詢語言,而HyperGraphDB支持SparQL.Neo4j沒有提供數(shù)據(jù)劃分策略,而HyperGraphDB支持數(shù)據(jù)分布到多個節(jié)點組成的聯(lián)盟中.這兩種圖模型數(shù)據(jù)庫中的事務(wù)都遵循ACID特性.最后,HyperGraphDB提供良好的內(nèi)存計算能力.

此外,通過比較結(jié)果可以看出,這 4種半結(jié)構(gòu)化模型實例都支持二級索引和觸發(fā)器,同時支持并發(fā)操作和數(shù)據(jù)持久.

Table 4 Semi-Structured database instance comparison表4 半結(jié)構(gòu)化數(shù)據(jù)庫實例對比

5.3 OLAP模型

在OLAP模型中,選取ROLAP模型實例(PivotTable)和MOLAP模型實例(Hyperion)進行分析,結(jié)果見表5.可以看出:PivotTable系統(tǒng)比 Hyperion系統(tǒng)占用的存儲空間要小,但 PivotTable查詢速度較慢.因此,一個新的OLAP結(jié)構(gòu) HOLAP被提了出來.但是迄今為止,對 HOLAP還沒有一個正式的定義,HOLAP不是 MOLAP與ROLAP結(jié)構(gòu)的簡單組合,而是這兩種結(jié)構(gòu)技術(shù)優(yōu)點的有機結(jié)合,可滿足用戶各種復(fù)雜的分析請求.HOLAP的優(yōu)越性就在于它能將ROLAP和MOLAP相互取長補短,充分利用ROLAP的靈活性和數(shù)據(jù)存儲能力以及MOLAP的多維性和高效率.不同OLAP應(yīng)用的優(yōu)化目標也不同,有的應(yīng)用優(yōu)先考慮效率和相應(yīng)時間,那么MOLAP的比重就應(yīng)該加大,常用匯總數(shù)據(jù)都應(yīng)該采用多維數(shù)據(jù)庫來存儲,有的應(yīng)用對存儲容量的要求較高,那么就應(yīng)該充分利用關(guān)系數(shù)據(jù)庫的存儲能力,把大部分統(tǒng)計數(shù)據(jù)用ROLAP的模式來存儲.

Table 5 Comparison between PivotTable and Hyperion表5 PivotTable和Hyperion對比

5.4 大數(shù)據(jù)模型

在大數(shù)據(jù)模型中,選取了 Key-Value模型實例(Redis、Memcached和 LevelDB)、Key-Document模型實例(MongoDB、DynamoDB和CouchDB)、Key-Column模型實例(HBase和Cassandra)進行分析.結(jié)果見表6.

通過比較結(jié)果可以看出:Key-Value模型實例不支持二級索引、SQL、觸發(fā)器、外鍵等傳統(tǒng)關(guān)系型數(shù)據(jù)庫的操作;Redis支持事務(wù)操作、數(shù)據(jù)劃分和數(shù)據(jù)副本存儲策略;這3種Key-Value模型實例都支持內(nèi)存計算,從而獲得更快的執(zhí)行效率.

在3種Key-Document模型實例中,都支持二級索引技術(shù)、數(shù)據(jù)分區(qū)、操作并發(fā)和數(shù)據(jù)持久,但都不支持事務(wù)操作、SQL查詢語言和外鍵.DynamoDB和CouchDB支持觸發(fā)器.MongoDB和CouchDB提供數(shù)據(jù)副本策略.MongoDB支持內(nèi)存計算.

在兩種Key-Column模型實例中,都支持觸發(fā)器、數(shù)據(jù)劃分、數(shù)據(jù)副本存儲、操作并發(fā)和數(shù)據(jù)持久,都不支持外鍵、事務(wù)操作和內(nèi)存計算.Cassandra支持二級索引,并提供類SQL查詢語言(CQL).

Table 6 NoSQL database instance comparison表6 NoSQL數(shù)據(jù)庫實例對比

6 總 結(jié)

在數(shù)據(jù)庫領(lǐng)域,數(shù)據(jù)模型用于表達現(xiàn)實世界中的對象,也就是將現(xiàn)實世界中雜亂的信息用一種規(guī)范而形象化的方式表達出來.經(jīng)過近半個世紀的發(fā)展,數(shù)據(jù)模型形成了堅實的理論基礎(chǔ)和廣泛的應(yīng)用領(lǐng)域.本文綜述了結(jié)構(gòu)化模型、半結(jié)構(gòu)化模型、OLAP分析模型和大數(shù)據(jù)模型這4種數(shù)據(jù)模型的概念、特點和國際上的主要研究進展,并選取每個模型的典型數(shù)據(jù)庫系統(tǒng)進行了性能的分析.

結(jié)構(gòu)化模型在20世紀60年代中后期被最早提出,包括了層次模型、網(wǎng)狀模型、關(guān)系模型和面向?qū)ο竽Ｐ偷?主要應(yīng)用有MySQL、PostgreSQL、Oracle和SQL Server等:PostgreSQL允許對象模型的存儲,比MySQL具有更為良好的可擴展性;Oracle支持多種操作系統(tǒng),而SQL Server只能運行在Windows或Linux上,通用性較差.20世紀 90代末期,隨著互聯(lián)網(wǎng)應(yīng)用和科學(xué)計算等復(fù)雜應(yīng)用的快速發(fā)展,開始出現(xiàn)半結(jié)構(gòu)化模型,包括 XML模型、JSON模型和圖模型等.主要的應(yīng)用有MarkLogic、BaseX、Neo4J和HyperGraphDB等:MarkLogic相較于BaseX支持SQL查詢語言,支持數(shù)據(jù)劃分策略并提供數(shù)據(jù)副本存儲方法;而HyperGraphDB支持SQL,比Neo4J內(nèi)存計算能力更強.21世紀,隨著電子商務(wù)、商業(yè)智能等應(yīng)用的不斷發(fā)展,數(shù)據(jù)分析模型成為研究熱點,出現(xiàn)了基于ROLAP模型的實例PivotTable和基于MOLAP模型的實例Hyperion:PivotTable比Hyperion占用存儲空間更小,但PivotTable查詢速度較慢.2010年以來,隨著大數(shù)據(jù)工業(yè)應(yīng)用的快速發(fā)展,以NoSQL和NewSQL數(shù)據(jù)庫系統(tǒng)為代表的大數(shù)據(jù)模型成為新的研究熱點,主要應(yīng)用實例有:基于 Key-Value模型的 Redis、Memcached和LevelDB;基于 Key-Document模型實例的 MongoDB、DynamoDB和 CouchDB;基于 Key-Column模型實例的HBase和Cassandra等.

目前,NewSQL一直在嘗試解決擺脫人工運維束縛,在存儲層實現(xiàn)真正的自生長、自維護,同時實現(xiàn)用戶可以用最自然的編程接口訪問和存儲數(shù)據(jù)等問題.解決這些問題以后,NewSQL就可以擺脫存儲的介質(zhì)及容量的限制.在未來,NewSQL將作為“下一代可擴展關(guān)系型數(shù)據(jù)庫”,成為數(shù)據(jù)庫主要的研究方向之一.