基于表集合劃分算法的數據交換方法研究

呂進來，楊秋琳

（1.太原理工大學 計算機科學與技術學院，山西 太原030024；2.哈爾濱工業大學 國家示范性軟件學院，黑龍江 哈爾濱150001）

0 引 言

在數據庫應用中，可能面臨著將異地異構數據庫中的數據集成到中心數據庫中的任務，而關系數據庫的異構特點又使得不同數據庫之間的數據不能直接交換［1，2］。以可擴展標記語言 （extensible markup language，XML）作為公共數據模型，實現異構關系數據庫之間數據交換的研究較多［3－8］，它不但能夠很好的描述關系數據，又具有自描述、可擴展及與平臺無關等特點，可以作為不同關系數據庫系統之間相互傳遞、交換數據的一種轉換標準［9］。但在數據交換過程中，各表之間并不是相互獨立的，而是具有關聯關系［10，11］。這種關聯關系引發了在將一個數據庫中的數據遷移到另一個數據庫時，必須在將被參照表中的數據遷移到目標數據庫之后，才能遷移參照表中的數據，否則，就會在遷移的過程中產生數據參照異常。在復雜的數據庫應用系統中，數據庫中的表可能多達數百個，甚至上千個，它們之間的參照關系更是錯綜復雜，那么應采用何種高效的算法來確定這些表中數據的遷移順序呢？本文利用集合論的相關理論，針對此問題提出一種全新的算法，即 “表集合劃分算法”，很好地解決了這一問題。

1 表集合劃分算法

數據交換的目的就如圖1所描述的那樣，是把數據庫1、數據庫2等中的表結構及 （或）對應的數據，遷移到數據中心的數據庫中。特別是在數據遷移的過程中，由于數據庫的表之間存在著關聯關系，因此在數據的遷移過程中，只有把主表 （被參照的表）數據遷移之后，才能遷移相應細表 （參照表）的數據，否則，就會產生參照異常。

圖1 數據交換流程模型

當數據庫中表的數量比較少，并且表之間的關系比較簡單時，數據庫中表數據遷移的順序問題，比較好解決；但當表的數量很大，并且表之間的關系錯綜復雜時，確定數據庫中表數據的遷移順序就是一個非常重要的問題。而在這一方面，國內外學者對其研究甚少。對此，本文結合集合論的集合劃分理論，給出相應的處理算法。

1.1 表順序算法原理

將數據庫的表集合按照參照關系進行劃分，從而確定對表進行數據遷移／更新的先后順序。原理1給出了如何按照參照關系對表集合進行劃分的形式化描述。

原理1：給定非空集合U，U的非空子集形成的集族π＝ ｛A1，A2，…，Am－1，Am｝成為U的一個劃分，如果π具有性質［12］：①Ai≠ （i＝1，2，…，m）；U；③Ai∩Aj＝ （i≠j，1≤i，j≤m）。

分割非空表集合 U，得到 U的劃分π，π＝ ｛A1，A2，…，Am－1，Am｝。集合的劃分方法如下：

（1）將表集合U中所有沒有外鍵的表放入集合A1中，同時也將只參照自身主鍵的表放到A1中；

（2）將表集合U中外鍵都是參照集合A1中表的主鍵的表放入A2中；

（3）將表集合U中外鍵都是參照集合A2中表的主鍵的表放入A3中，并且這些表有可能同時也參照集合A1中表的主鍵；

（4）將表集合U中外鍵都是參照集合Ak（k＞0）中表的主鍵的表放入 Ak＋1中 （k＋1≤m），并且這些表有可能同時也參照集合Aj（j＝1，2，…，k－1）中表的主鍵；

（5）循環執行步驟 （4），直至得到表集合U的劃分π。

1.2 表順序算法實現

對應上述算法原理的具體實現過程為：

（1）初始表關系矩陣的生成：假定非空表集合U中含有tb1，tb2，…，tbn共n個表，整個數據庫中各表之間的參照關系矩陣見表1。

表1 數據庫中表之間參照關系矩陣

在表1中

（2）表子集Ai的生成：對存在的表關系矩陣，遍歷矩陣的每一行，當一行中的每一個元素的值都為0時，把該表加入表子集Ai中，這樣就生成了表子集Ai（這里i的值從1開始計數，每生成一個新的表子集，i的值就增加1）；

（3）表關系矩陣值的修正：對應表子集Ai中的每一個表元素tbk（k＝1，2，…，m），修正表關系矩陣第k列的所有元素的值都為0；

（4）表關系矩陣行的約減：在表關系矩陣中，刪除表子集Ai中每個表元素tbk（k＝1，2，…，m）對應的行，形成新的表關系矩陣。

（5）表子集的繼續生成：檢查新生成的表關系矩陣，如果表關系矩陣的行數不為0，返回 （2），生成新的表子集；如果表關系矩陣的行數為0，則表集合的劃分結束。

