一種基于領(lǐng)域知識的XML數(shù)據(jù)模糊查詢

孟祥福，張霄雁，馬宗民，彭晏飛

(1.遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院，遼寧 葫蘆島125105;2.東北大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽110819)

隨著WWW的迅速膨脹和Internet的普遍應(yīng)用，訪問Web已成為人們獲取信息的重要手段.XML規(guī)范是當(dāng)今Web上信息表示與交換的標(biāo)準(zhǔn)，大量的異構(gòu)數(shù)據(jù)因而也就集成在XML文檔中［1］.然而在現(xiàn)實中，普通Web用戶的查詢意圖本身就可能是模糊或不精確的，他們所提交的查詢大多數(shù)情況下也只是其查詢意圖的模糊描述.因此，用戶希望系統(tǒng)能夠支持其模糊查詢要求的表達(dá)，通過直接含有模糊詞或模糊關(guān)系的模糊語言查詢XML數(shù)據(jù).

來看一個例子，在一個存儲房產(chǎn)信息的XML文檔(HouseDB.xml)中，假設(shè)用戶想查找“價格至多$300 000，建筑時間比較近，面積在130～200 m2”的房產(chǎn)，可能會輸入如下XPath查詢語句:

其中，基于內(nèi)容的查詢約束在XPath中用謂詞的形

式表示.很明顯，該查詢包含了3個查詢謂詞，分別是“Price at most 300 000”、“Buildyear='Recent'”和“SqFt between 130 and 200”，其中前2個查詢謂詞分別包含了模糊關(guān)系“at most”和模糊詞“Recent”.這里，將包含模糊關(guān)系或模糊詞的查詢謂詞稱為模糊查詢謂詞.如果一個以XPath形式表示的XML查詢中包含了一個或多個模糊查詢謂詞，則稱之為XML模糊查詢.然而，目前的XML數(shù)據(jù)查詢處理模式僅支持精確查詢匹配，還不能直接處理這樣的模糊查詢.因此，系統(tǒng)首先需要將模糊查詢條件轉(zhuǎn)換為精確查詢條件，然后再提交給XML數(shù)據(jù)管理系統(tǒng)執(zhí)行，進(jìn)而獲取滿足模糊查詢要求的結(jié)果.

在關(guān)系數(shù)據(jù)庫領(lǐng)域，Tahani［2］最先基于 Zadeh提出的模糊集［3］來處理關(guān)系數(shù)據(jù)庫中含有不精確查詢條件的模糊查詢;Bosc等對標(biāo)準(zhǔn)SQL進(jìn)行了模糊擴展［4-5］，提出了SQLf語言，該語言也是對以前經(jīng)典數(shù)據(jù)庫模糊查詢方法(如 Tahani［3］、Bosc［6］、Nakajima［7］)的特點和功能的集成.Chen［8］和 Ma［9］提出了模糊查詢條件轉(zhuǎn)換規(guī)則，能夠處理查詢條件中包含的模糊關(guān)系或模糊詞.文獻(xiàn)［10-11］提出了基于模糊集的模糊描述邏輯的推理方法.近年來，研究者開始關(guān)注XML數(shù)據(jù)的柔性查詢工作［12-17］.文獻(xiàn)［12-13］利用本體處理XML文檔的柔性查詢，使用查詢重寫機制獲取近似查詢結(jié)果，查詢重寫過程依賴于領(lǐng)域?qū)＜覅⑴c建立的本體知識庫和映射規(guī)則.文獻(xiàn)［14］提出了XML近似查詢結(jié)構(gòu)匹配TreeSketch算法，通過在精確的 TreeSkech上構(gòu)建概要來處理XML小枝模式查詢，進(jìn)而快速返回結(jié)構(gòu)近似匹配的查詢結(jié)果.文獻(xiàn)［15］在一個XML基本模式中，首先鑒定用戶提出的XML查詢模式與其他模式的結(jié)構(gòu)相似性，然后在查詢處理階段通過自動重寫當(dāng)前查詢，使查詢模式與其他相關(guān)XML模式兼容，從而找到更多模式匹配信息.文獻(xiàn)［16］提出了AQAX在線XML查詢系統(tǒng)，該系統(tǒng)基于XML數(shù)據(jù)概要實現(xiàn)快速的大規(guī)模數(shù)據(jù)集探測，AQAX使用了雙層體系結(jié)構(gòu):第1層在XML聚類(XCluster)框架上生成近似結(jié)果;第2層在XML聚類元素上構(gòu)建分類樹，為用戶提供查詢可視化界面.文獻(xiàn)［17］使用基本變異操作將用戶初始XML查詢樹改寫成系列變異查詢樹，在此基礎(chǔ)上根據(jù)基本變異操作代價和嵌入代價得到松弛查詢樹，從而實現(xiàn)近似查詢.然而需要指出的是，現(xiàn)有的XML數(shù)據(jù)柔性/近似查詢方法都是對精確查詢條件進(jìn)行放松處理，進(jìn)而獲取相關(guān)查詢結(jié)果，但這類方法不支持用戶直接表達(dá)模糊查詢要求，并且也不能對模糊查詢要求進(jìn)行轉(zhuǎn)換處理.因此，本文在模糊集理論基礎(chǔ)上，提出了一種直接支持用戶模糊查詢要求的查詢處理方法，該方法能夠處理模糊關(guān)系和模糊詞以及對精確數(shù)值區(qū)間進(jìn)行模糊擴展，并且查詢處理過程考慮了用戶偏好.該方法能夠在不改變傳統(tǒng)XML查詢語言和XML數(shù)據(jù)庫引擎的前提下實現(xiàn)模糊查詢，從而提高用戶與系統(tǒng)之間的交互能力.

