李 雪

(南京航空航天大學(xué) 計(jì)算機(jī)與技術(shù)學(xué)院，江蘇 南京 211106)

0 引 言

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

隨著信息網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，各種數(shù)據(jù)量呈指數(shù)級增長，傳統(tǒng)的關(guān)系數(shù)據(jù)庫無法對這些數(shù)據(jù)進(jìn)行很好的處理。為了解決數(shù)據(jù)量增多以及關(guān)系型數(shù)據(jù)庫在處理復(fù)雜結(jié)構(gòu)這方面的不足，引入了NoSQL數(shù)據(jù)庫，它被認(rèn)為是管理大量的圖數(shù)據(jù)或者復(fù)雜數(shù)據(jù)的最佳選擇[1]。

眾所周知，圖通?？梢允褂靡环N很自然的方法來表達(dá)這個(gè)世界[2]。圖被應(yīng)用于許多領(lǐng)域，可以用來表示或存儲數(shù)據(jù)，在不同的場合，圖亦擁有很多形式的表示方法或者使用方法[3]。理所當(dāng)然地，圖數(shù)據(jù)庫概念的誕生很快吸引了眾多專家學(xué)者的關(guān)注與研究，它可以有效地管理網(wǎng)絡(luò)實(shí)體中每個(gè)節(jié)點(diǎn)的特定屬性，以及每條邊和實(shí)體之間的聯(lián)系[4]。Neo4j是圖數(shù)據(jù)庫中比較受歡迎的一種數(shù)據(jù)庫，可以很容易地對關(guān)系進(jìn)行插入刪除，在各個(gè)領(lǐng)域應(yīng)用廣泛[5]。

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

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

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

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

1 相關(guān)基礎(chǔ)知識

1.1 隸屬函數(shù)

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

(1)

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

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

(2)

(3)

1.2 α截集

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

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

(4)

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

1.3 語氣算子

在日常生活中，經(jīng)常會說“很好”“非常大”“比較容易”等句子，其中“好”、“大”、“容易”等詞都是基本單詞，用“很”、“非?！薄ⅰ氨容^”等詞放在它們的前面，對它們的語氣程度進(jìn)行了調(diào)整。這種放在基本單詞之前，可以對語氣程度進(jìn)行調(diào)整的詞稱為語氣算子。

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

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

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

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

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

比如非常老的隸屬函數(shù)為：

(5)

1.4 模糊化算子

“差不多”、“幾乎”、“大約”等詞和語氣算子不同，它們可以放在原詞前，將原詞的詞義模糊化，這些詞統(tǒng)稱為模糊化算子?？紤]到這些詞意思相近，只將“大約”作為標(biāo)準(zhǔn)的模糊化算子。

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

(6)

其中，將δ(δ>0)作為一個(gè)參數(shù)對模糊范圍進(jìn)行調(diào)節(jié)，E為相似模糊關(guān)系，記為：

(7)

2 模糊查詢語言擴(kuò)展

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

圖1 電影演職員關(guān)系

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

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

2.1 簡單條件模糊查詢

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

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

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

在這邊，將閾值設(shè)定為α，然后將所有條件選項(xiàng)所對應(yīng)的數(shù)值帶入隸屬函數(shù)，計(jì)算出每個(gè)選項(xiàng)所對應(yīng)的隸屬度，具體的計(jì)算過程如下所示：

(8)

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

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

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

α2,…,αn)

(9)

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

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

α2,…,αn)

(10)

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

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

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

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

(11)

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

查詢年老的演職員：

MATCH (p:Person)

WHERE 2017-p.born=OLD(0.5)

RETURN DISTINCT p.name

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

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

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

MATCH(m:Movie)

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

RETURN DISTINCT m.title

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

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

復(fù)合條件查詢：

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 系統(tǒng)實(shí)現(xiàn)與實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)系統(tǒng)

3.1.1 實(shí)驗(yàn)環(huán)境

