一種基于決策樹(shù)的選擇查詢算法

鄧冬梅 譚鍵龍

1. 湖南師范大學(xué)計(jì)算機(jī)教學(xué)部，湖南 長(zhǎng)沙 410081 2. 中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京 100190

一種基于決策樹(shù)的選擇查詢算法

鄧冬梅1譚鍵龍2

1. 湖南師范大學(xué)計(jì)算機(jī)教學(xué)部，湖南 長(zhǎng)沙 410081 2. 中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京 100190

本文提出了一種基于決策樹(shù)的查詢索引結(jié)構(gòu)，筆者稱之為查詢決策樹(shù)。查詢決策樹(shù)不僅利用了查詢內(nèi)各個(gè)謂詞間的合取關(guān)系，還充分利用了單個(gè)屬性上的謂詞索引。

數(shù)據(jù)流管理系統(tǒng);查詢決策樹(shù)

引言

流動(dòng)數(shù)據(jù)處理長(zhǎng)期以來(lái)沒(méi)有受到足夠重視，目前并不存在像數(shù)據(jù)庫(kù)管理系統(tǒng)一樣的成熟的、通用的數(shù)據(jù)流處理平臺(tái)。但隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展和廣泛應(yīng)用，國(guó)際、國(guó)內(nèi)對(duì)數(shù)據(jù)流的研究已逐步得到重視。

1.選擇多查詢處理及其分類(lèi)

數(shù)據(jù)流管理系統(tǒng)和傳統(tǒng)的數(shù)據(jù)庫(kù)管理系統(tǒng)最重要的區(qū)別之一是持續(xù)查詢?cè)跀?shù)據(jù)流管理系統(tǒng)中的重要地位，而選擇查詢是數(shù)據(jù)流持續(xù)查詢中最基本、也是最重要和使用得最廣泛的一類(lèi)查詢。

直觀的說(shuō)，一個(gè)選擇查詢就是一個(gè)過(guò)濾條件，當(dāng)流數(shù)據(jù)到達(dá)時(shí)，數(shù)據(jù)流管理系統(tǒng)查詢處理引擎在選擇查詢上進(jìn)行條件測(cè)試，如果條件測(cè)試的結(jié)果為真，我們說(shuō)這個(gè)選擇查詢得到滿足（或者說(shuō)這個(gè)選擇查詢得到匹配）。

數(shù)據(jù)流管理系統(tǒng)中一般都注冊(cè)有大量的選擇查詢。數(shù)據(jù)流S上的選擇多查詢處理是指：給定S上的選擇查詢集合Qset{Q1,Q2,…,Qn}，當(dāng)S的一個(gè)數(shù)據(jù)元組t到達(dá)時(shí)，返回查詢集合中所有取值為真的查詢的編號(hào)。

Qset也可用表1直觀地表示，其中謂詞P[i, j]是查詢Qi在屬性aj上的謂詞。

表1 選擇多查詢的表格表示

一個(gè)流數(shù)據(jù)元組到達(dá)后，按照多查詢處理算法在表1中的處理順序，已有的多查詢處理算法可分為3類(lèi)：

1.1 行順序處理方法：當(dāng)一個(gè)數(shù)據(jù)流元組到達(dá)后，多查詢處理引擎逐行（逐查詢）處理表1中各查詢；

相對(duì)于傳統(tǒng)的人際互動(dòng)、書(shū)信來(lái)往等交往方式，新媒體環(huán)境下人們之間的交往更加多樣化。除了傳統(tǒng)交往方式外，QQ、BBS、微博、微信等使大學(xué)生人際之間的交往更加多樣和便捷。

1.2 列順序處理方法：當(dāng)一個(gè)數(shù)據(jù)流元組到達(dá)后，多查詢處理引擎逐列（逐屬性）處理表1中的查詢；

1.3 行列交錯(cuò)處理方法：當(dāng)一個(gè)數(shù)據(jù)流元組到達(dá)后，多查詢處理引擎按照行（查詢）、列（屬性）交錯(cuò)的順序處理表1中的查詢。

2.基于決策樹(shù)的選擇查詢算法

本文提出一種新的數(shù)據(jù)流選擇多查詢的處理算法，這種多查詢的索引具有決策樹(shù)形式的結(jié)構(gòu)，筆者稱之為數(shù)據(jù)流多查詢的決策樹(shù)索引算法。多查詢的決策樹(shù)索引同時(shí)利用了單個(gè)屬性上的謂詞索引和單個(gè)查詢內(nèi)各屬性謂詞間的合取關(guān)系，因而能更大程度減少冗余計(jì)算。各種單屬性上的謂詞索引能很容易集成到多查詢的決策樹(shù)索引中。這種多查詢的決策樹(shù)處理算法被歸入到行列交錯(cuò)處理算法類(lèi)別。

2.1 查詢決策樹(shù)的構(gòu)造

