本文選題：不一致數(shù)據(jù) + 一致性評估�。� 參考：《哈爾濱工業(yè)大學(xué)》2016年博士論文

【摘要】：各應(yīng)用領(lǐng)域信息量爆炸性地增長帶來了大量的劣質(zhì)數(shù)據(jù)。數(shù)據(jù)質(zhì)量低劣經(jīng)常導(dǎo)致災(zāi)難性后果,極大地限制了數(shù)據(jù)的正常使用。數(shù)據(jù)的劣質(zhì)性概括性地表現(xiàn)為數(shù)據(jù)的不一致性、不準確性、不完全性和非時效性等等,而其中不一致數(shù)據(jù)是最典型的劣質(zhì)數(shù)據(jù)。改善不一致性數(shù)據(jù)對于為提高數(shù)據(jù)可用性,確保大規(guī)模數(shù)據(jù)的正常使用有著十分重要的意義。然而已有的基于數(shù)據(jù)依賴規(guī)則描述數(shù)據(jù)一致性的處理方法發(fā)展還不夠完善,并且這種方法本身還有著很多固有的缺陷,主要有以下幾點:第一,一致性規(guī)則只能用于檢測不一致錯誤,但并不能給出數(shù)據(jù)不一致程度的直觀評估;第二,一致性規(guī)則不能指導(dǎo)修復(fù),僅基于規(guī)則的自動方法不能保證完全地修復(fù)不一致數(shù)據(jù);第三,人工很難定義出足夠的一致性規(guī)則以充分檢測數(shù)據(jù)的一致性錯誤。本文對不一致關(guān)系數(shù)據(jù)的評估、修復(fù)、查詢、規(guī)則挖掘等方面中的關(guān)鍵問題給出了一些列的計算復(fù)雜性和算法研究結(jié)果,分很好地決了上述問題,主要研究內(nèi)容如下所述。(1)本文研究了數(shù)據(jù)一致性規(guī)則發(fā)現(xiàn)算法。為了克服挖掘嚴格的函數(shù)依賴和條件函數(shù)依賴的局限性,以及不好的松弛導(dǎo)致的大量無效冗余規(guī)則,本文在第二章研究了如何定義松弛規(guī)則以及如何從更一般的數(shù)據(jù)中挖掘他們。本文提出了從更一般的概率數(shù)據(jù)中挖掘出近似條件函數(shù)依賴的方法,由于概率數(shù)據(jù)可以視作一般數(shù)據(jù)的泛化,因此從概率數(shù)據(jù)中挖掘候選規(guī)則可以提高挖掘能力,適配更廣泛的數(shù)據(jù)類型、提供專家用戶更充分的參考規(guī)則,同理我們定義了近似條件函數(shù)依賴是松弛的,使得挖掘結(jié)果質(zhì)量可控。在此基礎(chǔ)上,本文研究了其在不確定數(shù)據(jù)中的置信概率的動態(tài)規(guī)劃求解算法,以及候選依賴的概率下界來進行剪枝;給出了基于字典序的挖掘方法以及相應(yīng)的剪枝策略;最后,在真實和合成的數(shù)據(jù)集上進行充分的實驗以驗證挖掘算法的可擴展性和剪枝策略的高效性,發(fā)現(xiàn)真實的挖掘結(jié)果,極大地提高了數(shù)據(jù)一致性的發(fā)現(xiàn)能力。(2)本文研究了數(shù)據(jù)一致性評估問題的計算復(fù)雜性和評估算法。為克服當前不能很好地評估數(shù)據(jù)一致性的缺陷,避免局部計數(shù)的失真問題,本文在第三章提出通過最小元組刪除集規(guī)模來評估數(shù)據(jù)的不一致程度。在此基礎(chǔ)上研究了當給定規(guī)則集合的結(jié)構(gòu)復(fù)雜程度對問題的計算復(fù)雜性的影響。本文證明了當Σ包含2條僅涉及3個屬性的變量條件函數(shù)依賴、且每條元組最多僅涉及6個沖突對時,最小元組刪除集問題仍然是NP完全;進而又證明了當給定3條僅涉及4個屬性的變量條件函數(shù)依賴時,將最小刪除集問題近似到1716是NP難的。本文給出了最小元組刪除集問題的近優(yōu)化的近似算法,可以達到2-12r的近似比,其中r為集合Σ中變量條件函數(shù)依賴個數(shù),顯然這是一個獨立于數(shù)據(jù)量的、很好的近似比,因為條件函數(shù)依賴集合Σ通常規(guī)模遠遠小于數(shù)據(jù)量且固定。本文進一步說明了在UGC假設(shè)下,該近似比是近優(yōu)化的,很難再將近似比降低一個與n無關(guān)的常數(shù)。本文通過實驗驗證了本文給出的評估算法具有非常好的準確度,驗證了前述的理論結(jié)果。(3)本文研究了基于反饋的不一致數(shù)據(jù)修復(fù)問題計算復(fù)雜性和修復(fù)算法。對于不一致數(shù)據(jù)的修復(fù),自動的修復(fù)方法具有嚴重的局限性,數(shù)據(jù)質(zhì)量研究領(lǐng)域達成的共識是,引入人工反饋是得到高質(zhì)量修復(fù)的一個重要的環(huán)節(jié)。然而已有的工作都基于三個假設(shè):人工提供的回答認為是正確的,且可以直接使用;人工提供的回答都可以直接向數(shù)據(jù)傳播,無副作用;給定規(guī)則一定是正確的。這種假設(shè)在很多實際情況中是不合理的。因此,本文在第四章針對如何解決人工反饋的正確性保障問題,形式化地定義了兩個判定問題,即約束規(guī)則定義的不一致數(shù)據(jù)中的視圖刪除和插入傳播問題,同時研究了兩個問題的計算復(fù)雜性和數(shù)據(jù)修復(fù)算法。本文研究了不一致數(shù)據(jù)上視圖刪除問題的復(fù)雜性,證明了如果查詢?yōu)橐粋�投影或者并查詢時該問題為NP完全的,證明了當查詢?yōu)橐粋�合取查詢時該問題是Σp2完全的,同時也證明了然而當查詢是一個選擇連接查詢時,該問題的聯(lián)合復(fù)雜性是LOGSPACE的,同時這個結(jié)論意味著一般的無副作用刪除傳播問題在組刪除情況下,其聯(lián)合復(fù)雜性也是在LOGSPACE的,這填補了一般的刪除傳播問題復(fù)雜性結(jié)果中的空白。本文提出了基于刪除反饋的高效修復(fù)算法。本文也證明了不一致數(shù)據(jù)上視圖插入問題在單插入與組插入、有限域與無限域等情況下的數(shù)據(jù)復(fù)雜性與聯(lián)合復(fù)雜性結(jié)論。證明了對于不同類別的查詢,該問題的數(shù)據(jù)和聯(lián)合復(fù)雜性均位于PTIME與Σp2完全之間。不同于刪除反饋,本文證明了不一致數(shù)據(jù)上視圖插入問題會變得更難。本文在數(shù)據(jù)復(fù)雜性下分離出了一大類多項式可解情況,即無自連接的選擇連接查詢類sjf-SJ,提出了高效求解算法,通過實驗驗證了本文提出的修復(fù)算法極大提高了精確率和召回率。(4)本文研究了不一致數(shù)據(jù)查詢處理算法。為了克服一致性查詢回答方法對結(jié)果約束太過苛刻的不足,本文在第五章采用不確定概率數(shù)據(jù)來建模不一致數(shù)據(jù),并通過可能世界的概率閾值來定義查詢結(jié)果的質(zhì)量,從而保證了在盡可能多給出帶有自定義質(zhì)量保證的查詢結(jié)果�；诖�,本文進一步研究了這種方法在廣泛存在且研究較少的空間不一致數(shù)據(jù)上的應(yīng)用,利用空間數(shù)據(jù)的地理相關(guān)性和局部性的特點來加速查詢回答。以較為復(fù)雜的局部相關(guān)空間不一致數(shù)據(jù)為典型范例,給出帶有概率閾值保證的頻繁近鄰查詢結(jié)果。本文提出了一般的處理框架,包括對于概率質(zhì)量函數(shù)的動態(tài)規(guī)劃算法以及閾值過濾方法,很好地解決了應(yīng)用現(xiàn)有的基于傳統(tǒng)數(shù)據(jù)和基于不確定數(shù)據(jù)上的近鄰查詢算法直接處理這種查詢會產(chǎn)生昂貴開銷的問題,并在人工的和真實的數(shù)據(jù)上都進行充分地實驗以驗證算法的有效性和高效性。
[Abstract]:This paper studies how to define relaxation rules and how to dig them from more general data . In this paper , it is proved that when a given rule set is dependent on the variable condition function of 3 attributes , the minimum deletion set problem is considered to be NP complete . In this paper , it is proved that when a given rule set is dependent on the variable condition function of 3 attributes , it is difficult to reduce the approximation ratio directly to the data quantity . In order to overcome the shortage of inconsistent data query processing , this paper uses uncertain probability data to model inconsistent data and defines the quality of query results by using the probability threshold of the probable world .

【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：TP311.13

【相似文獻】

相關(guān)期刊論文 前10條

1 張曉梅;;文獻數(shù)據(jù)庫生產(chǎn)中的數(shù)據(jù)一致性問題分析[J];中華醫(yī)學(xué)圖書情報雜志;2010年02期

2 黃淑冬;;客戶數(shù)據(jù)一致性管理系統(tǒng)的研究與應(yīng)用[J];計算機光盤軟件與應(yīng)用;2013年21期

3 呂艷娥;周力青;;基于策略協(xié)商的數(shù)據(jù)一致性的維護方法[J];大眾科技;2009年02期

4 帖軍;王小榮;金佳;;移動實時環(huán)境下的數(shù)據(jù)一致性研究[J];中南民族大學(xué)學(xué)報(自然科學(xué)版);2011年02期

5 杜毅迪;數(shù)據(jù)一致性模型的設(shè)計與實現(xiàn)[J];湖北郵電技術(shù);2001年04期

6 宋長宏,劉宇棟,朱R，

本文編號：1841865