用於外包空間資料庫的範圍查詢完整性驗證方法
2023-05-23 19:48:16
用於外包空間資料庫的範圍查詢完整性驗證方法
【專利摘要】本發明公開了一種用於外包空間資料庫的範圍查詢完整性驗證方法，包括：1、基於自適應Hilbert曲線的範圍查詢轉換，生成一維數值段集合；2、用戶經過認證與外包空間資料庫的服務商建立會話連接，將一維數值段集合發送給服務商；3、服務商根據用戶提交的一維數值段集合，檢索資料庫中符合查詢條件的空間對象集合，並將該空間對象集合返回給用戶；4、用戶接收到服務商返回的查詢結果集合，並對其進行消息摘要驗證；5、用戶根據查詢結果中的鄰近空間對象信息，對結果集的完整性進行驗證。本發明方法可以在外包空間資料庫的模式下，為用戶提供高效、安全的範圍查詢完整性驗證功能，進而對服務商修改查詢結果的行為進行約束，保證範圍查詢服務的質量。
【專利說明】用於外包空間資料庫的範圍查詢完整性驗證方法
【技術領域】
[0001]本發明屬於資料庫處理【技術領域】，具體涉及一種用於外包空間資料庫的範圍查詢完整性驗證方法。
【背景技術】
[0002]隨著基於位置的服務與位置感知設備日益普及，與位置相關的信息爆炸式增長，由此產生的大量空間數據超出了小型企業和個人的處理能力。雲存儲服務提供彈性的資源分配，有效降低了數據擁有者維護數據的開銷，因此數據外包成為一種流行的服務模式。為了保護外包空間數據的隱私並支持空間數據查詢，需要在外包前對空間數據進行處理，構建用於查詢的空間數據索引，並對空間數據內容進行加密。然而，由於服務商在執行查詢的過程中，可能對查詢結果進行修改，例如刪除部分查詢結果，從而在用戶不知情的狀況下降低服務質量。因此，在空間資料庫外包的服務模式下，保證空間查詢的完整性是該服務模式健康發展所要解決的重要問題。
[0003]目前多採用Hilbert曲線構建空間數據的索引，以支持隱私保護的空間查詢，並提出了基於隨機複製的查詢完整性驗證方法，通過隨機抽取部分原始數據作為副本，對原始數據和副本數據採用不同的參數構建索引，從而生成外包數據，其查詢完整性驗證過程包括空間查詢和完整性驗證查詢兩個步驟，空間查詢階段獲得查詢結果，完整性驗證查詢階段則獲得完整性驗證信息，這個過程需要用戶與服務商建立兩次會話連接，這增加了服務商進行查詢分析的機會，通過對空間查詢和完整性驗證查詢的特徵進行抽取，進行針對性的調整，規避完整性驗證，另外，在外包空間資料庫中還需要存儲額外的對象副本信息，大大增加了資料庫系統的存儲與維護負擔。
【發明內容】
[0004]本發明的目的在於提供一種外包空間資料庫的範圍查詢完整性驗證方法，通過在外包的密文空間對象中附加基於索引的鄰近空間對象信息，使用戶可以從查詢結果中直接獲得完整性驗證的依據，將範圍查詢和完整性驗證通過一次會話連接完成，降低了系統負載，提高了外包空間資料庫的查詢效率，同時保證了資料庫服務商誠實地為用戶提供服務。
[0005]為了實現上述目的，本發明採用以下技術方案:
[0006]一種用於外包空間資料庫的範圍查詢完整性驗證方法，包括以下步驟:首先，用戶通過自適應Hilbert曲線將二維平面的範圍查詢轉換為一維數值段集合，作為查詢條件；然後，服務商將符合查詢條件的空間對象返回給用戶，用戶對查詢結果進行消息摘要驗證，若未通過則輸出查詢結果不完整；最後，用戶對查詢結果鄰居集合進行範圍查詢驗證，若未通過則輸出查詢結果不完整，否則輸出查詢結果完整。
[0007]一種用於外包空間資料庫的範圍查詢完整性驗證方法，包括以下步驟:
[0008]步驟一:用戶通過自適應Hi Ibert曲線的範圍查詢轉換方法，將二維平面的範圍查詢 W = [xl, xh] X [yl, yh]轉換為一維數值段集合 R= (R1 (S1, e)，R2 (s2, e2)，...，Rn(sn，en)}，即查詢條件；
[0009]xl, xh分別為二維平面的範圍查詢的χ軸方向的最小值、最大值；yl, yh分別為二維平面的範圍查詢的I軸方向的最小值、最大值；Si，e,分別表示數值段Ri的開始值、結束值，I < i < η，η為數值段的個數；
[0010]步驟二:用戶經過認證與外包空間資料庫的服務商建立會話連接，將步驟一中生成的一維數值段集合R發送給服務商；外包空間資料庫中的每一條記錄對應一個空間對象，數據表的核心欄位為一個三元組:〈index, Enc ((location, text, neighbors (f (1),f?，…，f(k)，b⑴，b⑵，…，b(k))), key), Sign〉；
[0011]index為根據當前空間對象的位置坐標location,使用自適應Hilbert曲線生成的索引；text為當前空間對象附屬的其他描述信息；neighbors為與當前空間對象在索引上近鄰的空間對象的位置坐標集合，f⑴、b(i)分別表示index的前驅、後繼空間對象的位置坐標，I < i ( k，k為前驅/後繼空間對象的個數，k的取值由數據擁有者設定；Enc為對稱加密算法，key為對稱密鑰；31811為使用哈希算法他也生成的當前空間對象消息摘要，即 Sign = Hash (location | text | neighbors), | 表不字符串連接運算；
[0012]步驟三:外包空間資料庫服務商根據用戶提交的一維數值段集合R ={Ri(s!, e), R2(s2, e2),…，Rn(sn, en)},檢索資料庫中符合查詢條件的空間對象集合G = {p1；P2,…，Pm}，並將該空間對象集合G返回給用戶，其中:
[0013]Pi表示一個檢索結果,包含索引值indeXi,密文數據信息Enc ((1cationi, texti；neighborsj)，以及消息摘要Signi, I≤i≤m, m為檢索結果的個數； [0014]步驟四:用戶接收到服務商返回的查詢結果集合G= {P1，P2，…，pm}，對其中的每一個對象 Pi =〈index」 Enc ((1cationi, text」 Iieighborsi), key), Signi),首先使用解密算法 Dec O 與密鑰 key 處理 Pi 的加密欄位 Enc ((1cationi, text」 neighbors), key),得到Pi的明文信息(1catioivtextpneighborsi),然後使用哈希算法HashO生成明文信息的消息摘要，即 Sign/ = HashGocationi I texti Ineighborsi),判斷 Sign/ 與 Signi 是否相同，若不相同，則證明空間對象Pi的信息被篡改，終止查詢完整性驗證過程，輸出查詢結果不完整；若對任意Pj e G,均有Sign/ = Sign」，，則進一步進行步驟五；
[0015]步驟五:將通過步驟四驗證的查詢結果集合G = {Pl, p2,…，P1J，分為兩類集合:查詢結果位置集合Q= (1cation1, 1cation2,..., 1cationJ ,查詢結果鄰居集合N =Ineighbors1, neighbors2,..., neighborsj ；
[0016]其中Jocationi 為第 i 個查詢結果的位置坐標！Iieighborsi = (fi(1), fi(2),...,fi(k)，bi(1)，bi(2)，…，bi(k))為與第i個查詢結果在索引上近鄰的空間對象的位置坐標集合，fi(J)>bi(J)分別為1cationi的第j個前驅、後繼空間對象的位置坐標，I ^ j ^ k, k為前驅/後繼空間對象的個數；
[0017]對於任意位置坐標d(x, y) e N,若d存在於範圍查詢W = [xl, xh] X [yl, yh]中，則判斷d是否屬於查詢結果位置集合Q，若不屬於，則終止查詢完整性驗證過程，輸出查詢結果不完整；若查詢結果鄰居集合N中不存在滿足上述條件的位置坐標，則完成查詢完整性驗證過程，輸出查詢結果完整。
[0018]優選的，步驟三種判Spi符合查詢條件的具體依據為:存在Rj e R，使得
Sj- ^ Indexi ^ ej0[0019]優選的，判定位置坐標d(x，y)存在於範圍查詢W中的具體依據為:xl< χ < xh,且yl < y < yh。其中x, y分別為d在χ軸、y軸方向的坐標值；判定位置坐標d(x, y)屬於查詢結果位置集合Q的具體依據為:存在location」(X」，y」)e Q,使得χ」=χ,且y」=y。
[0020]和現有技術相比，本發明具有以下優點:
[0021]1、更高的安全性
[0022]本發明提出的外包空間資料庫範圍查詢完整性驗證方法將傳統的空間查詢和完整性驗證查詢合併為一次，通過一次範圍查詢獲得查詢結果與完整性驗證信息，從而減少了服務商進行查詢分析的機會；並且由於不同的數據擁有者可能設置不同的鄰近空間對象數量，這進一步增大了服務商進行查詢結果更改的難度。
[0023]2、更高的存儲與查詢效率
[0024]傳統的基於隨機複製的查詢完整性驗證方法，在資料庫中需要存儲額外的對象副本信息，大大增加了資料庫系統的存儲與維護負擔，而本發明對外包空間資料庫中的對象，僅附加少許鄰近對象信息，從而提高了資料庫存儲資源的利用率；通過將空間查詢和完整性驗證查詢進行合併，減少了用戶與服務商的會話連接次數，提高了查詢效率。
[0025]本發明公開了一種用於外包空間資料庫的範圍查詢完整性驗證方法，包括:1、基於自適應Hilbert曲線的範圍查詢轉換，生成一維數值段集合；2、用戶經過認證與外包空間資料庫的服務商建立會話連接，將一維數值段集合發送給服務商；3、服務商根據用戶提交的一維數值段集合，檢索資料庫中符合查詢條件的空間對象集合，並將該空間對象集合返回給用戶；4、用戶接收到服務商返回的查詢結果集合，並對其進行消息摘要驗證；5、用戶根據查詢結果中的鄰近空間對象信息，對結果集的完整性進行驗證。本發明方法可以在外包空間資料庫的模式下，為用戶提供高效、安全的範圍查詢完整性驗證功能，進而對服務商修改查詢結果的行為進行約束，保證範圍查詢服務的質量。
【專利附圖】
【附圖說明】
[0026]圖1為本發明用於外包空間資料庫的範圍查詢完整性驗證方法的流程框圖。【具體實施方式】
[0027]下面結合附圖對本發明做進一步詳細說明。
[0028]請參閱圖1所示，本發明一種用於外包空間資料庫的範圍查詢完整性驗證方法，包括以下步驟:首先，用戶通過自適應Hilbert曲線將二維平面的範圍查詢轉換為一維數值段集合，作為查詢條件；然後，服務商將符合查詢條件的空間對象返回給用戶，用戶對查詢結果進行消息摘要驗證，若未通過則輸出查詢結果不完整；最後，用戶對查詢結果鄰居集合進行範圍查詢驗證，若未通過則輸出查詢結果不完整，否則輸出查詢結果完整。具體包括下列步驟:
[0029]步驟一:用戶通過自適應Hilbert曲線的範圍查詢轉換方法，將二維平面的範圍查詢 W = [xl, xh] X [yl, yh]轉換為一維數值段集合 R= (R1 (S1, e)，R2 (s2, e2)，...，Rn(sn，en)}，即查詢條件，其中:
[0030]xl, xh分別為二維平面的範圍查詢的χ軸方向的最小值、最大值，yl, yh分別為二維平面的範圍查詢的y軸方向的最小值、最大值。Si，ei分別表示數值段Ri的開始值、結束值，I Si Sn，η為數值段的個數。
[0031]步驟二:用戶經過認證與外包空間資料庫的服務商建立會話連接，將步驟一中生成的一維數值段集合R發送給服務商；外包空間資料庫中的每一條記錄對應一個空間對象，數據表的核心欄位為一個三元組:〈index, Enc ((location, text, neighbors (f (1),f(2)，…，f(k)，b(1)，b⑵，…，b(k))), key), Sign〉，其中:
[0032]index為根據當前空間對象的位置坐標location,使用自適應Hilbert曲線生成的索引；text為當前空間對象附屬的其他描述信息；neighbors為與當前空間對象在索引上近鄰的空間對象的位置坐標集合，f⑴、b(i)分別表示index的前驅、後繼空間對象的位置坐標，I < i ( k，k為前驅/後繼空間對象的個數，k的取值由數據擁有者設定；Enc為對稱加密算法，key為對稱密鑰；31811為使用哈希算法他也生成的當前空間對象消息摘要，即 Sign = Hash (location | text | neighbors), | 表不字符串連接運算。
[0033]步驟三:外包空間資料庫服務商根據用戶提交的一維數值段集合R ={Ri(s!, e), R2(s2, e2),…，Rn(sn, en)},檢索資料庫中符合查詢條件的空間對象集合G = {p1；P2,…，Pm}，並將該空間對象集合G返回給用戶，其中:
[0034]Pi表示一個檢索結果,包含索引值indexp密文數據信息Enc ((1cationi, texti；neighborsj)，以及消息摘要Signi, I≤i≤m, m為檢索結果的個數。
[0035]判定Pi符合查詢條件的具體依據為:
[0036]存在Rj e R,使得 Sj ( Indexi ( ej。
[0037]步驟四:用戶接收到 服務商返回的查詢結果集合G = {Pl, p2,…，pm}，對其中的每一個對象 Pi =〈index」 Enc ((1cationi, text」 neighbors), key), Signi)，首先使用與Enc O對應的解密算法Dec O與密鑰key處理空間對象Pi的加密欄位Enc ((1cationi,texti； neighborsj), key),得到 Pi 的明文信息(1cationi, texti； neighborsj),然後使用與步驟二相同的哈希算法HashO生成明文信息的消息摘要，即Sign/ = Hashdocationi | teXti Ineighborsi),判斷Sign/與Signi是否相同,若不相同，則證明空間對象Pi的信息被篡改，終止查詢完整性驗證過程，輸出查詢結果不完整；若對任意Pj e G，均有Sign/ = Signj,則進一步進行下述過程。
[0038]步驟五:將通過步驟四驗證的查詢結果集合G = {Pl, p2,…，P1J，分為兩類集合:查詢結果位置集合Q= (1cation1, 1cation2,..., 1cationJ ,查詢結果鄰居集合N =Ineighbors1, neighbors2,..., neighborsj，其中:
[0039]1cationi 為第 i 個查詢結果的位置坐標 ^eighborsi = (fi(1), fi(2),..., fi(k),bi(1),bi(2),…，bi(k))為與第i個查詢結果在索引上近鄰的空間對象的位置坐標集合，fi(J)>bi(J)分別為1cationi的第j個前驅、後繼空間對象的位置坐標，I ^ j ^ k, k為前驅/後繼空間對象的個數。
[0040]對於任意位置坐標d(x, y) e N,若d存在於範圍查詢W = [xl, xh] X [yl, yh]中，則判斷d是否屬於查詢結果位置集合Q，若不屬於，則終止查詢完整性驗證過程，輸出查詢結果不完整；若查詢結果鄰居集合N中不存在滿足上述條件的位置坐標，則完成查詢完整性驗證過程，輸出查詢結果完整。
[0041]判定位置坐標d(x，y)存在於範圍查詢W中的具體依據為:
[0042]xl≤χ≤xh,且yl≤y≤yh。其中x, y分別為d在χ軸、y軸方向的坐標值。[0043]判定位置坐標d(x，y)屬於查詢結果位置集合Q的具體依據為:
[0044]存在1cationj (Xj, Yj) e Q,使得 Xj = x，且 yj = y。
[0045]綜上所述，本發明提出一種用於外包空間資料庫的範圍查詢完整性驗證方法。該方法通過在外包空間對象中，附加基於索引的鄰近對象信息，降低了查詢完整性驗證對資料庫存儲系統的資源消耗。該方法將傳統的空間查詢和完整性驗證查詢合併為一次，降低了用戶與服務商的會話連接次數，提高了查詢效率，減少了服務商進行查詢分析的機會；並且由於不同的數據擁有者可能設置不同的鄰近空間對象數量，這進一步增大了服務商進行查詢結果更改的難度。
【權利要求】
1.一種用於外包空間資料庫的範圍查詢完整性驗證方法，其特徵在於，包括以下步驟: 首先，用戶通過自適應Hilbert曲線將二維平面的範圍查詢轉換為一維數值段集合，作為查詢條件； 然後，服務商將符合查詢條件的空間對象返回給用戶，用戶對查詢結果進行消息摘要驗證，若未通過則輸出查詢結果不完整； 最後，用戶對查詢結果鄰居集合進行範圍查詢驗證，若未通過則輸出查詢結果不完整，否則輸出查詢結果完整。
2.一種用於外包空間資料庫的範圍查詢完整性驗證方法，其特徵在於，包括以下步驟: 步驟一:用戶通過自適應HiIbert曲線的範圍查詢轉換方法，將二維平面的範圍查詢W=[xl, xh] X [yl, yh]轉換為一維數值段集合 R = (R1 (S1, e)，R2 (s2, e2)，...，Rn(sn, en)}，即查詢條件； xl, xh分別為二維平面的範圍查詢的X軸方向的最小值、最大值；yl, yh分別為二維平面的範圍查詢的y軸方向的最小值、最大值；Si，ei分別表示數值段Ri的開始值、結束值，Ι^?^η,η為數值段的個數； 步驟二:用戶經過認證與外包空間資料庫的服務商建立會話連接，將步驟一中生成的一維數值段集合R發送給服務商；外包空間資料庫中的每一條記錄對應一個空間對象，數據表的核心欄位為一個三元組:〈index, Enc ((location, text, neighbors (f(1), f ⑵，…，f(k)，b⑴，1?),…，b(k))), key), Sign〉； index為根據當前空間對象的位置坐標location,使用自適應Hilbert曲線生成的索引；text為當前空間對象附屬的其他描述信息；neighbors為與當前空間對象在索引上近鄰的空間對象的位置坐標集合，f(i)、b(i)分別表示index的前驅、後繼空間對象的位置坐標，I ^ i ^ k, k為前驅/後繼空間對象的個數，k的取值由數據擁有者設定；Enc為對稱加密算法，key為對稱密鑰；31811為使用哈希算法他也生成的當前空間對象消息摘要，即Sign = Hash (location I text I neighbors)，| 表不字符串連接運算； 步驟三:外包空間資料庫服務商根據用戶提交的一維數值段集合R ={Ri(s!, e), R2(s2, e2),…，Rn(sn, en)},檢索資料庫中符合查詢條件的空間對象集合G = {p1；P2,…，Pm}，並將該空間對象集合G返回給用戶，其中: Pi表示一個檢索結果，包含索引值Indexi,密文數據信息Enc ((1cationi, text」neighborsj)，以及消息摘要Signi, I≤i≤m, m為檢索結果的個數； 步驟四:用戶接收到服務商返回的查詢結果集合G= {ρι，ρ2，…，pm}，對其中的每一個對象 Pi = bi(J)分別為1cationi的第j個前驅、後繼空間對象的位置坐標，I ≤ j ≤ k, k為前驅/後繼空間對象的個數； 對於任意位置坐標d(x, y) e N,若d存在於範圍查詢W = [xl, xh] X [yl, yh]中，貝U判斷d是否屬於查詢結果位置集合Q，若不屬於，則終止查詢完整性驗證過程，輸出查詢結果不完整；若查詢結果鄰居集合N中不存在滿足上述條件的位置坐標，則完成查詢完整性驗證過程，輸出查詢結果完整。
3.根據權利要求2所述的一種用於外包空間資料庫的範圍查詢完整性驗證方法，其特徵在於，步驟三種判定Pi符合查詢條件的具體依據為:存在Rj e R,使得Sj≤ Indexi ≤ ej。
4.根據權利要求2所述的一種用於外包空間資料庫的範圍查詢完整性驗證方法，其特徵在於，判定位置坐標d(x，y)存在於範圍查詢W中的具體依據為:xl ≤ X ≤ xh,且yl≤y≤yh ;其中x, y分別為d在x軸、y軸方向的坐標值；判定位置坐標d(x, y)屬於查詢結果位置集合Q的具體依據為:存在locationj(Xj，yj)e Q,使得χj=x，且yj=y。
【文檔編號】G06F17/30GK103984728SQ201410209505
【公開日】2014年8月13日 申請日期:2014年5月16日 優先權日:2014年5月16日
【發明者】桂小林, 田豐, 楊攀, 楊建偉, 張學軍, 安健 申請人:西安交通大學