一种面向教育行业的多尺度渐进式差异数据定位方法

摘要

本发明公开了一种面向教育行业的多尺度渐进式差异数据定位方法，包括以下步骤：S1、数据排序：将运行表TR和备份表TB按照主键值大小进行排序；S2、计算起始主键值KStart和终止主键值KEnd；S3、对主键值数据范围[Kttart，KSnd]进行尺度划分；S4、对分组进行判断：S4.1、KStarti＜KEndi，计算TR和TB中主键值在该分组范围内的数据记录；S4.2、KStarti＝KEndi，令K＝KStarti＝KEndi，取出K对应的数据记录进行比较；S5、对所有分组都执行S4的操作，得到差异数据项。本发明可以在运行表和备份表中快速高效地定位那些存在差异的数据记录项，并输出数据比对的结果，并且对数据库的性能压力也较小。

说明书

技术领域

本发明属于数据处理技术领域，特别涉及一种面向教育行业的多尺度渐进式差异数据定位方法。

背景技术

随着教育信息化的持续推进和广泛应用，教育行业每天都会新增大量的数据。相对于其它行业，教育行业具有数据结构复杂、用户数量巨大、数据增长快的特点。以一个普通的高等院校为例，包含数万学生和数千老师，各个部门运行着各类不同的应用系统，比如财务系统、人事系统、学工系统、教务系统等，这些系统每时每刻都在产生着大量的数据，为了存储这些数据，需要使用数据库，其中关系型数据库是最常用和最成熟的数据库系统，它以行(row)为单位存储和检索数据。

教育行业数据库中的数据不仅数量庞大，而且随时可能发生各种变化，比如数据的新增、修改和删除操作，为了更安全和有效地管理数据，常常需要对数据库进行定期备份，备份库为数据清洗、纠错、恢复等维护操作提供了必要的支撑条件。这些操作很多时候都需要查找数据发生的变化情况，也就是将备份数据与当前运行数据进行比对，找出二者的区别。

传统的数据比对方法需要将备份库与运行库的数据行进行一一比较，这个操作非常耗时，随着数据量的膨胀，所需时间呈指数级增长。因此，需要设计一种更加高效快速的数据比较方法，可以在较短时间内定位两个不同数据库之间差异位置，并且给出具体发生的变化类型(新增、修改、删除)。

关系型数据库以数据表(table)的方式存储数据。数据表是一张二维表格，它包括若干列和若干行，其中列表示数据字段，行表示数据记录，如表1给出了用于存储学生信息的表student：

表1：学生信息表示例(student)

每张表都有一列或多列用于唯一标识数据行记录，称为“主键(key)”，例如表1中的学生ID就是student表的主键。尽管主键可以是多个字段，但在绝大多数情况下，都使用唯一列作为主键标识，因为这样更容易管理和维护，数据检索效率也更高。主键一般具有以下特征：

(1)主键不能为空且不可重复：主键必须有值，而且不能与已有记录的主键值重复，这是关系型数据库对主键的基本要求。

(2)主键值是可比较的，因此可以按照主键大小进行排序。最常见的主键值采用正整数依次增大的方式记录。尽管可以使用字符串作为主键，但由于其不可进行加减运算，在使用上有许多限制，所以较少采用。

(3)主键值不可修改。主键作为数据记录的唯一标识，它代表了某条记录的唯一检索依据，对它的修改可能导致数据不一致的情况，所以大多数数据库都不建议甚至不允许修改主键值。实际上我们总可以通过额外添加一列具有唯一值却没有实际物理含义的字段作为主键，从而避免修改它的值。

(4)主键值不可复用。如果某条记录被删除，该记录对应的主键值将不在新插入的数据记录中使用。例如表1中，ID为3的学生被删除后，后面新插入的数据不再使用3作为主键值。不复用主键值的原因：一是由于该主键值在运行表和备份表中同时存在，在比较备份表和运行表的数据过程中，无法区分究竟是删除再新增还是直接修改了该记录；二是因为主键仅作为数据检索标识，没有实际物理意义的情况下，没有必要复用主键值。