1 XML模糊查詢謂詞的構(gòu)成形式

傳統(tǒng)的XPath查詢形式由路徑(path)和基于內(nèi)容的查詢謂詞(value-based predicate)2部分構(gòu)成.基于內(nèi)容的查詢謂詞形式為AθY，其中A代表XML數(shù)據(jù)樹的葉節(jié)點，θ代表操作運算中的規(guī)則關(guān)系(例如=、＞、＜、≥、≤、≠、(not)between)，Y代表操作數(shù)(用戶查詢要求中指定的精確查詢值).在實際應(yīng)用中，由于用戶提出的模糊查詢要求通常體現(xiàn)在基于內(nèi)容的查詢謂詞中，也就是說在查詢謂詞中使用模糊關(guān)系(如“close to”)或模糊詞(如“young”).因此，本文主要研究XML模糊查詢謂詞的構(gòu)成形式及其向精確查詢謂詞的轉(zhuǎn)換方法.模糊查詢謂詞是由規(guī)則關(guān)系與模糊詞的結(jié)合或模糊關(guān)系(如(not)at most、(not)at least、(not)close to/around)與精確值的結(jié)合而構(gòu)成的，這類基本模糊謂詞條件可由具有隸屬函數(shù)的模糊集來表示.

1.1 模糊詞作為操作數(shù)

模糊詞作為操作數(shù)與規(guī)則關(guān)系作為操作符構(gòu)成的模糊查詢謂詞，形式為Aθ，其中A代表XML數(shù)據(jù)樹的葉節(jié)點，θ代表規(guī)則關(guān)系，是模糊詞.其中模糊詞包括簡單模糊詞、復(fù)合模糊詞和混合模糊詞，它們的含義都可由模糊集合表示［8］.

1.2 模糊關(guān)系作為操作符

精確值作為操作數(shù)與模糊關(guān)系作為操作符構(gòu)成的模糊查詢謂詞，形式為AY，其中A代表XML數(shù)據(jù)樹的葉節(jié)點是模糊關(guān)系，Y代表精確值，Y是一個模糊集.在前期工作［9，18］中，筆者已討論了由上述3種模糊關(guān)系與精確值構(gòu)成的模糊集隸屬函數(shù)的構(gòu)建方法.

1.3 數(shù)值區(qū)間作為操作數(shù)

數(shù)值區(qū)間作為操作數(shù)與規(guī)則關(guān)系作為操作符構(gòu)成的查詢條件，形式為AθY，其中A代表XML數(shù)據(jù)樹的葉節(jié)點，θ代表規(guī)則關(guān)系“between”，Y代表數(shù)值區(qū)間，用［Y1，Y2］表示.AθY的形式為“A between Y1and Y2”.這里，按照隸屬函數(shù)和用戶給出的閾值對數(shù)值區(qū)間進(jìn)行模糊擴展.

下面，結(jié)合具體實例描述以上3種情況下模糊查詢謂詞向精確查詢謂詞的轉(zhuǎn)換方法.

2 領(lǐng)域知識庫

領(lǐng)域知識庫由若干XML文檔構(gòu)成，存儲領(lǐng)域知識信息，這些信息用來對模糊查詢謂詞進(jìn)行轉(zhuǎn)換，這些信息包括模糊查詢謂詞涉及的葉節(jié)點，以及根據(jù)葉節(jié)點的語義對模糊查詢謂詞進(jìn)行擴展的范圍和程度.領(lǐng)域知識庫由領(lǐng)域?qū)＜揖S護或自學(xué)習(xí)獲取知識.

2.1 文檔的DTD

本文引言部分的模糊查詢謂詞轉(zhuǎn)換需要如下4個XML文檔.

文檔NodeRelax.xml提供 XML數(shù)據(jù)樹的葉節(jié)點信息.llimit和rlimit分別代表查詢謂詞所涉及的葉節(jié)點上進(jìn)行擴展的數(shù)值區(qū)間左極限和右極限;nimp中的語義詞代表該葉節(jié)點在XML文檔中的重要程度，這也是查詢條件中相應(yīng)的查詢謂詞的重要程度.

2.1.1 NodeRelax.xml的 DTD

＜!DOCTYPE NodeRelax［

＜!ELEMENT NodeRelax(nrelax*)＞

＜!ELEMENT nrelax(leaf_node，llimit，rlimit，nimp)＞

