论文摘要
近年来，劣质数据广泛出现于信息社会的各个领域，引发了很多问题并带来了巨大损失。关注该问题的数据可用性研究在国内外已经展开。实体同一性是数据可用性的重要维度之一。实体同一性基于数据库中存储的数据实体和现实世界中的物理实体定义。一个数据实体描述的是某个物理实体，是其在数据库中的表示形式；一个数据库被称作是满足实体同一性要求的，当且仅当数据库中没有任何两个数据实体描述的是同一个物理实体。对数据实体同一性的研究是当前数据处理领域的热点研究问题之一。针对关系数据的实体同一性研究已经有很多工作，然而，其中大部分的理论和方法并不适用于非关系数据，并且很难扩展到非关系数据上。针对非关系数据的实体同一性研究工作还很少，尚处于起步阶段。本文针对一类广泛使用的非关系数据，即XML数据，以完善XML数据可用性的管理技术为目标，从XML实体抽取、XML实体匹配以及实体匹配结果消解等问题切入，重点研究了XML数据实体同一性相关的技术。本文的主要工作可以概括如下：首先，本文提出并研究了XML数据上的实体抽取问题，提出了一种基于规则的实体自动抽取方法KEE。XML数据中没有实体的明显标识，且现有的实体同一性研究工作并没有考虑实体抽取问题，因此实体抽取是XML实体同一性研究的基础之一。提出的KEE方法利用XML查询描述实体，为实体提供了简洁的表示方法，避免了逐一表示XML实体的不便；允许用户利用键规则只描述感兴趣的少量实体，并自动地为用户寻找感兴趣的其它实体；利用查询松弛技术，克服了在异构数据上自动寻找相似实体时实体难以枚举、难以寻找的困难；基于自动机技术，利用共享中间计算结果的思想，实现了高效的XML数据实体抽取算法。从理论角度分析了KEE方法的性能，并用实验验证了该算法能够有效且高效地解决实体抽取问题。第二，本文研究了XML实体匹配问题，以提高XML实体匹配效率为目标，提出了基于哈希方法的XML实体匹配算法。给定实体间的相似函数，实体匹配是要找出所有相似函数值大于某个阈值的实体对，是检测数据实体同一性错误的重要基础。XML实体匹配要同时处理数据中结构和内容两部分信息，现有的技术仅关注内容之间的相似性，无法高效解决XML实体匹配问题。提出的基于局部敏感哈希的实体匹配方法把相似的实体以很高的概率映射到一个分组，仅两两计算同一分组内实体的相似函数值，大大提高了实体匹配的效率；考虑不同应用，抽象出三类实体相似函数定义，证明三类函数均具备局部敏感特性，并给出对应的哈希策略；基于三类函数的局部敏感哈希策略，给出了对应的实体匹配算法。从理论角度分析并证明了算法的有效性，并用实验验证了匹配算法的实际性能。第三，本文研究了实体匹配结果的消解问题，以求解更具意义的消解方式为目标，提出了两种形式化问题定义，并分别给出理论分析及算法。实体匹配的最终目标是解决实体同一性错误检测问题，即实体识别问题。将实体匹配结果转化为实体识别结果的问题就是实体匹配结果消解问题。本文基于融合多个匹配算法以及对不同实体对的匹配结果置信度不同的思想，形式化地定义了两种消解问题。针对最小化图代价的定义，从理论上证明了消解问题是NP完全问题；利用线性归约，给出近似算法；针对特殊情况，给出近似比更优的算法。针对最小化边权值的定义，证明该问题是NP完全问题；给出基于求解线性规划的近似算法；针对特殊情况，给出具有更优近似比的随机近似算法；针对大规模数据的情况，给出了四种启发式算法；用实验验证算法的性能，并对比不同算法的时间效率。最后，本文针对提出的实体抽取方法和匹配结果消解方法的不足，研究了两个相关的优化问题，分别从理论角度进行了分析。本文给出的实体抽取方法基于语义规则，但在某些应用中，用户无法给出规则。因此，本文以探究基于用户示例自动推断规则的可行性为目的，形式化地定义了XML查询学习问题。考虑四类不同查询，从理论角度分析其对应学习问题，对可解问题给出了多项式时间算法，对难解问题给出了复杂性证明并进一步分析其是否存在有效的近似算法。针对最小化图代价匹配结果消解问题，本文给出的近似算法的近似性能无法满足实际需求。因此，本文以近年来兴起的参数化复杂度理论为工具，研究该问题是否固定参数可解。给出了该问题的三种参数化定义，针对其中两个问题给出了有效的固定参数算法，并证明了另一个问题是固定参数难解的。