文中的原型系統(tǒng)使用Java的Eclipse集成環(huán)境開發(fā)完成，實(shí)現(xiàn)了一個(gè)可以在Neo4j數(shù)據(jù)庫進(jìn)行模糊查詢的系統(tǒng)，具體的硬件環(huán)境如下：處理器是Intel(R)Core(TM) i5-4590 CPU @ 3.30 GHz 3.30 GHz；8 GB RAM；

界面顯示結(jié)果所使用的軟件環(huán)境如下：操作系統(tǒng)是Windows 10專業(yè)版64位；具體代碼通過Java的Eclipse集成環(huán)境編寫；數(shù)據(jù)庫使用Neo4j 3.2.6 社區(qū)版。

3.1.2 數(shù)據(jù)集

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

在Neo4j圖數(shù)據(jù)庫中進(jìn)行模糊查詢實(shí)現(xiàn)的原型系統(tǒng)如圖2所示。

圖2 原型系統(tǒng)

3.2 實(shí)驗(yàn)分析

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

實(shí)驗(yàn)分別從常規(guī)條件下的查詢語句和模糊條件下的查詢語句中隨機(jī)選擇4條查詢用例進(jìn)行測試，相應(yīng)的查詢語句如表1所示。

對表1的測試用例分別進(jìn)行系統(tǒng)響應(yīng)時(shí)間測試。由于系統(tǒng)性能的影響，所有的測試用例都查詢十二次，然后去掉最長時(shí)間和最短時(shí)間，取十次響應(yīng)時(shí)間的平均值進(jìn)行說明。

從圖3可以看出，文中設(shè)計(jì)的系統(tǒng)的查詢響應(yīng)時(shí)間都比數(shù)據(jù)庫本身的要大，但是相差均不超過50 ms，時(shí)間差別很小，所以使用模糊系統(tǒng)進(jìn)行查詢是可以接受的。并且從圖中可以看出，第三條語句響應(yīng)時(shí)間明顯要小一些，是因?yàn)樗牟樵兘Y(jié)果很少，只有一條，所以查詢結(jié)果的數(shù)量也是影響響應(yīng)時(shí)間的因素之一。總的來說，圖中顯示了一般的Cypher查詢語言和擴(kuò)展后的具有模糊性的系統(tǒng)的執(zhí)行之間沒有什么大的區(qū)別，在系統(tǒng)中使用模糊語句的額外成本與使用NoSQL圖形數(shù)據(jù)庫是一致的。

圖3 模糊系統(tǒng)和一般查詢語言響應(yīng)時(shí)間對比

4 結(jié)束語

對Neo4j圖數(shù)據(jù)庫的查詢語言進(jìn)行擴(kuò)展使其可以進(jìn)行模糊查詢，有效解決了現(xiàn)如今大量數(shù)據(jù)情況下人們想要使用模糊的查詢條件查詢結(jié)果的問題。提出的模糊查詢方法主要是對查詢語言Cypher進(jìn)行擴(kuò)展，將這些擴(kuò)展在低級API上實(shí)現(xiàn)。對于Cypher查詢語言擴(kuò)展方面主要對帶有語言變量的模糊查詢進(jìn)行處理，說明了如何將模糊條件去模糊化轉(zhuǎn)換成精確的數(shù)值區(qū)間進(jìn)行查詢。同時(shí)，文中也存在很多不足之處。因?yàn)閷τ诓煌哪：胁煌碾`屬函數(shù)，很難對所有的模糊集都設(shè)置一個(gè)相對較為準(zhǔn)確的隸屬函數(shù)，而且就算是同一個(gè)模糊集，由于所在條件不同，隸屬函數(shù)的設(shè)定也有所區(qū)別，所以對該方法實(shí)現(xiàn)起來具有很大的工作量，難以運(yùn)用到實(shí)際工程中。目前國內(nèi)外相關(guān)研究還很少，還有很長的路要走。