基于表集合劃分算法的數(shù)據(jù)交換方法研究

呂進來，楊秋琳

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

0 引 言

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

1 表集合劃分算法

數(shù)據(jù)交換的目的就如圖1所描述的那樣，是把數(shù)據(jù)庫1、數(shù)據(jù)庫2等中的表結(jié)構(gòu)及 （或）對應(yīng)的數(shù)據(jù)，遷移到數(shù)據(jù)中心的數(shù)據(jù)庫中。特別是在數(shù)據(jù)遷移的過程中，由于數(shù)據(jù)庫的表之間存在著關(guān)聯(lián)關(guān)系，因此在數(shù)據(jù)的遷移過程中，只有把主表 （被參照的表）數(shù)據(jù)遷移之后，才能遷移相應(yīng)細表 （參照表）的數(shù)據(jù)，否則，就會產(chǎn)生參照異常。

圖1 數(shù)據(jù)交換流程模型

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

1.1 表順序算法原理

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

原理1：給定非空集合U，U的非空子集形成的集族π＝ ｛A1，A2，…，Am－1，Am｝成為U的一個劃分，如果π具有性質(zhì)［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）循環(huán)執(zhí)行步驟 （4），直至得到表集合U的劃分π。

1.2 表順序算法實現(xiàn)

對應(yīng)上述算法原理的具體實現(xiàn)過程為：

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

表1 數(shù)據(jù)庫中表之間參照關(guān)系矩陣

在表1中

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

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

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

（5）表子集的繼續(xù)生成：檢查新生成的表關(guān)系矩陣，如果表關(guān)系矩陣的行數(shù)不為0，返回 （2），生成新的表子集；如果表關(guān)系矩陣的行數(shù)為0，則表集合的劃分結(jié)束。

1.3 數(shù)據(jù)遷移過程

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

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

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

在將源數(shù)據(jù)庫最新更新的數(shù)據(jù)，即Update數(shù)據(jù)更新到目標數(shù)據(jù)庫時，不會引起數(shù)據(jù)參照異常。因此，不必按照固定的順序?qū)pdate數(shù)據(jù)更新到目標數(shù)據(jù)庫。

2 試驗描述

2.1 試驗用例選取

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

2.2 實現(xiàn)數(shù)據(jù)交換

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

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

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

（3）確定表的遷移順序

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

表2 表之間參照關(guān)系矩陣

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

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

表3 過度表關(guān)系矩陣

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

表4 新的表之間參照關(guān)系矩陣

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

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

2.3 數(shù)據(jù)初始遷移

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

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

（2）將集合A1中表對應(yīng)的XML文件中的數(shù)據(jù)插入數(shù)據(jù)中心；

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

2.4 數(shù)據(jù)持續(xù)更新

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

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

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

（3）轉(zhuǎn)到步驟 （1）。

3 結(jié)束語

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

：

［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技術(shù)的異構(gòu)關(guān)系數(shù)據(jù)庫集成模型 ［J］.計算機工程與設(shè)計，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的異構(gòu)數(shù)據(jù)交換技術(shù)研究 ［J］.蘇州科技學(xué)院學(xué)報 （工業(yè)技術(shù)版），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文檔存儲在關(guān)系數(shù)據(jù)庫中的研究 ［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）.［朱雄軍.網(wǎng)絡(luò)數(shù)據(jù)庫開發(fā)與應(yīng)用 ［M］.北京：清華大學(xué)出版社，2010.］

［8］ZHANG Xinyi.XML simple tutorial［M］.Beijing：Tsinghua University Press，2009 （in Chinese）.［張欣毅.XML簡明教程 ［M］.北京：清華大學(xué)出版社，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.數(shù)據(jù)庫原理、編程與性能 ［M］.周傲英，俞榮華，季文贇，等譯.北京：機械工業(yè)出版社，2007.］

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