[發(fā)明專利]一種基于多樣性XML文檔近似查詢方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 200710018535.1
• 申請(qǐng)日: 2007-08-24
• 公開（公告）號(hào): CN101114291A
• 公開（公告）日: 2008-01-30
• 發(fā)明（設(shè)計(jì)）人: 覃征;衡星辰;邵利平;姜山
• 申請(qǐng)（專利權(quán)）人: 西安交通大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 西安通大專利代理有限責(zé)任公司
• 代理人: 陳翠蘭

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)設(shè)計(jì)與應(yīng)用技術(shù)領(lǐng)域，涉及計(jì)算機(jī)軟件、信息檢索技術(shù)、半結(jié)構(gòu)化數(shù)據(jù)處理技術(shù)、人工智能技術(shù)以及XML描述語(yǔ)言，特別涉及一種基于多樣性XML文檔的近似查詢方法。

背景技術(shù)

近年來，隨著XML(Extensible?Markup?Language)的出現(xiàn)，針對(duì)XML文檔半結(jié)構(gòu)化數(shù)據(jù)的查詢算法的研究逐漸引起了國(guó)內(nèi)外信息檢索領(lǐng)域人們的關(guān)注。XML文檔具有靈活的表達(dá)能力，而這種靈活的表達(dá)能力使得不同組織和個(gè)人建立的XML文檔，難以遵照一個(gè)統(tǒng)一的數(shù)據(jù)模式，即使內(nèi)容完全相同的文檔，不同的組織和個(gè)人也很難按照統(tǒng)一的標(biāo)準(zhǔn)來建立結(jié)構(gòu)和標(biāo)識(shí)內(nèi)容完全相同的XML文檔，從而造成了XML文檔數(shù)據(jù)的多樣性。如何針對(duì)WEB上的大量的多樣性的XML數(shù)據(jù)進(jìn)行有效的信息提取成為了XML數(shù)據(jù)管理研究的重要課題。

目前，已有的XML查詢方法的研究主要關(guān)注單DTD下XML文檔集的精確查詢和近似查詢，解決方法主要采用了以樹模型匹配作為理論基礎(chǔ)的結(jié)構(gòu)化連接算法等相關(guān)技術(shù)，并取得了較好的查詢效果。而當(dāng)針對(duì)多樣性XML文檔集時(shí)，則效果并不理想。

針對(duì)基于多樣性XML文檔的近似查詢方法，申請(qǐng)人經(jīng)過查新，檢索到與本發(fā)明緊密相關(guān)的專利1個(gè)，國(guó)內(nèi)文獻(xiàn)1篇，國(guó)外相關(guān)文獻(xiàn)1篇：

(一)相關(guān)專利(名稱、申請(qǐng)人或發(fā)明者)1個(gè)：

1.專利名稱：XML流數(shù)據(jù)的復(fù)雜小枝模式查詢匹配方法

專利申請(qǐng)人：復(fù)旦大學(xué)

(二)國(guó)內(nèi)相關(guān)文獻(xiàn)(標(biāo)題、作者或機(jī)構(gòu)、出處)1篇：

1.標(biāo)題：XML查詢中DTD的排序技術(shù)

刊名：計(jì)算機(jī)研究與發(fā)展，2003，40(11)：1579～1585.

(三)國(guó)外相關(guān)文獻(xiàn)(標(biāo)題、作者或機(jī)構(gòu)、出處)1篇：

1.Title：Schema-Driven?Evaluation?of?Approximate?Tree-Pattern?Queries

Author(s)：Torsten?Schlieder.

Source：8^th?International?Conference?on?Extending?Database?Technology，

Prague，Czech?Republic，March?25-27，2002：514-532.

對(duì)上述文獻(xiàn)分析如下：

在專利1中，發(fā)明人提出了一種XML流數(shù)據(jù)的復(fù)雜小枝模式查詢匹配方法。通過定義的緊湊小枝模式查詢樹，將復(fù)雜的AND/OR謂詞作為單獨(dú)的抽象語(yǔ)法樹來處理，同時(shí)，將所有小枝模式查詢組合成單個(gè)可共享公共前綴的查詢樹，利用提出的基于運(yùn)行棧的算法，結(jié)合自頂向下和自頂向上過程，單遍、高效處理基于XML流的任何復(fù)雜小枝查詢。

國(guó)內(nèi)文獻(xiàn)[1]中，對(duì)“候選DTD定位”，“候選DTD與用戶查詢結(jié)構(gòu)的距離排序”等技術(shù)進(jìn)行了研究。在對(duì)候選DTD與用戶查詢結(jié)構(gòu)的距離進(jìn)行接近線性時(shí)間復(fù)雜性的排序運(yùn)算時(shí)，提出了以“樹間亞距離排序”代替“樹間距離排序”的觀點(diǎn)，即以查詢結(jié)構(gòu)與查詢?cè)诤蜻xDTD中的上下文之間的距離，代替查詢結(jié)構(gòu)與候選DTD之間的距離參與排序，提高了候選DTD排序的準(zhǔn)確性。但文中沒有進(jìn)一步給出排序后的DTD對(duì)用戶的查詢結(jié)構(gòu)進(jìn)行重構(gòu)的方法以及結(jié)合該DTD排序技術(shù)的XML近似查詢算法框架。

國(guó)外文獻(xiàn)[1]中，提出了一種XML近似查詢語(yǔ)言-ApproXQL以及基于該語(yǔ)言的近似查詢算法。為了獲得和查詢最近似的K個(gè)結(jié)果文檔，該文從樹編輯距離的角度出發(fā)，通過對(duì)查詢表達(dá)式進(jìn)行基于代價(jià)的查詢變異來評(píng)估用戶查詢和XML文檔之間的近似度，最后按XML文檔所對(duì)應(yīng)的查詢變異代價(jià)總和來決定最好的K個(gè)查詢結(jié)果文檔。但查詢的實(shí)現(xiàn)，需要人工設(shè)定查詢結(jié)構(gòu)中各結(jié)點(diǎn)的插入、重命名等變異操作的代價(jià)，并且在變異查詢數(shù)量很多的情況下，求解最優(yōu)的K個(gè)結(jié)果文檔的效率并不高，另外，該文并沒有考慮多DTD下XML文檔查詢的多樣性問題。

發(fā)明內(nèi)容

為了克服上述現(xiàn)有技術(shù)存在的缺陷或不足，本發(fā)明提供了一種基于多樣性XML文檔的近似查詢方法，能夠?qū)Χ郉TD下的XML文檔集按照一種統(tǒng)一的方式提出查詢，并通過兩次查詢重寫準(zhǔn)確地查詢出滿足用戶查詢需求XML文檔序列，并按近似度高低進(jìn)行排序。

本發(fā)明的技術(shù)方案是這樣實(shí)現(xiàn)的：