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

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

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