＜!ELEMENT leaf_node(#PCDATA)＞

＜!ELEMENT llimit(#PCDATA)＞

＜!ELEMENT rlimit(#PCDATA)＞

＜!ELEMENT nimp(#PCDATA)＞］＞

文檔NodeImportance.xml存儲表達(dá)葉節(jié)點重要程度的語義詞(如 high、medium、low 等)，mdegree代表nimp中不同語義詞所對應(yīng)的隸屬度.

2.1.2 NodeImprotance.xml的 DTD＜!DOCTYPE NodeImportance［

＜!ELEMENT NodeImportance(nimportance*)＞

＜!ELEMENT nimportance(nimp，leaf_node，mdegree)＞

＜!ELEMENT nimp(#PCDATA)＞

＜!ELEMENT leaf_node(#PCDATA)＞

＜!ELEMENT mdegree(#PCDATA)＞］＞

文檔Relaxation.xml指明了查詢謂詞在相應(yīng)葉節(jié)點上的擴展范圍、擴展程度和葉節(jié)點上的值對查詢謂詞的滿足方式.Directionrel代表查詢擴展范圍，例如查詢謂詞“Price around(大約)100 000”，如果Directionrel的值為“l(fā)eft、right”，則“Price”的擴展范圍同時包括小于和大于100 000的值.ldegrel和rdegrel分別代表查詢謂詞的左右擴展程度.lsatisfy和rsatisfy分別表示擴展范圍內(nèi)葉節(jié)點的值對查詢謂詞的滿足方式.例如，當(dāng)lsatisfy取值為“non desc”時，表示葉節(jié)點“Price”上小于100 000的值對查詢謂詞的滿足程度等于1;當(dāng)lsatisfy取值為“desc”時，表示葉節(jié)點“Price”上小于100 000的值對查詢謂詞的滿足程度小于1.

2.1.3 Relaxation.xml的 DTD＜!DOCTYPE Relaxation［

＜!ELEMENT Relaxation(relax*)＞

＜!ELEMENT relax(leaf_node，operator，directionrel，ldegrel，rdegrel，lsatisfy，rsatisfy)＞

＜!ELEMENT leaf_node(#PCDATA)＞

＜!ELEMENT operator(#PCDATA)＞

＜!ELEMENT directionrel(#PCDATA)＞

＜!ELEMENT ldegrel(#PCDATA)＞

＜!ELEMENT rdegrel(#PCDATA)＞

＜!ELEMENT lsatisfy(#PCDATA)＞

＜!ELEMENT rsatisfy(#PCDATA)＞］＞

文檔FuzzyTerm.xml存儲描述葉節(jié)點取值范圍的模糊詞，每個模糊詞都對應(yīng)一個預(yù)先定義的模糊集，模糊集的隸屬函數(shù)參數(shù)分別取自元素para1、para2、para3、para4中的值.

2.1.4 FuzzyTerm.xml的 DTD

＜!DOCTYPE FuzzyTerm［

＜!ELEMENT FuzzyTerm(fterm*)＞

＜!ELEMENT fterm(fuzzy_term，leaf_node，para1，para2，para3，para4)＞

＜!ELEMENT fuzzy_term(#PCDATA)＞

＜!ELEMENT leaf_node(#PCDATA)＞

＜!ELEMENT para1(#PCDATA)＞

＜!ELEMENT para2(#PCDATA)＞

＜!ELEMENT para3(#PCDATA)＞

＜!ELEMENT para4(#PCDATA)＞］＞

2.2 文檔實例

2.2.1 NodeRelax.xml文檔實例

＜NodeRelax＞

＜nrelax＞

＜leaf_node＞Price＜/leaf_node＞

＜llimit＞150 000＜ /llimit＞

＜rlimit＞1 000 000＜/rlimit＞

＜nimp＞high＜/nimp＞

＜/nrelax＞

＜nrelax＞

＜leaf_node＞SqFt＜/leaf_node＞

＜llimit＞ － ＜/llimit＞

＜rlimit＞800＜/rlimit＞

＜nimp＞medium＜/nimp＞

＜/nrelax＞

＜nrelax＞

＜leaf_node＞Buildyear＜/leaf_node＞

＜llimit＞1981＜ /llimit＞

＜rlimit＞ － ＜/rlimit＞

＜nimp＞medium＜/nimp＞

＜/nrelax＞

…

＜/NodeRelax＞

2.2.2 NodeImportance.xml文檔實例

＜NodeImportance＞

＜nimportance＞

＜nimp＞high＜/nimp＞

＜leaf_node＞Price＜/leaf_node ＞

＜mdegree＞0.8＜ /mdegree＞

＜/nimportance＞

＜nimportance＞

＜nimp＞medium＜/nimp＞

＜leaf_node＞SqFt＜/leaf_node ＞

＜mdegree＞0.5＜ /mdegree＞

＜/nimportance＞

＜nimportance＞

＜nimp＞medium＜/nimp＞

＜leaf_node＞Buildyear＜/leaf_node ＞

＜mdegree＞0.5＜ /mdegree＞

＜/nimportance＞

…

＜/NodeImportance＞

2.2.3 Relaxation.xml文檔實例

＜Relaxation＞

＜relax＞

＜leaf_node＞Price＜/leaf_node＞

＜o(jì)perator＞at most＜ /operator＞

＜directionrel＞right＜ /directionrel＞

＜ldegrel＞－＜/ldegrel＞

＜rdegrel＞0.2 ＜ /rdegrell＞

＜lsatisfy＞nondecr＜/lsatisfy＞

＜rsatisfy＞decr＜/rsatisfy＞

＜/relax＞

＜relax＞

＜leaf_node＞SqFt＜/leaf_node＞

＜o(jì)perator＞between＜/operator＞

＜directionrel＞left，right＜ /directionrel＞

＜ldegrel＞－＜/ldegrel＞

＜rdegrel＞ － ＜/rdegrell＞

＜lsatisfy＞decr＜/lsatisfy＞

＜rsatisfy＞nondecr＜/rsatisfy＞

＜/relax＞

＜relax＞

＜leaf_node＞Buildyear＜/leaf_node＞

＜o(jì)perator＞ = ＜/operator＞

＜directionrel＞left，right＜ /directionrel＞

＜ldegrel＞－＜/ldegrel＞

＜rdegrel＞ － ＜/rdegrell＞

＜lsatisfy＞decr＜/lsatisfy＞

＜rsatisfy＞decr＜/rsatisfy＞

＜/relax＞

…

＜/Relaxation＞

2.2.4 FuzzyTerm.xml文檔實例

＜FuzzyTerm＞

＜fterm＞

＜fuzzy_term＞recent＜/fuzzy_term ＞

＜leaf_node＞Buildyear＜/leaf_node ＞

＜para1＞0＜/para1＞

＜para2＞0＜/para2＞

＜para3＞5＜/para3＞

＜para4＞10＜/para4＞

＜/fterm＞

＜fterm＞

＜fuzzy_term＞moderate＜/fuzzy_term ＞

＜leaf_node＞SqFt＜/leaf_node ＞

＜para1＞80＜/para1＞

＜para2＞130＜/para2＞

＜para3＞200＜/para3＞

＜para4＞250＜/para4＞

＜/fterm＞

…

＜/FuzzyTerm＞

3 XML模糊查詢轉(zhuǎn)換方法

本文提出的XML模糊查詢轉(zhuǎn)換實現(xiàn)方法首先將模糊查詢條件中的每個模糊查詢謂詞用相應(yīng)的模糊集表示，然后借助領(lǐng)域知識庫中的領(lǐng)域知識構(gòu)建隸屬函數(shù)，同時根據(jù)模糊查詢謂詞的重要程度(在提出查詢要求時，用戶可根據(jù)個人偏好指定每個查詢謂詞的重要程度)，利用權(quán)重函數(shù)對其進(jìn)行放松處理，最后根據(jù)閾值和α-截集運算將其轉(zhuǎn)換成精確查詢謂詞.本節(jié)將使用引言中的例子:

結(jié)領(lǐng)域知識庫中的領(lǐng)域知識，描述不同情況下的模糊查詢謂詞轉(zhuǎn)換實現(xiàn)方法.

3.1 含模糊關(guān)系的模糊查詢謂詞轉(zhuǎn)換

對于模糊查詢條件中的模糊查詢謂詞“Price at most 300 000”，使用模糊集P表示該模糊查詢謂詞.為了確定模糊集P的隸屬函數(shù)，首先從領(lǐng)域知識庫文檔Relaxation.xml中找出對應(yīng)模糊關(guān)系“at most”和葉節(jié)點“Price”的左右擴展方向(Relaxation.xml中的directionrel元素)，葉節(jié)點值對模糊查詢謂詞的滿足方式Relaxation.xml中的 lsatisfy和 rsatisfy元素.這里，對應(yīng)葉節(jié)點“Price”和模糊關(guān)系“at most”的擴展方向directionrel元素取值為“right”，葉節(jié)點值對模糊查詢謂詞的滿足方式lsatisfy和rsatisfy元素取值分別為“nondecr”、“decr”.然后，再根據(jù)模糊集“close to Y”的隸屬函數(shù)［9］，可將模糊集P的隸屬函數(shù)定義為:

對于參數(shù)d的計算，需要用到Relaxation.xml中提供的擴展程度rdegrel元素的值.在Relxation.xml中葉節(jié)點Price上對應(yīng)模糊關(guān)系“at most”的向右擴展程度rdegrel=0.2，該擴展程度與模糊查詢謂詞的重要程度μimportance(high)=0.8相關(guān)，于是有

因此，隸屬函數(shù)式(1)可轉(zhuǎn)換成:

假設(shè)用戶(或系統(tǒng))設(shè)定的閾值為0.8，則模糊集P的0.8截集運算結(jié)果為:

根據(jù)文獻(xiàn)［8-9］提出的模糊查詢轉(zhuǎn)換規(guī)則，模糊查詢謂詞“Price at most 300 000”可轉(zhuǎn)換成精確查詢謂詞“Price 312 000”.

3.2 含模糊詞的模糊查詢謂詞的轉(zhuǎn)換

對于模糊查詢條件中的模糊查詢謂詞“Buildyear=more or less recent(建筑時間比較近)”，使用模糊集B表示該模糊查詢謂詞.首先從知識庫文檔FuzzyTerm.xml中找到描述葉節(jié)點“Buildyear”的模糊詞“Recent”及其對應(yīng)的參數(shù)值(注意，計算過程中將建筑時間轉(zhuǎn)換成距今的年數(shù)).然后，構(gòu)建模糊詞“Recent”的隸屬函數(shù)，即

根據(jù)擴張原理和模糊詞“Recent”的隸屬函數(shù)，則可得模糊集B的隸屬函數(shù)為

然而，該隸屬函數(shù)沒有考慮它所代表的模糊查詢謂詞的重要程度(假設(shè)用戶指定該模糊查詢謂詞的重要程度為“medium”).為了使隸屬函數(shù)式(2)體現(xiàn)模糊查詢謂詞的重要程度，本文利用了文獻(xiàn)［19-20］提出的權(quán)重函數(shù)對隸屬函數(shù)式(2)進(jìn)行轉(zhuǎn)換，即

式中:w代表模糊查詢謂詞的重要程度.根據(jù)知識庫文檔 NodeImportance.xml，可得式(3)中的 w=μimportance(medium)=0.5.于是，得到轉(zhuǎn)換后的隸屬函數(shù)為

權(quán)重函數(shù)的功能是根據(jù)用戶指定的模糊查詢謂詞在模糊查詢條件中的權(quán)重來決定其擴展程度.對于同一個模糊查詢謂詞，其重要程度越高，則擴展程度越小，在相同閾值下的查詢范圍相應(yīng)地越小，這樣才能確保轉(zhuǎn)換后得到的精確查詢謂詞與用戶查詢意圖和偏好最為相關(guān).

根據(jù)隸屬函數(shù)(4)，假設(shè)用戶(或系統(tǒng))設(shè)定的閾值為0.8，則模糊集B的0.8截集運算結(jié)果為

這樣，模糊查詢謂詞“Buildyear=more or less recent”可轉(zhuǎn)換成精確查詢謂詞“Buildyear≤8.2”.需要說明一點，若給定的閾值α低于(1－w)，則α-截集運算結(jié)果規(guī)定為該模糊查詢謂詞所對應(yīng)隸屬函數(shù)的支集.

3.3 含數(shù)值區(qū)間的模糊查詢謂詞的轉(zhuǎn)換

考慮模糊查詢謂詞“SqFt between 130 and 200”，使用模糊集S表示該模糊查詢謂詞.為了確定模糊集S的隸屬函數(shù)，需要在知識庫文檔Fuzzy-Term.xml中找出一個模糊詞，該模糊詞滿足如下2個條件:1)代表該模糊詞的模糊集與模糊查詢謂詞的隸屬函數(shù)形狀相同;2)代表該模糊詞的模糊集的核與模糊查詢謂詞所指定的數(shù)值區(qū)間具有相同范圍.通過查找，發(fā)現(xiàn)知識庫中描述葉節(jié)點“SqFt”的模糊詞“moderate”滿足上述條件(即模糊詞“moderate”的隸屬函數(shù)為梯形隸屬函數(shù)，并且其核為［130，200］)，因此模糊集S的隸屬函數(shù)可由定義模糊詞“moderate”的隸屬函數(shù)表示，即

如果文檔FuzzyTerm.xml中不存在滿足上述條件的模糊詞，需要采用如下方法解決:假設(shè)［Y1，Y2］為模糊查詢謂詞指定的數(shù)值區(qū)間，則代表該模糊查詢謂詞的隸屬函數(shù)取值分別為

式中:λ(λ∈［0，1］)是閾值，λ 值越小，則該模糊查詢謂詞的模糊集支集與核的距離越小.

假設(shè)用戶沒有指定模糊查詢謂詞“SqFt between 130 and 200”的重要程度，此時需訪問領(lǐng)域知識庫文檔NodeRelax.xml來獲取該模糊查詢謂詞對應(yīng)葉節(jié)點的權(quán)重(在NodeRelax.xml文檔中對應(yīng)葉節(jié)點SqFt的權(quán)重為“nimp=medium”)，利用權(quán)重函數(shù)g(0.5，S(s))=1－0.5(1 －S(s))對隸屬函數(shù)(5)進(jìn)行轉(zhuǎn)換，得到轉(zhuǎn)換后的隸屬函數(shù)為

假設(shè)用戶(或系統(tǒng))設(shè)定的閾值為0.8，則模糊集S的0.8截集運算結(jié)果為

這樣，模糊查詢謂詞“SqFt between 130 and 200”可轉(zhuǎn)換成精確謂詞“SqFt between 110 and 220”.

3.4 XML模糊查詢謂詞轉(zhuǎn)換算法

根據(jù)上述轉(zhuǎn)換方法，下面給出通用的XML模糊查詢謂詞轉(zhuǎn)換算法:

算法1 XML模糊查詢謂詞轉(zhuǎn)換算法

輸出:轉(zhuǎn)換后的精確查詢謂詞集合{C1，C2，…，Ck}.

1)Q←?;

3)MFS MembershipFunctionShape(relaxation direction，satisfaction type);

4)wj←用戶指定(或系統(tǒng)默認(rèn))的模糊查詢謂詞

5)if(擴展程度(relaxation degree)null)then

6)CjComputeMembershipFunction1(relaxdegree，wj，α);

7)else

9)Cj←ComputeMembershipFunction2(T，wj，α);

10)else

11)if(?FuzzyTerm T)∧(core(T)=的數(shù)值區(qū)間)∧(shape(T)=MFS)then

12)Cj←ComputeMembershipFunction2(T，wj，α);

13)else

14)Cj←ComputeMembershipFunction3(f_interval，wj，α);

15)return{C1，C2，…，Ck}.

4 查詢匹配與結(jié)果排序方法

4.1 查詢匹配方法

對于Xpath查詢匹配方法，本文利用了文獻(xiàn)［21］提出的基于TwigStack的查詢結(jié)構(gòu)匹配方法.

函數(shù):TwigStack(Q，T1，T2，…，Tn).

輸入:小查詢Q，n個查詢結(jié)點流T1，T2，…，Tn(其中n代表查詢Q的查詢結(jié)點數(shù)量).

輸出:按從葉到根有序的小枝查詢Q的匹配結(jié)果.

1)while(not end(Q))//如果查詢Q沒有結(jié)束，執(zhí)行循環(huán);

2)qact←getNext(Q);//取下一個XPath查詢條件;

3)if(isRoot(qact)or(not empty(Sparent(Qact))))//如果qact是根或//qact父親不為空;

4)cleanStack(Sqact，nextBegin(Tqact));//將qact待匹配結(jié)點流中 begin值最小的流放入//Sqact;

5)moveStreamToStack(Tqact，Sqact，pointer to top(Sparent(qact)));