設(shè)數(shù)據(jù)流S用模式R(a1:Ω 1, a2: Ω 2, …, am: Ω m)描述，Qset{Q1,Q2,…,Qn}是在S上定義的查詢集合，下面討論如何在Qset上建立基于決策樹(shù)的查詢索引。

查詢決策樹(shù)是以自上向下的方式構(gòu)造的，在構(gòu)造的過(guò)程當(dāng)中，每個(gè)結(jié)點(diǎn)關(guān)聯(lián)一個(gè)查詢集合和一個(gè)屬性集合，查詢集合是以當(dāng)前結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹(shù)所索引的查詢子集，屬性集合是當(dāng)前結(jié)點(diǎn)可選的劃分屬性集合。構(gòu)造從決策樹(shù)的根結(jié)點(diǎn)開(kāi)始，根結(jié)點(diǎn)關(guān)聯(lián)的查詢集合包含了原始查詢集合Qset中的所有查詢，根結(jié)點(diǎn)關(guān)聯(lián)的屬性集合包含了數(shù)據(jù)流模式S的所有屬性。利用一個(gè)先進(jìn)后出的棧(stack)來(lái)保存將要被擴(kuò)展的結(jié)點(diǎn)，及其關(guān)聯(lián)的查詢集合和屬性集合。初始化棧時(shí)，把根結(jié)點(diǎn)及其關(guān)聯(lián)的查詢集合和屬性集合壓入棧，然后每次從棧的頭部彈出一個(gè)待擴(kuò)展結(jié)點(diǎn)，將這個(gè)結(jié)點(diǎn)擴(kuò)展，再將擴(kuò)展得到的新結(jié)點(diǎn)壓入棧，重復(fù)這個(gè)過(guò)程直到棧變?yōu)榭諡橹?。使用棧?lái)保存待擴(kuò)展結(jié)點(diǎn)，按照先進(jìn)后出的順序依次擴(kuò)展每個(gè)結(jié)點(diǎn)，是一種深度優(yōu)先的樹(shù)構(gòu)造策略。

假設(shè)當(dāng)前從棧頂彈出的待擴(kuò)展結(jié)點(diǎn)關(guān)聯(lián)的查詢集合為Qset{Q1,Q2,…,Qn}，屬性集合為Aset{a1, a2, …, am}。從Aset中選擇一個(gè)屬性做為劃分屬性。預(yù)先對(duì)數(shù)據(jù)流的各屬性賦以一個(gè)序號(hào)，結(jié)點(diǎn)擴(kuò)展時(shí)總是選擇Aset中序號(hào)最小的屬性做為劃分屬性。

