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

無效

• 申請(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é)任公司
• 代理人: 陳翠蘭

1.一種基于多樣性XML文檔近似查詢方法，其特征在于：該方法包括XML文檔多樣性處理，單DTD下XML文檔近似查詢，查詢代價(jià)評(píng)估和Top-K問題求解四個(gè)部分；

XML文檔多樣性處理模塊采用基于PTO模型的映射規(guī)則自動(dòng)生成算法將用戶在全局查詢模式下提出的原始查詢重寫為不同DTD下的重寫查詢樹；單DTD下XML文檔近似查詢模塊利用重寫查詢樹，結(jié)合基本變異操作，通過對(duì)變異查詢樹的多次精確嵌入實(shí)現(xiàn)了單DTD下XML文檔集的近似查詢；查詢代價(jià)評(píng)估模塊采用基于XML樣本數(shù)據(jù)分布統(tǒng)計(jì)的方法，計(jì)算了每一個(gè)查詢結(jié)果的查詢代價(jià)；Top-K問題求解模塊通過對(duì)結(jié)點(diǎn)進(jìn)行區(qū)間編碼，并借助最優(yōu)變異查詢樹的預(yù)先估計(jì)，最終實(shí)現(xiàn)了對(duì)多樣性XML文檔近似查詢的Top-K求解。

2.根據(jù)權(quán)利要求1所述的一種基于多樣性XML文檔近似查詢方法，其特征在于，XML文檔多樣性處理模塊的實(shí)現(xiàn)步驟如下：

1)依據(jù)基于本體的全局查詢模式，按照面向?qū)ο蟛樵冋Z言提出原始查詢；

2)依據(jù)PTO模型：(v₁，v₂)-＞c₁.role，c₂.inverse(role)|c₃.attribute，按如下步驟建立DTD和全局查詢模式之間的映射規(guī)則集：

(1)廣度優(yōu)先遍歷DTD樹T_DTD，抽取T_DTD中每條有向邊對(duì)應(yīng)的結(jié)點(diǎn)v₁和v₂，若已遍歷結(jié)束，轉(zhuǎn)步(4)；否則，轉(zhuǎn)步(2)；

(2)查找v₁和v₂在全局查詢模式圖G中對(duì)應(yīng)的概念結(jié)點(diǎn)v₁和v₂或?qū)傩詀ttribute，若找到，轉(zhuǎn)步(3)；否則，把二元組(v₁，v₂)加入集合Set₁中，轉(zhuǎn)步(1)；

(3)如果找到的是兩個(gè)概念結(jié)點(diǎn)c₁和c₂，則生成規(guī)則：(v₁，v₂)-＞c’₁.role，c’₂.inverse(role)，轉(zhuǎn)步(1)；如果找到的是一個(gè)概念結(jié)點(diǎn)c₁和屬性attribute，則生成規(guī)則：(v₁，v₂)-＞c₁.attribute，轉(zhuǎn)步(1)；

(4)對(duì)Set₁集合中的二元組使用規(guī)則：(x，y)，(y，z)|-(x，z)進(jìn)行擴(kuò)展，將新生成的擴(kuò)展二元組放入集合Set₂；

(5)遍歷集合Set₂，抽取其中每一個(gè)元組中的結(jié)點(diǎn)v₁和v₂；若已遍歷結(jié)束，則終止算法；否則，轉(zhuǎn)步(6)；

(6)查找v₁和v₂在全局查詢模式圖G中對(duì)應(yīng)的概念結(jié)點(diǎn)c₁和c₂或?qū)傩詀ttribute，若找到，轉(zhuǎn)步(7)；否則，轉(zhuǎn)步(5)；

(7)如果找到的是兩個(gè)概念結(jié)點(diǎn)c₁和c₂，生成規(guī)則：(v₁，v₂)-＞c’₁.role，c’₂.inverse(role)轉(zhuǎn)步(5)；如果找到的是一個(gè)概念結(jié)點(diǎn)c₁和屬性attribute，生成規(guī)則：(v₁，v₂)-＞c₁.attribute轉(zhuǎn)步(5)；

3)利用生成的映射規(guī)則集按模式路徑，概念和角色逐一映射的方式將原始查詢改寫為不同DTD下的結(jié)構(gòu)謂詞集，并由結(jié)構(gòu)謂詞集進(jìn)一步構(gòu)成為重寫查詢樹形式。