1.3 數據遷移過程

設R為表集合劃分π上的二元關系，且R＝ ｛＜Ai，Aj＞，i＜j｝。二元關系R－1是二元關系R的逆。

在將源數據庫最新插入的數據 （Insert數據）更新到目標數據庫時，對于任何Ai與Aj（0＜i＜j≤m），必須先將集合Ai中表的Insert數據更新到目標數據庫，再更新集合Aj中表的Insert數據，Ai必須在Aj之前完成Insert數據的更新，否則會出現數據參照異常。因此，二元關系R是反自反的，反對稱的，傳遞的。由擬序的定義［12］可知，二元關系R是π上的擬序。

在將源數據庫最新刪除的數據 （Delete數據）更新到目標數據庫時，對于任何 Ai與 Aj（0＜i＜j≤m），必須先將集合Aj中表的Delete數據更新到目標數據庫，再更新集合Ai中表的Delete數據，Aj必須在Ai之前完成Delete數據的更新，否則會出現數據參照異常。因此，二元關系R－1是反自反的，反對稱的，傳遞的。同理，由擬序的定義可知，二元關系R－1也是π上的擬序。

在將源數據庫最新更新的數據，即Update數據更新到目標數據庫時，不會引起數據參照異常。因此，不必按照固定的順序將Update數據更新到目標數據庫。

2 試驗描述

2.1 試驗用例選取

選擇 MS SQLServer 2008為源數據庫，Oracle 11g為目標數據庫。如圖1所示，假設數據庫1中存儲的表如圖2所示，其中箭頭所指向的表為被參照表。

2.2 實現數據交換

數據庫1到數據中心的數據遷移整個流程如圖3所示。

（1）建立主表的輔表：建立輔表的目的是在源數據庫表中的數據發生插入、修改及刪除操作時，方便對目標數據庫進行更新。輔表的主鍵和主表的主鍵數據類型相同，輔表的operatype列的值被限定為1、2或3（1、2、3分別代表對記錄的操作類型為插入、更新、刪除）。為了防止觸發器和Kettle（一種數據交換工具軟件）同時對同一個輔表進行操作，對一個主表需要建立兩個輔表，分別為輔表1和輔表2。當Kettle對輔表1操作時，若觸發器也要對輔表進行操作，那么讓觸發器操作輔表2，在Kettle完成對輔表1的操作后，將輔表2中的數據轉移到輔表1中。也就是說，輔表2的建立是為了使輔表1更好地完成工作。

（2）建立主表的觸發器：觸發器的功能是在輔表中記錄每次對主表操作的類型。

（3）確定表的遷移順序

1）對圖2而言，表集合U＝ ｛學生，課程，班級，教師，課程類型，院系，職稱類型，選課，授課，管理｝，通過對各表關系的分析，得到如表2所示的表之間參照關系矩陣 （A－－學生，B－－課程，C－－班級，D－－教師，E－－課程類 型，F－－院 系，G－－職 稱 類 型， H－－選 課，I－－授 課，J－－管理）。

表2 表之間參照關系矩陣

2）對照表2所示的關系矩陣，遍歷該矩陣的每一行，把所有元素值都為0的行所對應的表加入表子集A1，得到A1＝ ｛課程類型 （E），院系 （F），職稱類型 （G）｝；

3）對照表子集A1中每一個表元素tbk（k＝1，2，3），修正表2所示關系矩陣，將該關系矩陣第k列的所有元素的值都置為0，形成如表3所示的過度表關系矩陣；

表3 過度表關系矩陣

4）對照表子集A1中每個表元素tbk（k＝1，2，3），刪除其在表3所示矩陣對應的行，形成如表4所示的新的表之間參照關系矩陣。

表4 新的表之間參照關系矩陣

5）重復2）到4），又分別得到A2＝ ｛課程 （B），班級（C），教 師 （D）｝，A3＝ ｛學 生 （A），授 課 （I），管 理（J）｝，A4＝ ｛選課 （H）｝。這樣就得到了表的劃分 U＝（A1，A2，A3，A4），也得到了表數據的遷移順序：課程類型，院系，職稱類型，課程，班級，教師，學生，授課，管理，選課。

（4）生成映射模型：映射模型主要處理對目標數據庫表的插入、修改及刪除3種數據更新行為。當向目標數據庫插入新數據及修改目標數據庫中已有數據時，映射模型按照所確定的表數據遷移順序處理XML數據文檔；若要刪除目標數據庫中的數據，映射模型按照所確定的表數據遷移順序的逆序處理XML數據文檔。

2.3 數據初始遷移

數據初始遷移的目的就是要把源數據庫中的數據遷移到目標數據庫。數據初始遷移的通用流程為：

