一種基于決策樹的選擇查詢算法

鄧冬梅 譚鍵龍

1. 湖南師范大學計算機教學部，湖南 長沙 410081 2. 中國科學院計算技術研究所，北京 100190

一種基于決策樹的選擇查詢算法

鄧冬梅1譚鍵龍2

1. 湖南師范大學計算機教學部，湖南 長沙 410081 2. 中國科學院計算技術研究所，北京 100190

本文提出了一種基于決策樹的查詢索引結構，筆者稱之為查詢決策樹。查詢決策樹不僅利用了查詢內各個謂詞間的合取關系，還充分利用了單個屬性上的謂詞索引。

數據流管理系統;查詢決策樹

引言

流動數據處理長期以來沒有受到足夠重視，目前并不存在像數據庫管理系統一樣的成熟的、通用的數據流處理平臺。但隨著互聯網技術的發展和廣泛應用，國際、國內對數據流的研究已逐步得到重視。

1.選擇多查詢處理及其分類

數據流管理系統和傳統的數據庫管理系統最重要的區別之一是持續查詢在數據流管理系統中的重要地位，而選擇查詢是數據流持續查詢中最基本、也是最重要和使用得最廣泛的一類查詢。

直觀的說，一個選擇查詢就是一個過濾條件，當流數據到達時，數據流管理系統查詢處理引擎在選擇查詢上進行條件測試，如果條件測試的結果為真，我們說這個選擇查詢得到滿足（或者說這個選擇查詢得到匹配）。

數據流管理系統中一般都注冊有大量的選擇查詢。數據流S上的選擇多查詢處理是指：給定S上的選擇查詢集合Qset{Q1,Q2,…,Qn}，當S的一個數據元組t到達時，返回查詢集合中所有取值為真的查詢的編號。

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

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

一個流數據元組到達后，按照多查詢處理算法在表1中的處理順序，已有的多查詢處理算法可分為3類：

1.1 行順序處理方法：當一個數據流元組到達后，多查詢處理引擎逐行（逐查詢）處理表1中各查詢；

相對于傳統的人際互動、書信來往等交往方式，新媒體環境下人們之間的交往更加多樣化。除了傳統交往方式外，QQ、BBS、微博、微信等使大學生人際之間的交往更加多樣和便捷。

1.2 列順序處理方法：當一個數據流元組到達后，多查詢處理引擎逐列（逐屬性）處理表1中的查詢；

1.3 行列交錯處理方法：當一個數據流元組到達后，多查詢處理引擎按照行（查詢）、列（屬性）交錯的順序處理表1中的查詢。

2.基于決策樹的選擇查詢算法

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

2.1 查詢決策樹的構造

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

查詢決策樹是以自上向下的方式構造的，在構造的過程當中，每個結點關聯一個查詢集合和一個屬性集合，查詢集合是以當前結點為根結點的子樹所索引的查詢子集，屬性集合是當前結點可選的劃分屬性集合。構造從決策樹的根結點開始，根結點關聯的查詢集合包含了原始查詢集合Qset中的所有查詢，根結點關聯的屬性集合包含了數據流模式S的所有屬性。利用一個先進后出的棧(stack)來保存將要被擴展的結點，及其關聯的查詢集合和屬性集合。初始化棧時，把根結點及其關聯的查詢集合和屬性集合壓入棧，然后每次從棧的頭部彈出一個待擴展結點，將這個結點擴展，再將擴展得到的新結點壓入棧，重復這個過程直到棧變為空為止。使用棧來保存待擴展結點，按照先進后出的順序依次擴展每個結點，是一種深度優先的樹構造策略。

假設當前從棧頂彈出的待擴展結點關聯的查詢集合為Qset{Q1,Q2,…,Qn}，屬性集合為Aset{a1, a2, …, am}。從Aset中選擇一個屬性做為劃分屬性。預先對數據流的各屬性賦以一個序號，結點擴展時總是選擇Aset中序號最小的屬性做為劃分屬性。

條件(I)和(II)保證了，aj的任何一個可能取值落入且僅僅落入某一個值域子集σ k（1≤k≤s）。條件(III)保證了，對于任意值域子集σk，任意查詢在劃分屬性上的謂詞P[i,j]確定的值域子集ωi要么完全包含σk，要么σk和不相交。等價的描述是，對于σk（1≤k≤s）中的任意兩個不同值x和y，P[i,j](x)=P[i,j](y) (" 1≤i≤n, 1≤j≤m)。在滿足上面三個條件的前提下，應使s盡量的小。

圖1 查詢決策樹結點擴展示意圖

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

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

最后，為當前結點關聯的查詢集合Qset在劃分屬性aj的謂詞上建立匹配器matcher，matcher是劃分屬性上的謂詞索引。利用matcher，對于給定的劃分屬性值，能快速計算它落入了哪個值域子集。各種單屬性上的謂詞索引都可以用來建立matcher。

給一個查詢決策樹結點擴展的簡單例子。假設當前結點關聯的查詢集合為：Q1:(50

2.2 查詢決策樹的匹配算法

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

match (P, Rset, T) //P為指向當前訪問結點的指針，Rset為存放匹配結果查詢ID的集合, T為待匹配的數據流元組

匹配算法中，訪問每個非葉結點時，用數據元組的劃分屬性值搜索當前結點的謂詞索引，如果元組的劃分屬性值落入了第k個值域子集，那么將搜索以第k個子結點為根的子樹，而直接跳過了其它的子結點及其子樹。因此，查詢內各屬性謂詞間的合取關系得到了充分利用。

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

3.結語

查詢決策樹不僅使用了單個屬性上的謂詞索引，各種單屬性上的謂詞很容易集成到查詢決策樹結構中，而且還充分利用了查詢內各謂詞間的合取關系，相對于以前的各種多查詢處理算法，能更有效減少冗余計算。

最后在一個模擬的網絡入侵檢測環境下測試了查詢決策樹的匹配時間效率和存儲使用量，并將其和改進的行順序處理算法及列順序處理算法進行對比，驗證了查詢決策樹在匹配時間效率上的巨大優勢。

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

[2]陳有祺.形式語言與自動機.南開大學出版社，1999，pp.45～78

[3]王曉東.計算機算法設計與分析.電子工業出版社，pp210～216, 2001

10.3969/j.issn.1001-8972.2012.03.033