论文部分内容阅读
数据质量是数据分析结论有效性和准确性的基础,也是最重要的前提和保障。造成数据质量问题的因素有很多,数据不一致性是其中的一个重要方面。在现实世界中,由于网络的普及,应用可以从多个数据源集成数据,使得不一致数据传播愈演愈烈。不一致数据给数据查询处理带来严重挑战:数据不一致导致查询结果不准确。目前,不一致数据查询处理主要包括两种方法:一是根据质量规则检测并修复不一致数据,之后在修复数据上执行查询。第二种方法直接在不一致数据上计算满足所有可能修复的查询结果。显然,由于修复具有多种可能,第一种方法并不能保证修复的正确性;第二种方法可能丢失大量可用信息。本文将不一致数据中可矫正的不一致信息修复之后,得到存在不一致且不一致不可被正确修复的不一致弱可用数据。之后对不一致弱可用数据的查询处理展开研究。主要研究工作如下: 首先,本文研究了不一致弱可用数据上近似查询的可行性判定问题。给定一个查询结果的一致性程度阈值,可行性判定判断弱可用不一致数据上查询结果的一致性程度是否大于给定的阈值。若不是,则查询结果对用户来说是没有意义的,此查询不可行。对于数据量大,查询开销较大的应用中,若能在查询之前预估查询结果的准确度,将在很大程度上节省查询开销,提高查询效率。尤其在查询密集型场景,判定查询的可行性具有重要的意义。查询可行性的判定等价于预估查询结果的一致性。本文采用抽样方法预估查询结果的一致性。抽样算法分别对一致的数据部分和不一致的数据部分采样,使得保证抽出的样本大概率下满足查询条件并且服从不一致数据的分布。根据抽出的样本,本文给出了估计一致性程度的方法,证明了一致性程度的估计是渐进无偏的。 其次,本文研究了不一致弱可用数据上合取查询结果的评估问题。一个不一致数据集合可能有多种修复。一致性查询结果指的是查询结果中的每一条记录都出现在对所有的修复进行查询的结果中。然而,数据的所有修复具有指数级可能空间,即使只考虑主键约束,一致性查询也是CoNP-完全问题。更重要的是,不一致数据中也可能包含着用户需求的信息,只返回一致性查询结果丢失了查询相关的有价值数据,返回的结果可能并不能满足用户需求,但是返回全部结果又使用户对查询的准确度没有了解,从而造成错误认知,做出错误决策。因此,本文考虑,返回所有查询结果,并给定查询结果的一个一致性估计,使得用户获得查询结果的一致性程度,了解查询结果的总体特征。对于可一阶改写的查询,其结果的一致性程度可以通过改写查询计算出的结果和原始查询结果直接获得。对于不可一阶改写的查询,本文使用抽样方法给出了近似一致性判定,并证明了其一致性的估计是一个(ε ,δ)估计。 再次,本文研究了不一致弱可用数据上的聚集查询。不同于传统数据上的聚集查询,不一致弱可用数据一致性修复的不确定性使得不一致弱可用数据上的聚集结果是不确定的。由于修复可能是指数级的,若聚集操作返回所有修复下可能的值将会给用户带来很大的信息干扰。本文返回所有可能修复下聚集查询结果的范围,即聚集结果可能值的最小上界和最大下界。文中考虑MAX , MIN ,SUM ,COUNT ,AVG 五种操作类型,分析了五种操作类型范围计算的时间复杂度,对于不可在多项式时间内计算的上下界,给出了相应的近似算法。 最后,本文提出了一个不一致弱可用数据查询处理的原型系统EntityManager。导致不一致信息出现的一个常见因素是现实世界中一个实体在不同数据集中可能有不同描述形式,或者随着时间迁移,同一实体的信息发生了变化。目前处理方法主要采用实体识别技术将这些描述同一实体的元组识别出来,然后进行修复,找到一个能够代表实体各个属性的最可能值表示实体。但在实际应用中,一个实体的某一属性的值可能并不是唯一的,上述处理方法造成了可用信息的丢失。基于此,EntgityManager系统这些描述同一实体的信息组织起来:对于属性的所有可能值,根据其出现的频率定义一个质量度,组成一个实体单元,将这些实体单元作为基本存储单元存储在系统中。由于属性值的多值及其携带质量度的特征,EntgityManager系统中的查询不再是精确查询,本文为EntityManager系统定义了新的查询操作,设计了类似于SQL的新的查询语言,并研究了适用于新的查询操作的查询算法以及查询优化。