數(shù)據(jù)模型及其發(fā)展歷程*

信俊昌,王國仁,李國徽,高云君,張志強(qiáng)

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

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

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

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

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

在信息化社會,數(shù)據(jù)庫技術(shù)是管理信息系統(tǒng)、辦公自動化系統(tǒng)、決策支持系統(tǒng)等各類信息系統(tǒng)的核心部分,是進(jìn)行科學(xué)研究和決策管理的重要技術(shù)手段.數(shù)據(jù)庫技術(shù)從誕生到現(xiàn)在,在不到半個世紀(jì)的時間里,形成了堅(jiān)實(shí)的理論基礎(chǔ)、成熟的商業(yè)產(chǎn)品和廣泛的應(yīng)用領(lǐng)域,吸引了越來越多的研究者加入.數(shù)據(jù)庫的誕生和發(fā)展,給計(jì)算機(jī)信息管理帶來了一場巨大的革命[1].幾十年來,國內(nèi)外已經(jīng)開發(fā)建設(shè)了成千上萬個數(shù)據(jù)庫,它已成為企業(yè)、部門乃至個人日常工作、生產(chǎn)和生活的基礎(chǔ)設(shè)施.同時,隨著應(yīng)用的擴(kuò)展與深入,數(shù)據(jù)庫的數(shù)量和規(guī)模越來越大,數(shù)據(jù)庫的研究領(lǐng)域也已經(jīng)大大地拓廣和深化了.自1966年計(jì)算機(jī)圖靈獎設(shè)立以來,數(shù)據(jù)庫領(lǐng)域共獲得了4次該獎項(xiàng)(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)實(shí)世界中客觀存在的事物之間存在著多種聯(lián)系,數(shù)據(jù)模型是將不同的聯(lián)系通過篩選、歸納、總結(jié)、命名等抽象過程產(chǎn)生出概念模型,用以表示對現(xiàn)實(shí)世界的描述,然后轉(zhuǎn)換成真實(shí)、容易被人們理解和便于計(jì)算機(jī)處理的數(shù)據(jù)表現(xiàn)形式.也可以說,數(shù)據(jù)模型用于表達(dá)現(xiàn)實(shí)世界中的對象,也就是將現(xiàn)實(shí)世界中雜亂的信息,用一種規(guī)范而形象化的方式表達(dá)出來.

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

因此,根據(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)進(jìn)行性能的分析.第6節(jié)進(jìn)行總結(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世紀(jì)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世紀(jì)70年代后期產(chǎn)生了E-R模型,通過E-R圖,計(jì)算機(jī)專業(yè)人員與非計(jì)算機(jī)人員可以進(jìn)行交流合作,以真實(shí)、合理地模擬一個單位,作為進(jìn)一步設(shè)計(jì)數(shù)據(jù)庫的基礎(chǔ).20世紀(jì) 80年代以前主要研究關(guān)系模型,關(guān)系模型為數(shù)據(jù)庫系統(tǒng)和產(chǎn)業(yè)的發(fā)展奠定了堅(jiān)實(shí)基礎(chǔ).20世紀(jì)80年代中期開始出現(xiàn)面向?qū)ο竽Ｐ?到20世紀(jì)90年代初期,面向?qū)ο竽Ｐ瓦_(dá)到一個頂峰.面向?qū)ο髷?shù)據(jù)模型是一種可擴(kuò)充的數(shù)據(jù)模型,它吸收了語義數(shù)據(jù)模型和知識表示模型的一些基本概念,同時又借鑒了面向?qū)ο蟪绦蛟O(shè)計(jì)和抽象數(shù)據(jù)類型的一些思想.面向?qū)ο髷?shù)據(jù)模型不是一開始就有明確的定義,而是在發(fā)展中逐步形成的.直到 1991年,美國國家標(biāo)準(zhǔn)協(xié)會(ANSI)的一個面向?qū)ο髷?shù)據(jù)庫工作組才提出第一個標(biāo)準(zhǔn)化的報(bào)告.

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

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

