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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

6 宋長(zhǎng)宏,劉宇棟,朱R，

本文編號(hào)：1841865