[發明專利]一種數據庫的查詢重寫方法

在審

• 申請號: 202110644943.8
• 申請日: 2021-06-09
• 公開（公告）號: CN113515540A
• 公開（公告）日: 2021-10-19
• 發明（設計）人: 李國良;周煊赫
• 申請（專利權）人: 清華大學
• 主分類號: G06F16/2453
• 分類號: G06F16/2453;G06F16/22;G06N3/04;G06N3/08
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 羅文群

1.一種數據庫數據的查詢重寫方法，其特征在于該方法利用策略樹表示任意一個查詢語句的大量等價查詢和相應的重寫順序，基于蒙特卡洛樹搜索算法在策略樹上選擇高收益的重寫順序，實現查詢開銷和重寫頻率的平衡，利用深度注意力網絡學習當前查詢與重寫規則和訪問數據的關聯關系，并利用深度學習根據查詢特征和提取的關聯關系，擬合當前查詢的整體收益，利用重寫收益估計網絡，在策略樹上利用一種最優算法選擇沒有祖先-后代關系且總收益最高的多個節點，并行擴展策略樹，以大幅提高查詢重寫效率。

2.如權利要求1所述的數據庫數據的查詢重寫方法，其特征在于，該方法具體包括以下步驟：

(1)向數據庫輸入一個待重寫的查詢語句；

(2)采用基于關系代數的變換方法，將步驟(1)中的查詢語句替換成等價的邏輯計劃，初始化一棵只有根節點的策略樹，根節點表示輸入查詢的邏輯計劃，根據查詢語句的多種重寫方式，在該策略樹上擴展出屬于根節點的所有子節點，每個子節點表示根節點利用一種重寫方式進行重寫得到的查詢語句，得到初始策略樹；

(3)對步驟(2)的初始策略樹進行搜索，得到全局收益值最高的查詢語句，包括以下步驟：

(3-1)設定最大搜索次數N；

(3-2)采用動態規劃方法，從步驟(2)的初始策略樹的根節點和多個子節點中選擇k個節點，將與k個被選節點相對應的所有重寫方式的查詢語句作為新的子節點，擴展到初始決策樹上，得到n-1次決策樹，n∈[1，N]；

(3-3)利用重寫收益估計神經網絡，估計得到k個被選節點的后續收益值，具體過程如下：

(3-3-1)分別對與步驟(3-2)的k個節點相對應的查詢語句、查詢語句的多種重寫方式和與查詢語句相對應的數據庫元數據進行編碼，得到一個編碼向量；

(3-3-2)分別將(3-3-1)中的查詢語句、查詢語句的重寫方式和與查詢語句相對應的數據庫元數據的編碼碼輸入到重寫收益估計神經網絡的第一注意力網絡中，輸出得到多種重寫方式之間的相關性，并根據查詢語句和數據庫元數據特征，為每種重寫方式生成一個壓縮向量；

(3-3-3)將步驟(3-3-2)的重寫方式的壓縮向量輸入重寫收益估計神經網絡的隱層神經網絡，使用S形激勵函數(SIGMOID)對所有重寫方式的壓縮向量進行歸一化，并使用兩層全連接神經網絡進行擬合，輸出得到；

(3-3-4)將步驟(3-3-3)的收益最高的重寫方式的壓縮向量和步驟(3-3-2)的查詢語句的壓縮向量輸入重寫收益估計神經網絡的第二注意力網絡中，計算重寫方式與查詢語句的算子特征之間的關系，輸出得到一個壓縮向量，將該壓縮向量輸入重寫收益估計神經網絡的輸出層，進行非線性轉換，輸出得到與n-1次決策樹上的節點相對應的查詢語句的后續收益值；

(3-5)n-1次決策樹上的節點分別將各自的后續收益值傳遞給各自的祖先節點，各祖先節點分別將接收的后續收益值與原收益值進行比較，若后續收益值大于原收益值，則用后續收益值更新原收益值，得到n次策略樹；若后續收益值小于或等于原收益值，則繼續與其它祖先節點的收益值進行比較，得到n次策略樹；

