随着大数据时代的到来,数据质量的重要性日益凸显。信息数字化过程中的种种错误,导致了数据库中的信息无法反映真实世界的完整面貌。当前的众多报告表明不完整数据会引起计算结果的偏差,进而对商业的决策和民众的生活造成广泛的不良影响,给查询的处理带来了挑战。因此设计不完整数据上的高效的查询处理技术,对弱可用数据进行有效使用至关重要。当前的数据可用性领域对于不完整数据上的查询处理的研究缺乏体系,这方面的研究面临极大的挑战。首先,缺乏统一的数据完整性评估模型,无法给出数据集合完整程度的真实评估结果。其次,面对无法修复全部缺失值的数据集合时,当前缺乏根据用户的需求,在查询结果中给出尽可能完整的信息的方法。第三,在不完整数据集合上,同时考虑完整信息程度和聚集目标时,当前缺乏在一定的质量误差条件下,给出高质量的查询结果的方法。第四,当前缺乏快速地估计查询结果的完整程度的方法,无法根据不完整数据的完整性特征,给出估计结果。为了有效地应对上述由不完整数据带来的挑战,在本文中,尝试在不进行数据修复的情况下,根据关系型数据的特点,提出不完整数据上的查询处理技术,提供具有较高完整性的查询结果,提出一系列的理论和对应的高效算法,解决了不完整数据上查询处理的一些关键问题,主要的研究内容可以进行如下概括。(1)在本文中,研究了数据完整性的评估模型和算法。为了克服当前对完整性的评估依赖具体查询,低估了数据中的有效信息含量的局限性,形式化地定义了基于函数依赖的数据完整性评估模型。这个模型可以从属性、元组和关系三个粒度,来度量所包含信息的完整程度。进而形式化了在此模型下的数据完整性评估问题,给出了这个问题的时间复杂性下界。然后,给出了结合函数依赖特点,用于完整性评估的完整性伪闭包。通过分析完整性伪闭包的性质,建立了完整性传播图来评估数据完整性。基于完整性传播图,给出了达到问题下界的高效评估算法。最后在真实数据集合与合成数据集合上的实验验证了算法的有效性和高效性。(2)在本文中,研究了基于支配集合的不完整数据的查询处理问题,并给出了高效的处理方法。当数据中的缺失值无法被修复,或者修复算法耗时较长时,可以根据用户的需求,选择一个完整程度较高,在用户感兴趣的属性上给出完整信息,并且规模较小的子集合,这个子集合被称为支配集合。基于这个集合,可以有效地处理查询,高效地给出查询结果。本文首先形式化了支配集合的选择问题,证明了其判定版本是一个NP-完全问题;其次,设计了高效的支配集合选择算法,通过理论分析,证明了所抽取的数据集合的良好性质。然后,基于支配集,给出了进一步处理查询的方法。最后,通过真实数据和合成数据上的实验,验证了所提出的方法的有效性和高效性,并研究了不同参数对于算法的影响。(3)在本文中,研究了带有完整性约束的不完整数据的查询处理问题,并给出了高效的处理方法。在不完整数据集合上,查询结果往往无法包含足够的信息。为此,提出了一种适用于不完整数据的查询结果的形式。在一定的质量误差范围内,对于返回的查询结果,既能在某些用户感兴趣的属性上给出较完整信息,又能在整体上近似地满足聚集性质,使之成为一个高质量的整体。首先,形式化地定义了这一问题,并证明了其判定版本是一个NP-完全问题。然后,根据用户是否明确地给出对于元组的选择策略,分别基于贪心策略和加权抽样方法,设计了两个多项式时间的近似算法。对于两个算法的时间复杂性,以及所给出的查询结果的质量给出了理论分析和证明。最后,通过实验验证了所提出的两个近似算法能够高效地给出高质量的查询结果,并且两个近似算法具有良好的可扩展性。(4)在本文中,研究了不完整数据上查询结果的完整性估计问题,并设计了高效的估计算法。当前缺乏对于整体数据集合的完整性信息的刻画方法,可以通过抽取一个反映整体数据集合的完整程度的特征数据集合,来进行查询结果的完整程度估计。为此,提出了特征数据集合应有的两条性质:覆盖性和完整度,分别从属性和属性值角度,给出了对于数据集合所容纳的完整信息的衡量。为了满足这两条性质和不同的需求,定义了6类不同的完整性特征数据集合,证明了上面6类特征数据集合的抽取问题的判定版本都是NP-完全问题;然后,设计了优化解规模猜测策略和误差分配策略,来充分利用不同完整程度的元组,近似地满足以上两个重要的性质。基于均匀抽样和上述策略,给出了抽取完整性特征数据集合的近似算法,它能在多项式时间内,高效地抽取近似满足这两个性质的特征数据集合。然后基于抽取的完整性特征集合,给出了高效的完整性估计的方法。通过理论分析,证明了估计算法具有良好的性质。最后,通过真实数据集合与合成数据集合上的实验,证明了所提出的完整性估计方法,能够高效地估计查询结果的完整程度。