1 引言 1.1 问题背景 为什么科尔伯特不是总统?为什么Travelocity并没有告诉我Drake Hotel也是芝加哥可以作为备选的落脚点?为什么Frank Sinatra没有棕色的眼睛?现实世界中, 很多没有发生的事情都有非常明确的原因.了解为什么该发生的事情没有发生, 是我们理解世界的正常方式.在数据库领域和软件系统领域, 这种问题经常是这种形式:为什么这个程序是不完整的?为什么这个元组没有出现在查询的结果集?由于在用户得到结果之前需要对数据进行较多步骤的计算, 所以这种问题的答案较难寻找. 数据起源, 或者可以叫做一段数据的历史信息, 曾经被用于研究解释数据从哪里来[1-3]和在原始数据变成结果集的过程中都发生了什么[4-7].对于这些信息的整合, 可以帮助我们理解为什么某些元组并没有出现在结果集中[4, 7, 8].数据起源在这些工作中可以帮助人们解释一些结果集中非正常的结果. 对于数据库用户, 一个常见的场景是这些编程人员被问为什么一条或者多条用户认为会有的数据并未出现在查询结果里.用户会猜想为什么.比如, 一个查询的结果集是空的或者为什么同样的查询没有返回相同的结果值.当查询用来定义多视图的时候, 用户可能会问为什么.例如, 一个雇员的信息在雇员注册的视图和工资名单的视图中都没有.经常地, 编程人员的第一反应是查看是否是查询本身的错误, 比如条件太严格筛掉了部分可能结果, 或者采用的outer-join本来应该是inner-join.然而, 如果查询的表示方式是正确的, 下一步编程人员要考虑的事情就是研究数据源, 确定是否用户期望的结果数据真的在数据源中有出现.我们将这种形式的解释, 即这种用数据来解释不在结果集中的元组的方式, 叫做依赖数据的解释.在本文中, 主要研究依赖数据的解释. 例 1:考虑表 1中的关系和查询Q1: $ Q1:SELECT\;{\rm{No}}.{\rm{O - rings}}, \;{\rm{Temp}}, \;{\rm{Order}}\;FROM\;{\rm{table}}\;WHERE\;{\rm{Temp}} > 70 $ Table 1 Challenger USA space shuttle O-ring dataset 表 1 挑战者号美国航天飞机O型圈数据集 查询后的结果见表 2.用户知道在查询结果中, 应该有一个发射温度为78华氏度的飞机, 时间顺序应是第12位, 但是这个元组并没有出现在查询的结果集中.用户可能会问, 为什么元组(6, 78, 12)没有出现?如果向原来的数据表插入元组(6, _, 78, _, 12), 元组(6, 78, 12)就可以出现在查询结果集中, 其中, “_”代表此属性可以取数据域中的任意值.我们根据观察表格发现, 属性No.ETD和Pressure都属于整数域, 而如果用户也需要这两个属性值的一个合理推断, 那么向原来的数据表插入元组(6, 0, 78, 200, 12)就可以看做是一个解释.若无法推断出精确属性值, 否定某些可能的属性值, 如向原来数据表中加入(6, ¬2, 78, 200, 12)也可以看做是一个合理的解释. Table 2 Query results 表 2 查询结果 为了令没有出现在结果中的期望元组成为Q1的查询结果, 枚举可能的缺失元组是一种可行的方案.但是在这些被枚举的可能中, 存在着大量不合理的解释, 通常违反唯一性约束或者源数据库内部的约束, 如函数依赖和条件函数依赖. 利用数据库内部的约束可以初步约减一些不合理的解释, 如文献[9-11]利用唯一性约束对得到的解释进行了约减, 但在较大数据集上, 利用数据库内部规则进行约减虽然有一定效果, 但仍然会返回大量的解释(如文献[9]在本文中所使用的Airfoil Self-Noise上, 在只有两个待修复属性的条件下, 仍然返回37 856条解释), 使得用户无法确认解释是否合理. 另外, 在返回的解释中存在非常多利用变量表示的属性, 即取属性域中的任意值均可.对于用户来说, 此种解释的参考价值不大, 所以生成用户可以理解的排序后的实例解释非常重要. 1.2 主要贡献 本文在以前工作的基础上, 做出了如下主要贡献. ●  重新定义了Why-not问题解释的格式, 使得呈献给用户的解释不含变量, 使得解释更容易被理解; ●  在多属性的情况下, 可能的值域会很大, 为了避免数据稀疏性问题, 提出将数据表示为两两比较关系, 以{0, 1}表示两个元组在某个属性上是否相等, 从而支持更有效的概率模型学习; ●  利用统计方法计算两两关系概率分布, 定义基于两两关系概率的支持度(support)与置信度(confidence), 并根据这些度量对候选解释进行相应的筛选和排序; ●  利用分类和回归方法计算两两关系概率分布.统计方法在计算概率分布时未能充分考虑不同程度的属性关系.在分类和回归方法后, 不同程度的属性间关系被考虑, 使得最后返回的解释排序结果更加合理.结合回归方法并考虑不同程度的属性间关系后, 我们提出了3种算法; ●  在不同数据集上的实验结果证明:利用统计、分类和回归方法计算两两关系概率分布的方法, 可以为用户寻找Why-not问题的解释并返回较为高质量的解释. 1.3 论文结构 本文第2节对相关工作进行具体介绍.第3节给出本文的一些通用基础定义和问题的形式化定义.解释的统计学特征定义将与利用统计学方法寻找候选解释和它们的概率分布的算法一起在第4节中说明.第5节呈现结合机器学习分类方法的寻找候选解释及其概率分布的算法和3种结合回归方法寻找候选解释及其概率分布的算法.在第6节中将给出不同算法在真实数据集上的实验结果的比较.最后, 在第7节中对本文的工作进行总结, 并对未来的工作进行展望. 2 相关工作 2.1 Why-not问题 现今, 数据量正在快速地增长.数据库管理系统从不同的数据源中抽取数据, 聚合数据并将它们添加到数据库中.但是数据源常常不具有很好的质量.由于数据源的低质量和低一致性, 用户或者数据科学家们经常会面临一种问题:当他们在一个数据库上执行查询的时候, 一些他们期望的答案并没有出现在返回的查询结果中.继而用户可能会询问为什么一个或者多个元组没有在查询结果集中出现, 也就是Why-not问题.显然, 为数据科学家或者用户提供针对于缺失元组的解释, 可以帮助他们更好地理解或修复数据库.这种问题其实是数据起源问题的一个扩展, 最早在文献[12]中被提出. 2.2 缺失答案解释 现今, 已经有很多方法来解决简化数据转换分析问题, 并使用户更容易理解和验证其行为和语义, 包括数据沿袭[13]和更一般的数据来源[14]、子查询结果检查[15]、可视化[16]或转换规范简化[17].本文中提到的工作属于数据来源研究的范畴, 重点是一个特定的子解决方案, 旨在解释查询结果中的缺失答案, 也就是解释为什么某些数据不存在. 缺失答案(MA)[10]在给出单个缺少的元组和单个选择项目连接(SPJ)查询后, 计算基于实例的解释.事实上, 它重写查询, 使得重写查询的结果对应于指定的缺失答案的所有可能的基于实例的解释.基于实例的说明插入或更新源数据, 并且可以通过信任表(属性)来减少需要被进行插入(更新)的数据. Artemis[9]扩展了MA算法, 使得它适用于一组涉及选择、投影、连接、联合和聚合(SPJUA查询)的非嵌套SQL查询.此外, 可以指定多个缺失答案.计算的基于实例的解释描述了插入源数据的所有可能的方案, 以便可以同时解释所有缺失答案.Artemis也考虑了修建解释的副作用.副作用在根据基于实例的解释更改源数据后, 新增的结果除了指定的缺失答案之外, 还会有其他的结果显示在查询的结果中. Meliou等人统一了查询结果和缺失答案中存在数据的基于实例的解释[18].不使用数据来源[14], 解决方案利用了因果关系和责任关系.此文详细研究了基于因果关系和责任的联合查询解释的复杂性, Meliou等人在文献[18]中还将现有数据的一种具体类型的解释统一为缺少数据的一种特定类型的解释. Why-not[12]计算基于查询的解释.首先, 给出一个缺失答案, 它识别源数据库中包含常量值的元组, 或者满足缺失答案的条件, 而不是查询结果中的任何元组谱系的一部分[3].这些元组中的值称为兼容元组, 通过查询运算符被跟踪, 以识别哪些运算符将它们作为输入, 而不是输出.在文献[12]中, 该算法被证明适用于涉及选择, 投影、连接和联合(SPJU查询)中的某一个查询. NedExplain[19]类似于Why-not, 跟踪源数据库的元组, 然而它不限制将兼容的元组限制到不是任何结果元组谱系的源元组.基于这种修改的基本假设和基于查询解释的新颖形式定义, NedExplain计算一个比Why- not更全面、正确和详细的解释集合, 并支持涉及选择、投影、加入和聚合(SPJA查询)以及SPJA查询的联合. ConQueR[20]输出基于修改的解释.给定一组缺失答案, SPJUA查询和源数据库, 它首先确定产生缺失答案的必要源数据是否可用, 这与Why-not类似.然后更改SQL查询, 使得所有缺失答案成为输出的一部分, 而副作用最小化.即在进行查询修改时, 原始查询结果中存在的元组必须保留, 只有最少数量的不是缺失答案的附加元组可以被允许出现在结果中. 最近已经提出了计算针对关系和SQL查询之外的查询基于修改的解释算法.在考虑副作用的同时, 计算基于修改的解释的一种算法专门解答Why-not的Top-k查询问题[21].这个算法重点在于改变k或偏好权重, 使缺失答案出现在查询结果中.Islam等人在文献[22]中提出了解决方案, 回答了Why-not的反向Skyline查询问题. 2.3 条件函数依赖 此节将介绍条件函数依赖的基础定义[23]和它的一些有趣的统计学特征[24], 即支持度和置信度.后文将基于条件函数依赖的统计学特征重新定义解释的统计学特征. 2.3.1 基础定义 一个在关系R上的条件函数依赖φ是一个元组R(X→Y, Tp), 其中, ●   X, Y是attr(R)中的一系列属性; ●   R(X→Y)是一个标准函数依赖, 又可以被叫做嵌在φ中的函数依赖; ●   Tp是一个具有X和Y中所有属性的表, 又可以被叫做φ的模式表, 其中, 对于每个元组t的任意的在X或Y中的属性A, t[A]为一个在dom(A)中的常数‘a’或者是一个未命名的变量‘_’.如果属性A在X和Y中都出现了, 则我们用t[AL]和t[AR]来表示左边和和右边的A.当已知关系R时, 我们将φ写为(X→Y, Tp). 关系R的一个实例I满足条件函数依赖φ, 定义为I⊨φ, 当且仅当对于实例I中的每对元组ti, tj, 和条件函数依赖φ的模式表Tp中的每个元组, 如果t1[X]=t2[X]≍tc[X]成立, 那么t1[Y]=t2[Y]≍tc[Y]成立.即:如果t1[X]和t2[Y]相等并且他们都与模式tc[Y]相配, 那么t1[Y]和t2[Y]一定相等并且他们都与模式tc[Y]相配.此外, 如果∑是条件函数依赖的一个集合, 我们说I⊨∑当且仅当对∑中的每一个条件函数依赖φ, 都有I⊨φ. 2.3.2 统计学特征 (1) 支持度 显然, 经常一起出现的值有更多可能性是相关的, 支持度就是基于这种思想的一种频率度量.关系R中的条件函数依赖φ=(X→A, tP)的支持度是R与φ相配的部分元组的数量占全部元组数量的比例, 表示为support(φ, R), 可定义为 $support(\varphi , R) = \frac{s}{N}, $ 其中, s是R中与φ相配的部分元组的数量, N是关系R中的元组数. (2) 置信度 在很多情况下, 有一些在支持度集中的元组在导因X处相同, 但是在结果A处不相同.可以考虑每种不同的导因值单独地属于支持度集.可以将一个(完全实例化的)先行x作为一个组相关联的行集合, 或者可以叫做“x组”.为了满足CFD, 每个组中的所有行必须具有相同的结果值. 下面我们定义关系R的一个条件函数依赖的置信度:Cφ(R), 它是可以保留的支持度集的最大分数, 因此在删除所有其他行之后, 支持度集的其余部分满足嵌入的函数依赖. 不失一般性, 我们可以将关系R看做一个或多个行的集合ri=(xi, yi), 其中, xi∈X是导因值, yi∈Y是结果值, 并且其他的属性都不需要予以考虑.定义关系R中的总元组数为N.定义Nx为