1.2 網(wǎng)狀模型

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

網(wǎng)狀模型具有更好的性能和較高的存取效率,但網(wǎng)狀模型結(jié)構(gòu)、數(shù)據(jù)定義語言和數(shù)據(jù)操作語言比較復(fù)雜,用戶不容易掌握和使用;其次,由于網(wǎng)狀模型記錄之間的聯(lián)系是通過存取路徑實(shí)現(xiàn)的,應(yīng)用程序在訪問數(shù)據(jù)時必須選擇適當(dāng)?shù)拇嫒÷窂?因此用戶必須了解系統(tǒng)結(jié)構(gòu)的細(xì)節(jié),加重了編寫應(yīng)用程序的負(fù)擔(dān).在采用網(wǎng)狀模型的典型數(shù)據(jù)庫系統(tǒng)中,最具代表性的是 20世紀(jì) 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)狀模型缺乏充實(shí)的理論基礎(chǔ),于是人們開始尋求具有較充實(shí)理論基礎(chǔ)的數(shù)據(jù)模型.IBM公司的E.F.Codd從1970年～1974年發(fā)表了一系列有關(guān)關(guān)系模型的論文[4,5],從而奠定了關(guān)系數(shù)據(jù)庫的設(shè)計(jì)基礎(chǔ).關(guān)系數(shù)據(jù)模型使用二維表表示實(shí)體和實(shí)體之間的關(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) 無論是實(shí)體、還是實(shí)體之間的聯(lián)系都被映射成一張二維表;

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

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

圖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)系模型實(shí)例

關(guān)系模型是一些表格的框架,實(shí)體的屬性是表格中列的條目,實(shí)體之間的關(guān)系也是通過表格的公共屬性來表示,結(jié)構(gòu)簡單明了;其次,存取路徑對用戶而言是完全隱蔽的,程序和數(shù)據(jù)具有高度的獨(dú)立性;再次,關(guān)系數(shù)據(jù)模型操作方便,在模型中操作的基本對象是集合而不是某一個元組數(shù)據(jù).但是關(guān)系數(shù)據(jù)模型查詢時只需指明數(shù)據(jù)存在的表和需要的數(shù)據(jù)所在的列,不用指明具體的查找路徑,因而加大了系統(tǒng)的負(fù)擔(dān),查詢效率較低.關(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)性強(qiáng)等特點(diǎn)而備受關(guān)注;PostgreSQL是由加州大學(xué)伯克利分校計(jì)算機(jī)系開發(fā)的POSTGRES系統(tǒng)發(fā)展而來,支持處理豐富的數(shù)據(jù)類型;DB2是由IBM公司開發(fā),采用多進(jìn)程、多線索體系結(jié)構(gòu),可以運(yùn)行于多種操作系統(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)點(diǎn).

1.4 E-R模型

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

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

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

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

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

Fig.4 E-R model instance圖4 E-R模型實(shí)例

通過E-R圖,計(jì)算機(jī)專業(yè)人員與非計(jì)算機(jī)人員可以進(jìn)行交流合作,以真實(shí)、合理地模擬一個單位,作為進(jìn)一步設(shè)計(jì)數(shù)據(jù)庫的基礎(chǔ).在 E-R圖中:實(shí)體用矩形表示,矩形框內(nèi)寫明實(shí)體名,如果是弱實(shí)體的話,在矩形外面再套實(shí)線矩形;屬性用橢圓形表示,并用無向邊將其與相應(yīng)的實(shí)體連接起來;聯(lián)系用菱形表示,菱形框內(nèi)寫明聯(lián)系名,并用無向邊分別與有關(guān)實(shí)體連接起來,同時在無向邊旁標(biāo)上聯(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ù)字等.因?yàn)?其結(jié)合了面向?qū)ο蟪绦蛟O(shè)計(jì)與數(shù)據(jù)庫技術(shù),提供了一個集成應(yīng)用開發(fā)系統(tǒng).

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

