李夷潔，李川

（四川大學計算機學院，成都　610065）

FC-InfoNet-Warehouse:信息網(wǎng)絡數(shù)據(jù)倉庫建模及實現(xiàn)

李夷潔，李川

（四川大學計算機學院，成都610065）

數(shù)據(jù)倉庫；信息網(wǎng)絡數(shù)據(jù)倉庫模型；信息維；拓撲維

0　引言

從社交網(wǎng)絡到基因結(jié)構(gòu)，越來越多的數(shù)據(jù)結(jié)構(gòu)是以圖結(jié)構(gòu)為基礎，人們試圖從圖數(shù)據(jù)結(jié)構(gòu)中挖掘出比單一數(shù)據(jù)值更有價值的網(wǎng)絡結(jié)構(gòu)信息。例如在傳統(tǒng)的銷售主題中人們除了關(guān)心某種物品的銷售量，開始更加關(guān)心銷售網(wǎng)絡，例如銷售額最大的一個商品銷售網(wǎng)絡，了解這個銷售網(wǎng)絡，商家可以針對這個銷售網(wǎng)絡進行一些促銷活動來實現(xiàn)利益最大化。信息網(wǎng)絡是Jiawei Han，Philip S Yu等在EDBT2009和SIGMOD2010上正式提出并倡導的一種處理圖數(shù)據(jù)結(jié)構(gòu)的新型概念[1-2]，旨在對現(xiàn)實空間中的網(wǎng)絡進行進一步的一致性抽象建模，得到一個更加一般具有普適性的模型。近年來關(guān)于信息網(wǎng)絡的研究主要集中于拓撲維/信息維上卷下鉆及其他應用型方面，例如文獻[6]主要研究了信息網(wǎng)絡中基于拓撲維異步上卷的單位間節(jié)點發(fā)現(xiàn)，文獻[7]主要研究了信息網(wǎng)絡中的子圖發(fā)現(xiàn)，文獻[8]主要研究了信息網(wǎng)絡中相似性度量。這些研究方向主要集中于應用層，關(guān)于底層存儲方面鮮有涉及。但是存儲設計是基礎，如果底層存儲設計優(yōu)秀，讀取方便快捷，可以更高效地進行整個研究過程。本文針對信息網(wǎng)絡進行研究，設計并構(gòu)建了信息網(wǎng)絡數(shù)據(jù)倉庫模型。

傳統(tǒng)數(shù)據(jù)倉庫是面向主題的、集成的、面向數(shù)據(jù)分析處理，主要用于企業(yè)決策分析[3]。傳統(tǒng)數(shù)據(jù)倉庫所面向的主題主要是單一數(shù)據(jù)值，信息網(wǎng)絡數(shù)據(jù)倉庫結(jié)合了信息網(wǎng)絡與數(shù)據(jù)倉庫的優(yōu)勢，面向的主題主要是圖度量方面。傳統(tǒng)數(shù)據(jù)倉庫對此場景不再適用[9-10]。

信息網(wǎng)絡數(shù)據(jù)倉庫是近年來新興的概念，相關(guān)的研究設計鮮有涉及。文獻[5]提出信息網(wǎng)絡數(shù)據(jù)倉庫模型但未給出數(shù)據(jù)倉庫的具體實現(xiàn)方法及模型的一般實施性方案。文獻[4]提出一種信息網(wǎng)絡數(shù)據(jù)倉庫模型，為了與本文所提出的信息網(wǎng)絡數(shù)據(jù)倉庫模型區(qū)分，筆者根據(jù)文獻[4]提出的信息網(wǎng)絡數(shù)據(jù)倉庫模型的特點，其核心為邊事實表和節(jié)點事實表，將其命名為EN信息網(wǎng)絡數(shù)據(jù)倉庫模型（Edge-Node），而根據(jù)本文所提模型結(jié)構(gòu)特點將本文所提模型命名為FC信息網(wǎng)絡數(shù)據(jù)倉庫模型(Frame-Clique)，僅在本文中作以區(qū)分。

本文提出FC信息網(wǎng)絡數(shù)據(jù)倉庫模型，該模型結(jié)合傳統(tǒng)數(shù)據(jù)倉庫與信息網(wǎng)絡優(yōu)勢，旨在解決信息網(wǎng)絡數(shù)據(jù)源存儲問題，提供一個一般性的信息網(wǎng)絡數(shù)據(jù)倉庫模型。該模型的一般性體現(xiàn)在，給定任何信息維、拓撲維、主題度量的場景，用戶都可以快捷設計和構(gòu)建特定的符合用戶需求的信息網(wǎng)絡數(shù)據(jù)倉庫。另外，本文所提模型支持多主題建模，易于完成多主題的相互切換，具備靈活性及可擴展性，可以為信息網(wǎng)絡上層應用研究提供高效快捷的數(shù)據(jù)讀取與存儲支持，提高研究效率，節(jié)省時間。