6)if(!isRoot(qact))//當(dāng)qact不是根時;

7)cleanStack(Sparent(qact)，nextBegin(Tqact));//下一個待查詢結(jié)點入棧;

8)if(isLeaf(qact))//當(dāng)qact是葉節(jié)點時;

9)showSolutions(qact，1);

10)pop(Sqact);

11)else advance(Tqact);

12)mergeAllPathSolutions().

子函數(shù):cleanStack(S，actBegin)

1)while(not empty(S)and topEnd(S)＜actBegin)

2)pop(S).

子函數(shù):getNext(Q)

1)if(isLeaf(Q))return Q;

2)for(every qiin children(Q))

3)ni=getNext(qi);

4)if(ni!=qi)return ni;

5)nmin=minargni{nextBegin(Tni)};

6)nmax=maxargni{nextBegin(Tni)};

7)while(nextEnd(Tq)＜nextBegin(Tnmax))

8)advance(Tq);

9)if(nextBegin(Tq)＜nextBegin(Tnmin))return Q;

10)else return nmin.

子函數(shù):showSolutions(SN，SP).

/*假設(shè)路徑查詢q中從根到葉的n個查詢結(jié)點的棧編號為1，2，…，n，假設(shè)通過數(shù)據(jù) index［1，2，…，n］存儲正在生成的匹配結(jié)果在各個棧中的位置，即index［i］表示正在生成的匹配結(jié)果n元組中第i個數(shù)據(jù)結(jié)點在第i個棧中的位置.這里，1代表棧底位置，SN，SP分別表示當(dāng)前正在處理棧的編號以及棧中當(dāng)前正在處理數(shù)據(jù)結(jié)點的位置.*/

