一種基于Neo4j圖數據庫的模糊查詢研究與實現

李 雪

(南京航空航天大學 計算機與技術學院，江蘇 南京 211106)

0 引 言

在日常生活中，人們想要得到某種結果時，并不能很明確地表達他們的查詢要求。例如，尋找一個“高個的年輕人”，其中“高”和“年輕”這樣的詞語就是模糊的概念。但是一般的數據庫管理系統并不能對這樣的模糊語句進行查詢，因此需要找尋一種有效的方法將模糊的查詢條件轉化成精確的查詢區間，使其可以在數據庫管理系統中執行。

隨著信息網絡技術的飛速發展，各種數據量呈指數級增長，傳統的關系數據庫無法對這些數據進行很好的處理。為了解決數據量增多以及關系型數據庫在處理復雜結構這方面的不足，引入了NoSQL數據庫，它被認為是管理大量的圖數據或者復雜數據的最佳選擇[1]。

眾所周知，圖通常可以使用一種很自然的方法來表達這個世界[2]。圖被應用于許多領域，可以用來表示或存儲數據，在不同的場合，圖亦擁有很多形式的表示方法或者使用方法[3]。理所當然地，圖數據庫概念的誕生很快吸引了眾多專家學者的關注與研究，它可以有效地管理網絡實體中每個節點的特定屬性，以及每條邊和實體之間的聯系[4]。Neo4j是圖數據庫中比較受歡迎的一種數據庫，可以很容易地對關系進行插入刪除，在各個領域應用廣泛[5]。

國內外對模糊查詢進行了大量研究，王青松根據模糊數據自身的各種特性,通過聚類的方法自動生成隸屬函數,避免了人為設定隸屬函數的主觀性[6]。王慧和陳逸菲等不僅對經典關系數據庫的查詢語言進行了擴展,使其可以處理模糊查詢條件,同時還通過對隸屬度的計算將權重的概念引入模糊查詢,滿足了人們查詢時各種偏好的設定[7-8]。鄭知卉等使用正向法和反向法對查詢條件進行處理，將其轉化成精確的查詢區間[9-10]。

對NoSQL模糊查詢研究最多的是A Castelltort等，他們對NoSQL圖數據庫Neo4j的查詢語言Cypher進行擴展，得到Cypherf語言使其可以進行模糊查詢,并分別對基于屬性、節點和關系的查詢語言的擴展進行了研究與介紹[11]。在此基礎上，他們還引入了必要的框架來支持NoSQL圖形數據庫中的近似查詢，通過定義和使用Scala，提出Fuzzy4S框架和Cypherf模糊聲明性查詢語言[11]來定義和運行NoSQL圖形數據庫的近似查詢。其中Fuzzy4S通過領域特定語言(DSL)提供一個框架來定義近似的語言變量。然后,該DSL可以用于查詢帶有Cypherf的NoSQL圖形數據庫,該數據庫擴展了現有的聲明性語言來管理近似查詢,該方法將整個鏈從最終用戶的聲明性查詢級別嵌入到數據庫引擎內的實現問題中[12]。

Arnaud Castelltort等還通過對NoSQL圖數據庫進行擴展，即擴展用于管理帶有DSL的不精確查詢(定義了靈活的操作符和使用Scala的操作),以及在NoSQL圖形數據庫中使用Cypherf聲明性的靈活查詢語言來處理和描述復雜的欺詐行為[13]。他們還提出使用合適的工具用來在Neo4j的Cypher語言中表達模糊查詢,用模糊性來幫助解決模糊模式匹配[14]。

BenAli-Sougui I等提出了一個基于圖的模糊NoSQL模型，即FNoSQL(Fuzzy NoSQL),用來處理大數據庫的同時也擴展了NoSQL[15]。Olivier Pivert等提出了一個可以靈活查詢模糊數據庫的系統SUGAR，該系統是建立在NoSQL圖數據庫管理系統中的,支持Cypher查詢,由轉換模塊和分數計算器模塊組成,并且引進了Fudge語言來實施,該語言可以靈活地處理模糊的或者精確的數據,可以用來處理模糊圖數據庫中的偏好查詢[16-17]。

