基于表集合划分算法的数据交换方法研究

吕进来，杨秋琳

（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.］