基于标记的不一致数据查询处理框架

吴爱华

(上海海事大学 信息工程学院，上海 201306)

0 引言

尽管完整性约束用于防止不一致已有多年，不一致关系数据仍普遍存在于多类现实应用中，涵盖系统集成与数据整合［1］、数据交换、Web 信息抽取、信息检索［2］、科学数据管理和传感器网络等多个应用领域.不一致数据蕴含着错误信息，在这样的数据库上回答用户查询，得到的结果也可能是错误的.而错误数据对企事业单位的日常工作、经营管理、决策等的不良影响和经济损害不言而喻.因此，怎样回答不一致数据库上的查询，如何保证查询回答准确可信，就成为亟待解决的实际问题.

但不一致数据上的查询处理比传统关系数据的查询处理复杂得多，哪怕只有互相矛盾的记录存在.首先，从理论模型上看，这是一个全、准、复杂度难以权衡的难题.如果在计算查询回答时排除所有不一致记录，虽返回给用户的结果确定可信，却不可避免地丢失不一致记录中的确定部分［3］.而若要把所有可能的确定回答都返给用户，则其计算复杂度非常高.有研究［4］表明，不一致数据库对应的全部确定数据库的求解是NP 完全问题.其次，给出好的理论模型，还要寻找高效的查询处理算法，以便能在不影响一致数据管理和商用RDBMS 使用的基础上，实现不一致数据的管理和查询，使用户仍能从不一致数据中获得有价值的查询结果.最后，尽管用户希望能从不一致数据库上得到唯一可信的查询回答，但其概率本质使得这样的查询结果不存在，须从语义上重新思考查询结果的可信性及其价值.

标记描述常被用于协同数据处理领域，如基因序列识别、蛋白质数据管理、天文数据处理、多样性物种归类和协同文档处理.这类应用要求多用户参与同一数据的收集、修改和处理，为了分享观点，标记常被用来解释和纠正数据，或否定其他用户的观点.不一致数据正是典型的有争议共享数据，只是标记对象不是协同文件或分子结构，而是一组组不一致数据.

文献［5］和［6］针对违反函数依赖且主码可信的不一致关系数据，提出一种基于标记的查询回答的研究方案(简称AQA)，通过区分查询回答中一致和不一致的部分，给用户可靠且信息量最大的查询回答.在AQA中，不一致性是数据的属性，可用标记加以描述;关系中的每个单元值都可附加0 至多个标记，有标记的单元值不一致，反之一致.且标记能随着查询计算从源数据库正确地迁徙到查询回答中.通过标记的使用，原数据库和查询回答中的不一致信息都不会被过滤掉，可避免信息丢失.文献［5］证明该方案的有效性和完备性.

但传统的关系代数运算并不支持AQA，已有DBMS 的SQL 查询处理模块也不支持不一致标记的计算.为了能把AQA 应用到现存各类不一致关系数据库上，须研究其实现方法.

对于不确定数据的管理和查询，仅已形成少数几个实用系统［7-14］.已有系统大多以PostgreSQL 等开源RDBMS为基础，扩展或重新编写其查询处理模块，形成专门的不确定数据库管理系统.这类系统不能很好地与Oracle，DB2，Sysbase 等现有商用RDBMS 相融合.但现有商业RDBMS 稳定成熟，新系统即便能同时管理和查询确定和不确定数据，也难以取代它们.另外，新系统还需定义全新的查询语言，给用户带来一定的负担.

本文以文献［5］和［6］提出的理论模型为依据，采用查询重写的方法实现一个不一致数据查询处理系统——AQA 系统，它是RDBMS 与用户之间的一类中间件，能将任意传统SQL 查询翻译成能返回带信任标记的SQL 查询集，由已有的RDBMS 响应.该系统虽效率稍低，但胜在:(1)能内嵌到现有数据库应用系统中;(2)用户无须掌握新查询语言，没有学习负担.

此外，本系统还有以下优点:(1)支持属性一级的不一致数据的检测和查询处理;(2)能同时处理来自不同DBMS 维护的不一致数据;(3)除初始标记外，该实现方案无须其他预处理或后处理，基本遵从关系数据模型，不影响一致数据的管理和查询处理.

1 不一致数据带标记的查询回答

1.1 基本概念

给定一个数据库D 及其上的完整性约束集合CI，如果∃c∈CI，使得D|≠c，那么数据库D 不一致.本文假设CI中只包含函数依赖，且主码确定，那么违反某约束的记录在被决定因素上的分量就不一致.