(1) 原子類型:包含整型、浮點(diǎn)型、字符型、字符串、布爾型和枚舉型,定義方式與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ū)ο竽Ｐ蜎]有準(zhǔn)確的定義,因?yàn)樵撁Q已經(jīng)應(yīng)用到很多不同的產(chǎn)品和原型中,而這些產(chǎn)品和原型考慮的方面可能不一樣,所以很難提供一個準(zhǔ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ù)模型的實(shí)例如圖5所示.

Fig.5 Object-Oriented model instance圖5 面向?qū)ο竽Ｐ蛯?shí)例

面向?qū)ο髷?shù)據(jù)模型提供強(qiáng)大的特性,如繼承、多態(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ù)模型維護(hù)困難;其次,面向?qū)ο髷?shù)據(jù)模型并不適合所有應(yīng)用,當(dā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),每個用戶進(jìn)程處理一個邏輯數(shù)據(jù)庫;O2是法國Altair公司研制開發(fā)的,其設(shè)計(jì)目標(biāo)是集成面向?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)化模型雖然可以很好地表達(dá)現(xiàn)實(shí)世界實(shí)體之間的關(guān)系,但對于諸如文本文件、超鏈接、HTML文檔等半結(jié)構(gòu)化數(shù)據(jù)缺乏有效的支持.不同于結(jié)構(gòu)化模型,半結(jié)構(gòu)化模型的特點(diǎn)主要有隱含的模式信息、結(jié)構(gòu)不規(guī)則、缺乏嚴(yán)格的類型約束等[17].半結(jié)構(gòu)化模型包括XML模型、RDF模型、JSON模型、圖模型和超模型等.

2.1 XML模型

