数据质量是数据管理中最重要的问题之一^[1].数据质量的一个重要内容是不一致性检测.不一致数据普遍存在却并非显而易见的,使用不一致数据可能导致错误的决策,甚至会付出昂贵的代价.

在实际应用中,为提高数据质量,通常需要找出不一致数据,也就是对数据进行不一致性检测.对一个集中式数据库来说,不一致性检测较为容易,如对集中式数据库进行函数依赖冲突检测,可以使用一种基于SQL技术的检测方法^[2].然而在现实中,一个关系表的数据可能被切分,并分布在不同的站点上^[2].

例1:考虑如下一个关系表STUDENT(id,SNo,SName,Dept,CNo,CName,CGrade,Instr,Office),每一个学生元组包含了学号、姓名、院系、课程编号、课程名称、课程成绩、任课教师、办公室编号等内容.这里,ID是关系表STUDENT的主键,STUDENT的一个实例D₀见表 1.

为了检测不一致性,在关系表STUDENT上定义了如下几个FD作为数据质量规则:

· φ₁:SNo→SName

· φ₂:CNo→CName

· φ₃:CNo,SNo→Instr

· φ₄:Instr→Office

这里,φ₁声明了学号唯一决定学生姓名,φ₂声明了课程编号唯一决定课程名称,φ₃表示课程编号和学号唯一确定任课教师,φ₄表示任课教师唯一确定办公室编号.

假定想要找到D₀中不一致的数据,即D₀中至少违反一个函数依赖的元组.这里,用t_i表示D₀中id为i的元组,则在D₀中存在冲突的元组有t₁,t₂,t₄,t₅,t₆,t₈,t₉,t₁₀.具体来说,元组t₄和t₆违反函数依赖φ₂:元组t₄和t₆课程编号相同,课程名称不同.与此类似,元组t₅和t₉违反函数依赖φ₂.

在集中式数据库中,要检测D₀中存在的冲突元组,可以使用基于SQL的技术.对于每一个函数依赖,编写一套相应的SQL语句,在数据库中执行该语句,即可检测违反该函数依赖的元组^[2].而如果D₀被水平或者垂直切分,各数据块分布在不同的站点.这种检测方法无法直接使用,通常需要进行数据迁移.

考虑前面提到的表 1,其数据被水平切分成3部分,分别见表 2~表 4,其中,分片${D_{{H_1}}},{D_{{H_2}}},{D_{{H_3}}}$分别分布在站点S₁,S₂和S₃上.为检测元组违反函数依赖φ₂的情况,需要进行数据迁移.数据迁移的原则是,函数依赖左端属性值相同的元组迁移到相同的节点.迁移的方案有多种:(a) 从站点S₃迁移元组t₉和t₁₀到S₁,从站点S₃迁移元组t₄到S₂,从站点S₁迁移元组t₈到S₂;(b) 从站点S₁迁移元组t₂和t₅到S₃,从站点S₃迁移元组t₄到S₂,从站点S₁迁移元组t₈到S₂;等等.可以看出:与集中式环境不同,在分布式环境下,不一致检测通常需要数据迁移,因此,集中式环境下的检测方法不适用于分布式环境下的不一致性检测.

已有的关于分布式环境下完整性约束的研究主要关注条件函数依赖(conditional functional dependency,简称CFD)的冲突检测,如Fan提出了一种分布式环境下检测条件函数依赖的方法^[2],该检测方法主要是基于模式表(pattern tableau).与条件函数依赖不同,函数依赖由于缺乏可以利用的模式表,无法利用该技术进行不一致性检测,因此,该技术不适合分布式环境下函数依赖的不一致性检测.其他关于分布式环境下完整性约束的研究主要集中于定义在系统状态上的约束^[3]或者是约束可以在本地进行验证的情况^{[4, 5]}.

本文的主要贡献如下:

(1) 给出了分布式环境下单个函数依赖不一致性检测响应时间代价模型,基于该模型,将最小化响应时间问题划归为整数规划问题.由于分布式环境不一致性检测任务分配问题为NP-难问题,无法在多项式时间得到最优解,本文基于该模型给出了3/2-近似最优检测任务分配算法.

(2) 研究了多个函数依赖进行批量检测的问题,总结了可以进行批量检测的多个函数依赖的特征,并给出了分布式环境下多个函数依赖批量并行检测的算法.

(3) 基于真实和人工数据集,通过实验验证了本文提出的单个函数依赖不一致性检测算法和多个函数依赖批量检测算法,并进行了对比分析.

本文使用真实及人工大数据集,基于Hadoop平台对提出的检测方法进行了性能检测,并与传统的集中式方法和基于Hadoop的Naïve方法进行了比较.实验结果表明:本文的方法在数据规模和分片数量方面扩展性良好,在减少响应时间和数据迁移方面效果明显.

1 预备知识 1.1 函数依赖

函数依赖可以看作是定义在关系上的完整性约束.假定R是一个关系模式,在其上定义了一个函数依赖集合,Attrs(R)={A₁,A₂,…,A_m}定义了R上的属性集合,R上的每一个属性A∈Attrs(R)的域用Dom(A)表示.R的一个实例I是一个元组的集合,其中每一个元组属于Dom(A₁)x…xDom(A_m).这里,用t[A]表示元组t的属性A的值,用t[L]表示Attrs(R)中一组属性L在t上的投影.

定义1. 函数依赖(简称FD)是定义在关系R上的形如X→Y的表达式,这里,X,Y是Attrs(R)上的属性集合.函数依赖X→Y在关系R上成立,当且仅当对R的每一个实例,如果R中的任意两个元组有着相同的X属性值,则必然有着相同的Y属性值.一个函数依赖X→Y是平凡的,如果Y是X的一个子集.平凡函数依赖对所有的关系实例都成立.如果一个函数依赖满足Y∩X=∅,则这个函数依赖是非平凡的.

对于函数依赖φ:X→Y,X是φ的左侧(left hand side,简称LHS),而Y是φ的右侧(right hand side,简称RHS).由于平凡函数依赖对所有关系实例都成立,本文中仅考虑非平凡函数依赖的不一致性检测问题.

1.2 函数依赖冲突

函数依赖作为完整性约束的一种,其冲突意味着违反了完整性约束.函数依赖冲突在现实中普遍存在,特别是在数据集成、数据融合以及Web数据抽取等应用中更为常见.

给定关系R的一个实例D,函数依赖φ:A→B,将D上违反φ的冲突表示为Viot(φ,D).对于D中的每一个元组t,如果存在一个元组t'满足t(A)=t'(A)且t(B)¹t'(B),说明元组t和t'违反了函数依赖φ,因此有t∈Viot(φ,D).假定S为定义在D上的函数依赖的集合,则Viot(S,D)表示D上的所有违反S中函数依赖的冲突.用符号Viot^P(φ,D)表示P_AViot(φ,D),这里,P_AViot(φ,D)是Viot(φ,D)在属性A上的投影,R中其他元素值用空值null表示.与Viot(φ,D)相比,Viot^P(φ,D)包含数据更少.

