各应用领域信息量爆炸性地增长带来了大量的劣质数据。数据质量低劣经常导致灾难性后果,极大地限制了数据的正常使用。数据的劣质性概括性地表现为数据的不一致性、不准确性、不完全性和非时效性等等,而其中不一致数据是最典型的劣质数据。改善不一致性数据对于为提高数据可用性,确保大规模数据的正常使用有着十分重要的意义。然而已有的基于数据依赖规则描述数据一致性的处理方法发展还不够完善,并且这种方法本身还有着很多固有的缺陷,主要有以下几点:第一,一致性规则只能用于检测不一致错误,但并不能给出数据不一致程度的直观评估;第二,一致性规则不能指导修复,仅基于规则的自动方法不能保证完全地修复不一致数据;第三,人工很难定义出足够的一致性规则以充分检测数据的一致性错误。本文对不一致关系数据的评估、修复、查询、规则挖掘等方面中的关键问题给出了一些列的计算复杂性和算法研究结果,分很好地决了上述问题,主要研究内容如下所述。(1)本文研究了数据一致性规则发现算法。为了克服挖掘严格的函数依赖和条件函数依赖的局限性,以及不好的松弛导致的大量无效冗余规则,本文在第二章研究了如何定义松弛规则以及如何从更一般的数据中挖掘他们。本文提出了从更一般的概率数据中挖掘出近似条件函数依赖的方法,由于概率数据可以视作一般数据的泛化,因此从概率数据中挖掘候选规则可以提高挖掘能力,适配更广泛的数据类型、提供专家用户更充分的参考规则,同理我们定义了近似条件函数依赖是松弛的,使得挖掘结果质量可控。在此基础上,本文研究了其在不确定数据中的置信概率的动态规划求解算法,以及候选依赖的概率下界来进行剪枝;给出了基于字典序的挖掘方法以及相应的剪枝策略;最后,在真实和合成的数据集上进行充分的实验以验证挖掘算法的可扩展性和剪枝策略的高效性,发现真实的挖掘结果,极大地提高了数据一致性的发现能力。(2)本文研究了数据一致性评估问题的计算复杂性和评估算法。为克服当前不能很好地评估数据一致性的缺陷,避免局部计数的失真问题,本文在第三章提出通过最小元组删除集规模来评估数据的不一致程度。在此基础上研究了当给定规则集合的结构复杂程度对问题的计算复杂性的影响。本文证明了当Σ包含2条仅涉及3个属性的变量条件函数依赖、且每条元组最多仅涉及6个冲突对时,最小元组删除集问题仍然是NP完全;进而又证明了当给定3条仅涉及4个属性的变量条件函数依赖时,将最小删除集问题近似到1716是NP难的。本文给出了最小元组删除集问题的近优化的近似算法,可以达到2-12r的近似比,其中r为集合Σ中变量条件函数依赖个数,显然这是一个独立于数据量的、很好的近似比,因为条件函数依赖集合Σ通常规模远远小于数据量且固定。本文进一步说明了在UGC假设下,该近似比是近优化的,很难再将近似比降低一个与n无关的常数。本文通过实验验证了本文给出的评估算法具有非常好的准确度,验证了前述的理论结果。(3)本文研究了基于反馈的不一致数据修复问题计算复杂性和修复算法。对于不一致数据的修复,自动的修复方法具有严重的局限性,数据质量研究领域达成的共识是,引入人工反馈是得到高质量修复的一个重要的环节。然而已有的工作都基于三个假设:人工提供的回答认为是正确的,且可以直接使用;人工提供的回答都可以直接向数据传播,无副作用;给定规则一定是正确的。这种假设在很多实际情况中是不合理的。因此,本文在第四章针对如何解决人工反馈的正确性保障问题,形式化地定义了两个判定问题,即约束规则定义的不一致数据中的视图删除和插入传播问题,同时研究了两个问题的计算复杂性和数据修复算法。本文研究了不一致数据上视图删除问题的复杂性,证明了如果查询为一个投影或者并查询时该问题为NP完全的,证明了当查询为一个合取查询时该问题是Σp2完全的,同时也证明了然而当查询是一个选择连接查询时,该问题的联合复杂性是LOGSPACE的,同时这个结论意味着一般的无副作用删除传播问题在组删除情况下,其联合复杂性也是在LOGSPACE的,这填补了一般的删除传播问题复杂性结果中的空白。本文提出了基于删除反馈的高效修复算法。本文也证明了不一致数据上视图插入问题在单插入与组插入、有限域与无限域等情况下的数据复杂性与联合复杂性结论。证明了对于不同类别的查询,该问题的数据和联合复杂性均位于PTIME与Σp2完全之间。不同于删除反馈,本文证明了不一致数据上视图插入问题会变得更难。本文在数据复杂性下分离出了一大类多项式可解情况,即无自连接的选择连接查询类sjf-SJ,提出了高效求解算法,通过实验验证了本文提出的修复算法极大提高了精确率和召回率。(4)本文研究了不一致数据查询处理算法。为了克服一致性查询回答方法对结果约束太过苛刻的不足,本文在第五章采用不确定概率数据来建模不一致数据,并通过可能世界的概率阈值来定义查询结果的质量,从而保证了在尽可能多给出带有自定义质量保证的查询结果。基于此,本文进一步研究了这种方法在广泛存在且研究较少的空间不一致数据上的应用,利用空间数据的地理相关性和局部性的特点来加速查询回答。以较为复杂的局部相关空间不一致数据为典型范例,给出带有概率阈值保证的频繁近邻查询结果。本文提出了一般的处理框架,包括对于概率质量函数的动态规划算法以及阈值过滤方法,很好地解决了应用现有的基于传统数据和基于不确定数据上的近邻查询算法直接处理这种查询会产生昂贵开销的问题,并在人工的和真实的数据上都进行充分地实验以验证算法的有效性和高效性。