異構空間數據系統查詢分解算法的研究

摘要：介紹了利用析取范式進行查詢分解的算法，該分解方法在語義分析和規范化的基礎上，對查詢語句進行重組，可以大幅度地減少連接運算的時間，提高查詢效率。

關鍵詞：空間數據集成; 查詢分解; 析取范式

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2007)12-0097-02

隨著Internet技術的迅速崛起和在全球范圍內應用的飛速發展，信息共享已經成為一種必然要求。在地理信息領域，集成分布式的、異構的信息一直是活躍的研究方向。對空間數據庫，由于空間數據結構的復雜性，且在GIS發展初期沒有確定的工業標準，這些GIS平臺所采用的數據結構、數據組織方法和數據在系統中的存儲與表現形式均各不相同，而且大量的空間數據被存儲在不同的物理位置上。這使得GIS的數據共享問題變得尤為突出。

基于Mediator－Wrapper的信息集成系統是當前信息集成系統研究的主要對象，已經出現了許多基于Mediator－Wrapper結構的信息集成系統，如Intergraph公司的GeoMedia系列軟件和中國科學院地理信息產業發展中心研制的SuperMap。

基于Mediator－Wrapper的方式集成空間和非空間數據，數據存儲格式可以包括關系數據庫（如Oracle、 SQL Server等）、專用空間數據庫（如Oracle Spatial、ArcSDE等）、文件數據庫（如Shapefile、MIF等）。空間數據集成系統查詢需要從多個異構的數據源中獲取數據，因此，Mediator應該具備查詢語句分解和對中間結果進行組織的能力。 筆者在項目中研究并實現了對GSQL查詢語言的分解算法，根據各個數據源的能力，將全局的針對多數據源的查詢分解為多個針對單數據源的子查詢，實現了多種數據源的無縫集成。

1多數據源查詢算法

多數據源查詢算法可以概括為以下五個步驟（本文重點討論查詢分解算法）：

a）獲取查詢語句中投影運算以及查詢條件中使用的屬性，構造查詢屬性集。

b）利用構造析取范式樹的方法對查詢條件進行分解，構造n個析取項；分離出只涉及單一圖層的查詢條件，以減少參與連接運算的元組數量。

c）按照a)提取的屬性集和b)得到的查詢條件析取范式的n個析取項，將查詢語句改寫為n個僅包含一個析取項的查詢語句。

d)對于每個僅包含一個析取項的查詢語句，進行以下處理：

(a)依次考慮查詢中涉及到的每個圖層及其查詢屬性（來自a)），各自構造一個僅涉及單一圖層的查詢語句。

(b)在析取項中提取出僅涉及單一圖層的查詢條件，添加到該圖層的查詢語句中。

(c)利用這些單一圖層的查詢語句對各圖層進行查詢，完成相應的選擇計算，構造出一組單一圖層的查詢結果集。查詢中將避免反復針對同一圖層。

(d)按照析取項中剩余的、涉及多個圖層的查詢條件，針對多個圖層的查詢結果集，完成原始查詢語句中指定的連接運算和集合運算，得到一個查詢結果集。

e)合并步驟d）得到的所有查詢結果集，消除重復項得到最終的查詢結果集，實現了空間數據集成。

2查詢分解

查詢分解是查詢處理的第一階段。其目標是將用高級語言表示的查詢轉換成為關系代數樹的形式，并從語法的角度驗證查詢的正確性。查詢分解通常又可分為規范化、語義分析、簡化和查詢重組這幾個過程^[1]。本文給出的查詢分解算法是在語義分析和規范化的基礎上，對查詢語句進行的重組。

2．1多數據源查詢中的啟發式優化策略

為了提高系統的執行效率，結合多數據源查詢算法，設計了以下啟發式策略對查詢語句的執行過程進行優化。

1)盡早執行選擇運算選擇運算減少了關系中元組的數量，從而降低了后面關系處理的復雜度。因此，可以將只涉及到單個表的選擇條件盡量在靠近數據源的層中完成。

2)盡早執行投影運算投影減少了關系屬性的數目，從而減少了下面的關系處理和數據傳輸量。因此對于底層查詢的投影要求盡量達到最少。

3)只計算一次公共表達式的值如果公共表達式在關系樹中出現了多次，而且運算得到的結果又不是太復雜的話，當計算一次后，可以將結果存儲起來，然后在后面需要它時直接使用。采用這種做法的前提是，必須確保表達式的計算結果要么存放在主存儲器中，要么從輔助存儲中讀取結果的開銷遠低于重新計算表達式的開銷。

2．2查詢分解方法

