FC-InfoNet-Warehouse:信息網絡數據倉庫建模及實現

李夷潔，李川

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

FC-InfoNet-Warehouse:信息網絡數據倉庫建模及實現

李夷潔，李川

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

數據倉庫；信息網絡數據倉庫模型；信息維；拓撲維

0　引言

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

傳統數據倉庫是面向主題的、集成的、面向數據分析處理，主要用于企業決策分析[3]。傳統數據倉庫所面向的主題主要是單一數據值，信息網絡數據倉庫結合了信息網絡與數據倉庫的優勢，面向的主題主要是圖度量方面。傳統數據倉庫對此場景不再適用[9-10]。

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

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

1　FC信息網絡數據倉庫模型

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

定義1（FC信息網絡數據倉庫模型）設雙核星型信息網絡數據倉庫模型是一個四元組，信息維表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相連接，根據該主題的數據結構特征確定該主題框架由哪幾種信息維屬性組成。CFT與TDT通過TDT的唯一標識ID連接，根據該子圖內節點的特征選定該子圖內節點的拓撲維屬性集合。

該模型具有如下優點：

（1）該模型解決了傳統數據倉庫無法對圖數據結構建模的問題。提供了針對圖數據結構的面向主題的數據組織模型。

（2）該模型具有一般性，給定原始數據集，通過分析主題，抽取信息維，拓撲維即可高效建立以圖結構為基礎的信息網絡數據倉庫模型。

（3）該模型可以很容易地在關系數據庫上實施建立。

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

圖1　信息網絡數據倉庫模型

2　FC信息網絡數據倉庫模型相應關系表生成算法

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

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

輸入：信息網絡原始數據source.xml

輸出：FCInfoNet-WareHouse相應關系表

3　實驗

本文通過對ACM以及DBLP數據集特點的分析，進行了信息維，拓撲維及事實表抽取，設計并構建了基于ACM及DBLP數據集的FN信息網絡數據倉庫模型，EN信息網絡數據倉庫模型及ACM數據集范關系模型。基于構建完成的信息網絡數據倉庫模型，本文在ACM數據集上進行了時間效率方面的分析實驗，在DBLP數據集上進行了存儲空間方面的分析實驗。

3.1查詢效率試驗

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

圖3代表查詢某年的所有作者的合作網絡。從圖中曲線可以看出，FC信息網絡數據倉庫模型，EN信息網絡數據倉庫模型均優于VRM的查詢效率。而本文所提出的FC信息網絡數據倉庫模型在論文數較多的情況下，更加優于文獻4所提出的EN信息網絡數據倉庫模型

3.2存儲空間實驗

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

以上兩組實驗表明，本文所提出模型在查詢效率方面及存儲空間方面均優于文獻4所提信息網絡數據倉庫模型及傳統的泛關系表模型。

4　結語

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

圖2　按年份論文數量分布

圖3　按年份查詢合作者網絡時間對比

圖4　核心邊數量對比

圖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]王珊,李翠平,李盛恩等.數據倉庫與數據分析教程[M].高等教育出版社,2012:6-13.

[4]聶章艷,李川,唐常杰,等.面向OLGP的多維信息網絡數據倉庫模型設計[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]楊尚乾,李川,唐常杰,等.基于拓撲維上卷的空航信息網絡樞紐節點發現[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-），女，河南新鄉人，碩士，研究方向為信息網絡數據倉庫

2015-12-10

2015-12-30

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

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

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.