不一致弱可用数据的近似查询处理研究

来源 :哈尔滨工业大学 | 被引量 : 1次 | 上传用户:jievons
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
数据质量是数据分析结论有效性和准确性的基础,也是最重要的前提和保障。造成数据质量问题的因素有很多,数据不一致性是其中的一个重要方面。在现实世界中,由于网络的普及,应用可以从多个数据源集成数据,使得不一致数据传播愈演愈烈。不一致数据给数据查询处理带来严重挑战:数据不一致导致查询结果不准确。目前,不一致数据查询处理主要包括两种方法:一是根据质量规则检测并修复不一致数据,之后在修复数据上执行查询。第二种方法直接在不一致数据上计算满足所有可能修复的查询结果。显然,由于修复具有多种可能,第一种方法并不能保证修复的正确性;第二种方法可能丢失大量可用信息。本文将不一致数据中可矫正的不一致信息修复之后,得到存在不一致且不一致不可被正确修复的不一致弱可用数据。之后对不一致弱可用数据的查询处理展开研究。主要研究工作如下:  首先,本文研究了不一致弱可用数据上近似查询的可行性判定问题。给定一个查询结果的一致性程度阈值,可行性判定判断弱可用不一致数据上查询结果的一致性程度是否大于给定的阈值。若不是,则查询结果对用户来说是没有意义的,此查询不可行。对于数据量大,查询开销较大的应用中,若能在查询之前预估查询结果的准确度,将在很大程度上节省查询开销,提高查询效率。尤其在查询密集型场景,判定查询的可行性具有重要的意义。查询可行性的判定等价于预估查询结果的一致性。本文采用抽样方法预估查询结果的一致性。抽样算法分别对一致的数据部分和不一致的数据部分采样,使得保证抽出的样本大概率下满足查询条件并且服从不一致数据的分布。根据抽出的样本,本文给出了估计一致性程度的方法,证明了一致性程度的估计是渐进无偏的。  其次,本文研究了不一致弱可用数据上合取查询结果的评估问题。一个不一致数据集合可能有多种修复。一致性查询结果指的是查询结果中的每一条记录都出现在对所有的修复进行查询的结果中。然而,数据的所有修复具有指数级可能空间,即使只考虑主键约束,一致性查询也是CoNP-完全问题。更重要的是,不一致数据中也可能包含着用户需求的信息,只返回一致性查询结果丢失了查询相关的有价值数据,返回的结果可能并不能满足用户需求,但是返回全部结果又使用户对查询的准确度没有了解,从而造成错误认知,做出错误决策。因此,本文考虑,返回所有查询结果,并给定查询结果的一个一致性估计,使得用户获得查询结果的一致性程度,了解查询结果的总体特征。对于可一阶改写的查询,其结果的一致性程度可以通过改写查询计算出的结果和原始查询结果直接获得。对于不可一阶改写的查询,本文使用抽样方法给出了近似一致性判定,并证明了其一致性的估计是一个(ε ,δ)估计。  再次,本文研究了不一致弱可用数据上的聚集查询。不同于传统数据上的聚集查询,不一致弱可用数据一致性修复的不确定性使得不一致弱可用数据上的聚集结果是不确定的。由于修复可能是指数级的,若聚集操作返回所有修复下可能的值将会给用户带来很大的信息干扰。本文返回所有可能修复下聚集查询结果的范围,即聚集结果可能值的最小上界和最大下界。文中考虑MAX , MIN ,SUM ,COUNT ,AVG 五种操作类型,分析了五种操作类型范围计算的时间复杂度,对于不可在多项式时间内计算的上下界,给出了相应的近似算法。  最后,本文提出了一个不一致弱可用数据查询处理的原型系统EntityManager。导致不一致信息出现的一个常见因素是现实世界中一个实体在不同数据集中可能有不同描述形式,或者随着时间迁移,同一实体的信息发生了变化。目前处理方法主要采用实体识别技术将这些描述同一实体的元组识别出来,然后进行修复,找到一个能够代表实体各个属性的最可能值表示实体。但在实际应用中,一个实体的某一属性的值可能并不是唯一的,上述处理方法造成了可用信息的丢失。基于此,EntgityManager系统这些描述同一实体的信息组织起来:对于属性的所有可能值,根据其出现的频率定义一个质量度,组成一个实体单元,将这些实体单元作为基本存储单元存储在系统中。由于属性值的多值及其携带质量度的特征,EntgityManager系统中的查询不再是精确查询,本文为EntityManager系统定义了新的查询操作,设计了类似于SQL的新的查询语言,并研究了适用于新的查询操作的查询算法以及查询优化。
其他文献
该论文的主要研究内容是能够适用于城域网或小区网环境的视频点播和信息管理系统.传统的电视系统信息单向传送,用户只能被动接收.而VOD是以"选择控制权在用户"的崭新概念为基
一般而言,星形计算机局域网(LAN)中心结点只有一条通道,形成所谓的单星LAN,而多星LAN的中心结点由多条通道构成。与单星LAN相比,多星LAN相当于由多个单星LAN形成。 关于多星LAN
实现网络入侵检测与防御系统离不开具有数据包捕获和过滤功能的软件工具包。 本文首先比较了具有代表性的包过滤机制如CSPF(CMU/Stanford Packet Filter)和BPF(Berkeley Pa
数据的存储和处理一直都是信息系统的中心,而数据集成则是信息系统研究的经典问题.随着信息集成的飞速发展,产生了越来越多的异构数据源,这些数据源在语义和模式上都互不相同
随着软件技术的不断发展,开发者和用户对于软件质量提出了更高的要求.为此,软件开发者试图从技术、管理等各层面控制软件开发过程,提高软件产品的针对性和可靠性,保证软件对
无线传感器网络作为一个智能信息系统,在很多领域都有着重大的应用前景。但是由于传感器节点本身的资源限制,诸如能量、带宽、处理能力,使得其应用设计面临着很多挑战。降低网络
随着计算机技术得不断发展,特别是网络技术的发展,企业信息系统和以往相比,也有了巨大的进步.企业级的应用不再满足于单机系统和简单的客户/服务器系统,而是向着三层或多层体
多小波理论是小波理论的新发展,多小波能同时拥有正交性、对称性、紧支撑性和高阶消失矩等特性,理论上优于传统的单小波;与L~2[R]上的多小波相比,定义在L~2[0,1]上的区间多小波能
随着Internet技术的发展,以B/S结构为基础的新型管理信息系统,以其零客户端、易维护性、分布性等优点成为了企业应用系统的主流.在信息化发展过程中,企业积累了大量数据,并为
随着信息技术的发展,"信息化带动工业化,工业化促进信息化"[1]己成为我国的战略任务.工作流技术是实现企业业务过程建模、业务过程优化、业务过程管理与集成,从而最终实现业