1　FC信息網(wǎng)絡數(shù)據(jù)倉庫模型

本文將傳統(tǒng)數(shù)據(jù)倉庫與信息網(wǎng)絡相結(jié)合，期望得到一個能夠處理圖數(shù)據(jù)結(jié)構(gòu)的一般性數(shù)據(jù)倉庫模型。與傳統(tǒng)數(shù)據(jù)倉庫模型類似，本文所提出的FC信息網(wǎng)絡數(shù)據(jù)倉庫模型中所存儲的也是面向主題的、集成的、不可更新、且隨時間變化而不斷變化的數(shù)據(jù)[11]。該模型結(jié)構(gòu)包含事實表和維表，面向的主題是圖。其中事實表分別為框架事實表（Frame Fact Table）和團事實表（Clique Fact Table）?？蚣苁聦嵄泶鎯υ撃Ｐ妥訄D的主題，團事實表存儲與該主題相關(guān)的節(jié)點。但在實際存儲中，因為傳統(tǒng)關(guān)系數(shù)據(jù)庫的特性，團事實表將會被拆分成兩個或多個表，其中一部分表存儲與主題相關(guān)的節(jié)點，另外一部分表存儲主題與節(jié)點之間的聯(lián)系。這種拆分需要針對不同的數(shù)據(jù)結(jié)構(gòu)及需求具體確定。維表則分為存儲信息維屬性的信息維表，存儲拓撲維屬性的拓撲維表。該模型能較完整地保存信息網(wǎng)絡研究中所需信息，并且在查詢效率及存儲空間方面均優(yōu)于其他信息網(wǎng)絡數(shù)據(jù)倉庫模型。具體定義見定義1。結(jié)構(gòu)如圖1 所示。

定義1（FC信息網(wǎng)絡數(shù)據(jù)倉庫模型）設雙核星型信息網(wǎng)絡數(shù)據(jù)倉庫模型是一個四元組，信息維表IDT（Information Dimensions Table），拓撲維表TDT（Topological Dimensions Table），框架事實表FFT（Frame Fact Table）以及團事實表CFT（Clique Fact Table）。其中FFT 和CFT通過Topic_id連接，即通過主題Id連接，每個主題確定一個圍繞該主題的子圖。IDT與FFT通過IDT的唯一標識ID相連接，根據(jù)該主題的數(shù)據(jù)結(jié)構(gòu)特征確定該主題框架由哪幾種信息維屬性組成。CFT與TDT通過TDT的唯一標識ID連接，根據(jù)該子圖內(nèi)節(jié)點的特征選定該子圖內(nèi)節(jié)點的拓撲維屬性集合。

該模型具有如下優(yōu)點：

（1）該模型解決了傳統(tǒng)數(shù)據(jù)倉庫無法對圖數(shù)據(jù)結(jié)構(gòu)建模的問題。提供了針對圖數(shù)據(jù)結(jié)構(gòu)的面向主題的數(shù)據(jù)組織模型。

（2）該模型具有一般性，給定原始數(shù)據(jù)集，通過分析主題，抽取信息維，拓撲維即可高效建立以圖結(jié)構(gòu)為基礎的信息網(wǎng)絡數(shù)據(jù)倉庫模型。

（3）該模型可以很容易地在關(guān)系數(shù)據(jù)庫上實施建立。

（4）該模型以主題為基本框架建立，具備很強的靈活性和可擴展性。用戶對于主題及各個表之間的關(guān)系一目了然，極大地簡化了查詢分析過程。

圖1　信息網(wǎng)絡數(shù)據(jù)倉庫模型

2　FC信息網(wǎng)絡數(shù)據(jù)倉庫模型相應關(guān)系表生成算法

在整個信息網(wǎng)絡算法應用研究中，存儲是基礎。如何有效存儲原始數(shù)據(jù)，在后續(xù)的算法實施中更加高效簡潔地讀取數(shù)據(jù)至關(guān)重要。根據(jù)本文所提模型，用戶可以根據(jù)特定的需求抽象出主題及與主題相關(guān)的子圖，通過對原始數(shù)據(jù)集結(jié)構(gòu)的特點分析抽取出信息維，拓撲維。通過以下算法執(zhí)行，即可簡便的在關(guān)系數(shù)據(jù)庫上建立FC信息網(wǎng)絡數(shù)據(jù)倉庫模型，為后續(xù)的各種圖結(jié)構(gòu)分析提供數(shù)據(jù)存儲基礎。