1)index［SN］ =SP;

2)if(SN==1)//當(dāng)前正在處理根棧;

3)output(index［n］，…，index［1］);//輸出來自棧鏈的已經(jīng)生成的匹配結(jié)果n元組

4)else//遞歸調(diào)用

5)for(i=1 to index［SN］.pointer)index［SN］.pointer//表示index［SN］所指向結(jié)點在雙親棧中的位置

6)showSolutions(SN －1，i).

4.2 結(jié)果排序方法

模糊查詢結(jié)果排序的基本思想是按結(jié)果元素對模糊查詢的滿足程度進(jìn)行排序.結(jié)果元素t對模糊查詢的滿足程度定義為

5 實驗測試與結(jié)果分析

5.1 實驗環(huán)境和測試數(shù)據(jù)

所有實驗都是在配置為Pentium(R)Dual-Core CPU E6500@2.93GHz，2GB 內(nèi)存，160GB、7200rpm硬盤和Microsoft Windows XP操作系統(tǒng)下進(jìn)行，使用SAX2解析XML文檔，用Java和eclipse集成環(huán)境開發(fā)實驗系統(tǒng).測試文檔由 IBM XML data generator［22］產(chǎn)生，生成2個XML數(shù)據(jù)集，Car DB和 House DB的文檔結(jié)構(gòu)如圖1所示).1)CarDB.xml數(shù)據(jù)集:從 http://autos.yahoo.com/網(wǎng)站隨機抽取了200 000條二手車信息，利用IBM XML data generator生成 CarDB.xml數(shù)據(jù)集，該數(shù)據(jù)集包括200 000個UsedCar元素.

