數據模型及其發展歷程*

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

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

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

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

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

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

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

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

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

因此,根據數據模型的發展歷程,本文第 1節和第 2節分別綜述結構化模型和半結構化模型.第 3節綜述OLAP分析模型.第4節綜述大數據模型.第5節選取每個模型的典型數據庫系統進行性能的分析.第6節進行總結.

Fig.1 Timeline for the development of data models圖1 數據模型的發展時間軸

1 結構化模型

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

結構化模型可以分為傳統數據模型和非傳統數據模型,如圖2所示.傳統數據模型主要包括層次模型、網狀模型和關系模型;非傳統數據模型主要包括E-R模型和面向對象模型等.

Fig.2 Classification of structured models圖2 結構化模型類別

1.1 層次模型

層次模型采用樹形結構來表示各類實體以及實體間的聯系,具有數據結構比較簡單清晰、數據庫的查詢效率高等優點.然而,現實世界中很多聯系是非層次性的,而層次數據庫系統只能處理一對多的實體聯系;其次,由于層次模型查詢子女節點必須通過雙親節點,查詢效率較低.

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

1.2 網狀模型

由于層次數據庫系統只能處理一對多的實體聯系,對現實世界的描述比較局限,因此出現了網狀模型.網狀模型的主要特點是子女節點與雙親節點的聯系可以不唯一.

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

1.3 關系模型

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

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

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

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

關系型數據庫管理系統的特征如下.

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

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

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

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

Fig.3 Relationship model instance of student圖3 學生關系模型實例

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

1.4 E-R模型

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

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

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

(3) 聯系,也稱關系,信息世界中反映實體內部或實體之間的關聯.實體內部的聯系通常是指組成實體的各屬性之間的聯系;實體之間的聯系通常是指不同實體集之間的聯系.

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

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

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

1.5 面向對象模型

基于面向對象模型的數據庫屬于非傳統的數據庫.與傳統的數據庫和 E-R模型相比,面向對象數據庫適合存儲不同類型的數據,如圖片、聲音、視頻、文本、數字等.因為,其結合了面向對象程序設計與數據庫技術,提供了一個集成應用開發系統.

基于對象定義語言描述的面向對象模型允許使用以下數據類型.

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

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

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

(4) 接口類型:即類類型,面向對象模型定義的類型.

面向對象模型沒有準確的定義,因為該名稱已經應用到很多不同的產品和原型中,而這些產品和原型考慮的方面可能不一樣,所以很難提供一個準確的定義來說明面向對象DBMS應建成什么樣.

面向對象模型的數據結構是非常容易變化的.與傳統的數據庫(如層次、網狀或關系)不同,面向對象模型沒有單一固定的數據結構.編程人員可以給對象類型定義任何有用的結構,如鏈表、集合、數組等.此外,對象可以包含可變的復雜度,利用多重類型和多重結構.面向對象數據模型的實例如圖5所示.

Fig.5 Object-Oriented model instance圖5 面向對象模型實例

面向對象數據模型提供強大的特性,如繼承、多態和動態綁定,允許用戶不用編寫特定對象的代碼即可構成對象并提供解決方案,提高了數據庫應用程序開發人員的開發效率;其次,面向對象數據模型明確地表示聯系,支持導航式和關聯式兩種方式的信息訪問,比基于關系值的聯系更能提高數據訪問性能;再次,面向對象數據模型適合于需要管理數據對象之間存在復雜關系的應用,特別適合特定的應用,如工程、電子商務、醫療等.

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

2 半結構化模型

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

2.1 XML模型

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

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

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

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

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

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

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

XML模型如圖6所示.

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

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

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

2.2 RDF模型

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

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

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

2.3 JSON模型

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

JSON模型中有兩種結構.

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

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

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

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

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

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

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

Fig.7 JSON and XML conversion examples圖7 JSON和XML相互轉換舉例

2.4 圖模型

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

(1) 圖G=(V,E,∑),其中,V是節點集合,E是邊集合,表示節點之間的關系,∑表示標簽集合.更進一步地,如果圖中的邊是沒有方向的,如圖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中的元素稱為節點e;E是X的一個非空子集,稱為超邊或連接.超圖模型如圖8(e)所示.

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

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

2.5 超模型

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

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

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

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

3 數據分析模型

3.1 OLAP模型

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

為了嚴謹地綜述OLAP模型[60],下面我們對一些OLAP模型用到的定義給出形式化描述.

(1) 度量:度量u是一個獨立變量,它們參照每個維的某一維值,并作為OLAP的分析對象.度量的粒度是度量參照的維值所在的維級別,最細粒度的度量參照每一維d中的最低維級別的某一維值.設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) 數據立方:根據定義1～定義3,數據立方是OLAP中的多維數據結構,簡稱立方;

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

3.2 ROLAP模型

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

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

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

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

Fig.11 Star data model instance圖11 星型數據模型實例

Fig.12 Snowflake data model instance圖12 雪花型數據模型實例

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

3.3 MOLAP模型

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

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

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

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

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

3.4 Storm模型

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

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

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

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

4 大數據模型

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

4.1 NoSQL模型

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

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

4.1.1 Key-Value模型

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

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

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

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

4.1.2 Key-Document模型

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

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

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

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

4.1.3 Key-Column模型

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

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

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

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

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

4.2 NewSQL模型

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

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

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

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

5 數據庫實例的分析與比較

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

5.1 結構化模型

在結構化模型中,選取開源關系型數據庫實例(MySQL和 PostgreSQL)和商業型關系型數據庫(Oracle和SQL Server)作為分析對象.

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

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

表3給出了商業的關系型數據庫Oracle和SQL Server的分析結果.

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

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

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

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

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

5.2 半結構化模型

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

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

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

此外,通過比較結果可以看出,這 4種半結構化模型實例都支持二級索引和觸發器,同時支持并發操作和數據持久.

Table 4 Semi-Structured database instance comparison表4 半結構化數據庫實例對比

5.3 OLAP模型

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

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

5.4 大數據模型

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

通過比較結果可以看出:Key-Value模型實例不支持二級索引、SQL、觸發器、外鍵等傳統關系型數據庫的操作;Redis支持事務操作、數據劃分和數據副本存儲策略;這3種Key-Value模型實例都支持內存計算,從而獲得更快的執行效率.

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

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

Table 6 NoSQL database instance comparison表6 NoSQL數據庫實例對比

6 總 結

在數據庫領域,數據模型用于表達現實世界中的對象,也就是將現實世界中雜亂的信息用一種規范而形象化的方式表達出來.經過近半個世紀的發展,數據模型形成了堅實的理論基礎和廣泛的應用領域.本文綜述了結構化模型、半結構化模型、OLAP分析模型和大數據模型這4種數據模型的概念、特點和國際上的主要研究進展,并選取每個模型的典型數據庫系統進行了性能的分析.

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

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