1 相關基礎知識

1.1 隸屬函數

對于論域U∈[0,1]上的模糊集合A，可以表示為：任意一個元素x∈U，都有與其對應的一個隸屬函數μA(x)∈[0,1]，使得：

(1)

其中，μA(x)表示隸屬度x屬于模糊集合A的程度。

例如：設論域U=[0，100],模糊集A表示“young”，模糊集B表示“old”，則

(2)

(3)

1.2 α截集

論域U中所有的元素x所對應的隸屬函數μA(x)的值都不小于α的一個集合稱為模糊集合A的α截集：

Aα={x|μA(x)≥α,?x∈U,α∈[0,1]}

(4)

其中，α是置信水平(閾值)。

1.3 語氣算子

在日常生活中，經常會說“很好”“非常大”“比較容易”等句子，其中“好”、“大”、“容易”等詞都是基本單詞，用“很”、“非常”、“比較”等詞放在它們的前面，對它們的語氣程度進行了調整。這種放在基本單詞之前，可以對語氣程度進行調整的詞稱為語氣算子。

定義1：設Hα為語氣算子，HαA=Aα，如果α小于1，稱Hα為散漫化算子，如果α大于1，稱Hα為集中化算子。其中集中化算子會將原詞的影響范圍變窄，而散漫化算子正好相反。

假設原詞的隸屬函數為μ(x)，可以有以下規定：

(1)“很”、“非常”等詞加上基本詞的隸屬函數為[μ(x)]2；

(2)“稍微”、“略微”、“有點”等詞加上基本詞的隸屬函數為[μ(x)]0.5；

(3)“極”等詞加上基本詞的隸屬函數為[μ(x)]4。

比如非常老的隸屬函數為：

(5)

1.4 模糊化算子

“差不多”、“幾乎”、“大約”等詞和語氣算子不同，它們可以放在原詞前，將原詞的詞義模糊化，這些詞統稱為模糊化算子。考慮到這些詞意思相近，只將“大約”作為標準的模糊化算子。

定義2：可以用一個相似模糊關系μE(x,y),x,y∈U在模糊化算子和被修飾詞的隸屬函數μ(y)之間作運算，來實現對隸屬函數μ(y)的模糊化，記作：

(6)

其中，將δ(δ>0)作為一個參數對模糊范圍進行調節，E為相似模糊關系，記為：

(7)

2 模糊查詢語言擴展

要在Neo4j圖數據庫上實現模糊查詢，關于模糊性的處理可以基于三方面，分別是基于節點(圖數據里面的一個個記錄)，關系(用來連接節點的一條條邊)和屬性(也叫作數據的值)。選擇一個電影演職員關系圖(部分)(見圖1)進行介紹。

圖1 電影演職員關系

圖1顯示了在數據庫中的演職員和電影的例子，包含了兩種節點，分別是導演或者參演電影的演職員，以及上映的電影；其中有“DIRECTED”和“ACTED_IN”這兩種關系；關系和節點都通過屬性進行具體的描述，其中演職員的屬性有：“name”、“born”，電影的屬性有：“released”、“title”以及“tagline”。

在此根據電影演職員例子查詢“年老的演員出演的2000年左右上映的電影”，其中模糊條件分別是“年老”以及“2000年左右”，將它們分解后逐個進行分析。

2.1 簡單條件模糊查詢

其中“年老”不是精確的表述，是一種模糊性的概念，但是怎么算是年老？以平時的生活經驗可知，50歲以下一般不屬于年老，但是50歲以上的人該怎么判斷他們哪些是年老的？由式3所定義的關于“年老”的隸屬函數可知，50歲及以下可以肯定不是“年老”的人，但是對于50歲以上的人并不能絕對地說他是或者不是年老的人，而是要通過計算隸屬函數，得到他們屬于年老的“程度”是多少。

進行模糊查詢一般根據這樣一個過程：用戶結合自己的需求輸入自己所需的相關條件，根據用戶輸入的模糊條件找到其中模糊項相對應的隸屬函數，根據隸屬函數計算所得結果和查詢條件進行匹配，看是否滿足條件。其中對隸屬函數的計算就分為兩種方法，即根據文獻[9-12]介紹的正向法和反向法實現模糊條件的去模糊化，然后將模糊的查詢條件轉換成精確的CQL查詢，這樣就可以在當前的Neo4j數據庫中對帶有模糊性的條件進行查詢。