数据量的含义为：绝大多数情况下表的列(即字段)不会发生变化，如果是列发生变化，则认为数据库结构发生了质变，这将导致所有与该数据表有关的数据使用、运行和维护程序都会受到巨大影响，因此在数据库实际运行过程中，一旦正式上线，绝不发生列定义的变化。因此，数据表的数据量的度量标准由行数来决定，目前尚无对数据库量级的通用标准，经验上一般认为百万级是大量数据，千万级是超大量数据，亿级以上是巨量数据。

在教育信息化系统中实际使用的数据表称为运行表，例如学工系统中的学生信息表，实时记录了全部学生信息。将某个时刻的运行表的结构和记录复制保存，在备份完成的时刻，备份表与当前的运行表具有完全相同的数据，但随着时间的推移，运行表会发生许多变化，例如学生ID为3的类型从“学士”修改成了“硕士”等，但此时备份表的数据不会发生任何变化。

如上所述，运行表会随着业务操作的执行过程，发生许多变化，这些变化类型主要包括以下情况：

(1)插入数据：在运行表中新增了一条记录，此时新记录的主键在备份表中并不存在；

(2)修改数据：运行表中的某条记录的某个或多个字段(不能是主键)值发生了变化，此时运行表和备份表的该记录有相同的主键值；

(3)删除数据：从运行表中删除一条或多条记录，此时备份表中有被删除记录的主键而运行表中没有。

差异数据定位就是将运行表与备份表进行数据对比，精准定位发生了变化的记录。由于数据列是固定且有限的，所以只要定位到了数据行，就很容易进行字段值的比较了。行的唯一标识是主键，因此差异数据比较需要给出差异数据的主键值和变化类型。根据不同的变化类型，给出差异结果描述如下：

(1)插入数据：changeType＝insert，newId＝新记录的主键值；

(2)修改数据：changeType＝update，id＝修改记录的主键值；

(3)删除数据：changeType＝delete，oldId＝被删除记录的主键值。

要定位差异数据，需要对运行表和备份表进行数据比对，特别当数据量很大时(百万级以上)，要寻找一些微小的数据变化，是比较困难的。当前的数据比对方法主要包括：

(1)全表比对：将备份表中的每一行数据依次取出，与运行表中的数据一一比较，这个过程可以定位修改和删除的数据，但无法找到新增的数据(因为备份表中没有这些数据)，因此还需要把运行表中的所有未进行比对的数据进行记录，所以非常耗时。对于大数据量的情况，全表比对无法满足对时间和效率的要求。

(2)日志分析：大多数的数据库都提供数据操作的日志记录，理论上可以从日志中找到所有的数据变化信息，进一步定位到数据差异位置。但从实际操作来看，日志分析技术难度很大，首先日志信息是“非结构化”的，它只是一段文字描述，需要从中提取和解析数据变化的详细内容是很困难的；其次日志信息量本身也非常庞大，需要从备份时间开始，依次分析所有的数据操作，所需时间很长；第三，不同的数据库提供的日志信息格式、数据描述方式都不相同，可能无法精准定位到发生变化的主键值位置。所以大数据量情况下，日志分析法也无法满足差异数据精准定位的要求。

(3)编写触发器程序：大多数数据库支持编写触发器程序，当运行表发生某些操作(如新增、修改和删除)时，执行一项特定的任务(比如将变化信息记录到某个指定的数据表或文件中)，这样就可以实时获取数据变化。尽管触发器程序功能强大，但缺点也非常明显：首先触发器程序是伴随数据变化操作实时发生的，因此每一次数据操作都会额外执行触发器程序，极大地加重了数据库服务器的负担，将大大降低数据库的性能，这对于大数据量环境是无法容忍的；二是触发器程序并不是通用标准，不同数据库的触发器程序编写格式各不相同；三是触发器程序编写具有较高难度，容易出现BUG从而影响正常的数据存储操作导致系统不稳定甚至崩溃。因此触发器程序只适用于小数据量的场景并且不具有通用性。

综上所述，目前常用的技术手段和方法都不能很好地支持快速定位运行表和备份表的差异数据，特别是在大数据量环境下，因此需要从方法上重新设计。