圖1 CarDB和HouseDB的文檔結(jié)構(gòu)圖Fig.1 The schema of CarDB and House DB

2)HouseDB 數(shù)據(jù)集:從 http://homes.yahoo.com/網(wǎng)站隨機抽取了250 000條房產(chǎn)信息記錄，利用IBM XML data generator生成 HouseDB.xml數(shù)據(jù)集，該數(shù)據(jù)集包括250 000個House元素.

5.2 測試模糊查詢效果

該實驗以用戶調(diào)查方式測試XML模糊查詢方法的查全率(recall)和準(zhǔn)確率(precision).查全率是指查詢結(jié)果中的相關(guān)元素數(shù)占文檔中相關(guān)元素總數(shù)的百分比.準(zhǔn)確率是指查詢結(jié)果中的相關(guān)元素數(shù)占查詢結(jié)果中總元素數(shù)的百分比.邀請了10位測試者，每位測試者根據(jù)自己的需求和偏好，對CarDB和HouseDB分別提出各1條模糊查詢進(jìn)行效果測試.用戶提出的測試模糊查詢?nèi)绫?所示.

表1 HouseDB和CarDB上的模糊測試查詢Table 1 Fuzzy test queries over HouseDB and CarDB

對于CarDB和HouseDB上的每個測試查詢Qi，從原始數(shù)據(jù)集中為其生成一個小型數(shù)據(jù)集Hi，Hi中包含了60個與該查詢相關(guān)的和不相關(guān)的適量元素.然后，將所有測試查詢和相應(yīng)數(shù)據(jù)集提供給每個測試者，讓這些測試者從Hi中標(biāo)出與查詢Qi相關(guān)的所有元素.最后將系統(tǒng)返回的結(jié)果與用戶標(biāo)注的結(jié)果進(jìn)行對比來測試本文方法的查全率和準(zhǔn)確率.