正向法：需要把所有的模糊性條件都帶進相對的隸屬函數中，根據隸屬函數計算出所有的隸屬度，系統會自動生成相應的表來存儲這些結果，然后根據題意對隸屬度表中的所有隸屬度進行求交集或者求并集，得到總的隸屬度，將這個隸屬度和之前設定好的閾值進行對比，如果匹配度大于或者等于閾值，那么這個條件就是滿足的。

在這邊，將閾值設定為α，然后將所有條件選項所對應的數值帶入隸屬函數，計算出每個選項所對應的隸屬度，具體的計算過程如下所示：

(8)

對求得的所有隸屬度進行求交集或者并集得到總匹配度，具體計算方法如下：

邏輯“AND”的總隸屬度計算方法為:

M=min[μ(x1),μ(x2),…,μ(xn)]=min(α1,

α2,…,αn)

(9)

邏輯“OR”的總隸屬度計算方法為:

M=max[μ(x1),μ(x2),…,μ(xn)]=max(α1,

α2,…,αn)

(10)

然后將計算出來的總隸屬度和原先設定好的閾值α進行比較，如果結果滿足M≥α，那么當前的記錄是滿足要求的；如果結果不滿足M≥α，則當前記錄不滿足條件。

以上方法簡單易懂，計算容易，適用于只有少量數據的時候，但是對于要研究的大數據來說計算量尤其復雜，需要掃描數據庫中的所有數據，并且計算出這些數據對應的模糊項的隸屬度，而且最后還需要自動分配一個表來存儲這些結果，表占用了很多的內存空間，會大大降低查詢速度，因此更傾向于使用反向法。

反向法：同樣也需要事先設定好閾值(α截集)，將閾值代入模糊查詢條件所對應的隸屬函數反向計算得到相應的精確的結果區間，然后用這個精確的結果區間取代原先的模糊查詢條件，就可以以常規的方式在Neo4j中實現模糊查詢。由于反向法不需要對所有的數據條件進行計算，而是可以根據隸屬函數直接進行轉換，對于查詢龐大數據量時具有很大的優勢，而Neo4j是區別于關系數據庫的云數據庫，里面數據尤其多，所以可以使用反向法進行去模糊化處理。

通過設定的α截集將帶有自然語言表述的模糊查詢語言轉換成精確的查詢語句，假設閾值α=0.5，則有如下方程組：

(11)

求解得到的結果為：x∈[55,100]。由此可知，年老的演職員年齡為55到100歲之間。以上成功地將查詢“年老”的演職員這一模糊條件轉換成了查詢年齡在[55,100]這一精確的區間。去模糊化后可以對Cypher查詢語言進行擴展來實現這一查詢，具體查詢語句如下:

查詢年老的演職員：

MATCH (p:Person)

WHERE 2017-p.born=OLD(0.5)

RETURN DISTINCT p.name

其中，OLD(α)是將Cypher查詢語言擴展后的API,主要為了對是否符合“年老”這一模糊條件進行判斷，其中α是閾值，此處設置為0.5。并且由于數據庫中并沒有直接給出具體的年齡，只是給了每個人的出生年，所以需要用“2017-p.born”進行轉換，將它轉換成具體的年齡。

2.2 帶有語言變量的模糊查詢

查詢2000年左右上映的電影：

MATCH(m:Movie)

WHEREm.released=GENERAL(0.5,10,2000)

RETURN DISTINCT m.title

對于這個查詢語句也使用了一個擴展的API:GENERAL(α，δ,y),其中α是隸屬函數的閾值，y是要查詢的條件，結果會根據這三個值的改變而進行改變。

以上兩個擴展得到了兩個查詢條件的結果，最后需要查詢演員出演的電影，而不僅僅只是將兩個擴展的查詢條件進行簡單的求交集，需要使用(p)-[:ACTED_IN]->(m)語句對它們之間的關系進行限定，然后才能對演職員的關系進行篩選，得到需要的結果。具體擴展的查詢語句如下：

