定義
數據集成系統是一個三元組<G,S,M >,其中:G是全局模式,S是數據源模式, M為全局模式和數據源模式之間的映射。在數據集成系統中,在創建虛擬的全局模式及其與下層數據源模式之間的“映射關係”後,用戶在全局模式上提出“查詢請求”,系統將查詢請求按照映射關係轉換為對應下層數據源模式的“子目標” (稱之為“查詢重寫”),而後進入子目標的“執行”,重寫和執行過程中都可能存在“最佳化”,子目標並不是直接運行在下層數據源系統內,而是通過一個“封裝器”間接地和下層數據源交流,最後系統將每個子目標執行結果整合為統一結果,按照用戶要求或系統設定格式提供給用戶。
主要問題
數據集成系統遇到的主要問題集中在建立語義联系,查詢重寫,查詢最佳化和查詢執行中,核心和基礎是建立語義联系。
語義联系
語義联系是多模式套用(數據集成、語義Web、數據移植、實體整合等)中的一個基礎性問題, 在數據集成系統中它是用戶查詢和下層數據源數據建立聯繫的唯一橋樑。
使用最多的語義联系方式是採用映射, 其終極目的就是獲得一個正確的、滿足套用要求的映射。映射語義就是對兩個模式之間的元組所實施的約束,決定了在給定映射下哪些元組對可以共存。一個映射能否滿足特定的主題要求必須具備三個條件:清晰語義,對不完整信息的適應性和允許模式異構。映射有三個重要的屬性:查詢回答能力,映射推理能力和映射整合能力。
顯然,實際中的映射是不精確的,也是不確定的。因此目標就是要找到一個“最好”的映射,或者“最有效”的映射。這個研究結論對於指導尋找映射非常有價值。目前對於映射性質的研究,主要是基於有明確定義的模式之間的映射,對於在集成套用系統中存在音樂、拓片、電影等無具體的模式定義的情況仍然需要進一步研究。
模式只是一個象徵性符號,並不能完全表達出它所代表對象的全部含義,所以完全自動地建立語義联系是不可能的。建立語義联系在現實中大多通過人工完成,但這個過程是一個勞動力密集型且容易出錯的工作。
模式是指和某個結構聯繫的元素的集合,映射是兩個模式中有映射關係的規則集合,意味著一個模式中某些特定的元素映射到另一個模式中某些特定的元素。一個映射關係必須存在兩個部分:映射的元素和映射元素之間的映射描述。
匹配就是找到分布在兩個不同模式中的元素之間的某種映射關係的行為,可以理解為將兩個模式作為參數輸入,輸出結果是它們之間的映射關係的函式,輸出的結果為匹配結果,每個匹配結果中的元素都表示一個輸入參數中有特定的元素和另一個輸入參數中某些特定的元素存在邏輯上的對應關係,這些對應關係的語義就是通過映射元素的映射描述來表達的。所以關鍵是尋找匹配方法,而這個方法的目標應該是自動的、精確的、廣泛適應的。映射可以分為兩個階段:首先找到下層數據源模式與全局模式之間的映射;其次在全局模式中描述這些映射。
顯然無法利用數學公式或者數學方法來對兩個模式之間的對應關係進行計算,只能利用模式本身所蘊涵的語義和數據來尋找二者之間的對應關係。儘可能多地挖掘這些信息,並對這些信息正確加以運用是匹配的核心。從目前研究看,使用到的信息可以分為幾類:1)模式信息, 包括模式的結構、關係類型、注釋和描述、元素名稱、元素數據類型、約束條件、關鍵字屬性、外鍵屬性、命名空間、所在域等;2)實例/內 容信息;3)輔助信息, 包括字典、先前的成功映射、用戶輸入、套用領域規範等。
匹配算法除了利用不同種類的信息外,也對這些信息採用了兩種不同的使用方式:一種只根據單一信息標準完成匹配,如以名字的相似程度作為標準;另一種則綜合多種信息標準來完成匹配。這些匹配算法找到的匹配結果就是映射,考慮到精度問題,多數作為候選映射供手工選擇或調整,它們可能帶有0 ~ 1之間的某個權值作為匹配精度。為了提高匹配的精確度,有些匹配方案會將多個不同匹配算法得到的匹配結果再進行綜合整理後提供給用戶。
查詢重寫
查詢重寫是利用語義联系,將建立在全局模式上的查詢用(且僅用)下層數據源的資源描述來重新表述。全局模式採用不同的描述方式對應著不同的查詢重寫方式,前面提到LAV方式引入了一個關鍵難題:利用視圖來回答查詢的問題。該問題在不同的套用領域有不同的側重點, 它有三種輸出結果:最終查詢結果、查詢計畫和查詢重寫形式。
數據集成中的查詢重寫有幾個特點需要注意:第一是涉及的視圖數量非常多;其次視圖定義中可能包含非常複雜的謂詞邏輯;第三數據源的數據往往是不完整的,即數據源只包含部分滿足視圖定義的數據。
查詢算法主要如下:
(1)Bucket algorithm:算法主要的想法是先單獨考慮每個子目標,確定哪些視圖和子目標相關,從而達到顯著減少重寫個數的目的。算法分為兩個階段,第一階段確定bucket中的視圖;第二階段根據bucket中的視圖寫出查詢重寫表達式。在第一階段中算法為每個子目標創建一個bucket存放與該子目標相關的視圖。算法通過兩個步驟確定視圖和子目標相關:1)檢查視圖定義和子目標參數表是否存在某種一致性;2)檢查查詢和視圖是否兼容。兩個條件均滿足則把視圖放到bucket中,重複數據只出現一次。第二階段中組合這些bucket中的視圖。每次從每個bucket中取出一個視圖組合形成一個候選的查詢重寫(不重複),檢測它是否為查詢的重寫形式,最後將所有檢測通過的重寫結果聯合起來就是原查詢的最大包含查詢重寫,但不一定是等價重寫。Bucket算法的優點是在算法的早期就充分利用信息去掉了很多後面需要考慮的候選重寫,其缺陷是第二階段所產生的笛卡兒乘積數仍然很多,而對每個重寫均要進行包含檢測。
(2)Inverse rules algortihm:算法思想是構建一個由反轉視圖定義後形成特殊規則的集合。反轉規則是將LAV的描述方式變換成GAV的描述方式,查詢可以按照反轉規則直接展開,返回的是最大包含重寫。算法最大的優點是概念非常清楚而且很容易模型化,另外獲得最大包含重寫的時間開銷是相對於視圖和查詢大小的多項式。該算法的缺點有兩個:反轉規則會包含一些對查詢沒有意義的視圖,需要在算法中利用單獨過程來消除無用視圖;沒有充分利用已經物化的視圖,從而喪失了很多計算上的優勢。
查詢最佳化和查詢執行
數據集成系統的下層數據源有幾個特點:1)下層數據源的數據可能冗餘,相互覆蓋,甚至衝突;2)數據源是自治的,其狀態是動態變化的,故最佳化器不能獲取足夠的統計信息,而且歷史統計數據很難具有直接的參考價值;3)數據源分布在廣闊地理空間中,其傳輸延遲、異常等無法把握,即使採用了最好的執行方案,也完全可能因為數據延遲而變得不可行;4)下層數據源數據表現形式多樣結構化,半結構化,甚至無結構,故其執行查詢的能力也大不相同等。正是這些特點使得查詢最佳化和執行變得非常困難,傳統的最佳化技術已經無法適應這樣的環境。另外,數據集成的查詢最佳化和傳統資料庫查詢最佳化目標並不相同,後者是從整體上來最佳化查詢的執行,而前者由於套用了大量的數據源,重寫後形成的子查詢數量非常多,對這些計畫評估的開銷巨大,不是每一個計畫都去執行,可能在執行的過程中用戶對已經返回的結果滿意了就會終止執行,或者計畫執行過程中達到了某種資源限制或閾值而結束執行,所以儘快獲得第一批結果非常重要,最佳化的目標不是要求整個查詢的代價最小,而是要儘可能快地返回儘可能多的結果。這也造成了數據集成的最佳化和傳統資料庫最佳化有著本質上的區別。
查詢最佳化是非常關鍵的步驟,一個沒有最佳化的計畫也許根本就不能獲得結果,最佳化方法可分為本地執行方案和分散式(多節點)執行方案兩類,這兩類又可細分為適應性最佳化策略和非適應性最佳化策略。
由於數據集成環境中數據源的遠程分布、自治等特點,使得非適應性最佳化並不能從根本上提高執行效率,最佳化方案必須隨著環境變化而作出相應調整,這就是適應性最佳化方案,是目前研究得最多的,也應該是最有前途的方案。不管是本地執行的最佳化還是分布在網路中多個節點執行的最佳化均可以採用適應性策略。
發展方向
近來研究者們已經將最佳化的目光放在網路分散式執行方面了,但幾個方面仍然需要足夠重視:第一是主動最佳化的概念。除了被動利用各數據資源的數據和能力,也需要主動挖掘網路和數據資源的潛力,如將部分數據內容複製到其他節點以加速訪問(數據分布問題),或者對某些功能強大而且持久有效的節點賦予更多的訪問優先權等。第二是挖掘傳統技術潛力。比如建立輔助手段來保證傳統最佳化數據的可用性。第三是運用分散式計算。比如異地計算將結果傳回本地而不是把數據取回本地等。