算法1給出在確定主題及信息維，拓撲維的條件下，通過對原始數(shù)據(jù)集的分析，構(gòu)建信息網(wǎng)絡數(shù)據(jù)倉庫模型的過程。本文以xml文件為例，xml文件是以記錄為單位，每條記錄包含多種屬性。構(gòu)建相應的信息網(wǎng)絡數(shù)據(jù)倉庫時，根據(jù)主題的不同，抽取不同的子圖。以記錄為單位解析該xml文件，根據(jù)前期對xml文件數(shù)據(jù)結(jié)構(gòu)的分析，第2，4行完成信息維，拓撲維的抽取。第3，5行完成相應維度的表插入過程。第6，7行完成topic及interest的抽取，第7，9行根據(jù)3，4行插入信息維拓撲維返回得到的相應維度的id，完成topic及interest的數(shù)據(jù)庫表插入。至此，完成整個抽取構(gòu)建過程。

輸入：信息網(wǎng)絡原始數(shù)據(jù)source.xml

輸出：FCInfoNet-WareHouse相應關(guān)系表

3　實驗

本文通過對ACM以及DBLP數(shù)據(jù)集特點的分析，進行了信息維，拓撲維及事實表抽取，設計并構(gòu)建了基于ACM及DBLP數(shù)據(jù)集的FN信息網(wǎng)絡數(shù)據(jù)倉庫模型，EN信息網(wǎng)絡數(shù)據(jù)倉庫模型及ACM數(shù)據(jù)集范關(guān)系模型?；跇?gòu)建完成的信息網(wǎng)絡數(shù)據(jù)倉庫模型，本文在ACM數(shù)據(jù)集上進行了時間效率方面的分析實驗，在DBLP數(shù)據(jù)集上進行了存儲空間方面的分析實驗。

3.1查詢效率試驗

在查詢效率方面，本文實驗共進行30次，對查詢時間進行平均值求取。在實驗數(shù)據(jù)選取方面，首先分析數(shù)據(jù)，得到論文數(shù)量分布。分別使用論文數(shù)目最多的三年數(shù)據(jù)，論文數(shù)目平均值附近的三年數(shù)據(jù)，以及論文數(shù)目最少的三年數(shù)據(jù)作為查詢條件進行實驗。可以看出在實驗效果方面，本文所提模型均優(yōu)于其他兩個模型，從而證明本文所提模型的有效性。

圖3代表查詢某年的所有作者的合作網(wǎng)絡。從圖中曲線可以看出，F(xiàn)C信息網(wǎng)絡數(shù)據(jù)倉庫模型，EN信息網(wǎng)絡數(shù)據(jù)倉庫模型均優(yōu)于VRM的查詢效率。而本文所提出的FC信息網(wǎng)絡數(shù)據(jù)倉庫模型在論文數(shù)較多的情況下，更加優(yōu)于文獻4所提出的EN信息網(wǎng)絡數(shù)據(jù)倉庫模型

3.2存儲空間實驗

本文使用DBLP數(shù)據(jù)集進行空間存儲方面的實驗。圖5 給出不同論文數(shù)目時，整個模型所占空間對比圖。從圖中可以看出，在空間存儲方面，隨著論文數(shù)目的增長，本文提出的模型所占存儲空間的增長趨勢明顯緩慢于文獻4所提模型。圖4 表示隨著論文數(shù)目增長，EN模型和FC模型中存儲關(guān)系記錄數(shù)增長情況。其中EN模型存儲的是作者與作者之間的合作關(guān)系，而本文是以論文為連接點，存儲的是論文與作者之間的合作關(guān)系。雖然存儲方式不一樣，但是后期讀取數(shù)據(jù)可以達到同樣的效果。從圖中可以看出，本文所提出模型的關(guān)系數(shù)增長明顯緩慢于文獻4所提模型。所以本文所提出模型在存儲空間方面占據(jù)優(yōu)勢。

以上兩組實驗表明，本文所提出模型在查詢效率方面及存儲空間方面均優(yōu)于文獻4所提信息網(wǎng)絡數(shù)據(jù)倉庫模型及傳統(tǒng)的泛關(guān)系表模型。

4　結(jié)語

本文提出FC信息網(wǎng)絡數(shù)據(jù)倉庫模型，并給出該模型的形式化概念及一般性實現(xiàn)算法，以期能夠結(jié)合信息網(wǎng)絡與數(shù)據(jù)倉庫的優(yōu)勢，解決原始數(shù)據(jù)集結(jié)構(gòu)內(nèi)容混亂導致數(shù)據(jù)分析過程效率低的問題，具有查詢靈活、高效、存儲空間小等優(yōu)點。基于本文提出的FC信息網(wǎng)絡數(shù)據(jù)倉庫模型，可以方便的對現(xiàn)實生活中的各種信息網(wǎng)絡數(shù)據(jù)進行建模及構(gòu)建實施。