本文的測試方法是從0～100%之間選取10個不同的查全率水平，然后計算對應(yīng)的準(zhǔn)確率(通過調(diào)整閾值，可以獲得不同的查全率).也就是說，對于由本文方法返回的模糊查詢結(jié)果，用戶逐個檢查結(jié)果元素是否為用戶標(biāo)注的相關(guān)元素.如果是相關(guān)元素，則對應(yīng)該元素的準(zhǔn)確率為100%，否則為0，最終該測試查詢的準(zhǔn)確率為所有結(jié)果元素對應(yīng)準(zhǔn)確率的平均值.圖2給出了從0～100%之間選取的10個不同查全率水平下獲得的對應(yīng)準(zhǔn)確率.圖中顯示的評估值是分別在CarDB和HouseDB上的10個測試查詢的準(zhǔn)確率的平均值.

圖2 HouseDB和CarDB上的查全率和準(zhǔn)確率Fig.2 Precision and recall over HouseDB and CarDB

從圖2中可以看出，高準(zhǔn)確率的獲得是以查全率的犧牲為代價的，反之亦然.但該實驗主要反映的是，當(dāng)本文方法的查全率為100%時，HouseDB和CarDB上的平均準(zhǔn)確率分別為71%和69%;當(dāng)查全率為90%時，HouseDB和CarDB上的平均準(zhǔn)確率均為73%;當(dāng)查全率為80%時，HouseDB和CarDB上的平均準(zhǔn)確率分別為78%和76%.由于用戶在提交查詢時可以根據(jù)個人偏好為查詢謂詞指定重要程度，因此返回的查詢結(jié)果也就更能貼近用戶需求和偏好.也就是說，本文提出的模糊查詢方法能夠同時具有較高的查全率和準(zhǔn)確率.

5.3 測試結(jié)果排序質(zhì)量

該實驗?zāi)康氖菧y試結(jié)果排序方法的排序質(zhì)量.為了觀察不同測試查詢下排序方法的質(zhì)量，讓測試者從他們所標(biāo)注的相關(guān)元素中選出最相關(guān)的前10個元素.然后，分別在CarDB和HouseDB上執(zhí)行排序方法為每條測試查詢返回前10個元素.本文采用式(7)所示的排序準(zhǔn)確率評價排序質(zhì)量:

式中:ri代表排序函數(shù)返回的元素列表中第i個元素的得分(若該元素被標(biāo)記為最相關(guān)的，則ri取值為1，否則ri取值為0).可見，在R度量方法下，如果本文排序方法返回的相關(guān)元素在列表中所處的位置越靠前，則它對R值的影響就越大.對于每個測試查詢，取10個測試者根據(jù)式(7)計算得到的平均排序準(zhǔn)確率作為該查詢結(jié)果的排序準(zhǔn)確率.圖3給出了在CarDB和HouseDB上對應(yīng)于每個測試查詢的查詢結(jié)果排序準(zhǔn)確率.實驗結(jié)果表明，本文提出的排序方法在2個數(shù)據(jù)集上的平均排序準(zhǔn)確率分別達(dá)到0.77 和 0.80.

圖3 HouseDB和CarDB上的排序準(zhǔn)確率Fig.3 Ranking quality over HouseDB and CarDB

5.4 響應(yīng)時間測試

本文方法的執(zhí)行過程主要包括模糊查詢轉(zhuǎn)換和結(jié)果排序處理2個階段.第1階段完成模糊查詢謂詞到精確查詢謂詞的轉(zhuǎn)換，其時間復(fù)雜度為O(mk)，其中m代表模糊查詢條件中的模糊查詢謂詞個數(shù)，k代表每個模糊查詢謂詞所涉及知識庫文檔中包含的不同元素個數(shù)的平均數(shù).第2階段包括結(jié)果元素的排序分值計算和排序處理2個部分，結(jié)果元素的排序分值計算時間復(fù)雜度為O(n)，n代表結(jié)果元素個數(shù);排序處理的時間復(fù)雜度為O(nlog n)，n代表結(jié)果元素個數(shù).因此，第2階段的總體時間復(fù)雜度為O(nlog n).圖4給出了本文方法在2個數(shù)據(jù)集上不同結(jié)果元素個數(shù)下的響應(yīng)時間.從圖中可以看出，本文的響應(yīng)時間隨著查詢結(jié)果元素個數(shù)的增加幾乎呈線性增長趨勢.

圖4 不同查詢結(jié)果元素個數(shù)下的響應(yīng)時間Fig.4 Response time of different number of elements in query results

6 結(jié)束語

本文以模糊集理論為基礎(chǔ)，提出了一種利用隸屬函數(shù)、領(lǐng)域知識和模糊集的α-截集運算相結(jié)合實現(xiàn)XML模糊查詢和結(jié)果排序的方法.該方法不需要改變傳統(tǒng)XDBMS的結(jié)構(gòu)和XML查詢語言就能夠?qū)崿F(xiàn)XML數(shù)據(jù)的模糊查詢轉(zhuǎn)換和結(jié)果排序處理，從而在很大程度上提高了用戶與系統(tǒng)之間的交互能力.實驗結(jié)果表明，本文方法能夠同時具有較高的查詢準(zhǔn)確率和查全率，具有較好的查詢結(jié)果排序質(zhì)量，能夠較好地滿足用戶需求和偏好.未來工作將從查詢結(jié)果排序和知識庫的自學(xué)習(xí)方面作進(jìn)一步的完善.