可擴(kuò)展標(biāo)記語言(extensible markup language,簡稱XML)是一種標(biāo)記語言被作為互聯(lián)網(wǎng)信息交換的標(biāo)準(zhǔn)[18],XML是一種分層自描述模型,具有良好的語義和可擴(kuò)展性,可以靈活地表示和組織數(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模型是由若干帶有標(biāo)簽的節(jié)點(diǎn)組成的有向樹,具體定義如下.

(1) 元素節(jié)點(diǎn):該類型的節(jié)點(diǎn)為XML樹中的標(biāo)簽;

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

(3) 值節(jié)點(diǎn)(葉子節(jié)點(diǎn)):該類型的節(jié)點(diǎn)為標(biāo)簽的值;

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

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

XML模型如圖6所示.

Fig.6 XML model instance圖6 XML模型實(shí)例

在圖6(a)所示的XML樹模型中,book節(jié)點(diǎn)表示一個元素,title節(jié)點(diǎn)表示book的一個屬性,而Database節(jié)點(diǎn)表示book的值.在圖6(b)所示的XML圖模型中,author=“Jim”的節(jié)點(diǎn)通過ID屬性指向了他的friend節(jié)點(diǎn)(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以及二進(jìn)制文檔的存儲和管理;MarkLogic Server是一個面向?qū)ο蟮腦ML數(shù)據(jù)庫,支持多維模型,支持JSON和RDF數(shù)據(jù).

2.2 RDF模型

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

RDF三元組:給定一個URI集合R、空節(jié)點(diǎn)集合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上的任何被標(biāo)識的信息,并且使得它可以在應(yīng)用程序之間交換而不喪失語義信息.因此,RDF模型成為語義數(shù)據(jù)描述的標(biāo)準(zhǔn),被廣泛應(yīng)用于元數(shù)據(jù)的描述、本體及語義網(wǎng)中很多機(jī)構(gòu)和項(xiàng)目,如Wikipedia、DBLP等都用RDF表達(dá)它們的元數(shù)據(jù).

2.3 JSON模型

雖然XML模型有統(tǒng)一的格式和標(biāo)準(zhǔn)、可提供多種復(fù)雜查詢方法等優(yōu)點(diǎn),但數(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 模型進(jìn)行相互轉(zhuǎn)換[35],例如,圖7(a)所示的 JSON文檔可以轉(zhuǎn)換成圖7(b)所示的XML模型.

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

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

· 其次,XML的設(shè)計(jì)理念與JSON不同.XML利用標(biāo)記語言的特性提供了良好的延展性(如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ù)雜實(shí)體關(guān)系時的可讀性較差.針對這一問題,研究人員基于圖論提出了圖模型來存儲和表示實(shí)體間關(guān)系[36,37].圖模型是一種良好的數(shù)據(jù)表現(xiàn)形式,并提供多種查詢方法,例如最短路徑查詢[38]、子圖同構(gòu)[39]等.圖模型的應(yīng)用十分廣泛,如社交網(wǎng)絡(luò)、知識圖譜、時序數(shù)據(jù)管理等.基本的圖模型可以分為無向圖模型和有向圖模型.隨著研究的進(jìn)展,圖模型又細(xì)分為不確定圖模型[40-43]、超圖模型[44-48]、時序圖模型[49-52].

(1) 圖G=(V,E,∑),其中,V是節(jié)點(diǎn)集合,E是邊集合,表示節(jié)點(diǎn)之間的關(guān)系,∑表示標(biāo)簽集合.更進(jì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表示在時間點(diǎn)tx時的圖G,時序圖模型如圖8(d)所示;

(4) 超圖H=(X,E),其中,X表示一個有限集合S,S中的元素稱為節(jié)點(diǎn)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是一個輕量級的、可擴(kuò)展的、高性能的圖數(shù)據(jù)庫,支持多種操作系統(tǒng).HyperGraphDB是一種通用的開源數(shù)據(jù)存儲機(jī)制,提供高效的數(shù)據(jù)管理方式.Neo4j是最常用的圖數(shù)據(jù)管理系統(tǒng),具有原生圖存儲機(jī)制,并支持ACID事務(wù).

2.5 超模型

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

Fig.9 Super entity representation圖9 超實(shí)體表示形式

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

Fig.10 Instance of super entity圖10 超實(shí)體實(shí)例

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

3.1 OLAP模型

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

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

(1) 度量:度量u是一個獨(dú)立變量,它們參照每個維的某一維值,并作為OLAP的分析對象.度量的粒度是度量參照的維值所在的維級別,最細(xì)粒度的度量參照每一維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)進(jìn)行多維數(shù)據(jù)的表示和存儲.ROLAP將多維數(shù)據(jù)庫的多維結(jié)構(gòu)劃分為兩類表:一類是事實(shí)表,用來存儲數(shù)據(jù)和維關(guān)鍵字;另一類是維表,即對每個維度使用一個或多個表來存放層次、成員類別等維度的描述信息.ROLAP模型主要包括星型模型、雪花模型.

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

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

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

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

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

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

3.3 MOLAP模型

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

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

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

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

采用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ù)改進(jìn)流程,并提供詳細(xì)報(bào)表.這樣不僅可以分析出推動企業(yè)成長的主要動力,還可以預(yù)測核心業(yè)務(wù)的前景.

3.4 Storm模型

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

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

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

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

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ù)模型逐漸成為新的研究熱點(diǎn).

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è)計(jì)時需要考慮基本可用性(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)存中,從而提高運(yùn)算速度.此外,Key-Value模型又可以細(xì)分為臨時性和永久性兩種類型.臨時性Key-Value模型中所有操作都在內(nèi)存中進(jìn)行,這樣做的好處是讀取和寫入的速度非?？?但一旦數(shù)據(jù)庫實(shí)例關(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)的值是一個字符串?dāng)?shù)組{Name:Jim,Tel:1234}.綜上可以看出,Key-Value模型支持任意格式的值存儲.

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

基于 Key-Value模型的數(shù)據(jù)庫實(shí)例主要有 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àng)目,實(shí)現(xiàn)了分布式內(nèi)存鍵-值存儲和可選持久性,提供字符串、列表、位圖和空間索引;LevelDB是一個開源的Key-Value數(shù)據(jù)庫,實(shí)現(xiàn)了快速讀、寫機(jī)制,并提供鍵-值之間的有序映射.