（1）從FTP服務器獲取從源數據庫提取的XML數據文件，將XML數據文件放在本地目錄下，以便于本地數據操作；

（2）將集合A1中表對應的XML文件中的數據插入數據中心；

（3）將集合A2中表對應的XML文件中的數據插入數據中心；然后依次對集合A3，…，Am－1，Am進行同樣操作，直至所有數據都被插入到數據中心。

2.4 數據持續更新

數據持續更新流程的目的是把源數據庫中最近更新過的數據及時更新到目標數據庫中，以保證數據中心數據的正確性。數據持續更新的流程為：

（1）按照一定的時間間隔，檢查FTP服務器目錄，如果有XML數據文件，則獲取XML數據文件，將XML數據文件放在本地目錄下，并將FTP服務器目錄下的XML數據文件刪除，如果沒有XML數據文件，那么本次流程結束，重新執行步驟 （1）；

（2）將 所 有 的 Update＿XML、Insert＿XML 及Delete＿XML文件中的數據更新到數據中心；

（3）轉到步驟 （1）。

3 結束語

數據庫應用系統中普遍存在數據交換，對數據交換過程中的數據遷移／更新順序的問題研究并不多見。本文通過應用集合劃分理論，提出了基于表集合劃分算法的數據交換方法，為數據交換過程中表數據遷移／更新的順序問題提出了很好的解決方案，為建立高質量、高可靠性、高效率的數據交換系統奠定了基礎。本文所提出的確立表數據遷移／更新順序的方法，適用于任何種類、環境下的關系型數據庫管理系統。

：

［1］HAO Shaohua，HAN Xie.Integrated model of heterogeneous rela－tional database based on XML technology ［J］.Computer Engineering and Design，2010，31 （24）：5285－5288 （in Chinese）. ［郝少華，韓燮.基于XML技術的異構關系數據庫集成模型 ［J］.計算機工程與設計，2010，31 （24）：5285－5288.］

［2］ZHANG Lihua.Research on heterogeneous exchange database technology based on XML ［J］.School Newspaper of Suzhou College of Technology （Technology of Industry），2010，23（2）：77－80 （in Chinese）.［張麗華.基于 XML的異構數據交換技術研究 ［J］.蘇州科技學院學報 （工業技術版），2010，23 （2）：77－80.］

［3］TAN Mao，LI Youzhi.Design and implementation of general distributed heterogeneous data exchange system ［C］／／IEEE Press.China：IEEE 3rd International Conference on Communication Software and Networks，2011：416－420.

［4］JIA Xiaoheng.XML word store in the research of relational database ［J］.Computer Programming Skills and Maintenance，2009，15 （24）：56－57 （in Chinese）. ［賈小恒.XML文檔存儲在關系數據庫中的研究 ［J］.電腦編程技巧與維護，2009，15 （24）：56－57.］

［5］Md Anisur Rahman，Masud Karim S M.Tabular representation of schema mappings of a data exchange system ［C］／／IEEE Press.Bangladesh：14th International Conference on Computer and Information Technology，2011：423－427.

［6］Shenyi Qian，Zhongju.Design and implementation of the data share and data exchange system based on SOA ［C］／／IEEE Press.China：IEEE 3rd International Conference on Communi－cation Software and Networks，2011：697－699.

［7］ZHU Xiongjun.Development and application of network database ［M］.Beijing：Tsinghua University Press，2010 （in Chinese）.［朱雄軍.網絡數據庫開發與應用 ［M］.北京：清華大學出版社，2010.］

［8］ZHANG Xinyi.XML simple tutorial［M］.Beijing：Tsinghua University Press，2009 （in Chinese）.［張欣毅.XML簡明教程 ［M］.北京：清華大學出版社，2009.］

［9］Bertossi Leopoldo，Bravo Loreto.Information sharing agents in a peer data exchange system ［C］／／Globe，Data Management in Grid and Peer－to－Peer Systems－First International Conference，2008：70－81.

［10］Reddy K Suresh Kumar，Narayana G，Padmavathamma M.Learner integrated data exchange system architecture ［C］／／IEEE Press.India：IEEE 2nd International Conference on Software Engineering and Service Science，2011：63－65.

［11］Patrick O’Neil，Elizabeth O’Neil.Database principles，programming and performance ［M］.ZHOU Aoying，YU Ronghua，JI Wenbin，et al transl.Beijing：China Machine Press，2007 （in Chinese）.［Patrick O’Neil，Elizabeth O’Neil.數據庫原理、編程與性能 ［M］.周傲英，俞榮華，季文贇，等譯.北京：機械工業出版社，2007.］

［12］WANG Yihe.Introduction to discrete mathematics ［M］.3rd ed.Harbin：Harbin Institute of Technology Press，2007 （in Chinese）.［王義和.離散數學引論 ［M］.3版.哈爾濱哈：爾濱工業大學出版社，2007.］