［1］BRAY T.Extensible markup language(XML)1.0［CP/OL］.［2011-03-18］.http://www.w3.org/TR/REC-xml/.

［2］TAHANI V.A comceptual framework for fuzzy querying processing:a step toward very intelligent databases systems［J］.Information Processing Management，1997，13:289-303.

［3］ZADEH L A.Fuzzy sets［J］.Information and Control，1965，8(3):338-353.

［4］BOSC P，PIVERT O.SQLf:a relational database language for fuzzy querying［J］.IEEE Transactions on Fuzzy Systems，1995，3(1):1-17.

［5］BOSC P，PIVERT O.Extending SQL retrieval features for the handing of flexible queries［C］//Proceedings of International Conference on Fuzzy Information Engineering.New-York，USA，1997:233-251.

［6］BOSC P，GALIBOURG M，HAMON G.Fuzzy querying with SQL:extensions and implementation aspects［J］.Fuzzy Sets Systems，1988，28:333-349.

［7］NAKAJIMA H，SOGOH T，ARAO M.Fuzzy database language and library:fuzzy extension to SQL［C］//Proceedings of the 1993 International Conference on Fatigue Science.Washington DC，USA，1993:477-482.

［8］CHEN S M，JONG W T.Fuzzy query translation for relational database systems［J］.IEEE Transcations Systems，Man，and Cybernetics，Part B:Cybernetics，1997，27(4):714-721.

［9］MA Z M，YAN Li.Generalization of strategies for fuzzy query translation in classical relational databases［J］.Information and Software Technology，2007，49(2):172-180.

［10］李言輝，徐寶文，陸建江.一般術(shù)語公理下的模糊描述邏輯FALCN推理［J］.軟件學(xué)報，2008，19(3):594-604.LI Yanhui，XU Baowen，LU Jianjiang.Reasoning with general terminological axioms in fuzzy description logic FALCN［J］.Journal of Software，2008，19(3):594-604.

［11］康達(dá)周，徐寶文，陸建江，等.支持模糊隸屬度比較的擴展模糊描述邏輯［J］.軟件學(xué)報，2008，19(10):2498-2507.KAN Dazhou，XU Baowen，LU Jianjiang，et al.Extended fuzzy description logics with comparisons between fuzzy membership degrees［J］.Journal of Software，2008，19(10):2498-2507.

［12］KANZA Y，SAGIV Y.Flexible queries over semi-structured data［C］//Proceedings of the 20th ACM SIGACTSIGMOD Symposium on Principles of Database Systems.Scottsdale，USA，2001:40-51.

［13］王真星，顧寧，施伯樂.基于本體的半結(jié)構(gòu)化數(shù)據(jù)的柔性查詢［J］.計算機研究與發(fā)展，2003，40(11):1571-1578.WANG Zhenxing，GU Ning，SHI Bole.An ontology-based flexible query method for semistructured data［J］.Journal of Computer Research and Development，2003，40(11):1571-1578.

［14］POLYZOTIS N，GAROFALAKIS M，IOANNIDIS Y.Approximate XML query answers［C］//Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data.Paris，F(xiàn)rance，2004:263-274.

［15］MANDREOLI F，MARTOGLIA R，TIBERIO P.Approximate query answering for a heterogeneous XML document base［C］//Proceedings of the International Conference on Web Information Systems Engineering.Brisbane，Australia，2004:337-351.

［16］SPIEGEL J，PONTIKAKIS E D，BUDALAKOTI S，et al.AQAX:a system for approximate XML query answers［C］//Proceedings of the 32nd International Conference on Very Large Data Bases.Seoul，Korea，2006:1159-1162.

［17］衡星辰，覃征，邵利平，等.基于兩階段查詢重寫的XML近似查詢算法［J］.電子學(xué)報，2007，35(7):1271-1278.HENG Xingchen，QIN Zheng，SHAO Liping，et al.Twophase query rewriting based approximate XML query algorithm［J］.Chinese Journal of Electronics，2007，35(7):1271-1278.

［18］MA Z M，MENG X F.A knowledge-based approach for answering fuzzy queries over relational databases［C］//Proceedings of the 12th International Conference on Knowledge-based and Intelligent Information and Engineering Systems.Zagreb，Croatia，2008:623-630.

［19］LARSEN H L.An approach to flexible information access systems using soft computing［C］//Proceedings of the 32nd Annual International Conference on System Sciences.Maui，USA，1999:6042.

［20］YAGER R R.Information fusion and weighted median aggregation［C］//Proceedings of the 5th International Work-shop on Current Issues in Fuzzy Technologies.Trento，Italy，1995:209-219.

［21］BRUNO N，KOUDAS N，SRIVASTAVA D.Holistic twig joins:optimal XML pattern matching［C］//Proceedings of the 2002 ACM SIGMOD Conference on Management of Data.Madison，USA，2002:310-321.

［22］IBM Corporation.XML data generator［EB/OL］.［2011-10-15］.http://www.alphaworks.ibm.com/tech/xmlgenerator.