4.1.2 Key-Document模型

雖然Key-Document模型可以快速地訪問數(shù)據(jù),但當(dāng)數(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).每個集合都有一個唯一標(biāo)識,并且存儲在集合中的文檔沒有數(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ù)庫實(shí)例主要有MongoDB[77]、CouchDB[78]等.MongoDB是開源的、跨平臺、面向文檔的數(shù)據(jù)庫,使用JSON文檔和模式存儲數(shù)據(jù).CouchDB是開源的、基于Key-Document模型的數(shù)據(jù)庫,專注于易用性和可擴(kuò)展的體系結(jié)構(gòu),它使用JSON來存儲數(shù)據(jù).

4.1.3 Key-Column模型

雖然Key-Value模型和Key-Document模型在特定的場景下得到了廣泛的應(yīng)用,但它們對范圍查詢、掃描等操作的效率較低.Key-Column模型是一個稀疏的、分布式的、持久化的多維排序圖,并通過字典順序來組織數(shù)據(jù),支持動態(tài)擴(kuò)展,以達(dá)到負(fù)載均衡.存儲在Key-Column模型中的數(shù)據(jù)可以通過行鍵(row key)、列鍵(column鍵)和時間戳(timestamp)進(jìn)行檢索.其中,列族(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)的行鍵標(biāo)識的行對象存儲在相鄰的位置.每個列由列族和列標(biāo)示符組成,并用“:”隔開,例如 anchor:cnnsi.com.單元格是行、列族和列標(biāo)識符的組合,并且包含了一個值和一個時間戳來標(biāo)示數(shù)據(jù)的版本,如t2.

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

4.2 NewSQL模型

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

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

Table 1 Comparison of RDBMS,NoSQL,and NewSQL features表1 RDBMS、NoSQL和NewSQL特點(diǎn)比較

基于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ù)庫,運(yùn)行在無共享的群集上;S-Store是一個全球化的流式 OLTP引擎,將在線事務(wù)處理和實(shí)時數(shù)據(jù)流處理相結(jié)合,并支持事務(wù)的 ACID特性和事務(wù)的有序性;Spanner是Google公司推出的全球化的基于BigTable模型的NewSQL數(shù)據(jù)庫,在原有BigTable模型的基礎(chǔ)上實(shí)現(xiàn)了事務(wù)的ACID特性;VoltDB是一個橫向可擴(kuò)展的NewSQL關(guān)系數(shù)據(jù)庫,支持SQL訪問和事務(wù)的ACID特性,并基于連續(xù)快照和命令日志記錄的組合實(shí)現(xiàn)數(shù)據(jù)持久性.

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

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

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

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

表2給出了開源的關(guān)系型數(shù)據(jù)庫MySQL和PostgreSQL的分析結(jié)果:相比于MySQL,PostgreSQL允許對象模型的存儲,具有良好的可擴(kuò)展性,可擴(kuò)展到多節(jié)點(diǎn)中進(jìn)行部署;而 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ù)中的命令也可以被獨(dú)立地運(yùn)行;

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

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

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

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

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

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

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

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

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

5.3 OLAP模型

在OLAP模型中,選取ROLAP模型實(shí)例(PivotTable)和MOLAP模型實(shí)例(Hyperion)進(jìn)行分析,結(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)點(diǎn)的有機(jī)結(jié)合,可滿足用戶各種復(fù)雜的分析請求.HOLAP的優(yōu)越性就在于它能將ROLAP和MOLAP相互取長補(bǔ)短,充分利用ROLAP的靈活性和數(shù)據(jù)存儲能力以及MOLAP的多維性和高效率.不同OLAP應(yīng)用的優(yōu)化目標(biāo)也不同,有的應(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)計(jì)數(shù)據(jù)用ROLAP的模式來存儲.

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

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

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

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

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

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

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

6 總 結(jié)

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

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

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