圖2　按年份論文數(shù)量分布

圖3　按年份查詢合作者網(wǎng)絡時間對比

圖4　核心邊數(shù)量對比

圖5　存儲空間對比

[1]Han Jiawei,Yan Xifeng,Yu P S.Scalable OLAP and Miningof Information Network[C].Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology(EDBT'09).New York,NY,USA:ACM,2009:1159.

[2]Han Jiawei,Sun Yizhou,Yu P S,et al.Mining Knowledgefrom Databases:an Information Network Analysis Approach[C].Proceedings of the 2010International Conference on Management of Data(SIGMOD'10).New York,NY,USA:ACM,2010:1251-1252.

[3]王珊,李翠平,李盛恩等.數(shù)據(jù)倉庫與數(shù)據(jù)分析教程[M].高等教育出版社,2012:6-13.

[4]聶章艷,李川,唐常杰,等.面向OLGP的多維信息網(wǎng)絡數(shù)據(jù)倉庫模型設計[J].計算機科學與探索,2014,8(1):51-60.

[5]Li C,Yu P S,Zhao L,et al.Infonetolaper:Integrating Infonetwarehouse and Infonetcube with Infonetolap[C].Proc of VLDB.2011,4.

[6]楊尚乾,李川,唐常杰,等.基于拓撲維上卷的空航信息網(wǎng)絡樞紐節(jié)點發(fā)現(xiàn)[J].華中科技大學學報:自然科學版,2012(S1):280-283.

[7]Gupta M,Gao J,Yan X,et al.Top-k Interesting Subgraph Discovery in Information Networks[C].Data Engineering(ICDE),2014 IEEE 30th International Conference on.IEEE,2014:820-831.

[8]Pei-xiang Zhao,Jia-wei Han,Yi-zhou Sun.P-Rank:A Comprehensive Structural Similarity Measure over Information Networks.Proc. 2009 ACM Conf.on Information and Knowledge Management(CIKM'09),Hong Kong,China,Nov.2009.

[9]Jia-wei Han,Yi-zhou Sun,etc.Minning Heterogeneous Information Networks.Tutorial at the 2010 ACM SIGKDD Conf.on Knowledge Discovery and Data Mining(KDD'10),Washington,D.C.,July 2010.

[10]Jim Gray,SurajitChaudhuri,Adam Bosworth,Andrew Layman,Don Reichart,MuraliVenkatrao,Frank Pellow,Hamid Pirahesh.Data cube:A Relational Aggregation Operator Generalizing Group-by,Cross-Tab,and Sub Totals.Data Min.Knowl.Discov.,1(1):29-53, 1997.

[11]Inmon W H.Building the Data Warehouse[M].John Wiley&Sons,2005.

Information Network;Database Warehouse;Information Network Warehouse;Information Dimension;Topological Dimension

FC-InfoNet-Warehouse：Modeling and Implementation of Information Network Warehouse

LI Yi-jie，Li Chuan
(College of Computer Science,Sichuan University,Chengdu 610065)

李夷潔（1991-），女，河南新鄉(xiāng)人，碩士，研究方向為信息網(wǎng)絡數(shù)據(jù)倉庫

2015-12-10

2015-12-30

信息網(wǎng)絡是一種對復雜網(wǎng)絡進行高度一致性抽象、用于處理圖數(shù)據(jù)的新型概念。為了更加靈活高效地讀取數(shù)據(jù)，提升研究效率，提出一種以圖為主題結(jié)合信息網(wǎng)絡與數(shù)據(jù)倉庫優(yōu)勢的FC信息網(wǎng)絡數(shù)據(jù)倉庫模型。實驗表明該模型在查詢效率，存儲空間及查詢靈活性等方面較前人所提EN信息網(wǎng)絡數(shù)據(jù)倉庫模型均具有明顯優(yōu)勢。

李川（1977-），男，河南鄭州人，博士，副教授，研究方向為數(shù)據(jù)庫、數(shù)據(jù)挖掘

The information network is a new concept and model aims to modeling and abstracting complex network in a unified way.Presents the information network data warehouse model to combine the information network and the advantages of data warehouse,the theme of this model is graph,it is named FC-information network data warehouse model.The experimental results show that the model in the query time,storage space and flexible and efficient query than previous proposed EN-information network data warehouse model has obvious advantages.