所有不一致分量都可附加一个以上的标记，以识别查询结果中不可信的部分.虽然初始数据库中分量的不一致性不会在查询估值中改变，但有些一致分量会因违反蕴含约束而在查询结果中不一致.为此，本系统采用两种标记:静态标记和动态标记.前者描述初始数据库中的不一致分量，示以符号“* ”;后者描述仅在查询结果中不一致的分量，标记符号为导致该分量不一致的决定因素的属性名.图1 给出一个不一致数据库及其标记的例子，其中student表上的查询Q1中，“EE081”班的Teacher 因违反CName→Teacher 而标以“* ”，而“EE081”班的Cellphone 则因违反蕴含依赖CName→Cellphone，而被附上动态标记“Class.CName”.静态标记不会变，但动态标记则可能在查询处理中创建和消亡.

定义2 根据给定域等和ArmStrong 公理系统，蕴含依赖(Derived FD)是那些不属于给定函数依赖集F，但属于F+的函数依赖.

定义3 标记过的关系(annotated relation).对于任意给定关系r 及其上的函数依赖集CI，∀x→y∈CI，∀t1，t2∈r，如 果t1［x］=t2［x］但t1［y］≠t2［y］，t1［y］和t2［y］都被附上标记，那么r是一个依据CI标记过的关系.

定义4 带标记的查询回答(annotation-based query answer).对于任意给定关系r，其上的函数依赖集CI及查询Q，设C'I是CI在Q(r)上的投影，C″I是Q(r)上的蕴含依赖集，如果Q(r)依据C'I和C″I标记过，那么Q(r)是一个带标记的查询回答.

图1(c)的表格即是一个带标记的查询回答.

1.2 数据模型

为了在存储上区分一致分量和不一致分量，本文扩展传统的关系数据模型，对每一个字段C，增加字段CA，用于存储记录在C 上分量的信任标记.如果t［C］不一致，那么t［CA］是由一个或多个标记组成的字符串，否则为空值.新增字段只能由系统更新.

此外，因大多RDBMS 只支持主码和外码，本文还在数据库中增加一些描述原始约束和蕴含约束的系统表，以存储数据库上的函数依赖集.

2 AQA 系统框架

AQA 系统由查询重写、初始标记、初始标记维护和蕴含约束计算等4个模块组成，见图2.

图2 AQA 的系统框架

蕴含约束计算模块根据给定函数依赖和域等关系计算关系模式上所有的蕴含依赖.查询结果上成立的蕴含函数依赖是源关系模式上成立的蕴含依赖在其上的投影.源关系模式不变，其蕴含函数依赖就不变.查询处理时仅需求解其在查询结果上的投影.此处一次计算可用于任意查询处理中，效率提高.

初始标记模块在数据载入时运行，该模块依据给定函数依赖集(不包括蕴含依赖)给不一致分量附加静态标记.

数据日常维护后，初始标记可能无法正确表示其语义，另外，约束改变时不一致性也需重新计算.初始标记维护模块包括全维护和增量维护两个子模块，全维护模块根据最新函数依赖集重新检测数据的不一致性，用于约束集合改变时的标记维护，增量维护模块在记录值改变时根据当前函数依赖重新计算其不一致性，它们均以触发器的形式实现.

查询重写模块在整个系统中最重要.对用户提交的常用SQL 语句，该模块会将其翻译成一系列可得到带标记查询结果的SQL 语句，这组SQL 语句计算蕴含依赖在查询结果上的投影、并依据每个蕴含依赖计算查询结果中的动态标记.

另外，为了测试性能，本系统还包括一个数据产生器，依据图1 所示的数据库模式及其函数依赖产生给定大小和脏数据比例的人工数据.

尽管数据库中新增的约束表和每张表的标记字段会有一定的硬盘开销，它们并不改变原始记录，AQA 仍支持传统SQL 查询;从性能上讲，现实应用不会经常改变数据模式，因此系统中的初始标记模块和蕴含约束计算模块很少执行，全维护模块也几乎不运行.除查询重写和标记维护外，所有模块都可在数据库不太忙时运行，对用户影响有限.

3 关键问题

3.1 不一致分量的初始检查标记算法