一个关系R的任一水平分片与R有着相同的模式,因此,如果函数依赖φ是定义在R的实例D上面的,则φ同样也是定义在D的各个分片上的.这里,将D的任一水平分片D_i上违反φ的冲突定义为Viot(φ,D_i).

1.3 函数依赖冲突检测

给定关系R的实例D,D水平切分为(D₁,…,D_n).假定D的每一个切分分布在一个单独的节点上,对于i∈[1,n],D_i分布在节点S_i上.函数依赖φ是定义在R上的一个函数依赖,函数依赖φ的冲突检测问题是查找Viot^P(φ,D).给定函数依赖φ,φ可以在本地检测当且仅当满足$Vio{t^\Pi }(\varphi ,D) = \bigcup olimits_{i \in [1,n]} {Vio{t^\Pi }(\varphi ,{D_i})} .$

具有最小响应时间的函数依赖不一致性检测问题,其输入是一个函数依赖的集合S和水平切分的关系R的实例D,响应时间满足以下条件:(a) 集合S中的函数依赖在数据迁移U之后可以本地检测;(b) 响应时间RT是最小的.然而找到一个最小响应时间的检测算法是不现实的,在水平切分情况下,具有最小响应时间的函数依赖不一致性检测问题是一个NP-难问题^[4].

2 分布式大数据不一致性检测

这一节探讨分布式环境下水平切分的关系数据不一致性检测问题.与集中式数据相比,分布式环境下函数依赖不一致性检测更具挑战性,通常需要进行数据的迁移.在进行不一致检测时,需要确定哪些元组需要迁移以及迁移到哪个节点.对于单个函数依赖来说,该问题是已经是非平凡的.根据前面的介绍,找出一个具有最小响应时间的检测算法是NP-难的.

2.1 单个函数依赖冲突检测

· 算法CetDetect.

首先,选择一个节点S_j作为函数依赖φ的执行节点,其他节点上的元组都迁移到节点S_j;最后,函数依赖φ的冲突检测可以在节点S_j进行.这里选择元组数量分布最多的节点作为执行节点,可以减少数据迁移量及通信代价.算法CetDetect中,每个元组最多迁移一次.由于该算法将所有数据迁移到一个节点,在该节点进行不一致性检测,在数据规模特别大时,大量数据迁移到一个节点,检测任务由一个节点承担,导致负载严重不均衡,该节点很容易成为检测的瓶颈.

· 算法SingleFdDet_RT.

算法SingleFdDet_RT进行分布式环境大数据不一致检测时,分为以下几个步骤:(a) 数据预处理;(b) 任务分配;(c) 数据迁移;(d) 不一致性检测.

给定关系R的实例D,D水平切分为(D₁,…,D_n).假定D的每一个切分分布在一个单独的节点上,对于∀i∈[1,n],D_i分布在节点S_i上.对任一节点S_i,i∈[1,n],算法首先对其上的数据D_i进行预处理,假定其数据预处理时间为predeal(D_i).为保证不一致检测的准确性,预处理后的数据需要进行数据的迁移,也就是不一致性检测任务的分配.假定任一节点S_i迁入的数据为DD_i-in,迁出的数据为DD_i-out,则总的数据迁移量为

${\rm{\Delta }}D = \sum\limits_{i \in [1,n]} {{\rm{\Delta }}{D_{i{\rm{ - }}in}}} = \sum\limits_{i \in [1,n]} {{\rm{\Delta }}{D_{i{\rm{ - }}out}}} .$

也就是说,在数据迁移过程中,各节点总的迁入数据量与总的迁出数据量相同.假定对任一节点S_i,i∈[1,n], 完成数据迁移后,其数据规模为${D'_i}$,则有${D'_i} = {D_i} + {\rm{\Delta }}{D_{i{\rm{ - }}in}} + {\rm{\Delta }}{D_{i{\rm{ - }}out}}$.假定函数依赖φ不一致性检测总的响应时间为cost_RT(φ),这里定义不一致性检测响应时间代价模型如下:

$cos{t_{RT}}(\varphi ) = \mathop {\max }\limits_{i \in [1,n]} predeal({D_i}) + \frac{1}{{bw}}\sum\limits_{i \in [1,n]} {{\rm{\Delta }}{D_{i{\rm{ - }}out}}} + \mathop {\max }\limits_{i \in [1,n]} check({D'_i})$

(1)

其中,predeal(D_i)为各节点数据预处理耗时,n为节点个数,bw为网络带宽,φ为待检测的函数依赖.

依据公式(1),函数依赖不一致性检测的响应时间取决于3部分:各节点数据预处理的最大耗时$\mathop {\max }\limits_{i \in [1,n]} predeal({D_i})$、数据迁移耗时$\frac{1}{{bw}}\sum\limits_{i \in [1,n]} {{\rm{\Delta }}{D_{i{\rm{ - }}out}}} $以及数据重分布后各节点最大检测耗时$\mathop {\max }\limits_{i \in [1,n]} check({D'_i})$.要想减少总的响应时间cost_RT(φ),就要考虑对以上几个阶段的响应时间进行优化.

不一致性检测的第1步是数据的预处理.数据预处理的主要目的是消除与待检测函数依赖属性值相关的冗余数据,其好处有两个方面:一是可以减少数据迁移量,特别是在冗余数据比较多的情况;二是可以提高检测效率.预处理一方面消除了冗余数据,另一方面,预处理后的数据更有利于不一致性检测.

定义2. 关系r上基于函数依赖X→Y的属性集X∪Y将r中所有元组划分成不同的等价类,称为r在X∪Y上的一个划分,用P_X∪Y表示.等价类划分的原则是同一个等价类内有着相同的X属性值,且去除冗余.

在数据预处理阶段,首先在各个节点并行扫描一遍本地数据,依据定义2,将本地元组进行等价类的划分.进一步将划分好的等价类表示成键值对<key,value>的形式,用P_<X,Y>表示,其中,以每个等价类中X属性值为key,Y的不同属性值集合为value.这种键值对的表示形式对X和Y属性值是相同的,仅保留一组值,因此可以有效去除各个节点的冗余数据.经过预处理后的数据由于去除了冗余数据,因此可以减少数据迁移量和检测的工作量.以表 2为例,对函数依赖φ₂,根据定义2,可以得到关系r在数据片段${D_{{H_2}}}$上的属性集合CNo∪CName上的一个划分为

P_CNo∪CName={{(202,Ecology)},{(301,Geometry)},{(101,Economics)}}.

用键值对表示为

P_<CNo,CName>={<202,[Ecology]>,<301,[Geometry]>,<101,[Economics]>}.

对于各个节点得到的局部数据等价类,为并行检测函数依赖不一致性,需要进行数据迁移.这里使用哈希函数计算每个等价类的哈希值,哈希函数的输入为函数依赖LHS属性值.根据定义2,同一等价类内的函数依赖LHS属性值相同,因此其哈希值也相同.也就是说,每一个等价类有唯一的哈希值.然后,将具有相同哈希值的等价类迁移到同一个执行节点,并进行等价类的合并.等价类合并过程中消除了全局的冗余数据,因此可以减少不一致性检测要处理的数据规模,提高检测效率.各个执行节点得到合并后的等价类后,根据同一等价类中包含的元组个数进行不一致性检测:如果等价类中元组个数为1,说明不存在违反函数依赖的情况;如果等价类中元组个数大于1,说明存在违反函数依赖的情况.

完成以上的数据等价类合并工作,得到初步预处理数据,下一步考虑在各个节点对得到的初步预处理数据进行分片.数据分片的目的是为了便于接下来的并行检测.数据分片的原则是,存在潜在冲突的元组数据分配到相同的分片内,这样可以保证不一致检测结果的准确性.

本文考虑利用散列函数对各节点初步预处理过的数据进行分片,假定每个节点上的预处理数据根据散列函数m散列为m片,将预处理得到的键值对的key作为散列函数m的输入,可以将key转换为0到m-1的整数值.

根据各个键值对散列值的不同,散列函数将D的任一切分D_i分成m片,分别为$H_i^1,...,H_i^m$.对∀k∈[1,m],$H_i^k$内的键值对有着相同的散列值.这样可以将D分成m片,片内的键值对有着相同的散列值,如图 1所示.

图 1中,H¹为散列值为0的键值对组成的块,H²为散列值为1的键值对组成的块,以此类推.对∀φ∈[1,m],有:

${H^j} = H_1^j \cup ... \cup H_n^j.$

这里考虑分片大小m的取值问题.m取值的大小会影响数据分配时的负载均衡,m取值越小,则分片的粒度越大;m取值越大,则分片的粒度越小.如果m<n,说明分片数量<节点数量,在进行任务分配时,会出现有些节点没有负载,而有些节点的负载较大的情况.如果分片过多,理论上有利于负载分配更加均衡,但是进行负载分配也需要耗时.为提高不一致性检测的并行度,使得每个节点都不会因为没有分配检测任务而空闲,本文中散列分片数量不少于节点个数,即m≥n.

在得到散列及合并后的数据分片H¹,…,H^m后,为对数据分片执行不一致性检测,需要将数据片分配到执行节点,接下来考虑m个数据片的任务分配情况,该问题为多处理机调度问题.

问题1(多处理机调度问题). 任给有穷的任务集A,每一个任务a∈A的响应时间为t(a)∈Ζ⁺,处理机数目为n∈Ζ⁺,任务截止时间为D∈Ζ⁺,其中,Ζ⁺为正整数集合.判定:

是否能将任务集A划分成n个不相交的集合A=A₁∪…∪A_n,使得:$\max \left\{ {\sum\limits_{a \in {A_i}} {t(a):1 \le i \le n} } \right\} \le D$.

定理1. 多处理机调度问题为NP-完全问题^[6].

证明:利用限制法证明.考虑该问题的一种特例,当m=2且$D = \left[ {\frac{1}{2}\sum\limits_{a \in A} {t(a)} } \right]$时,该问题可以限制成划分问题.由文献^[6]知,划分问题为NP-完全问题.因此,多处理机调度问题为NP-完全问题.

本文中需要检测的数据块为m个,节点个数为n个,对每个i=1,2,…,m和每个φ=1,2,…,n,第i个数据块在第φ个节点上检测耗时为t_ij.依据不一致性检测响应时间代价模型cost_RT(φ),要想减少总的响应时间,应当最小化数据迁移时间$\frac{1}{{bw}}\sum\limits_{j \in [1,n]} {{\rm{\Delta }}{D_{j{\rm{ - }}out}}} $和不一致性检测时间$\mathop {\max }\limits_{j \in [1,n]} check({D'_j})$.也就是在对所有待检测数据块进行任务分配后,数据迁移耗时与最后检测完成的节点耗时之和最小.这里,用x_ij表示在第φ个节点上处理第i个数据块,则当第i个数据块分配给第φ个节点时,x_ij=1;否则,x_ij=0.该问题可以转化为整数规划问题:

· 目标函数:

$\min {\rm{ }}t + \frac{1}{{bw}}\sum\limits_{j = 1}^n {{\rm{\Delta }}{D_{j{\rm{ - }}out}}} .$

· 约束条件:

$\begin{align} & \sum\limits_{j=1}^{n}{{{x}_{ij}}}=1,\text{ }1\le i\le m; \\ & \text{ }\forall j\in [1,n],\text{ }t\ge \sum\limits_{i=1}^{m}{{{x}_{ij}}{{t}_{ij}}}; \\ & \text{ }\forall j\in [1,n],\text{ }\!\!\Delta\!\!\text{ }{{D}_{j\text{-}out}}={{D}_{j}}-\sum\limits_{i=1}^{m}{{{x}_{ij}}H_{j}^{i}},\text{ }1\le i\le m; \\ & \text{ }{{x}_{ij}}\in \{0,1\},\text{ }1\le i\le m,\text{ }1\le j\le n. \\ \end{align}$

可以将上述整数规划问题关于x_ij的约束进行松弛,松弛后的约束条件为0≤x_ij≤1,1≤i≤m,1≤φ≤n.这样,可以将上述整数规划问题松弛为线性规划问题.

由于该问题为NP-完全问题,在多项式时间内难以得到问题的精确解,本文给出一种近似最优的综合考虑数据迁移量与负载均衡的算法.

算法1. Sorted-LoadBalance.

Input:机器集合M={M_i},i∈[1,n];任务集合A={A₁,…,A_m}.

Output: A(1),A(2),…,A(n).

1. for each i∈[1,n] do

2. T_i=0,A_i={};

3. end for;

4. Desc(A); //依据A中任务耗时t_j的大小对A中任务降序排列

5. 假定t₁≥t₂≥…≥t_m;

6. for each φ∈[1,m] do

7. if机器M_i任务耗时达到最小值

8. if $|H_{i}^{k}|\ge |H_{l}^{k}|$,i,l∈[1,n]且i¹l,任务φ对应的数据块为H^k

9. 将任务φ分配给机器M_i;

10. end if;

11. A(i)←A(i)∪φ;

12. T_i←T_i+t_j;

13. end if;

14. end for.

引理1. 给定包含m个任务的集合A={A₁,…,A_m},n个机器节点,T为响应时间最优值,t_j为任务A_j的响应时间,φ∈[1,m],则有:T≥$\frac{1}{n}\sum\limits_{j=1}^{m}{{{t}_{j}}}$.

证明:m个任务的总的处理时间为$\sum\limits_{j=1}^{m}{{{t}_{j}}},$由于n个机器节点中至少有一个机器节点处理的任务量不少于总任务量的$\frac{1}{n}$,因此,该机器节点的响应时间≥$\frac{1}{n}\sum\limits_{j=1}^{m}{{{t}_{j}}};$而T为所有机器节点响应时间的最大值,因此有T≥$\frac{1}{n}\sum\limits_{j=1}^{m}{{{t}_{j}}}.$

引理2. 给定包含m个任务的集合A={A₁,…,A_m},n个机器节点,T为响应时间最优值,t_j为任务A_j的响应时间,φ∈[1,m],如果m>n,则有T≥2t_n+1.

证明:对于根据执行时间大小降序排序后的任务序列,其前n+1个任务中,每一个需要的响应时间至少为t_n+1.任务个数为n+1个,而机器节点个数为n个,根据鸽笼原理,必然有一个机器节点分得的任务个数为2个,因此,该节点的响应时间≥2t_n+1;而T为所有机器节点响应时间的最大值,因此有T≥2t_n+1.

定理2. 当m>n时,算法Sorted-LoadBalance的响应时间T≤$\frac{3}{2}$T^*[7].

证明:并行执行多个任务时,如果负载最大的机器M_i的负载为一个任务,则调度是最优的.假定节点S_i负载至少为2个任务,设t_j为分配给S_i的最后一个任务的响应时间,这里,φ≥n+1.因为前n个任务分配给不同的节点,由引理2,

${{t}_{j}}\le {{t}_{n}}_{+1}\le \frac{1}{2}{{T}^{*}}$

(2)

在将响应时间为t_j的任务分配给节点S_i之前,S_i的负载是所有节点里最小的,此时,S_i的负载响应时间为T_i-t_j,其中,T_i为在将响应时间为t_j的任务分配给节点S_i之后,S_i的所有负载的响应时间.因此,所有节点负载的响应时间均≥T_i-t_j.所有节点的负载响应时间相加得到$\sum\limits_{k=1}^{n}{{{T}_{k}}}\ge n({{T}_{i}}-{{t}_{j}}),$进一步得到T_i-t_j≤$\frac{1}{n}\sum\limits_{k=1}^{n}{{{T}_{k}}}.$

由于所有节点负载的任务响应时间之和与全体任务的响应时间之和相等,因此有:$\sum\limits_{k=1}^{n}{{{T}_{k}}}=\sum\limits_{j=1}^{m}{{{t}_{j}}}.$由引理1,

${{\tilde{T}}_{i}}{{t}_{j}}\le T*$

(3)

公式(2)和公式(3)相加,可得:T_j≤$\frac{3}{2}$T.

引理3. 给定函数依赖φ,哈希函数m,${{D}_{i}}=\bigcup olimits_{j\in [1,n]}{H_{i}^{j}}$,则有$Vio{{t}^{\Pi }}(\varphi ,D)=\bigcup olimits_{j\in [1,n]}{Vio{{t}^{\Pi }}(\varphi ,\bigcup olimits_{i\in [1,n]}{H_{i}^{j}})}$.

根据该引理,为计算Viot^P(φ,D),可以通过为任一数据块H^j,φ∈[1,n],选择一个执行节点S_j,在该节点上计算$Vio{{t}^{\Pi }}(\varphi ,\bigcup olimits_{i\in [1,n]}{H_{i}^{j}})$,即可得到函数依赖φ的所有冲突元组.算法SingleFdDet_RT就是基于这种思想.

算法SingleFdDet_RT如算法2所示.

算法2. SingleFdDet_RT.

Input: Functional Dependency φ:X→Y; D=(D₁,…,D_n).

Output: Viot^P(φ,D).

/* 在任一节点S_i,并行执行以下程序: */

1. D_i-pd←predeal(D_i); //数据预处理

2. for each k∈[1,m] do

3. for each <key,[value]>∈D_i-pddo

4. if m(key)==k-1 //m(key)为散列函数

5. $H_{i}^{k}\leftarrow H_{i}^{k}\cup \langle key,[value]\rangle $;

6. end for;

7. ${{H}^{k}}\leftarrow {{H}^{k}}\cup H_{i}^{k}$;

8. end for;

9. H←{H¹,…,H^m};

10. H'←Desc(H); //依据数据规模大小降序排列

11. 假定H'={H¹',…,H^m'},其中,|H¹'|≥…≥|H^m'|

12. for each φ∈[1,m] do

13. if H'¹{}

14. if 节点S_i分配任务最少

15. A(i)←A(i)∪H^j'; //A(i)为S_i负载

16. H'←H'\H^j';

17. end if;

18. end if;

19. end for;

20. return $Vio{{t}^{\Pi }}((X\to Y),\bigcup olimits_{i\in [1,n]}{A(i)}).$

根据函数依赖的定义,对函数依赖X→Y,当出现多个元组X属性值相同、Y属性值不同的情况,表明函数依赖冲突存在.在算法2中,经过散列和数据迁移后,任一执行节点上的数据块内的元组有着相同的散列值.由于散列函数本身是稳定的,同一散列函数,相同的输入,其输出也是相同的,因此对于有着相同X属性值的元组来说,其散列后的值是相同的.因此在算法2中,有着相同X属性值的元组会被迁移到相同的节点,这保证了算法结果的正确性.

2.2 多个函数依赖的检测算法

下面给出分布式环境下检测水平切分数据多个函数依赖冲突的算法.

· 算法SuccDetect

该算法检测多个函数依赖的冲突时,顺序对多个函数依赖中的每一个函数依赖进行检测,对单个函数依赖进行检测的时候,使用前面提到的算法SingleFdDet_RT.算法SuccDetect对多个函数依赖不一致性进行检测的时候,采用流水线处理方式,在检测完一个函数依赖的不一致性之后,接着检测下一个函数依赖的不一致性,直到所有函数依赖全部检测完为止.

算法SuccDetect在对多个函数依赖不一致性进行检测的时候,会产生过多的网络负载:检测每一个函数依赖不一致性的时候,通常都要进行数据迁移,同一个元组,在检测不同的函数依赖不一致性的时候可能会被多次迁移,这样就产生了较多的负载.由于对每个函数依赖进行检测的时候都要对全部数据扫描一遍,而数据的扫描是十分耗时的,特别是在数据量比较大的情况下,因此算法SuccDetect的响应时间比较长.

函数依赖冲突检测是一个耗时的工作,特别是大数据的背景下,扫描数据的时间开销比较大,如果能够一次扫描数据库,实现对多个函数依赖不一致性的检测,则可以有效提高检测效率.算法MultiFdDet_RT可以对多个函数依赖冲突进行批量检测,检测时只需扫描一次数据库.

· 算法MultiFdDet_RT

该算法利用输入的多个函数依赖的LHS部分的结构特点,通过对数据的一次扫描,实现对多个函数依赖不一致性的批量检测,可以有效减少函数依赖不一致性检测的响应时间.

定义2. 关系r上基于LHS(φ₁)∩…∩LHS(φ_n)不为空的函数依赖集合F={φ₁,φ₂,…,φ_n}的属性集Attr(F)= LHS(φ₁)∪…∪LHS(φ_n)∪RHS(φ₁)∪… ∪RHS(φ_n)将r中所有元组分成不同的等价类,称为r在Attr(F)上的一个划分,用P_Attr(F)表示.等价类划分的原则是同一个等价类内有着相同的LHS(φ₁)∩…∩LHS(φ_n)属性值,且去除冗余.

算法MultiFdDet_RT首先依据定义2并行地对各个节点的数据进行等价类划分,进一步将划分好的等价类转换成<key,value>键值对的形式,key值为LHS(φ₁)∩…∩LHS(j_n)属性值,value为Attr(F)\LHS(φ₁)∩…∩LHS(j_n)去重后的属性值.进行数据重分布时,以键值对的key值为散列函数的输入,每一个键值对对应一个散列值,然后,将有着相同散列值的键值对迁移到同一个执行节点.由于有着相同散列值的键值对包含了所有的潜在违反多个FD的情况,因此可以在各个节点并行进行多个函数依赖的不一致性检测.

与直接散列相比,先进行等价类的划分,再进行数据迁移和不一致性检测,其优势在于:

1) 有效消除冗余数据,减少数据迁移量;

2) 冗余数据的消除可以减少数据迁移时间,同时将潜在冲突的元组划分到相同的等价类,可以减少不一致性检测的响应时间;

3) 冗余数据的消除可以减少不一致检测时的数据规模,提高检测效率;

4) 一个等价类内的元组仅需散列一次,无需每个元组单独散列一次,可以减少总的散列时间.

数据预处理后,在各个节点以键值对的key值为散列函数的输入计算其散列值,将key值转换为0~m1的整数值.与算法SingleFdDet_RT类似,根据各个键值对的key值对应散列值的不同,散列函数将D的任一切分D_i分成m块,分别为$H_{i}^{1},...,H_{i}^{m}$.对∀k∈[1,m],$H_{i}^{k}$内的元组有着相同的散列值,这样可以将D分成m块,每一块内的元组有着相同的散列值.算法MultiFdDet_RT如算法3所示.

算法3. MultiFdDet_RT.

Input:函数依赖集合S={φ₁,…,φ_n};D=(D₁,…,D_n).

Output:Viot^P(φ₁,D),Viot^P(φ₂,D),…,Viot^P(φ_n,D).

1. Compute s(S); //计算S中函数依赖LHS部分交集

/* 在任一节点S_i,并行执行以下程序: */

2. D_i-pd←predeal(D_i); //数据预处理

3. for each k∈[1,m] do

4. for each <key,[value]>∈D_i-pd do

5. if m(key)==k1 //m(key)为散列函数

6. $H_{i}^{k}\leftarrow H_{i}^{k}\cup \langle key,[value]\rangle $;

7. end for;

8. ${{H}^{k}}\leftarrow {{H}^{k}}\cup H_{i}^{k}$;

9. end for;

10. H←{H¹,…,H^m};

11. H'←Desc(H); //依据数据规模大小降序排列

12. 假定H'={H¹',…,H^m'},其中,|H¹'|≥…≥|H^m'|

13. for each φ∈[1,m] do

14. if H'¹{}

15. if 节点S_i分配任务最少

16. A(i)←A(i)∪H^j'; //A(i)为S_i负载

17. H'←H'\H^j';

18. end if;

19. end if;

20. end for;

21. return $Vio{{t}^{\Pi }}({{\varphi }_{1}},\bigcup olimits_{i\in [1,n]}{A(i)}),Vio{{t}^{\Pi }}({{\varphi }_{2}},\bigcup olimits_{i\in [1,n]}{A(i)}),...,Vio{{t}^{\Pi }}({{\varphi }_{n}},\bigcup olimits_{i\in [1,n]}{A(i)})$.

显然,LHS(φ₁)∩…∩LHS(j_n)为LHS(φ₁),…,LHS(j_n)的子集.根据散列函数的定义,有着相同s(S)属性值的元组被散列到相同的数据块.对于∀i∈[1,n],D中有着相同LHS(j_i)属性值的元组是有着相同s(S)属性值的元组集合的子集合.因此经过散列函数m()散列后,对集合S中所有的函数依赖,其存在潜在冲突的元组都被散列到相同的数据块中,这保证了算法MultiFdDet_RT不一致性检测结果的准确性.接下来在各个节点统计各散列子数据块的元组个数,节点之间交换统计数据,汇总后根据前面算法SingleFdDet_RT中提到的执行节点分配策略,将数据块分配到相应的执行节点,各节点并行进行数据的迁移.数据迁移完成后,函数依赖集合S中所有函数依赖存在潜在冲突的元组都被分配到相同的节点,根据引理2,对∀i∈[1,n],为计算Viot^P(j_i,D),可以通过在任一执行节点S_j计算$Vio{{t}^{\Pi }}\left( \varphi ,\bigcup olimits_{i\in [1,n]}{A(i)} \right)$最后将各执行节点的检测结果汇总得到.这样,算法MultiFdDet_RT通过一次数据遍历和一次数据迁移,实现了对分布式环境多个函数依赖的不一致性检测.

引理4. 给定关系R的一个实例D,假定存在函数依赖X→Y,X'→Y,XX',∀t_i,t_j∈D,如果t_i[X']=t_j[X']且t_i[Y]¹ t_j[Y],i¹φ,则必然有t_i[X]=t_j[X]且t_i[Y]¹t_j[Y].

证明:已知t_i[X']=t_j[X']且t_i[Y]¹t_j[Y],i¹φ.又XX',即,属性集合X为X'的真子集.对于元组t_i,t_j来说,其属性集合X'的属性值相同,去掉属性集合X'\X,剩余属性集合为X.假设t_i[X]¹t_j[X],由XX'可知,t_i[X']=t_i[X]∪t_i[X'\X],t_j[X']=t_j[X]∪t_j[X'\X].由t_i[X]¹t_j[X]可知,t_i[X]∪t_i[X'\X]¹t_j[X]∪t_j[X'\X],即t_i[X']¹t_j[X'],与已知t_i[X']=t_j[X']矛盾.故假设不成立,t_i[X]=t_j[X]成立.

算法MultiFdDet_RT在检测多个函数依赖的不一致性时,根据多个函数依赖的LHS部分以及RHS部分所包含的属性情况的不同,实现了中间计算结果的共享,可以有效减少检测的计算量,提高检测效率.前面提到,多个函数依赖不一致性检测中,散列函数的key为LHS(φ₁)∩…∩LHS(j_n)属性值,value为Attr(F)\LHS(φ₁)∩…∩ LHS(j_n)去重后的属性值.在数据迁移之后,可能存在冲突的元组都被散列到相同的节点.根据待检测多个函数依赖的LHS部分及RHS部分所包含的属性情况,检测过程中可以实现如下的中间计算结果共享:

(1) 待检测的多个函数依赖LHS部分与LHS(φ₁)∩…∩LHS(j_n)相同,则在不一致性检测过程中,所有节点在处理各元组数据时,这些函数依赖的LHS部分属性值为<key,value>键值对的key值,因此无需计算.只需根据其RHS所包含属性情况,对元组所对应的键值对的value部分进行切分,进而得到相关的属性值,合并去重后可以得到各函数依赖的冲突元组.

(2) 待检测的多个函数依赖LHS部分相同且与LHS(φ₁)∩…∩LHS(j_n)不同,检测时,多个函数依赖的LHS部分属性值的计算结果可以共享,即,只需计算一遍,无需每个FD都单独计算一遍.每个待检测FD的RHS部分可由<key,value>键值对的value部分切分得到.

(3) 待检测的多个函数依赖RHS部分相同,则根据<key,value>键值对进行计算时,RHS部分的属性值计算中间结果可以共享,无需每个FD都单独计算一遍,因此可以有效提高计算效率.

(4) 如果待检测的多个函数依赖存在LHS包含的情况,假定LHS存在包含情况的多个待检测函数依赖中LHS包含属性最多的函数依赖为φ,由引理4,违反该函数依赖的元组必然违反LHS为其子集合的其他函数依赖,故在不一致性检测时,违反φ的元组必然违反LHS部分为LHS(φ)子集合的其他函数依赖,因此对于这些函数依赖来说,违反φ的元组无需重复验证.

算法MultiFdDet_RT的前提是给定的多个函数依赖LHS部分的交集不为空.然而通常情况下,给定一个函数依赖集合S,其LHS部分不一定有公共属性,这种情况下不能直接使用算法MultiFdDet_RT.为了将算法MultiFdDet_RT应用到多个函数依赖的不一致性检测,考虑将函数依赖集合S中的多个函数依赖进行分组.分组的依据是组内的函数依赖LHS部分有公共属性,同一分组内的函数依赖可使用前面提到的批量并行检测算法MultiFdDet_RT进行不一致性检测,从而提高分布式环境下函数依赖不一致性检测的效率,同时减少网络负载.

例2:以表 1中实例D₀上定义的函数依赖集合S={φ₁,φ₂,φ₃}为例,函数依赖φ₂和φ₃的LHS部分存在公共属性CNo,而φ₁与φ₂和φ₃在LHS部分没有公共属性,因此可以将S={φ₁,φ₂,φ₃}分成两组:{φ₁}和{φ₂,φ₃},组内的函数依赖可以使用批量并行检测算法MultiFdDet_RT进行不一致性检测,有效提高检测效率.

由于对函数依赖进行不一致性检测的时候需要扫描全部数据,在大数据背景下,扫描全部数据是一个十分耗时的工作.而前面提到,算法MultiFdDet_RT在对多个函数依赖进行不一致性检测的时候只需要对全部数据进行一次扫描,因此在对函数依赖集合S中的多个函数依赖进行分组的时候,要满足组内的函数依赖LHS部分有公共元素,而且分组的个数尽可能地少,这个问题可以划归为最小集合覆盖(minimal set cover,简称MSC)问题.根据文献^[6],最小集合覆盖问题是一个NP-完全问题,不存在一个多项式时间的解,除非P=NP,但是可以在多项式时间内得到该问题的近似解.算法4是一个最小集合覆盖问题的贪心算法.

算法4. GreedyMSC.

Input:集合X={1,2,…,n};X的子集合构成的集合F=(S₁,S₂,…,S_n).

Output:X的具有最小势的集合覆盖C.

1. Initialize: C←{},U←X;

2. while U¹{} do

3. Select S where S∈F and S is a set such that |S∩U| is maximized; //S覆盖U中最多的元素

4. C←C∪{S}; //将S并入覆盖C

5. U←U\S; //从U中移除被S覆盖的所有元素

6. return C.

算法4初始化时U←X,然后逐步从U中减去新增到覆盖C中的集合中的元素,直到C包含X中全部元素为止.算法的时间复杂度主要取决于F的情况.然而,贪心算法并不总是能得到最优解.

例3:假定X={1,2,3,4,5,6,7,8,9,10},F=(S₁,S₂,…,S₅),S₁={1,2,5,7,9,10},S₂={1,2,3,4,5},S₃={3,4,8},S₄={4,6,8},S₅= {6,7,8,9,10}.贪心算法在执行的时候首先选择包含最多元素的集合S₁,剩余的集合在去掉S₁中元素后为{3,4},{3,4,8},{4,6,8},{6,8}.要想最终得到X的一个覆盖,至少还要选取S₂和S₃中的至少一个以及S₄和S₅中的至少一个.因此,最终选取的集合X的覆盖至少包含F中的3个元素.而该问题的最优解可以通过选择S₂和S₅共2个子集合得到.

为得到该问题的最优解,可以考虑将该问题表述为如下的(0-1)-规划问题:

任给集合S,S的子集合S₁,S₂,…,S_n,求解以下(0-1)-规划:

求最小值c(x)=x₁+x₂+…+x_n,

满足条件S₁xx₁∪S₂xx₂∪…∪S_nxx_n=S;x₁,x₂,…,x_n∈{0,1}.

令opt为目标函数最优值,则opt≤n.对于子集合I⊆{1,2,…,n},令S_I表示编号在I中的S的子集合的并集,${{S}_{I}}=\bigcup olimits_{k\in I}{{{S}_{k}}}$.对{i,φ},1≤i≤n,0≤φ≤n,如果存在集合I={1,2,…,n},使得$\sum olimits_{k\in I}{1}=j$且S_I=S,则令c(i,φ)为使得S_I=S的最小子集合I;否则认为c(i,φ)无定义,记为c(i,φ)=nil.根据以上定义,目标函数最优值可以表示为opt=min{φ| c(i,φ)¹nil}.要找出该(0-1)-规划问题的最优解,只需计算出所有的c(i,φ),具体的计算过程见算法5.

算法5. OptimalMSC.

Input:集合S={1,2,…,n};S₁,S₂,…,S_nS.

Output:S的具有最小势的集合覆盖C.

1. Initialize: C←{};

2. for (int i=1; i≤n; i++)

3. for (int φ=0; φ≤i; φ++)

4. if (c(i-1,φ)=nil && S_c(i-1,φ)S)

5. c(i,φ)=c(i-1,φ)+{i};

6. else if (c(i,φ)¹nil);

7. c(i,φ)=c(i-1,φ);

8. end for;

9. end for;

10. return C=min{φ|c(n,φ)¹nil}.

对于任意一个子集合I⊆{1,2,…,n},计算S_I需要时间O(n²),因此,算法5的时间复杂度为O(n⁴).该算法为一个伪多项式时间算法,如果问题的最大输入值比较大,则算法的效率会比较低.

通常情况下,得到的一个函数依赖集合的最小集合覆盖不是一个最小精确覆盖(minimum exact cover),意味着所得到的最小集合覆盖中通常存在冗余元素.假定函数依赖集合S的元素个数为n,所得到的最小集合覆盖为C=(C₁,C₂,…,C_k),则出现C中任意2个子集合有交集或者满足|C₁|+|C₂|+…+|C_k|>n,意味着C中存在S的冗余元素.冗余元素的存在,使得对多个函数依赖进行不 一致性批量检测的时候出现重复检测的问题.

为解决所得到的最小集合覆盖存在冗余元素的问题,需要对最小集合覆盖进行预处理.算法6用来去除最小集合覆盖中冗余元素.在算法6中,多个函数依赖的最小集合覆盖用包含0,1元素的矩阵M表示,矩阵的行为X中的所有元素,列为最小集合覆盖中的元素.如果矩阵的任一列值为1的元素个数大于1,则意味着在最小集合覆盖中该列所代表的元素出现了冗余.

算法6. MSCRedundantEliminate.

Input:集合X={1,2,…,n};X的最小集合覆盖C=(C₁,C₂,…,C_k).

Output:每一列元素值为1的元素个数不超过1个的矩阵M.

1. If the matrix M is empty,terminate;

2. Otherwise:

3. for (int i=0; i<|X|,i++)

4. for (int φ=0,counter=0; φ<|C|,φ++)

5. if (M_j,i==1 && counter<1)

6. counter++;

7. else if (M_j,i==1 && counter==1)

8. M_j,i=0; /*修改当前值为0*/

9. end for;

10. end for;

11. return M.

例4:给定X={1,2,3,4,5,6,7},C={A,B,C}是X的一个最小集合覆盖,其中,A={1,2,4},B={2,3,5},C={4,6,7},用矩阵表示的X的最小覆盖如图 2(a)所示.

算法6对图 2(a)的矩阵M进行扫描,发现第2列和第4列分别有2个值为1的元素,因此算法分别修改M[B]^[2]以及M[C]^[4]的值为0,修改后的矩阵如图 2(b)所示.根据图 2(b)的矩阵可以得到X的一个最小精确覆盖,C'={{1,2,4},{3,5},{6,7}}.

通过算法6求解最小精确覆盖的方法,可以得到一个函数依赖集合S的最小精确覆盖.基于该最小精确覆盖对S中的多个FD进行分组,实现任意情况的多个FD在分布式环境下不一致性的并行检测.

3 实 验

为了验证文中提出的分布式环境下函数依赖不一致性检测算法的有效性,本文使用真实数据集和合成数据集对算法进行了实验验证,测试了算法在不同节点个数、不同数据集规模以及不同函数依赖个数等情况下的响应时间以及数据迁移量情况.

· 实验设置

本实验中使用了由10台服务器通过局域网连接构成的一个集群,每一台机器配备了主频为1.87G的Intel Xeon 2处理器和16G内存,操作系统为Ubuntu10.4.所有算法均由Java实现,算法运行平台为分布式系统架构Hadoop平台与基于BSP(bulk synchronous parallel)并行计算框架的Hama平台.

(a) 数据集.本文中使用了2种不同类型的数据集:一种是TranStats data library提供的Airline On-Time Statistics统计数据^[8],这是一个真实的数据集;另外一种是人工生成的数据集.第一种数据集简称“OTPF”,包含了64个属性,如airline ID,flight number等.数据集的规模为35GB,包含了15亿条元组.本文使用该数据集生成一个包含4 000万条元组的数据库实例otpf₄,一个包含8 000万条元组的数据库实例otpf₈,一个包含1.2亿条元组的数据库实例otpf₁₂.另外一种数据集是一个人工生成的前文提到的STUDENT表的数据集,简称“STUD”,包含了2亿条元组.利用该数据集生成一个包含4 000万条元组的数据库实例stud₄,一个包含8 000万条元组的数据库实例stud₈,一个包含1.2亿条元组的数据库实例stud₁₂.

(b) 函数依赖.对于数据集OTPF,找出一组反映真实约束关系的函数依赖,函数依赖个数为8个,每个包含了2~5个属性.对于STUD,定义了10个函数依赖,为了验证实验效果,数据集中人为增加了噪声.

· 实验结果

本文设计了5组实验,分别对单个函数依赖的集中式算法CetDetect、基于Hadoop的Naïve算法SingleFdDet_Hadoop以及本文提出的SingleFdDet_RT、基于多个函数依赖的顺序检测算法SuccDetect、基于Hadoop的多函数依赖不一致性检测Naïve算法MultiFdDet_Hadoop以及本文提出的MultiFdDet_RT进行测试,并对近似最优算法与真正最优方案的执行时间进行了比较.在实验中,分别改变节点的个数(|S|)、数据的规模(|D|),每一组实验均在相同条件下运行3次,取实验结果的平均值为最终结果值.

首先评估基于单个函数依赖的检测算法,对每一个数据集选取一个函数依赖进行检测.

· 实验1:改变数据的分片个数

为了评价算法在不同分块数(节点数)情况下的扩展性,本文在数据规模固定的情况下增加节点数|S|从2到8,分别基于数据集otpf₈和stud₈,对算法的执行时间进行测试.图 3和图 4反映了算法CetDetect,SingleFdDet_Hadoop,SingleFdDet_RT在不同节点下响应时间情况.跟预想的情况类似,算法SingleFdDet_Hadoop与SingleFdDet_RT的响应时间随着节点的增加呈现减少的趋势.由于算法CetDetect随着节点的增加,数据迁移量相应增加,相应数据传输时间增加,而集中检测的检测时间在每种情况下基本相同,因此算法总的响应时间有增加的趋势.由于算法SingleFdDet_RT可以进行并行检测,因此响应时间明显比算法CetDetect要小.算法SingleFdDet_Hadoop与SingleFdDet_RT相比,由于本身Hadoop任务启动存在一定的耗时,且数据未经过去重等预处理,数据迁移量及数据规模相对较大,因此响应时间比SingleFdDet_RT要长.

· 实验2:改变数据的规模

为评价算法在不同数据规模情况下的扩展性,本文在节点个数固定(4个节点)的情况下,增加数据规模|D|从2 000万条元组到1.2亿条元组,分别基于数据集otpf₁₂和stud₁₂,对算法的响应时间进行测试.图 5和图 6反映了算法CetDetect,SingleFdDet_Hadoop,SingleFdDet_RT在不同数据规模下响应时间情况.

从图中可以看出,3种算法的响应时间随着数据规模的增加而增大,数据规模的增大直接影响到检测的时间消耗及数据传输时间,因此数据规模与算法响应时间成正相关.从图 5和图 6不难看出,算法SingleFdDet_Hadoop,SingleFdDet_RT比算法CetDetect的响应时间少很多,说明分布式并行算法SingleFdDet_Hadoop,SingleFdDet_RT的检测效率明显高于集中式算法CetDetect.而且从图 5和图 6可以看出,随着数据规模的不断增大,算法Single FdDet_Hadoop,SingleFdDet_RT与CetDetect相比,在响应时间方面优势明显;而算法SingleFdDet_RT与Single FdDet_Hadoop相比,随着数据规模的增加,减少的响应时间呈增加的趋势.

其次评估基于多个函数依赖的检测算法,对数据集OTPF和STUD,分别选取LHS包含公共属性的3个FD进行检测.

· 实验3:改变数据的分片数

为评价多个FD的检测算法在不同分块数情况下的扩展性,本文在数据规模固定的情况下增加节点数|S|从2到8,分别基于数据集otpf₈和stud₈,对算法的执行时间进行测试,实验结果如图 7和图 8所示.从实验结果可以看出:随着节点数的不断增加,算法的响应时间呈减少的趋势.与顺序检测的算法SuccDetect相比,批量检测算法MultiFdDet_Hadoop,MultiFdDet_RT的响应时间还不到其一半,说明批量检测算法在检测多个FD不一致性时优势明显.随着节点数的增加,MultiFdDet_RT响应时间均明显少于MultiFdDet_Hadoop,说明本文提出的检测算法与基于Hadoop的Naïve方法相比在响应时间方面优势明显.

· 实验4:改变数据的规模

为评价多个FD的检测算法在不同数据规模下的扩展性,本文在节点个数固定(4个节点)的情况下增加数据规模|D|从2 000万条元组到1.2亿条元组,对算法的响应时间进行测试.图 9和图 10反映了算法SuccDetect,MultiFdDet_Hadoop,MultiFdDet_RT在不同数据规模下响应时间情况.

不难看出,随着数据规模的不断增加,3种算法的响应时间也不断增加.与分布式并行算法MultiFdDet_Hadoop,MultiFdDet_RT相比,算法SuccDetect的响应时间更长,说明MultiFdDet_Hadoop,MultiFdDet_RT的检测效率更高.而就分布式并行算法来看,本文提出的算法MultiFdDet_RT与Naïve算法MultiFdDet_Hadoop相比,在响应时间方面优势明显.随着数据规模的不断增加,算法MultiFdDet_RT的效率优势呈现出不断扩大的趋势.

· 实验5:近似算法与最优算法比较

为了评价本文提出的近似最优的分布式环境不一致性检测算法与真正最优方案的响应时间差距情况,增加节点数|S|,基于数据集otpf₈和stud₈,分别对单个函数依赖以及多个函数依赖情况下近似最优算法与真正最优方案的执行时间进行测试.图 11和图 12是单个函数依赖情况下近似最优检测算法SingleFdDet_RT和真正最优检测算法SingleFdDet_OPT在不同节点下响应时间情况.不难看出,在节点个数为2个时,近似最优算法与真正最优方案的执行时间基本相同;随着节点各种的增加,与近似最优算法相比,真正最优方案的执行时间相对较少,但是总体来说相差不大.图 13和图 14是多个函数依赖情况下近似最优检测算法MultiFdDet_RT和真正最优检测算法MultiFdDet_OPT在不同节点下响应时间情况.可以看出,与单个函数依赖情况类似,在节点个数较少的情况下,近似最优算法与真正最优方案的耗时基本相同;随着节点数的增加,真正最优方案与近似最优算法在执行时间方面相比优势有增加的趋势,但是并不十分明显.

4 相关工作

函数依赖的概念最早由Armstrong提出^[1].Fan提出了一种基于SQL技术检测集中式环境中条件函数依赖冲突的方法^[2].然而在分布式环境下对函数依赖冲突进行检测,文献^[2]中的方法并不适用.Fan等人对分布式环境下条件函数依赖冲突检测进行了研究,利用条件函数依赖的结构减少数据迁移或响应时间^[4].文献^[9]研究了分布式环境下条件函数依赖不一致性的增量检测.与条件函数依赖不同,函数依赖没有条件函数依赖特有的模式元组,因此,文献^{[2, 9]}中提到的算法不适合分布式环境下对函数依赖进行检测.

文献^{[5, 10]}研究了分布式数据库中完整性约束的检测问题.文献^[10]中给出了检测的本地条件,满足这些条件,不用进行数据的迁移,减少了通信代价.文献^[5]研究了在不访问全部基本关系的情况下对基本关系更新时全局不一致性检测问题.在某些条件下,条件函数依赖可以在不进行数据迁移的情况下进行不一致性检测^[4].与文献^{[5, 10]}不同,在分布式环境下检测函数依赖的不一致性的时候,通常需要数据迁移.

文献^{[11, 12]}对分布式数据源的异常检测问题进行了研究.文献^[11]提出了一种分布式环境中检测流量异常的框架,避免了全局通信和集中决策.文献^[12]提出了一种针对包含混合属性数据集的快速分布式异常检测策略.这些方法主要针对的是异常检测,而函数依赖冲突检测主要是检测函数依赖约束的违反情况.

文献^[13]对数据融合中数据冲突的解析进行了研究,主要针对的是集中式环境下的冲突问题.文献^[14]中对约束的冲突情况进行了研究,主要研究了分布式系统中使用本地约束检测全局约束违反的情况.

文献^[15-17]对函数依赖冲突的修复进行了相关研究.为了对存在违反函数依赖情况的不一致数据进行修复,通常采用对属性值进行修改的方法.与本文工作不同,这些文献主要关注的是函数依赖冲突的修复问题.文献^{[18, 19]}研究了函数依赖发现的问题,主要是研究给定一个模式,如何发现隐含的约束关系.文献^[20]研究了分布式环境函数依赖发现问题.

5 结论和下一步工作

本文研究了分布式背景下函数依赖冲突检测的问题,给出了分布式环境下单个函数依赖和多个函数依赖不一致性并行检测的算法,并利用函数依赖的结构特征对多个函数依赖实现批量并行检测.为实现对多个函数依赖的批量检测,考虑对多个函数依赖进行分组,组内的可以进行批量不一致性检测.将多个函数依赖的分组问题划归为最小集合覆盖问题,给出了得到问题近似解的贪心算法.为了消除最小集合覆盖中存在的冗余元素导致的重复检测问题,给出了消除最小集合覆盖中冗余元素得到一个最小精确覆盖的算法.基于真实数据集和人工数据集对本文提出的检测算法进行了验证,实验结果表明,算法在数据规模和节点个数方面扩展性良好,而且在减少响应时间方面优势明显.限于篇幅,本文仅对分布式环境下水平切分的数据不一致性检测进行了研究,下一步考虑对分布式环境下垂直切分的数据不一致性检测问题进行研究.