圖形數據庫

在一個圖形數據庫中，最主要的組成有兩種，結點集和連接結點的關係（有的也稱泡泡和箭頭）。結點集就是圖中一系列結點的集合，比較接近於關係數據庫中所最常使用的表，而關係則是圖形數據庫所特有的組成。 ^[4] 

在需要表示多對多關係時，常常需要創建一個關聯表來記錄不同實體的多對多關係，而且這些關聯表常常不用來記錄信息。如果兩個實體之間擁有多種關係，那麼就需要在它們之間創建多個關聯表。而在一個圖形數據庫中，我們只需要標明兩者之間存在着不同的關係。如果希望在兩個結點集間建立雙向關係，就需要為每個方向定義一個關係。 ^[4] 

也就是説，相對於關係數據庫中的各種關聯表，圖形數據庫中的關係可以通過關係能夠包含屬性這一功能來提供更為豐富的關係展現方式。因此相較於關係型數據庫，圖形數據庫的用户在對事物進行抽象時將擁有一個額外的武器，那就是豐富的關係。 ^[4] 

在許多情報和執法程序中，重要的是要尋找一個模式的事件。這些事件中的任何一個都可能看起來是無害的，但他們觀點以及他們是怎樣直接或間接相關的，概念是不一樣的。再例如社會網絡分析(SNA)對許多供應商的消費品非常感興趣，他是構建人與人之間的關係圖。Facebook是一個社交網絡，它可以與家人和朋友之間保持聯繫。圖形數據庫能很好地顯示出這個人在他/她的朋友圈中是否有影響力，這羣朋友是否有着共同的興趣愛好。 ^[3] 

截至2013年6月底，我國網民規模達5.91億人，隨着越來越多用户的加入，數據量呈指數增長，對社交網絡的分析將面臨很大的困難。Aggarwal等在文獻中介紹了一些社交網絡分析應用場景，以及在中心地位分析、角色分析、網絡建模等方面研究中存在的問題。針對在社交網絡分析面臨數據增量較大和圖形數據庫更適於存儲和處理社交網絡關係的特點，R.Soussi等提出了一種從關係數據庫數據轉換成圖形數據庫數據的機制，並從圖形數據庫中抽取社交網絡關係的方法。S.Kadge等提出了基於圖預測社交網站，預測是基於有向加權的社交圖，方法是構建用户行為的社交網絡圖，用圖挖掘技術預測未來的社交行為，並與Apriori和F-Tree兩種算法的預測效率進行了對比。J.Cao等分析和模擬企業社交網絡中的用户交互行為，形成企業用户的組織圖和社交圖，用兩類圖構建用户交互模型，用於預測企業用户之間的交互行為。李孝偉等提出了一種融合節點與鏈接屬性的社交網絡社區劃分算法，該算法融合節點屬性的相似度、節點間鏈接權值等鏈接屬性信息，結合聚類算法實現了對社交網絡的社區劃分。 ^[5] 

Neo4j是一個流行的圖形數據庫，它是開源的。最近，Neo4j的社區版已經由遵循AGPL許可協議轉向了遵循GPL許可協議。儘管如此，Neo4j的企業版依然使用AGPL許可。Neo4j基於Java實現，兼容ACID特性，也支持其他編程語言，如Ruby和Python。 ^[1] 

FlockDB是Twitter為進行關係數據分析而構建的。FlockDB迄今為止還沒有穩定的版本，對於它是否是一個真正的圖形數據庫，尚有爭議。FlockDB和其它圖形數據庫（如Neo4j、OrientDB）的區別在於圖的遍歷，Twitter的數據模型不需要遍歷社交圖譜。儘管如此，由於FlockDB應用於Twitter這樣的大型站點，以及它相比其它圖形數據庫的簡潔性，仍然值得我們值得關注。 ^[1] 

AllegroGrap是一個基於W3c標準的為資源描述框架構建的圖形數據庫。它為處理鏈接數據和Web語義而設計，支持SPARQL、RDFS++和Prolog。 ^[1] 

GraphDB是德國sones公司在.NET基礎上構建的。Sones公司於2007年成立，近年來陸續進行了幾輪融資。GraphDB社區版遵循AGPL v3許可協議，企業版是商業化的。GraphDB託管在Windows Azure平台上。 ^[3] 

