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

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

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

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

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

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

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

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

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