數(shù)據(jù)流環(huán)境下無(wú)阻塞連接算法研究.pdf

1、隨著網(wǎng)絡(luò)的普及，信息處理技術(shù)有了一些新的應(yīng)用領(lǐng)域，例如，傳感器網(wǎng)絡(luò)，網(wǎng)上在線交易系統(tǒng)，股票行情實(shí)時(shí)監(jiān)控。在這些應(yīng)用中，數(shù)據(jù)不再是靜態(tài)的，而是一種實(shí)時(shí)的、不穩(wěn)定的流式數(shù)據(jù)，稱(chēng)之為數(shù)據(jù)流數(shù)據(jù)，同時(shí)應(yīng)用系統(tǒng)要求數(shù)據(jù)的處理結(jié)果能夠及時(shí)地，分批次地，無(wú)阻塞地反饋給用戶。傳統(tǒng)關(guān)系數(shù)據(jù)處理技術(shù)突顯出其局限性，數(shù)據(jù)流上的關(guān)系查詢處理技術(shù)成為數(shù)據(jù)庫(kù)研究領(lǐng)域的一大熱點(diǎn)。 在數(shù)據(jù)查詢中，關(guān)系連接算法則是一個(gè)制約查詢處理性能的重要因素。在數(shù)據(jù)流上的關(guān)系

2、連接算法其時(shí)間復(fù)雜度必須能適應(yīng)數(shù)據(jù)流的傳輸速度實(shí)現(xiàn)無(wú)阻塞連接，其空間復(fù)雜度必須能夠充分利用有限的內(nèi)存空間處理大量的流數(shù)據(jù)。為了提高其性能，需要維護(hù)一個(gè)盡量小的連接狀態(tài)，并利用數(shù)據(jù)的分布特征設(shè)計(jì)約束條件來(lái)進(jìn)行狀態(tài)簡(jiǎn)化。同時(shí)，要充分利用多級(jí)存儲(chǔ)系統(tǒng)，優(yōu)化數(shù)據(jù)在內(nèi)外存之間的刷新策略。 為兩個(gè)相連接的關(guān)系流分別劃分內(nèi)存分區(qū)M和外存分區(qū)D，利用內(nèi)存的緩沖作用將數(shù)據(jù)流上的關(guān)系連接劃分為MM，MD，DD 三個(gè)階段。隨著網(wǎng)絡(luò)的傳輸速度的變化，連接