初始标记主要依据给定的函数依赖集检查违反约束的分量.这里假设待标记数据库遵从3NF 且主码一致.具有相同主码的记录可被认作同一实体，其不同属性值就不一致.另外，由于主码一致，检测时可忽略两类约束:一是被决定因素是主属性的函数依赖，二是决定因素是其他候选码的函数依赖.

算法1 首先极小化输入的函数依赖集，确保主码对其他字段的函数依赖在待处理的函数依赖集中.剔除上述两类函数依赖，对剩余任意函数依赖x→y，设数据库中有两条记录t1和t2，t1［x］=t2［x］且t1［y］!=t2［y］，则将标记“* ”添加到t1［yA］和t2［yA］中.该算法须对每个函数依赖扫描一遍数据库，能标记所有主码正确的3NF 数据库.

3.2 标记增量维护

静态标记在两种情况下需加以维护:一是日常记录维护，二是数据库模式改变(此时原有标记可能无法正确反映数据的不一致性).数据库模式改变又可分成:(1)数据库结构改变，如增加新表及其上的约束、删除表、增加字段、修改字段或删除字段;(2)约束改变，增加或删除某些表上的约束.

日常记录维护可能使标记与其语义不符.记录增加时，AQA 采用触发器1 检测该记录是否与表中的其他记录矛盾;记录值修改后，AQA 采用触发器2检测并修改其静态标记;记录删除虽不会带来新的标记，但可能改变其他记录的不一致性，AQA 采用触发器3 检测并修改静态标记.

对于模式改变:首先，修改字段并不会影响数据和约束，无须任何处理;其次，数据库表或表中字段的删除，AQA 仅简单地将标记和数据一起删除;再次，由于新增表暂时无数据，静态标记可延后维护，同样采用触发器1 在增加记录时维护其静态标记，类似地，新增字段也可留待修改其值时维护标记;最后，增加新约束需通过触发器4 对整个表按此约束重新检测并标记不一致分量，删除约束时要对违反了该约束的记录用触发器5 检测并修改标记.

触发器1 UpdateAnno_Insert

触发器2 UpdateAnno_update

触发器3 UpdateAnno_Delete

触发器4 UpdateAnno_AddFD

触发器5 UpdateAnno_DelFD

3.3 查询重写方法

采用查询重写的方法在标记过的关系数据库上为任意用户输入的所有SQL 语句(除了统计查询和含相关子查询的嵌套查询之外)，计算其基于标记的查询回答.除了为初始数据库创建初始标记之外，这个实现方案不需要其他的预处理或者后处理，也不会改变现有关系数据库及其应用系统.

select-project-join 查询(SPJ 查询)可以重写成包含3 类查询的一组查询:第一类查询只有一个，创建包含所有可能违反蕴含依赖记录的表;第二类查询修改上一步所得临时表的动态标记，对于每个蕴含依赖，都有一个这样的update 查询;第三类查询也只有一个，用于检索并合并所有可能的查询结果及其标记.

蕴含约束则采用算法2 求得.

算法2:DerivedFD

输入:数据库模式r，r 上的函数依赖及其域等属性集

输出:r 上成立的函数依赖集

(1)将所有给定函数依赖的右边逐一替换为它的域等属性(如果存在的话)，然后将得到的函数依赖加入函数依赖集.

(2)将所有给定函数依赖的左边属性逐一替换为其域等属性(如果存在的话)，再将得到的函数依赖加入函数依赖集.

(3)若函数依赖集中存在函数依赖A→B，C→D，且B域等于C，则将函数依赖A→C，A→D，B→D 加入函数依赖集.

(4)重复第(3)步直到函数依赖集不再变化为止.

(5)删除所得函数依赖集中重复的和已知的函数依赖.

返回最后的函数依赖集.

4 实 验

完成实验的配置如下:Intel Celeron 420 2.0 GHZ CPU，1GB 内存，Windows XP+SP2，SQL Server 2000，编程语言是C#和VC 6.0.

实验共使用两组8个数据库.第1 组数据库规模均为1GB 左右，但脏数据比例分别为1%，5%，10%，15%;第2 组数据库中脏数据比例均为5%，但规模分别为0.13，0.54，1.00和1.50 GB.

查询共11个:q1～q6均为单表查询;q7为嵌套查询;q8和q9分别是2 张表和3 张表之间的自然连接;q10是并查询;q11是差查询.

本组实验旨在查询重写的性能，比较它在大小不同和脏数据比例不同的数据源上的时间性能表现.