发明内容

本发明的目的在于克服现有技术的不足，提供一种可以在运行表和备份表中快速高效地定位那些存在差异的数据记录项，并输出数据比对的结果，并且对数据库的性能压力较小的面向教育行业的多尺度渐进式差异数据定位方法。

本发明的目的是通过以下技术方案来实现的：一种面向教育行业的多尺度渐进式差异数据定位方法，包括以下步骤：

S1、数据排序：将运行表TR和备份表TB按照主键值大小进行排序，TR的主键记为KR，TB的主键记为KB；

S2、计算起始主键值KStart和终止主键值KEnd；

S3、对主键值数据范围[KStart，KEnd]进行尺度划分；尺度大小的选择按照以下公式确定：

其中符号

利用选择的尺度对[KStart，KEnd]进行划分，第i个分组G

G

i≥1；

S4、根据尺度大小对分组G

S4.1、如果KStart

S4.2、如果KStart

S5、对[KStart，KEnd]的所有分组都执行步骤S4的操作，得到TR和TB中的所有差异数据项。

步骤S2具体实现方法为：

S2.1、计算KR的最小值min(KR)；

S2.2、计算KB的最小值min(KB)；

S2.3、计算KR的最大值max(KR)；

S2.4、计算KB的最大值max(KB)；

S2.5、计算起始主键值KStart＝min(min(KR)，min(KB))；

S2.6、计算终止主键值KEnd＝ max(max(KR)，max(KB))。

步骤S4.1具体实现方法为：