復合條件查詢：

MATCH(p:Person),(m:Movie),(p)-[:ACTED_IN]->(m)

WHERE 2017-p.born=OLD(0.5) and m.released=GENERAL(0.5,10,2000)

RETURN p.name,m.title

3 系統實現與實驗分析

3.1 實驗系統

3.1.1 實驗環境

文中的原型系統使用Java的Eclipse集成環境開發完成，實現了一個可以在Neo4j數據庫進行模糊查詢的系統，具體的硬件環境如下：處理器是Intel(R)Core(TM) i5-4590 CPU @ 3.30 GHz 3.30 GHz；8 GB RAM；

界面顯示結果所使用的軟件環境如下：操作系統是Windows 10專業版64位；具體代碼通過Java的Eclipse集成環境編寫；數據庫使用Neo4j 3.2.6 社區版。

3.1.2 數據集

實驗數據采用Neo4j數據庫系統自帶的“Movie Graph”演職員關系圖，主要是數據庫中的演職員和電影的例子，包含了兩種節點，分別是參演電影的演員或者其他相關的工作人員，以及上映的電影。數據集中所有的關系和節點都通過屬性值進行具體的描述，其中演職員“Person”的屬性有姓名和出生日期，電影“Movie”的屬性有電影名稱、上映時間以及電影簡介。節點通過關系連接，并且節點通過標簽進行說明，其中標簽是沒有屬性的。

在Neo4j圖數據庫中進行模糊查詢實現的原型系統如圖2所示。

圖2 原型系統

3.2 實驗分析

基于Neo4j圖數據庫的模糊查詢擴展方法主要是對Cypher查詢語言進行擴展，根據隸屬函數和α截集相關知識在查詢語言上擴展一個API，使用戶可以自行輸入自己想要查詢的條件，通過這個API連接到數據庫中，將模糊查詢條件經過去模糊化，轉換成精確的取值區間，然后在數據庫中進行查詢，得到所需要的結果。為了驗證原型系統的性能，選取不同的查詢條件分別在Neo4j數據庫和設計的模糊系統中進行查詢，對它們的響應時間進行分析比較。

實驗分別從常規條件下的查詢語句和模糊條件下的查詢語句中隨機選擇4條查詢用例進行測試，相應的查詢語句如表1所示。

對表1的測試用例分別進行系統響應時間測試。由于系統性能的影響，所有的測試用例都查詢十二次，然后去掉最長時間和最短時間，取十次響應時間的平均值進行說明。

從圖3可以看出，文中設計的系統的查詢響應時間都比數據庫本身的要大，但是相差均不超過50 ms，時間差別很小，所以使用模糊系統進行查詢是可以接受的。并且從圖中可以看出，第三條語句響應時間明顯要小一些，是因為它的查詢結果很少，只有一條，所以查詢結果的數量也是影響響應時間的因素之一。總的來說，圖中顯示了一般的Cypher查詢語言和擴展后的具有模糊性的系統的執行之間沒有什么大的區別，在系統中使用模糊語句的額外成本與使用NoSQL圖形數據庫是一致的。

圖3 模糊系統和一般查詢語言響應時間對比

4 結束語

對Neo4j圖數據庫的查詢語言進行擴展使其可以進行模糊查詢，有效解決了現如今大量數據情況下人們想要使用模糊的查詢條件查詢結果的問題。提出的模糊查詢方法主要是對查詢語言Cypher進行擴展，將這些擴展在低級API上實現。對于Cypher查詢語言擴展方面主要對帶有語言變量的模糊查詢進行處理，說明了如何將模糊條件去模糊化轉換成精確的數值區間進行查詢。同時，文中也存在很多不足之處。因為對于不同的模糊集有不同的隸屬函數，很難對所有的模糊集都設置一個相對較為準確的隸屬函數，而且就算是同一個模糊集，由于所在條件不同，隸屬函數的設定也有所區別，所以對該方法實現起來具有很大的工作量，難以運用到實際工程中。目前國內外相關研究還很少，還有很長的路要走。