InfiniteGraph基於Java實現，它的目標是構建“分佈式的圖形數據庫”，已被美國國防部和美國中央情報局所採用。除此之外，還有其他一些圖形數據庫，如OrientDB、InfoGrid和HypergraphDB。Ravel構建在開源的Pregel實現之上，微軟研究院的Trinity項目也是一個圖形數據庫項目。 ^[3] 

百度開源的分佈式圖數據庫。 ^[6]  支持標準的Apache Tinkerpop Gremlin圖查詢語言，支持屬性圖，可支持千億級規模關係數據；支持多種後端存儲（Cassandra，HBase，RocksDB，MySQL，PostgreSQL，ScyllaDB）；支持各類索引（二級索引、範圍索引、全文索引、聯合索引，均無需依賴第三方索引庫）； ^[7]  提供可視化的Web界面，可用於圖建模、數據導入、圖分析；提供導入工具支持從多種數據源中導入數據到圖中，支持的數據源包括：CSV、HDFS、關係型數據庫（MySQL、Oracle、SQL Server、PostgreSQL）；支持REST接口，並提供10+種通用的圖算法；支持與Hadoop、Spark GraphX等大數據系統集成。 ^[8] 

圖形數據庫是非關係型數據庫NoSQL按照數據模型分類中的一個分支體系，通過應用圖形存儲實體及實體間的關係信息，為某一圖模型問題提供了良好的數據庫存儲與數據處理解決方案。最常見的社交網絡中人與人的關係信息為例，使用傳統關係型數據庫RDBMS存儲社交網絡數據的效果並不理想，難以查巧及深度遍歷大量複雜且互連接的數據，響應時間緩慢超出預期，而圖形數據庫的恃點恰到好處的填補了這一短板。作為NoSQL的一種,圖形數據庫很長一段時間都侷限於學術與實驗室，它利用圈的頂點和邊來表示要素和要素之間的關係。隨着社交網絡Facebook、電子商務以及資源檢索等領域的發展，急需一種可以處理複雜關聯的存儲技術，而採用圖形數據庫組織存儲、計算分析挖掘低結構化且互連接的數據則更為有效，因此圖形數據庫得W逐漸從實驗室走出,同時反過來也極大地推動了圖形數據庫的飛速發展。圖數據庫依託圖論為理論基礎，描述並存儲了圖中節點與其之間的關係。國內外基於圖論數據挖掘展開的工作分為圖的匹配、關鍵字查詢、圖的分類、圖的聚類和頻繁子圖挖掘問題等五個方面。 ^[2] 

圖的匹配即通過研究圖與圖之間的拓撲結構，從而分析圖之間的相似度大小，Conte等在圖匹配方面有着突出的貢獻；在團形數據庫關鍵字檢索方面，一方面是通過研巧網絡關係圖的巧化關係從而分析檢索子圖，包括雙向查詢算法算法，另一方面則基於索引指導圖挖掘，著名的有BLINKS算法；圖分類包括有監督分類和無監督分類兩種，Boser等基於core進行分類，Horvath等提出一種基於支持向量機分類的方法；圖的聚類算法包括節點和對象兩種不同的範圍，Aggarwal等則使用文擋結構進行聚類；頻繁子圖挖掘是指在圖集合中挖掘公共子結構，常見的頻繁子圖挖掘算法包括FSG(Frequent Subgraph Discovery)、FFSM(Fast Frequent Subgraph Minning)和Splat等。同時，為改善圍形數據庫的性能，相關學者進行了廣泛的研究，巧得了一些研究成果：N.Mar提出了一種性能化良的存儲結構DEX，其利用位圖的設計思想，對檢索進行優化處理後，能夠準確島效的檢索高達10億級別的數據；Prima針對圖數據庫訪問節點延遲較大這一問題，設計了一類線上數據隔離模型；Ylping等則基於皮爾森相關係數(Pearson correlation coefficient)方法設計了CGS(Correelated Graph Search)算法，其優點是提高了圖的遍歷速度及穩定性，同時大大減少了檢索過程中的服務器壓力，減少系統開銷。 ^[2]