XML數(shù)據(jù)實(shí)體同一性相關(guān)技術(shù)的研究.pdf

1、近年來,劣質(zhì)數(shù)據(jù)廣泛出現(xiàn)于信息社會的各個領(lǐng)域,引發(fā)了很多問題并帶來了巨大損失。關(guān)注該問題的數(shù)據(jù)可用性研究在國內(nèi)外已經(jīng)展開。實(shí)體同一性是數(shù)據(jù)可用性的重要維度之一。實(shí)體同一性基于數(shù)據(jù)庫中存儲的數(shù)據(jù)實(shí)體和現(xiàn)實(shí)世界中的物理實(shí)體定義。一個數(shù)據(jù)實(shí)體描述的是某個物理實(shí)體,是其在數(shù)據(jù)庫中的表示形式;一個數(shù)據(jù)庫被稱作是滿足實(shí)體同一性要求的,當(dāng)且僅當(dāng)數(shù)據(jù)庫中沒有任何兩個數(shù)據(jù)實(shí)體描述的是同一個物理實(shí)體。對數(shù)據(jù)實(shí)體同一性的研究是當(dāng)前數(shù)據(jù)處理領(lǐng)域的熱點(diǎn)研究問題之

2、一。針對關(guān)系數(shù)據(jù)的實(shí)體同一性研究已經(jīng)有很多工作,然而,其中大部分的理論和方法并不適用于非關(guān)系數(shù)據(jù),并且很難擴(kuò)展到非關(guān)系數(shù)據(jù)上。針對非關(guān)系數(shù)據(jù)的實(shí)體同一性研究工作還很少,尚處于起步階段。
　　本文針對一類廣泛使用的非關(guān)系數(shù)據(jù),即XML數(shù)據(jù),以完善XML數(shù)據(jù)可用性的管理技術(shù)為目標(biāo),從XML實(shí)體抽取、XML實(shí)體匹配以及實(shí)體匹配結(jié)果消解等問題切入,重點(diǎn)研究了XML數(shù)據(jù)實(shí)體同一性相關(guān)的技術(shù)。本文的主要工作可以概括如下:
　　首先,本文

3、提出并研究了XML數(shù)據(jù)上的實(shí)體抽取問題,提出了一種基于規(guī)則的實(shí)體自動抽取方法KEE。XML數(shù)據(jù)中沒有實(shí)體的明顯標(biāo)識,且現(xiàn)有的實(shí)體同一性研究工作并沒有考慮實(shí)體抽取問題,因此實(shí)體抽取是XML實(shí)體同一性研究的基礎(chǔ)之一。提出的KEE方法利用XML查詢描述實(shí)體,為實(shí)體提供了簡潔的表示方法,避免了逐一表示XML實(shí)體的不便;允許用戶利用鍵規(guī)則只描述感興趣的少量實(shí)體,并自動地為用戶尋找感興趣的其它實(shí)體;利用查詢松弛技術(shù),克服了在異構(gòu)數(shù)據(jù)上自動尋找相似實(shí)

4、體時實(shí)體難以枚舉、難以尋找的困難;基于自動機(jī)技術(shù),利用共享中間計(jì)算結(jié)果的思想,實(shí)現(xiàn)了高效的XML數(shù)據(jù)實(shí)體抽取算法。從理論角度分析了KEE方法的性能,并用實(shí)驗(yàn)驗(yàn)證了該算法能夠有效且高效地解決實(shí)體抽取問題。
　　第二,本文研究了XML實(shí)體匹配問題,以提高XML實(shí)體匹配效率為目標(biāo),提出了基于哈希方法的XML實(shí)體匹配算法。給定實(shí)體間的相似函數(shù),實(shí)體匹配是要找出所有相似函數(shù)值大于某個閾值的實(shí)體對,是檢測數(shù)據(jù)實(shí)體同一性錯誤的重要基礎(chǔ)。XML實(shí)

5、體匹配要同時處理數(shù)據(jù)中結(jié)構(gòu)和內(nèi)容兩部分信息,現(xiàn)有的技術(shù)僅關(guān)注內(nèi)容之間的相似性,無法高效解決XML實(shí)體匹配問題。提出的基于局部敏感哈希的實(shí)體匹配方法把相似的實(shí)體以很高的概率映射到一個分組,僅兩兩計(jì)算同一分組內(nèi)實(shí)體的相似函數(shù)值,大大提高了實(shí)體匹配的效率;考慮不同應(yīng)用,抽象出三類實(shí)體相似函數(shù)定義,證明三類函數(shù)均具備局部敏感特性,并給出對應(yīng)的哈希策略;基于三類函數(shù)的局部敏感哈希策略,給出了對應(yīng)的實(shí)體匹配算法。從理論角度分析并證明了算法的有效性,

6、并用實(shí)驗(yàn)驗(yàn)證了匹配算法的實(shí)際性能。
　　第三,本文研究了實(shí)體匹配結(jié)果的消解問題,以求解更具意義的消解方式為目標(biāo),提出了兩種形式化問題定義,并分別給出理論分析及算法。實(shí)體匹配的最終目標(biāo)是解決實(shí)體同一性錯誤檢測問題,即實(shí)體識別問題。將實(shí)體匹配結(jié)果轉(zhuǎn)化為實(shí)體識別結(jié)果的問題就是實(shí)體匹配結(jié)果消解問題。本文基于融合多個匹配算法以及對不同實(shí)體對的匹配結(jié)果置信度不同的思想,形式化地定義了兩種消解問題。針對最小化圖代價的定義,從理論上證明了消解問題

7、是NP完全問題;利用線性歸約,給出近似算法;針對特殊情況,給出近似比更優(yōu)的算法。針對最小化邊權(quán)值的定義,證明該問題是NP完全問題;給出基于求解線性規(guī)劃的近似算法;針對特殊情況,給出具有更優(yōu)近似比的隨機(jī)近似算法;針對大規(guī)模數(shù)據(jù)的情況,給出了四種啟發(fā)式算法;用實(shí)驗(yàn)驗(yàn)證算法的性能,并對比不同算法的時間效率。
　　最后,本文針對提出的實(shí)體抽取方法和匹配結(jié)果消解方法的不足,研究了兩個相關(guān)的優(yōu)化問題,分別從理論角度進(jìn)行了分析。本文給出的實(shí)體抽

8、取方法基于語義規(guī)則,但在某些應(yīng)用中,用戶無法給出規(guī)則。因此,本文以探究基于用戶示例自動推斷規(guī)則的可行性為目的,形式化地定義了XML查詢學(xué)習(xí)問題?？紤]四類不同查詢,從理論角度分析其對應(yīng)學(xué)習(xí)問題,對可解問題給出了多項(xiàng)式時間算法,對難解問題給出了復(fù)雜性證明并進(jìn)一步分析其是否存在有效的近似算法。針對最小化圖代價匹配結(jié)果消解問題,本文給出的近似算法的近似性能無法滿足實(shí)際需求。因此,本文以近年來興起的參數(shù)化復(fù)雜度理論為工具,研究該問題是否固定參數(shù)可