S4.1.1在TR中查询数据记录，查询条件为：KR∈[KStart

S4.1.2、在TB中查询主键值范围在[KStart

S4.1.3、对DataSetR

如果hash(DataSetR

如果hash(DataSetR

步骤S4.2具体实现方法为：

S4.2.1、在TR中查询数据记录，查询条件为：KR＝K，对应SQL语句为：Select*fromTR where KR＝K，查询结果记为DataR

S4.2.2、在TB中查询数据记录，查询条件为：KB＝K，对应SQL语句为：Select*fromTB where KB＝K，查询结果记为DataB

S4.2.3、比较DataR

如果DataR

如果DataR

如果DataR

如果DataR

本发明的有益效果是：本发明可以在运行表和备份表中快速高效地定位那些存在差异的数据记录项，并输出数据比对的结果。并且本方法支持任何通用的关系型数据库，对数据库的性能压力也较小，从而解决了传统数据对比方法的各种缺陷。

附图说明

图1为本发明的多尺度渐进式的数据比对方法的流程图。

具体实施方式

对本发明出现的词汇进行如下定义：

数据划分：可以将某个数据集中的所有数据进行分组，设分组数量为n，各个分组记为G

(1)G

(2)对任意序号i≠j，都有

满足上述情况的分组方式就称为U的一个划分，比如按主键值划分为奇数组和偶数组，或者按性别分为男和女等。

数据的尺度：本发明涉及的数据尺度定义是度量数据分组G

如果把某个数据分组G

多尺度渐进就是指通过调整划分的尺度，逐步逼近那些具有某些特征的数据记录，而划分里面那些不满足条件的大尺度分组可以整体淘汰，这样就大大提升了数据匹配和对比的效率。

数据的哈希(Hash)运算：通过哈希函数将一条或多条数据记录映射为具有相等长度的信息摘要。理想的哈希运算的要求是：

(1)无论原始数据r的大小，hash运算快速且运算结果的长度相等。

(2)如果2条数据记录r

(3)如果r

对于任意哈希函数，(1)和(2)是必须满足的，但(3)仅在理想状态下满足，也就是r

哈希函数的算法过程可以是自主设计的，也可以直接使用已知公开的算法，本发明推荐使用MD5摘要算法，它具有运算速度快，冲突概率低(低于2

在一些极限情况下，需要以极大概率保证哈希运算的可靠性，可以使用双重哈希的方式，也就是使用2种不同的哈希算法进行数据比较，如果有：hash1(r1)＝hash1(r2)并且hash2(r1)＝hash2（r2），此时发生冲突的概率降至冲突概率1×冲突概率2，可以认为是非常可靠的哈希运算，完全可以认为此时r1＝r2成立。

使用hash运算的原因是一条或多条数据记录在比较时，可以避免逐行逐列地依次比较各个数据项，只需要整体比较它们的哈希值即可。

下面结合附图进一步说明本发明的技术方案。

如图1所示，本发明的一种面向教育行业的多尺度渐进式差异数据定位方法，用于在运行表和备份表中快速定位那些存在差异的数据记录项，并输出数据比对的结果。本发明的前提条件包括：

(1)运行表(记为TR)和备份表(记为TB)具有完全相同的列(字段)，包括数量和类型，以及字段的顺序；在教育信息化系统中实际使用的数据表称为运行表，例如学工系统中的学生信息表，实时记录了全部学生信息。

(2)TR和TB具有唯一主键且不会修改；

(3)TR和TB的主键类型为整数，因此可以进行排序和加减运算。

本发明的定位方法包括以下步骤：

S1、数据排序：将运行表TR和备份表TB按照主键值大小进行排序(升序或降序，若无特殊要求，一般使用升序，因为这是大多数数据库的默认排序规则)，TR的主键记为KR，TB的主键记为KB；排序的目的是方便后续计算主键值范围。

S2、计算起始主键值KStart和终止主键值KEnd；具体实现方法为：

S2.1、计算KR的最小值min(KR)；

S2.2、计算KB的最小值min(KB)；

S2.3、计算KR的最大值max(KR)；

S2.4、计算KB的最大值max(KB)；

由于数据库对主键值默认采用了索引技术，因此上述计算主键的最小值和最大值的速度非常快，经测试，千万级的数据量一般可以在0.1秒以内查询得到结果。

S2.5、计算起始主键值KStart＝min(min(KR)，min(KB))；

S2.6、计算终止主键值KEnd＝max(max(KR)，max(KB))。

即：起始主键值KStart等于KR和KB的最小主键值，终止主键值KEnd等于KR和KB的最大主键值。

S3、对主键值数据范围[KStart，KEnd]进行尺度划分；尺度大小的选择与数据范围(即KEnd-KStart)值大小有关，可以按照以下公式确定：

其中符号

可以根据实际情况适当调整n的值，过大的n得到的尺度值较小，使得分组数过多，数据比对次数增多而导致效率下降；过小的n得到较大的尺度值，使得每个分组的范围较大，包含差异数据的概率增大，从而引发组内新一轮的划分比对过程。一般来说，p可取当前计算机CPU的核心数，以便支持多线程并发计算，提高运算效率。

利用选择的尺度对[KStart，KKnd]进行划分，第i个分组G

G

i≥1；该公式符合划分的定义且保证了上限值不会超过KEnd，从而避免无效的数据搜索范围。

S4、根据尺度大小对分组G

S4.1、如果KStart

S4.1.1在TR中查询数据记录，查询条件为：KR∈[KStart

S4.1.2、在TB中查询主键值范围在[KStart

S4.1.3、对DataSetR

如果hash(DataSetR

如果hash(DataSetR

S4.2、如果KStart

S4.2.1、在TR中查询数据记录，查询条件为：KR＝K，对应SQL语句为：Select*fromTR where KR＝K，查询结果记为DataR

S4.2.2、在TB中查询数据记录，查询条件为：KB＝K，对应SQL语句为：Select*fromTB where KB＝K，查询结果记为DataB

S4.2.3、比较DataR

如果DataR

如果DataR

如果DataR

如果DataR

S5、对[KStart，KEnd]的所有分组都执行步骤S4的判断操作，得到TR和TB中的所有差异数据项。

本发明涉及的方法和步骤适用于较大数据量以上(10万以上)，且差异数据量<＝20％的情况。较多的差异数据可能引发较多的渐进划分对比，效率会有所下降。经测试，千万级数据量(5万条差异数据)可以在2分钟以内完成查找。

本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。本领域的普通技术人员可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各种具体变形和组合，这些变形和组合仍然在本发明的保护范围内。