(3-6)重復步驟(3-2)-步驟(3-5)，直到完成N次迭代，得到N次策略樹；

(4)對N次策略樹上所有節點的后續收益值進行比較，將與N次策略樹上查詢時間最短的節點相對應的查詢語句輸出給用戶，實現數據庫的查詢重寫方法。

3.如權利要求1所述的查詢重寫方法，其特征在于，所述的步驟(3-3)的重寫收益估計網絡的構建和訓練，包括以下步驟：

(1)重寫收益估計網絡由第一注意力網絡、隱層神經網絡、第二注意力網絡和輸出神經網絡組成，所述的第一注意力網絡和第二注意力網絡均由余弦計算單元和單層全連接神經網絡組成；所述的隱層神經網絡為兩層全連接神經網絡；所述的輸出神經網絡為單層全連接神經網絡；第一注意力網絡的單層全連接神經網絡的輸入層大小為n×(m+k)，輸出層大小為n×(m+k)，n、m、k分別表示重寫方式數目、查詢語句特征數、數據庫元數據特征數；隱層神經網絡的第一層全連接神經網絡的輸入層大小為n×(m+k)，輸出層大小為n×(m+k)；隱層神經網絡的第二層全連接神經網絡的輸入層大小為n×(m+k)，輸出層大小為1×(m+k)；第二注意力網絡的單層全連接神經網絡的輸入層大小為1×(m+k)，輸出層大小為1×(m+k)；輸出神經網絡的單層全連接神經網絡的輸入層大小為1×(m+k)，輸出層大小為1×1；

(2)根據數據庫查詢語句的訪問特征，對數據庫中的查詢語句進行聚類，在每個聚類中選取一個查詢語句，分別計算該查詢語句的所有重寫方式的查詢時間，將其中最短的查詢時間作為該聚類的所有查詢語句的查詢時間；

(3)從數據庫中劃分出80％的查詢語句作為訓練集，訓練集中的訓練數據的格式為q，R，D，C^↓(q)，其中q表示查詢語句，R表示查詢語句的重寫規則集合，D表示查詢語句的元數據特征，C^↓(q)表示查詢語句q經過后續查詢重寫后的最大可獲得的未來收益值；

(4)用步驟(3)獲得的訓練集對步驟(1)的重寫收益估計網絡進行訓練，即，將訓練集的每組重寫方式、查詢語句和數據庫元數據的編碼輸入到第一注意力網絡，第一注意力網絡輸出得到表示向量；將表示向量輸入隱層神經網絡，隱層神經網絡輸出得到隱藏向量；將隱藏向量輸入給第二注意力網絡，第二注意力網絡輸出得到收益最大的重寫方式的壓縮向量；將壓縮向量輸入給輸出網絡，輸出網絡輸出估計的查詢語句q的后續收益值F(q)；計算估計的查詢語句的后續收益值的均方誤差MSE，MSE＝(F(q)-C^↓(q))²，其中F(q)表示估計的查詢語句的后續收益值，C^↓(q)表示真實的查詢語句q的后續收益值；

(5)根據步驟(4)的均方誤差，計算拉普拉斯正則項L_reg：L_reg＝∑_q’μ_q′||F(q)-F(q‘)||，其中，q’為和q在同一聚類中的任意一個除了q的查詢語句，||F(q)-F(q‘)||表示L1距離，以使絕對差之和最小，用拉普拉斯正則項更新重寫收益估計網絡；

(6)設定一個查詢語句的后續收益值的均方誤差的驗證閾值γ，將數據庫中其余20％的查詢語句作為驗證集，分別將驗證集中所有的查詢語句輸入到步驟(5)的重寫收益估計網絡中，分別得到估計的查詢語句的后續收益值的均方誤差，計算所有均方誤差的平均值將該平均值與真實的查詢語句q的后續收益值進行比較，若則重復步驟(4)-步驟(5)，直到得到訓練好的重寫收益估計網絡。