[發明專利]基于部分二進制前綴編碼的XML流緩存管理方法

無效

• 申請號: 200710043705.1
• 申請日: 2007-07-12
• 公開（公告）號: CN101089851A
• 公開（公告）日: 2007-12-19
• 發明（設計）人: 楊衛東;王清明;朱皓
• 申請（專利權）人: 復旦大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海正旦專利代理有限公司
• 代理人: 陸飛;盛志范

1.一種基于部分二進制前綴編碼的XML流緩存管理方法，其特征在于具體步驟如下：

(1)構造XQuery查詢的緊湊查詢樹，將用戶提交的所有XQuery查詢構造為單顆緊湊查詢樹，并為每一個返回節點構造一個緩存池；在緊湊查詢樹中，所有查詢共享公共前綴；

(2)查詢匹配，查詢匹配過程包括自頂向下和自底向上兩部分，在查詢匹配的過程中，執行緩存管理的基本操作，包括進行緩存結果的加入和刪除；

(3)緩存管理過程，緩存管理過程優化與XQuery查詢匹配的返回結果的緩存，包括：

(a)建立緩存管理的數據結構：XQuery查詢中的每一個緩存節點對應于一個緩存池，所有緩存池構成一個鏈表，其中，每兩個緩沖池之間的鏈接由緩存池中返回節點之間的語義關系定義，包括父子關系、子孫關系、兄弟關系和共同祖先關系；

(b)建立基于運行時棧的部分二進制前綴編碼表示，通過運行時棧驅動基于二進制的前綴編碼，在運行時確定結果集中節點之間的關系，遲早構成返回結果元組，避免中間結果集之間的連接操作；

(c)進行返回結果的緩存管理；

所述的XQuery的緊湊查詢樹，定義如下：

定義1：一顆緊湊查詢樹是表示XQuery的查詢樹，其中的節點稱為查詢節點，記為QNode，具有惟一標識，查詢節點分為以下兩種類型：

(1)OQNode：不帶有謂詞的定位步，稱為通常查詢節點，在緊湊查詢樹中，OQNode關聯相關信息，包括節點名字“name”和表示父子“/”或子孫“//”關系的算子，用兩元組<name，“/”or“//”>表示；

(2)PQNode：帶有謂詞的定位步，稱為謂詞查詢節點，謂詞查詢節點是緊湊查詢樹中的特殊節點，它通過AND/OR邏輯謂詞將其子樹連接起來；除了節點標識，節點名和父子或者子孫外，還關聯一個邏輯表達式；該邏輯表達式在內部表示為抽象語法樹；該抽象語法樹的每一個葉子節點都維護一個到其對應的節點的引用；

(3)RNode：返回結果節點，即是指那些構成XQuery結果元組的節點；

定義2：謂詞子樹，在一個緊湊查詢樹中，以距離根節點最近的謂詞節點為根所形成的子樹稱為謂詞子樹；同時擴充相應的節點結構：謂詞子樹中的OQNode，也關聯一個邏輯表達式，該邏輯表達式是只含有一個項，即其孩子節點的標識；而如果OQNode是葉子?節點，則含有一個邏輯標記，初始為真，當遇到CLOSE事件后，將邏輯標記的值賦為假；

定義3：接受節點，在一顆緊湊查詢樹的表示中，距離根節點最近的謂詞節點稱為該樹所表示查詢的接受節點；如果計算過程中，接受節點相關邏輯表達式的值為真，則該文檔與查詢匹配；如果一個XQuery是不帶謂詞的一般查詢XP{/，//，*}，其接受節點則是其通常查詢樹的葉子節點；如果在匹配過程中到達接受節點，則該文檔與查詢匹配；

所述的查詢匹配，其過程分為OPEN和CLOSE兩部分，其中：

(a)OPEN事件通過回調函數調用該句柄，傳入事件名字，元素名字和元素的文檔層次；對每一個到達的XML元素，進行節點測試和文檔層次檢查；如果節點檢查返回TRUE，則該節點被壓入一個運行時棧；若遇到的節點是PQNode或謂詞子樹的子節點，其狀態標記的值設為FALSE；若遇到的節點是一個查詢的接受節點，且不是PQNode節點，則一個查詢匹配發生；若遇到的節點是同一節點的不同層次，則將其作為不同的狀態節點，用節點標識和文檔層次來共同識別該狀態節點；如果該接受節點是PQNode，則需要等到遇到CLOSE事件時才能判定文檔與查詢是否匹配；若遇到的是返回結果節點RNode，則將該節點放入緩存池中；

(b)在CLOSE事件發生時，如果遇到的節點是OQNode，簡單地將節點從棧中彈出；如果遇到的節點是PQNode或謂詞子樹的子節點，將執行下列步驟：a)如果是葉子節點，將其狀態標記賦為TRUE，意味著該節點匹配成功，從運行棧彈出該節點，并將當前棧頂對應的節點中相關的邏輯表達式中對應的項賦值為TRUE；如果是謂詞子樹中的中間節點，計算其邏輯表達式，若為TRUE，則其狀態標記賦值為TRUE，否則為FALSE，從棧中彈出該節點，并將當前棧頂節點的相關邏輯表達式中的對應項賦值為其狀態標記的值TRUE或FALSE；如果是一個查詢的接受節點，計算其邏輯表達式，并將邏輯表達式的結果賦給狀態標記；如果是TRUE，則文檔與該查詢匹配；如果是FALSE，則文檔與該查詢不匹配；如果是一個返回節點，在確定匹配成功或失敗時，從緩存中刪除相應節點；

所述建立基于運行時棧的部分二進制前綴編碼表示，具體步驟如下：

根節點編碼為空串empty；為任一個節點X下的第i個子節點Y分配一個二進制串bits(i)；子節點的編碼Label(Y)就是其父節點的編碼與分配的二進制串的連接即Label(X)·bits(i)；分配的二進制串bit(s)，必須滿足子節點的編碼是前綴無關的，即沒有一個子節點的編碼是另一個的前綴；根據前綴編碼，通過兩個基本操作確定兩個節點之間的任何關系。