對于涉及多數據源的空間數據查詢，需要將查詢請求分解為針對各個單數據源的查詢。為了獲得較高的查詢效率，避免過多的數據傳輸，應采用適當的查詢分解方法，盡可能將查詢條件分解到單數據源查詢中，以獲得經過數據源篩選的查詢結果，減少數據傳輸和數據集成的系統開銷。

本文采取提取析取范式的方法，將查詢條件的邏輯組合轉換成析取范式結構，即多個與項組合的并集；然后對每個與項中針對同一圖層的查詢條件組合組織一次查詢，每次得到一個子結果集，將同一個與項中不同圖層的查詢中間結果進行連接；最后再對所有與項的結果取并集，得到正確的結果集。每個與項組合查詢中條件間的關系為“與”。可以將針對同一圖層的查詢條件合并，一次性完成篩選，則取得的中間結果集就相對較小，即參加連接運算的元組數量減少，可以大幅度地減少連接運算的時間；同時，混合查詢條件只是作為每個析取項的組織最終結果的連接條件，不用單獨為中間結果組織連接運算。

2．3查詢條件進行析取范式變換

在查詢分解的過程中，通常采用關系代數樹來表示查詢條件，因為在關系代數樹上可以方便地進行條件變換^[1]。本文在條件變換過程中設計了兩種關系代數樹結構，即BLRTree（binary logic relation tree，二元邏輯關系樹）和OATree（樹中只有OR、AND和確切的查詢條件三層節點）。前者是一種二叉樹結構，通過對原查詢條件的語法分析，自底向上構造這樣一棵樹。在此樹中，所有的非葉子節點均是二元邏輯運算符AND或OR，而所有的葉子節點均是單個查詢條件。原查詢中的NOT節點已降至葉子節點處，且不以節點的形式存在，而是作為條件節點的一個布爾值參數。圖1是一個BLRTree的例子。

由于最終結果是多個與項組合的并集（析取范式結構），即將多個與項組合“或”起來。若把每個與項組合中的所有條件項看做是同一層，而把每個與項組合之間看做是同一層，最上層的“或”關系為一層，則可將一個由多個與項組合的并集用一種三層孩子兄弟樹OATree結構來表示，如(A*C)+(A*D)+(B*C)+(B*D)可以表示為圖2的形式。

3結束語

本文首先給出了多數據源查詢過程中Mediator中的關鍵步驟。查詢分解是數據集成系統中一個不可回避的問題，一個好的查詢分解算法能夠有效地提高數據集成系統的性能。本文給出了對擴展GSQL查詢語言的查詢分解算法。查詢分解算法不僅實現了空間數據集成系統中跨數據源查詢的功能，而且通過啟發式策略對查詢分解進行了優化，提高了系統的執行效率。用戶在編寫查詢時，可以簡單

地將多個數據源理解為相同的單一數據源，而無須對跨數據源查詢的處理進行任何干預。查詢結果集的組織算法首先將對應的單數據源查詢結果進行笛卡兒操作，得到完整的記錄內容；然后通過對主鍵序列的歸并運算有效避免了重復記錄的出現，得到用戶最終的查詢結果。通過查詢分解算法和查詢結果集組織算法的實現，再加上系統的單表查詢能力，即可實現一個簡單的進行異構空間數據集成的Mediator。

參考文獻：

[1]CONNOLLY T， BEGG C. 數據庫系統設計、實現與管理[M]. 寧洪，等譯. 北京：電子工業出版社， 2004:142-150.

[2]HULL R， ZHOU Gang. A framework for supporting data integration using the materialized and virtual approaches[C]//Proc of ACM SIGMOD. New York:ACM Press，1996:481-492.

[3]ZHANG Jian－ting， JAVED M. Prototype for wrapping and visulizing geo－referenced data in a distributed environment using XML technology[C]//Proc of ACM Symposium on GIS. WashingtonDC:ACM Press，2000:27-31.

[4]MILLSTEIN T， LEVY A， FRIENMAN M.Query containment for data integration systems[C]//Proc of PODS. Orlando:Academic Press，2000:67-75.

[5]廖湖聲，王晉強，鄭玉明，等.多源空間數據庫引擎的研究與實現[J].計算機應用研究，2004，22(8):182-184.

[6]廖湖聲，鄭玉明.面向空間數據庫引擎的擴充數據模型及其操縱語言GSQL[J].計算機工程與應用，2002，38(3):123-125.

[7]邵佩英.分布式數據庫系統及其應用［M］.北京:科學出版社，2000:105-112.

[8]鄔倫，張毅.分布式多空間數據庫系統的集成技術[J].地理學與國土研究，2002(1):6-10.

[9]樊昱，高紅雨，廖湖聲.基于Java的ArcSDE空間數據查詢的設計與實現[C].第七屆Java應用技術大會.2004:37-39.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”