如图3(a)所示，当数据库大小不变，而脏数据比例增大时，非连接查询的时间性能变化不大，而连接查询的时间消耗对于脏数据比例呈线性增长.这是因为随着不一致数据的增加，在连接结果集上需验证的不一致分量随之增加.另外，当脏数据比例不变，而数据库大小逐步增大时(如图3 (b)所示)，查询q3，q4，q5，q10和q11变化不大，此时虽然数据库变大，但符合查询条件的记录却不变，且在查询条件上建有索引，因此时间消耗基本不变;查询q2，q6和q7的时间随着数据库的增大而增大，虽然它们也无蕴含依赖的验证，但因条件字段上无索引，需全表扫描，时间消耗自然会增加;查询q8和q9的时间消耗会随着数据库的增大而迅速增加，其主要原因在于蕴含依赖检验所需的时间随着数据库的增大而增大;q9的时间消耗比q8更多，原因是其需验证的蕴含依赖更多.

5 结束语

不一致数据的查询与管理是近期的一个难点和热点问题.本文以前期理论工作为基础，实现了不一致数据的查询处理系统.该系统能处理大多数用户查询，支持常用谓词，如NOT，IN，BETWEEN，…，AND，LIKE，EXISTS 等;支持属性级的不一致数据的检测和查询处理;能同时处理不同DBMS 维护的不一致数据;除初始标记之外，无须其他预处理或后处理，基本遵从关系数据模型，不影响一致数据的管理和查询处理.

［1］ANDRITSOS P，FUXMAN A，MILLER R J.Clean answers over dirty databases［C］// Proc 22nd Int Conf on Data Eng.Atlanta:IEEE Comput Soc，2006:30.

［2］SEN P，DESHPANDE A.Representing and querying correlated tuples in probabilistic databases［C］// Proc 23rd Int Conf on Data Eng，Istanbul，Turkey:IEEE Comput Soc，2007:596-605.

［3］ARENAS M，BERTOSSI L E，CHOMICKI J.Consistent query answers in inconsistent databases［C］// Proc PODS Conf，Philadelphia:ACM，1999:68-79.

［4］LOPATENKO A，BERTOSSI L.Complexity of consistent query answering in databases under cardinality based and incremental repair semantics［C］// Proc 11th Int Conf of Database Theory.Barcelona:Springer-Verlag，2007:179-193.

［5］WU Aihua，TAN Zijing，WANG Wei.Annotation based query answer over inconsistent database［J］.J Comput Sci ＆ Technol (JCST)，2010，25(3):467-479.

［6］吴爱华，谈子敬，汪卫.不一致数据库上带信任标记的查询结果［J］.软件学报，2012，23(5):1167-1182.

［7］HUANG Jiewen，ANTOVA L，KOCH C，et al.MayBMS:a probabilistic database management system proc［C］// Proc.ACM SIGMOD Int Conf on Mana of Data.Rhode Island，USA:ACM，2009:1071-1074.

［8］AGRAWAL P，BENJELLOUN O，DAS SARMA A，et al.Trio:a system for data，uncertainty，and lineage［C］// Proc 32th Conf on Very Large Data Bases，New York:ACM，2006:1151-1154.

［9］JAMPANI R，PEREZ L，WU M，et al.MCDB:a Monte Carlo approach to managing uncertain data［C］// Proc ACM SIGMOD Int Conf on Management of Data，Vancouver，Canada，ACM 2008:687-700.

［10］BOULOS J，DALVI N，MANDHANI B，et al.MYSTIQ:a system for finding more answers by using probabilities［C］// Proc ACM SIGMOD Int Conf on Mana of Data，Baltimore:ACM，2005:891-893.

［11］WANG D Z，MICHELAKIS E，GAROFALAKIS M，et al.BayesStore:Managing Large，Uncertain Data Repositories with Probabilistic Graphical Models［J］// J Proc VLDB Endowment 2008(1):340-351.

［12］SINGH S，MAYFIELD C，MITTAL S，et al:Orion 2.0:native support for uncertain data［C］// Proc ACM SIGMOD Int Conf on Management of Data，Vancouver，Canada，ACM 2008:1239-1242.

［13］SARMA A D，BENJELLOUN O，HALEVY A，et al.Representing uncertain data:models，properties，and algorithms［J］.The VLDB J，2009，18(5):989-1019.

［14］Nilesh Dalvi，Chris Re，Dan Suciu.Probabilistic databases:diamonds in the dirt［J］.Commun of the ACM，2009，52(7)，86-96.