數(shù)據(jù)流查詢處理(數(shù)據(jù)庫)

時(shí)間：2022-11-20 14:30:01 | 來源：信息時(shí)代

時(shí)間：2022-11-20 14:30:01 來源：信息時(shí)代

    數(shù)據(jù)流查詢處理 : 針對(duì)數(shù)據(jù)流數(shù)據(jù)的特點(diǎn),研究和探討處理數(shù)據(jù)流查詢所用的新技術(shù)和新方法。與傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)中的查詢處理不同,目前在數(shù)據(jù)流系統(tǒng)中都是用基于有界內(nèi)存的近似查詢處理方法來處理數(shù)據(jù)流。同時(shí)因?yàn)閮?nèi)存空間的有限性,因此,無法對(duì)整個(gè)數(shù)據(jù)流進(jìn)行操作,而只能對(duì)一部分?jǐn)?shù)據(jù)進(jìn)行處理。所以數(shù)據(jù)流系統(tǒng)中的查詢處理只能得到近似的結(jié)果。目前的近似查詢處理技術(shù)有很多的研究成果,像直方圖、抽樣方法、小波技術(shù)、滑動(dòng)窗口等都廣泛地應(yīng)用于數(shù)據(jù)流系統(tǒng)中。
1.連續(xù)查詢語義
對(duì)數(shù)據(jù)流進(jìn)行的查詢?yōu)檫B續(xù)查詢,指的是數(shù)據(jù)流系統(tǒng)在一段時(shí)間內(nèi)是連續(xù)執(zhí)行的,隨著新的數(shù)據(jù)的到達(dá)將不斷地產(chǎn)生新的查詢結(jié)果。
假設(shè)A(Q,t)表示連續(xù)查詢Q在時(shí)刻t的查詢結(jié)果,τ表示當(dāng)前時(shí)間,o表示開始時(shí)間,為了簡(jiǎn)便起見,假設(shè)時(shí)間是一系列整數(shù)。如果一個(gè)連續(xù)查詢是單調(diào)的,那么它對(duì)新到來的數(shù)據(jù)項(xiàng)進(jìn)行查詢,并對(duì)結(jié)果進(jìn)行二次評(píng)價(jià),將滿足條件的元組追加到結(jié)果中去。由此,一個(gè)單調(diào)的連續(xù)查詢Q在時(shí)刻τ的查詢結(jié)果為:

相應(yīng)地,非單調(diào)查詢則需要對(duì)每一個(gè)二次評(píng)價(jià)之后的結(jié)果進(jìn)行重新計(jì)算,由此產(chǎn)生如下語義:

2. 近似查詢處理技術(shù)
近似查詢處理技術(shù)有: 直方圖、抽樣方法、小波分析和滑動(dòng)窗口。
直方圖技術(shù)是一種常用的概要結(jié)構(gòu)表示方法,它是指將一個(gè)大數(shù)據(jù)集劃分為很多個(gè)連續(xù)的桶(bucket),也就是小數(shù)據(jù)集,每個(gè)桶都由一個(gè)數(shù)字來代表其特征。直方圖表示法直觀、簡(jiǎn)潔,能夠很好地表示大數(shù)據(jù)集的輪廓,可用于多重目的,如查詢大小估計(jì),近似查詢結(jié)果以及數(shù)據(jù)挖掘等,其在一些商業(yè)數(shù)據(jù)庫中經(jīng)常采用。直方圖又可以劃分成多種,例如,等寬直方圖、壓縮直方圖、V-優(yōu)化直方圖等。
抽樣方法也是生成大綱數(shù)據(jù)結(jié)構(gòu)的常用手段。它從數(shù)據(jù)集中抽取小部分?jǐn)?shù)據(jù)代表整個(gè)數(shù)據(jù)集,并根據(jù)該樣本集合獲得查詢結(jié)果。但抽樣可能會(huì)產(chǎn)生一些誤差,比如: 求最大值、求最小值等。如何有效地對(duì)數(shù)據(jù)進(jìn)行抽樣,以及如何減少誤差則成了進(jìn)一步研究的問題。
小波分析方法是一種通用的數(shù)字信號(hào)處理技術(shù)。類似于傅立葉變換,小波分析根據(jù)輸入的模擬量,變換成一系列的小波參數(shù),并且少數(shù)幾個(gè)小波參數(shù)就擁有大部分能量。根據(jù)這個(gè)特性,可以選擇少數(shù)小波參數(shù),近似還原原始信號(hào)。小波分析方法也被應(yīng)用到數(shù)據(jù)庫領(lǐng)域,例如,對(duì)高維數(shù)據(jù)進(jìn)行降維處理、生成直方圖等。
用近似的一部分?jǐn)?shù)據(jù),特別是當(dāng)前的一部分?jǐn)?shù)據(jù),來代替全部數(shù)據(jù)用于計(jì)算,這種技術(shù)稱為滑動(dòng)窗口技術(shù)。
在數(shù)據(jù)流中引入滑動(dòng)窗口來產(chǎn)生近似的查詢結(jié)果的方法是有其自身的道理。首先,滑動(dòng)窗口被詳細(xì)定義過,且易理解,近似語義清楚,因此系統(tǒng)的用戶可以確信他們能夠理解在產(chǎn)生近似結(jié)果時(shí)丟棄掉的那部分?jǐn)?shù)據(jù)。其次,由于滑動(dòng)窗口具有確定性,所以不必?fù)?dān)心不適宜的任意地選取將產(chǎn)生非近似的計(jì)算結(jié)果。最重要的一點(diǎn)是,滑動(dòng)窗口強(qiáng)調(diào)的是最近的數(shù)據(jù),在現(xiàn)實(shí)世界的大多數(shù)應(yīng)用中,最近的數(shù)據(jù)要比舊的數(shù)據(jù)重要得多。從另外一個(gè)角度理解,滑動(dòng)窗口的目的是阻止陳舊的數(shù)據(jù)影響系統(tǒng)的分析和統(tǒng)計(jì),并且它是利用有限的內(nèi)存空間的一種近似工具。Datar等人研究了如何對(duì)滑動(dòng)窗口進(jìn)行簡(jiǎn)單的統(tǒng)計(jì),包括綱要的提取技術(shù)。Babock、Datar和Motwani將抽樣技術(shù)用于滑動(dòng)窗口模型。目前在將概要技術(shù)用于滑動(dòng)窗口方面的工作還很少,此方面的研究時(shí)機(jī)已經(jīng)成熟。在數(shù)據(jù)流的連續(xù)查詢系統(tǒng)中,滑動(dòng)窗口可以看作是數(shù)據(jù)流有限部分的一個(gè)歷史性快照?；谶@種定義可以將滑動(dòng)窗口劃分成兩種類型:基于時(shí)間的滑動(dòng)窗口和基于流元組的滑動(dòng)窗口。