1. 摘要

因為圖數據庫的復雜模式和不同的信息描寫敘述方式，對于非專業用戶來說查詢復雜的圖數據庫是異常困難的。

一個好的圖查詢引擎應該支持多種轉化——同義詞、縮略詞、簡寫以及本體等等，而且應該可以對搜索結果進行一個非常好地排序。

基于此問題本文提出了一種新型的查詢框架來方便用戶查詢，解放了為構造查詢圖而抓耳撓腮的用戶群。

2. 應用背景

2.1 應用

圖數據庫也是一種流行的數據存儲方式。如知識圖、信息網絡以及社交網絡等應用的數據都存儲在圖數據庫中。由于圖數據的無模式或者模式太復雜以及信息的多種描寫敘述方式使得基于圖數據的查詢變得很困難。對于一般用戶來說更是望之卻步。

圖2-1 a為圖數據庫中的一部分，若查詢大約30歲而且跟“Universityof California Berkley”以及“Mission:Impssible”相關的演員。易得圖2-1中綠色與黃色部分均為比較好的結果。圖2-1 b為一個可以表達查詢語義的查詢，可是現有的圖數據庫查詢僅僅能查詢到綠色的部分或者一個都查不到。

原因在于結點的信息都不匹配。而原有查詢又不支持語義轉換或者僅僅支持一種轉化。

圖2-1 圖數據庫G

該文解決的問題能夠描寫敘述為：給定一個查詢Q以及數據庫G，找出圖數據庫中全部由Q經轉換函數能夠轉化的圖。

2.2 抽象定義

給定一個查詢Q、一個圖數據庫G以及一系列轉化函數L，求跟Q匹配的最好的k個子圖。當中轉化函數L包含表2-1中全部的轉化。

表2-1 本文支持的轉化函數

注：本文的方法能夠輕松地增加其他轉化函數來滿足不同的需求

3 已有方法

Spark查詢僅僅需用戶輸入keyword就可以，而無需輸入復雜的圖結點關系就能得到查詢結果。但其僅僅能提取字符串相似匹配，通過改動能夠使其支持其他轉換。

NeMa支持圖結構和字符串相似度匹配（Jaccard）。

4 本文的方法

4.1 離線操作

4.1.1 度量函數

下述公式中v表示結點，e表示邊，φ(·)表示匹配，比如φ(v)表示圖數據庫G中與查詢圖v中匹配的結點。若v能夠經過第i個轉換函數變為φ(v)，則f_i(v,φ(v)) = 1。反之φ(v) = 0。

結點匹配代價：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

邊匹配代價：

? ? ? ? ? ? ? ? ? ? ? ? ? ??

圖匹配函數：

? ? ?

且易得圖匹配函數P的值越小，與Q匹配的圖φ(Q)的質量越高，即查詢結果應該為P值最小的k個子圖。

4.1.2 參數確定

令W={α₁, α₂, … ; β₁, β₂…}，則

當中T表示訓練集。

4.1.3 冷啟動

令啟動的目的在于怎樣生成好的查詢訓練集，從而能夠得到好的匹配函數的參數。冷啟動步驟：

(1) 從圖數據庫中隨機選擇一些子圖作為查詢模板Q’；

(2) 將查詢模板中的一些結點和邊用轉換函數進行轉化得到查詢Q。

(3) 提取和Q精確匹配的子圖Q^e；

(4) (Q, Q’)與(Q, Q^e)組成訓練集。

4.2 在線查詢

一般的圖查詢均屬于NP-hard問題，其能夠歸約為子圖同構問題，從而證明該問題是NP-hard的。

因此本文設計了兩個啟示式用于求解該問題。

4.2.1 啟示式1

將圖匹配的代價累加到一個結點上，則每一個結點的匹配得分能夠代表包含該節點在內的圖匹配代價。

每一個結點計算公式：

當中m_ji^(t)(u_i)表示第t次迭代u_j結點對節點u_i匹配貢獻的得分。

該公式的直觀理解參考圖4-1。當中a、b中左邊均表示數據庫，右邊表示查詢圖。

圖4-1 啟示式1的直觀意義

4.2.2 啟示式2

利用啟示式1進行計算時須要計算大量的結點。由結點匹配代價計算公式可得。對于隨意的查詢結點v經過同樣的轉換函數匹配代價同樣。基于此將經過同一個結點轉換的結點濃縮為一個結點計算，則能夠有效降低結點得分的計算個數。由濃縮結點組成的圖成為概要圖。若查詢圖中兩個結點之間存在邊，則連接概要圖中相應的結點，而與圖數據庫無關。當中，邊的匹配代價為圖數據庫中全部這類邊的匹配代價的上界。

基于這樣的發現問題的求解步驟為：

(1) 構造概要圖；

(2) 在概要圖上利用啟示式1計算；

(3) 利用概要圖中計算出的結果求原圖中與之相應子圖的得分。

循環運行直到找到k個結果。

?

以上為我對論文Schemaless and Structureless Graph Querying-vldb2014的個人理解。當然當中僅僅介紹了論文中的主要內容。具體的解說請查看論文解說的ppt，地址http://download.csdn.net/detail/woniu317/7391539。

?

總結

以上是生活随笔為你收集整理的基于多种转换语义的图数据库查询的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。