條件(I)和(II)保證了，aj的任何一個(gè)可能取值落入且僅僅落入某一個(gè)值域子集σ k（1≤k≤s）。條件(III)保證了，對(duì)于任意值域子集σk，任意查詢?cè)趧澐謱傩陨系闹^詞P[i,j]確定的值域子集ωi要么完全包含σk，要么σk和不相交。等價(jià)的描述是，對(duì)于σk（1≤k≤s）中的任意兩個(gè)不同值x和y，P[i,j](x)=P[i,j](y) (" 1≤i≤n, 1≤j≤m)。在滿足上面三個(gè)條件的前提下，應(yīng)使s盡量的小。

圖1 查詢決策樹(shù)結(jié)點(diǎn)擴(kuò)展示意圖

在給定屬性aj的值域Ω上，定義關(guān)系R：對(duì)于任意的x, y，xRy當(dāng)切僅當(dāng)對(duì)所有的1≤i≤n有P[i,j](x)=P[i,j](y)。容易證明R是Ω上的一個(gè)等價(jià)關(guān)系，而σ1，σ 2，……，σs則是由這個(gè)等價(jià)關(guān)系劃分出的一族等價(jià)類(lèi)。

接下來(lái)，為當(dāng)前結(jié)點(diǎn)創(chuàng)建s個(gè)子結(jié)點(diǎn)，每個(gè)子結(jié)點(diǎn)分別對(duì)應(yīng)于一個(gè)值域子集。每個(gè)子結(jié)點(diǎn)都和屬性集合Aset{aj}關(guān)聯(lián)，其中aj是當(dāng)前結(jié)點(diǎn)的劃分屬性。每個(gè)子結(jié)點(diǎn)初始時(shí)都和一個(gè)空的查詢集合關(guān)聯(lián)，然后對(duì)于Qset中的每個(gè)查詢Qi和每個(gè)值域子集σk，如果P[i, j]完全包含了σk，則將Qi插入到第k個(gè)子結(jié)點(diǎn)關(guān)聯(lián)的查詢集合中。后面用Qset’[k]表示當(dāng)前結(jié)點(diǎn)第k個(gè)子結(jié)點(diǎn)關(guān)聯(lián)的查詢集合。注意，一個(gè)查詢可能被插入到多個(gè)子結(jié)點(diǎn)所關(guān)聯(lián)的查詢集合中。然后，這新建立的s個(gè)子結(jié)點(diǎn)及其關(guān)聯(lián)的屬性集合和查詢集合被壓入棧頂。每個(gè)子結(jié)點(diǎn)關(guān)聯(lián)的屬性集合為Aset{aj}，也就是說(shuō)，每個(gè)子結(jié)點(diǎn)所關(guān)聯(lián)的屬性集合大小至少比其父結(jié)點(diǎn)關(guān)聯(lián)的屬性集合少1，因此，構(gòu)造的查詢決策樹(shù)的最大深度為M，這里M是數(shù)據(jù)流屬性的個(gè)數(shù)。

最后，為當(dāng)前結(jié)點(diǎn)關(guān)聯(lián)的查詢集合Qset在劃分屬性aj的謂詞上建立匹配器matcher，matcher是劃分屬性上的謂詞索引。利用matcher，對(duì)于給定的劃分屬性值，能快速計(jì)算它落入了哪個(gè)值域子集。各種單屬性上的謂詞索引都可以用來(lái)建立matcher。

給一個(gè)查詢決策樹(shù)結(jié)點(diǎn)擴(kuò)展的簡(jiǎn)單例子。假設(shè)當(dāng)前結(jié)點(diǎn)關(guān)聯(lián)的查詢集合為：Q1:(50

2.2 查詢決策樹(shù)的匹配算法

利用查詢決策樹(shù)，搜索給定的數(shù)據(jù)流元組T滿足了哪些查詢的匹配算法，是一個(gè)從樹(shù)的根結(jié)點(diǎn)往下遍歷直到某個(gè)葉結(jié)點(diǎn)的過(guò)程。初始化時(shí)將匹配結(jié)果查詢ID集合Rset置為空，結(jié)點(diǎn)指針P指向查詢決策樹(shù)的根結(jié)點(diǎn)，那么遞歸的匹配算法可以描述如下：

match (P, Rset, T) //P為指向當(dāng)前訪問(wèn)結(jié)點(diǎn)的指針，Rset為存放匹配結(jié)果查詢ID的集合, T為待匹配的數(shù)據(jù)流元組

匹配算法中，訪問(wèn)每個(gè)非葉結(jié)點(diǎn)時(shí)，用數(shù)據(jù)元組的劃分屬性值搜索當(dāng)前結(jié)點(diǎn)的謂詞索引，如果元組的劃分屬性值落入了第k個(gè)值域子集，那么將搜索以第k個(gè)子結(jié)點(diǎn)為根的子樹(shù)，而直接跳過(guò)了其它的子結(jié)點(diǎn)及其子樹(shù)。因此，查詢內(nèi)各屬性謂詞間的合取關(guān)系得到了充分利用。

匹配算法最多需要搜索M個(gè)結(jié)點(diǎn)的謂詞索引，這里M是查詢決策樹(shù)的最大深度，即數(shù)據(jù)流屬性的個(gè)數(shù)。如果每個(gè)結(jié)點(diǎn)中的謂詞索引的搜索時(shí)間不大于O(f(N))，其中N是查詢的個(gè)數(shù)，f(N)為單屬性謂詞索引的搜索時(shí)間復(fù)雜度上界，那么上述匹配算法的最壞情況時(shí)間復(fù)雜度為O(Mf(N))。一般情況下，常用的單屬性上的謂詞索引能滿足f(N) = O(log(N))。多查詢行順序處理算法、列順序處理算法和行列交錯(cuò)處理算法最壞情況下的時(shí)間復(fù)雜度都為O(MN)，而查詢決策樹(shù)O(Mlog(N))的最壞情況時(shí)間復(fù)雜度顯然更適合實(shí)時(shí)數(shù)據(jù)流應(yīng)用。

3.結(jié)語(yǔ)

查詢決策樹(shù)不僅使用了單個(gè)屬性上的謂詞索引，各種單屬性上的謂詞很容易集成到查詢決策樹(shù)結(jié)構(gòu)中，而且還充分利用了查詢內(nèi)各謂詞間的合取關(guān)系，相對(duì)于以前的各種多查詢處理算法，能更有效減少冗余計(jì)算。

最后在一個(gè)模擬的網(wǎng)絡(luò)入侵檢測(cè)環(huán)境下測(cè)試了查詢決策樹(shù)的匹配時(shí)間效率和存儲(chǔ)使用量，并將其和改進(jìn)的行順序處理算法及列順序處理算法進(jìn)行對(duì)比，驗(yàn)證了查詢決策樹(shù)在匹配時(shí)間效率上的巨大優(yōu)勢(shì)。

[1]徐恪,徐明偉,吳建平,吳劍.路由查找算法研究綜述.軟件學(xué)報(bào)，Vol.13(1),pp42～50

[2]陳有祺.形式語(yǔ)言與自動(dòng)機(jī).南開(kāi)大學(xué)出版社，1999，pp.45～78

[3]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析.電子工業(yè)出版社，pp210～216, 2001

10.3969/j.issn.1001-8972.2012.03.033