有质量保证的清洗不确定数据

1、有质量保证的清洗不确定数据内容摘要 不确定或不精确的数据在应用中普遍存在，像基于位置的服务，传感器监控及数据的采集和整合。对于这些应用，概率数据库可以被用来存储不确定的数据，提供的查询设施用于产生统计置信度。假设一个有限的资源可用来“清洗”数据库（例如，通过探测一些传感器数据值来获得他们最新的值），我们要解决清洗不确定对象集的选择问题，为了在查询答案时达到最好的质量改善。为此，我们提出PWS-quality指标，这是一个普遍的措施，是在可能世界的语义下量化查询答案的模糊性。我们研究PWS-quality指标如何被有效的评价，主要有两个等级：（1）审查元组与其他元组之间相互独立的可满足性的查询（

2、例如，范围查询）;（2）需要的一系列相关联的元组知识的查询（如最大查询）。然后，我们提出了一个多项式时间的解决方案，以达到在PWS-quality指标中最优的改善。也将提出其他快速启发式算法。在实验中，表现出实际和综合的数据集，表明该PWS-quality标准的评估可以很快，而且我们的清洗算法提供了一个高效率的最佳解决方案。据我们所知，为概率数据库开发质量标准是第一个工作，然后探讨这个标准如何用于数据清洗。关键词：不确定数据；数据库；PWS-quality指标；质量改善；清洗算法1 导言传统上，数据库假定数据存储的值是准确或精确的。但是，在许多新兴的应用程序中，数据库本身存在不确定性。考虑一个

3、栖息地监测系统，其中的数据，如温度，湿度和风速是从传感器获得的。由于传感器性质的不完善，所获得的数据通常含有噪声污染。再举一个例子,在全球定位系统(GPS)中，定位值的收集有一些测量误差。在生物特征数据库，存储的特征向量的属性值是不准确的。综合与记录联动工具也会使置信度的值与根据匹配质量输出的元组联系在一起。为了应付处理不确定性日益增长的需要，研究人员最近提出将其不确定性看作一个“一等公民”， 通过一个“不确定数据库”管理数据。在这些数据库中，查询可以进行评估，以产生有概率保证的不精确的答案。查询答案的模糊性构成了查询质量的概念，它描述了查询答案是“多么好”。在本论文中，我们就如何通过减少模糊

4、数据库的方法来提高查询质量的问题进行分析。不精确的数据可以以不同的方式得到缓解。例如，在传感器监测中的应用，数据库系统是用来存储在一个地理区域部署的成千上万个传感器的当前值。由于资源有限，系统可能无法捕捉到在每一个时间点的传感器信息；相反，它使用存储的值来估计当前传感器的读数。为了减少估计的误差，系统可以“探测”传感器，这是对系统最新估值的响应。再举一个例子，考虑一个电影评级的数据库，是一个基于把IMDB电影信息和从Netflix挑战中得到的用户评级相融合的数据库。该数据库包含了每部电影的用户评级，可描绘出一个概率分布表。澄清这些等级的不确定性可以通过联系各自的用户来 “消毒”。由此产生的数据

5、库，不确定性比以前少，而且可以提供更高质量的服务。理想的情况下，整个数据库都应该被清洗。事实上,这可能是不可行的,因为清洗数据是很昂贵的。例如，一个传感器监测系统，可能只探测传感器的一小部分，部分原因是由于无线网络带宽有限，部分是由于传感装置稀缺的电池电源。至于电影评级数据库，困难的可能是验证电影评级中涉及的所有的用户评级。一般来说，清洗操作是受限制的，例如，通过一个固定的“预算”，它描述了可用于投资清洗数据的最大努力量。对于一个传感器监测系统的清洗预算，可以是传感器探测使用的最大带宽量。对于电影评级数据库，这样的预算可以是考虑验证电影评级需要工时的最大数值。在本论文中，我们要解决在有限的预算

6、下，为达到更好的查询或服务质量目标，清洗不确定数据的问题。尽管不确定数据库的清洗具有重要性，但相对较少的工作已经完成。我们的主要想法是利用查询的信息来决定要被清洗的数据项的设置。通过对这些数据的操作，返回给用户的答案质量可以达到最高改善。我们在概率数据库的基础上开发我们的解决方案，这是一种被广泛研究的不确定性数据的模型。，我们面对的主要挑战包括：（1）通过查询结果定义一个健全的综合的质量标准；（2）制定有效的方法来计算这个指标；（3）制定有效的和最佳的清洗算法。为了说明这一点，图1显示了一个概率数据库报价关系，其中通过使用从网页收集而来的某一匹配的自动模式方法，存储了四个产品的价目（带有ID的

7、a，b，c和d）。所谓的存在概率（缩写为Prob）的属性是用来注明每个元组存在的置信度。一个元组也与一个“x -元组”相联系，这个“x -元组”表示一个分配方案的替代选择。例如，产品a有0.7的机会提供一个120美元的价格，并且有一个0.3的机会提供80美元的报价。现在考虑一个最大查询：“返回元组的最高价格。” 由于数据不准确，这个查询可以产生不准确的答案。表2显示了查询的结果，它包含了元组ID和作为正确答案的非零概率（或条件概率）。产生的有统计保证答案的这些查询，一般被称为概率查询。表1 不确定的数据库实例表2 在表1中进行最大查询的结果 在概率结果的基础上，为捕捉一个查询结果的模糊程度，可

8、以定义一个 “质量分数”的实数值。例如，在最大查询的查询结果（见表2）分数为-1.73（根据我们的质量指标）。假设表1是部分清洗（例如，通过咨询公司的有关产品的实际价格）。表3显示了一种可能的情形，其中不确定性与x -元组相关的a和c都被删除。在此表中，每一个a和c只有一个元组存在，这个元组的存在概论等于1。最大查询的新结果显示在表4，具有较低的模糊性，或得出了一个改进的质量分数-0.97。在极端情况下，如果所有的x -元组被清洗过，质量分数最高（我们的质量标准值为0）。表3 对表1部分清洁的实例表4 对表3进行最大查询的结果这样的查询质量标准应该如何定义？尽管之前提出一些质量措施，但他们要么

9、提供特定的查询，要么没有为概率数据库的使用做设计。为了解决这些问题，我们提出了PWS-quality指标。这个度量标准提供了一个查询概率数据库的查询质量（即可以被任何查询使用）的通用方法。它实际上是一种熵函数，它很方便地返回一个实数值分数，表示在查询答案中不精确的数量。PWS-quality标准也是使数据高效清洗的解决方案，我们也将在本论文中显示。PWS-quality标准的另一个显著特点是，它假设了可能世界语义学（或简称PWS）。PWS提供了对一个正式的概率数据模型的诠释，在这个模型中一个数据库被看作是一种确定性数据库实例集(称为可能世界），每个实例都包含了从每个x -元组中提取的元组集。表

10、1的一个可能世界例子包含了元组a1，b2，c3，d1。概率数据库查询评价算法应遵循PWS的概念，即产生的结果应该是与在所有可能世界上的查询评价相一致的。类似地，PWS-quality指标分数是从所有可能世界获得的查询结果中计算得来的。朗读一个关于PWS-quality指标明显的问题是，它的计算效率很低。这是因为评估这一措施要求检查所有的可能世界，数量可以以指数增大。有趣的是，我们观察到，不是经常需要检查所有的数据库实例； 事实上PWS-quality指标的计算是通过使用返回给用户的查询答案。这是作为一个以实体为基础的查询而广泛熟知的一类查询。这种类型的查询满足了返回给用户包含元组ID的最后答案

11、，以及其条件概率（例如，表2）。我们研究两个实体查询的代表性的例子，即范围查询和最大查询。两种查询都在许多应用中被使用。例如，在一个传感器监测中的应用，可以查询的范围是：“返回温度值在10，20的传感器的ID”。在电影数据库中，最大查询可以是：“返回观众评价最高的电影ID”。我们发现，这两个查询的PWS-quality标准，可通过查询答案信息快速计算出来。我们的方法是有效的，因为一个查询答案可以通过现有的查询评估和索引算法有效地被保证，而且我们的技术复杂性是与查询答案的大小成线性关系的。PWS-quality指标也可作为数据清洗问题的有用工具。给定要清洗的x-元组集，我们证明PWS-quali

12、ty指标的预期值总是单调递增的。这有助于我们制订数据清洗问题，如：选择x-元组的子集X，使得（1）在X中清洗x-元组的预期质量改进是最高的；及（2）清洗X的总成本不超过给定的预算。这个问题是有挑战性的，因为计算X的预期质量改善需要在X中的所有元组的组合。此外，找到最佳X集要求对数据库中x-元组的不同组合测试，呈现一个指数时间复杂度。为了解决这些问题，我们把PWS-quality表达转换到一个“x-形式”中 x-元组概率信息的一种线性函数。x-形式使我们非常容易地计算出清洗x-元组集的预期质量改进。除此之外，范围查询和最大查询有相同的格式（具有不同的参数），所以支持两种查询只需要有一个唯一的解决

13、方案。要找到没有从整个数据库测试的所有x-元组组合的最佳解决方案，我们发现，选择x-元组是唯一必须的，即出现在查询答案中的元组。然后，我们模拟作为优化问题的清洗工作，并开发一个基本动态编程算法，以推算出多项式时间中x-元组的最优集。我们也建议用其他近似的启发式(如贪心算法)。我们的算法，同时服务范围查询和最大查询。他们也支持数据库包含相同属性值的元组。我们已进行详细评估，以检验我们的实验方法。结果表明对于既真实又综合的数据集，PWS-quality可以有效计算。此外，x-元组可以迅速选择实现预期质量的最优改善。其中启发式贪心算法，提供了一个具有最高效率近乎最佳的操作。图1说明了采用了我们的解决

14、方案的系统设计。，自接到用户的请求，查询引擎产生一个概率查询答案。此信息传递到质量经理。在这个模块里，质量评估计算PWS-quality分数。然后它会给数据清洗算法发送必要的信息，该算法可以在可用的预算范围内推导出要清洗（或“清洗集”）的x-元组的最优解集。清洗经理负责执行消毒活动（例如，索取选定的来源报告给其更新后的值）。当再次执行时，查询将在预期查询中有所改善，值得注意的是，质量经理是与查询引擎脱钩的，因为它只需要查询答案元组的概率信息。另一个问题是，PWS-quality分数也发送给用户。这种实值评级为用户提供一种直观的方式去了解答案的模糊程度，无需解释出现在查询答案中众多可能的概率值。

15、在本论文中，我们注重质量评估员的设计和数据清洗算法。朗读图1 我们解决办法的框架本文其余部分的组织如下。在第2节，我们提出了相关工作。第3节讨论了数据和查询模式。在第4节我们介绍了PWS-quality的正式概念，以及有效的评估方法。第 5节描述了以质量为基础的清洗方法和其他启发式。在第6节给出我们的实验结果。论文是在第7节结束。附录A中，我们详述为PmaxQ找到x-形式的证明。附录B介绍了针对清洗问题的动态规划算法。附录C中，我们还讨论了在一个被清洗的数据库中，查询如何可以有效地进行评估。2 相关工作查询不确定数据库。由于其简单和明确的语义，概率数据库模型已受到大量的关注。特别是对x-元组的

16、概念，已作为代表元组不确定性的正式模型被普遍采用。 Dalvietal表明，使用PWS概念的评估查询是低效的，因为一个可能世界的指数增长需要研究。因此，研究人员提出修改查询语义。举一个例子，不同变体的top- k查询有效解决方案的研究。另一个研究数据模型是“属性的不确定性”，其中属性值具有范围查询和概率分布函数的特点。对于这个数据模型，有效评估和索引算法已经被提出，包括范围查询，最近查询，最小/最大查询，轮廓查询和反向轮廓查询。数据不确定性有效查询算法的分类进行了研究。最近，一个基于PWS属性不确定性的正式模型已经被提出。在ULDB中，提出了一种结合了概率数据库和血统数据库的属性模型。虽然我们

17、的工作是以概率数据库为基础的，这个想法可能会被扩展，以支持其他数据模型。不确定性数据的质量指标。大量的质量措施也进行了研究。在文献10,14中,如果结果的条件概率高于用户自定义的阈值，那么查询结果将被认为是令人满意的。在文献29中，一个top-k查询的质量被包含在查询结果中的实际top-k值所赋予。在文献9中，为范围查询，最近查询，AVG和SUM查询定义了不同的指标。在这些工作中，质量指标是专为特定的查询类型定义的。另一方面，PWS-quality提供了质量的一般概念，即适用于任何类型的查询。因此，PWS-quality可以提供来自不同查询答案的质量的公平比较。另一个质量指标，所谓的查询可靠性

18、，在13,17中定义。然而，这个指标没有在概率数据库的情况中研究。另外，目前还不清楚如何将它们应用到数据清洗问题。清洁不确定数据。在文献6，14，21，25中，从资源流和传感器网络探测新鲜数据的方法被认为是有效的。在文献 18中，完整性约束用于清洗脏数据。在文献2中，作者检查了对不一致数据库的探测和重复元组的合并。为了补充这些工作，我们研究PWS-quality指标如何用于促进概率数据库的清洗。3 数据和检索模型我们现在描述概率数据模型(3.1节),这个查询的类型在本论文中已经研究过(3.2节)。3.1 概率数据库模型一个概率数据库D包含m个实体，被称为“x-元组”。我们用k表示第k个 x-元

19、组, k = 1,m。我们假定x-元组之间是相互独立的。每个x-元组是元组的集,代表了在x-元组内值的分布范围。D中总共有n个元组。每个元组有四个属性：(IDi, vi, ei, xi)。这里IDi是的一个唯一标识符, 是用于查询的实数值属性 (称为查询属性)。为了简单起见,我们假设是一维的,但是我们的方案一般可延伸到支持多维属性。属性是的存在概率,这个概率存在于现实世界。每一个元组属于x-元组之一,并且= k | k = 1,m,表示属于第k个x-元组。在相同的x-元组中,元组的存在是互相排斥的。我们也可以假定在同一个x-元组中所有元组的总和中,k等于1。如果小于1,我们从概念上增加一个“空

20、”的元组给k,它的查询属性值等于,并且存在概率等于1。这个空元组仅用于完整性的证明；他们实际是不存在的。举例来说，在表1中有四个x-元组(a、b、c、d)。“价格”和“概率”栏目代表查询属性和各自的存在概率。3.2 查询我们研究基于实体查询的两种类型：不以等级为基础的查询和以等级为基础的查询。在不以等级为基础的查询中，一个元组的条件概率是独立于其他元组存在的。例如，查询只涉及单个属于这一查询种类的元组属性。另一个好例子是范围查询：定义1 概率范围查询（PRQ）。鉴于闭区间a，b上，其中a，bR,并且ab，一个PRQ返回一组元组，其中为的条件概率，是上的非零概率。对于以等级为基础的查询，一个元组

21、的条件概率独立于其他元组的存在。此类例子包括最大/最小查询和最近查询。我们在本论文中研究最大查询。定义2 概率最大查询（PMaxQ）。PMaxQ返回一个元组集（ti，pi），其中为的条件概率，是当时, 的非零概率。虽然这两个查询返回的答案具有相同的形式，其PWS-quality分数是以不同的方式计算的，就像在下一节的说明。我们还将讨论在其他实体查询（例如，最近查询）中如何计算PWS-quality。表5显示了本文中所用的符号。表5 本论文中使用到的符号。现在让我们简单介绍一下如何有效地评估（未经咨询可能世界）PRQ和PMaxQ。PRQ通过检查每个元组就可以计算，并且测试其在区间a，b中是否有查

22、询属性。如果不存在，那么的条件概率必须为零。否则，其存在概率。这个满足PmaxQ的的概率可以为（1）它的存在概率（2）除了属于的x-元组以外没有一个元组值大于vi的概率。索引解决方案（如B-树和R-树）可以建立在查询属性上，以提高查询的性能。同样，像在第1节所述的，查询可能需要在清洗后重新进行评估。然而，这一轮查询评估可以更有效地完成。特别的是，只有在第一轮查询答案出现的x-元组中的元组的评价似乎需要加以考虑。我们在附录C中解释这些细节。4 PWS-QUALITY 质量指标 要理解这个指标，让我们回顾可能世界语义（PWS）如何用于评估一个查询。如图2所示，一个概率数据库扩展到可能世界集（步骤1

23、）。然后在每一个可能世界上发布查询，产生的答案，我们称之为PW-results（步骤2）。在第3步，与PW-results相结合产生最终的查询答案。例如，在表1中的可能世界中，其标识元组集W的ID为a1，b2，c3和d1。如果一个最大查询发布了价，W的PW-result为a1（它拥有最大的价格），概率为0.7 0.4 0.2 1 = 0.056。在最后的查询答案中，a1的条件概率等于概率总和，即a1是在所有可能世界的答案，即0.35。图2 PWS和PWS-QualityPWS-quality基本上是PW-results的函数（在图2中的步骤A计算）。因为计算PW-results的查询形式没有指

24、定，PWS-quality可应用于任何形式的查询。此方法的主要问题是可以有一个指数增长的可能世界，也就是PW-results。计算PWS-quality非常昂贵。为了解决这个问题，我们将指出PWS-quality如何通过使用元组信息在最后查询答案中被评估，而不是PW-results（步骤B），对于PRQ和PMaxQ。由于在查询结果集中的元组数目远远小于在可能世界中的数目，PWS-quality计算效率也比较好。我们现在在4.1节中研究PWS-quality的定义（即A步骤）。然后，我们在4.2节提出了一个更好的方法（即步骤B）。第4.3节和4.4节论述了对PRQ和PMaxQ新方法的证明。 4.

25、1 评价PWS-QualityPWS-Quality实质上是图2的步骤2中产生的PW-results的熵。设r1, . . . , rd是d的不同PW-results集。此外，设是为实际答案的概率（我们称为的PW-result可能性）。定义3 在数据库D上PWS-quality的一个Q查询被评估，S(D,Q)表示为：注意到log（）函数的基是2。此外，PW-result概率的和必须等于1。通过使用这一事实，并与熵函数比较，它可以证明PWS-quality（方程1）是对PWS-quality熵的否定值。熵，是一种很常见的用来测量信息理论文献中的不确定性的函数，就是采用这个函数量化查询答案的不确定

26、性。PWS-quality分数的范围值从-log d（即最模棱的答案）到0（即一个单PW-resul）。在这种方法下计算PWS-quality的问题是，我们需要知道所有的PW-result概率。这可能代表一个性能瓶颈，因为从可能世界中导出得到的PW-result概率的数量可以成倍扩大。这才是真正的PRQ，每个PW-result包含一个独特的元组集，其查询属性正在查询范围内。对于PMaxQ，如果超过一个元组包含相同的查询属性值，PW-results的数量也可以组合。例如，在表1中，元组b1和c2的有相同的价格（即110美元）。然后，我们有PW-results为，其中包含一个或多个作为答案的这些元

27、组（即b1，c2，b1和c2），来自可能世界里110美元以上价格的所有元组并不包括在内。让我们研究这些查询如何有效地评价PWS-quality。4.2 PWS-Quality的x-形式PWS-quality其实都可以使用查询答案中的元组的概率信息计算出来（图2步骤B）。特别的是，PWS-quality（无论PRQ和PMaxQ）可转换为x-形式的表达式。x-形式，本质上是一些评价每个x-元组k的g函数，并且g可以在k中以元组概率信息为基础有效地进行计算。为标记方便起见，我们采用Y（x）来表示函数x logx。我们还令作为k的条件概率（即它满足查询的概率）。由于属于X -元组的元组是相互排斥的，我

28、们有下面的公式提出了一种PWS-quality的替代方案。定理1 PWS-quality的x-形式的提出由:对PRQ,对于PMaxQ，令k的第i个元组为，按递减顺序排序。如果的存在概率和条件概率，那么， 这时有 定理1规定，PWS-quality是一些g函数的总和，对于k = 1, ,m，每个g是对x-元组的元组k的存在概率和条件概率的函数。有趣的是，即使PRQ和PMaxQ有不同的语义，其PWS-quality有相同的形式（即方程3）。评价PMaxQ的 x-形式需要一些预处理，通过将带有查询属性的属于同一x-元组的元组进行排序。用这种方法排序元组的的例子见表1。鉴于g(k,D,Q)的值是可用的

29、，两种查询的x-形式可在x-元组整个表上迭代O（m）次计算出来。对于PMaxQ， 额外的平均成本可能需要排序元组。这仍然比使用PW-result概率值的指数评估PWS-quality更快。就x-形式可用于解决数据清洗的问题，将在第5节介绍。我们接下来展示一个有用的事实。定理2 g(k,D,Q) 0，当且仅当存在k是，有。否则，g(k,D,Q) = 0。给定一个x -元组k，以上陈述中g(k, d,Q)是小于零的，如果存在一个元组 k，那么其条件概率，既不是0也不是1。更重要的是，一个x-元组的条件概率是0还是1并不需要包含在PWS-quality的计算中（方程3）。因此，我们并不需要检查整个数

30、据库。相反，我们可以只挑选满足定理2条件规定的x -元组。这正是在最后查询答案中条件概率不等于1的元组的x-元组集。如果我们给出查询答案（由查询引擎产生的），则计算PWS-quality需要的x-元组集可以很容易得到。我们注意到对于PRQ和PmaxQ，x-形式也可用于其他基于实体的查询。特别的是，PRQ的x-形式可以被用于其他不以等级为基础的查询，其选择条件只涉及单个元组的属性。PMaxQ的x形式也可用于最小查询和最近查询，通过使用不同的排序标准来查询属性。接下来，我们简单解释一下PRQ和PmaxQ是如何获得x -形式的。朗读4.3 PRQ中x-形式的得出 现在，我们勾勒出了PRQ中x-形式表

31、达的证明。在这里，一个独特的PW-result 实质上是在一个或多个可能世界中满足PRQ（即a, b）的元组的集。注意不能从同一的x-元组中拥有一个以上的元组，因为每一个可能世界唯一包含从每个x -元组选择的一个元组。获得的概率等于：方程7是以下条件的结果：（1）满足PRQ的所有元组的概率在内（即），（2）但满足PRQ的其他x-元组的概率不在内（即）。然后，我们将它代入方程1。我们还观察到条件概率（元组的）可以通过总结不同的PW-result概率（的），其结果包含。也就是说，这是一个重要的方程，因为它可以允许我们以取代表达式的所有。因为在最终查询答案中有最多m个，PWS-quality的计算可

32、以比使用速度更快，其数量是以指数增长的。最后，通过使用属性，log(ab) =log a + log b(log()函数用于PWS-quality 标准中），我们得到了“结果总和”的表达，如方程4所示。注意到我们的证明仍适用于涉及不同选择限制的其他查询,通过更换在可能结果（即，“ a, b”）中一个元组所要求的条件(例如, “ b”)。也就是说， PRQ的x-形式可以推广到不以等级为基础的查询，在元组自身属性的基础上测试它是否符合。对于证明的细节，读者可以参考我们的技术报告。4.4 PmaxQ中x-形式的得出 PMaxQ的x-形式的推导类似PRQ，以下是主要的区别：（1）在x-元组中的所有元组

33、被假定是按降序排序的，（2）PW-result的概率有一个不同的公式。我们的解决方案也掌握了存在多个相同查询属性值的元组的场景。为方便起见，让k的第i个元组为，按的降序排序分类，PMaxQ一个独特的PW-result是在一个或多个可能世界中具有相同最大值的的元组集。令为属性值被中的元组共享。得到的的概率等于：其中Pr(k ) 是k中查询属性值比小的元组的概率。方程9是以下条件的结果：（1）所有元组的概率是在的范围内（即），（2）所有其他x-元组至少有一个元组的概率值比（即）小。此外，由于x-元组的所有元组是按降序排序分类的，我们可以重写为：其中s(j, k)是一些在1, |k|内的整数，使得满

34、足不小于的最小值。然后，我们将方程9和方程10代入到PWS-quality的定义（方程1）中，并得出最终结果（方程5）。这些细节在附录A中解释。我们可以很容易的使PMaxQ的x-形式适用于其他以等级为基础的查询。例如，对于最小查询，我们可以将x-元组的元组按升序排列来分类，并相应地改变比较的标志。作为另一个例子，最近查询的x-形式可通过排序来得出，根据来自查询点中元组的查询属性的欧氏距离。5 清洗不确定数据现在让我们讨论PWS-quality如何用来帮助清洗不确定数据。 5.1节介绍了这个问题的正式定义。在第5.2和5.3节，我们描述了一个高效的解决方案，它可应用于正在研究的问题。提供高效解决

35、方案的几个启发式在5.4节提出。5.1 问题定义回想一下，我们的目标是要选择一个最合适的要清洗的x-元组集，在严格的预算下，以达到最高的预期质量改进。正式地，让我们定义一个操作叫作清洗（k）：定义4 给定一个x-元组k，清洗（k）取代了包含一个单一元组的x-元组k：，这样IDi和是分别为标识和属于k的某一元组的查询属性值。从本质上讲，k在清洗（k）后变成“确定”被执行。只有在原来的x-元组中的元组之一被保留，其存在概率改为1。新的元组的值取决于清洗操作。例如在表1中，在清洗（a）执行后，a包含一个单一元组a2, 80, 1, a，来源于a2，价格为80美元，存在概率为1。清洗x-元组可能涉及到

36、成本。例如，如果一个x-元组代表了一个传感器监测应用中的传感器的读数，那么清洗这种x-元组的成本可以是被运到基站的传感器需要的电池电量的数量值。我们用一个自然数，来获得执行清洗（k）的成本。我们也假设一个Q查询与C单位的预算有关，其中C是一个自然数。它的值限制了清洗工作的最高限额，可用于改善Q的质量。在传感器监测中，C可以是传感器允许探测能量的总额。C的值可能会基于可用的系统资源的数量，或查询用户的优先级。我们的目标是在给定的预算下获得的x-元组集，PWS-quality中最显著的预期产量亟待改善。这个x -元组集之后将被选择清洗。具体来说，令X 为从数据库D中选择的任一x-元组集。不失一般性

37、地，令X = 。此外，令是一个|x |维的“元组向量”，这里的第k维是一个属于X第k个x-元组的元组，例如，如果，其中和，然后的两个可能值为和。现在，令为新的数据库中，在X中每个x-元组k执行清洗（k）后获得的，产生中描述的元组。清洗x-元组的集合X的预期质量等于：对于每个元组向量，方程11计算了新数据库 的概率（即）和在（即）上评价的Q查询的PWS-quality分数。定义5 清洗x-元组中X集的质量改进：现在我们的问题可以用如下定义表示：定义6 数据清洗问题。给定单位C的预算，选择D中的x-元组的X集，因此I(X,D,Q)获得最高值。解决这个问题的一个简单方法是获得在D中所有x-元组的幂集

38、。对于幂集的每个元素（x-元组的X集），我们测试清洗x-元组中X的总成本是否超出预算C。在那些不是这样的幂集中，我们选择了x-元组集，其质量的改善是最高的。这个解决方案效率低下的原因有两个。首先，给定一个x-元组的集合X，计算方程12需要X的所有元组向量，这是从x-元组的X中选择的元组组合。第二，被检查的x-元组集的数量是以指数增长的。我们在5.2节解决第一个问题。第二个问题在5.3节讨论。朗读5.2 评价质量改进 公式12可以使用PWS-quality的x-形式更容易地计算，如下面的定理所示。定理3 清洗x-形式的集合X的质量改进：其中g(k,D,Q)被方程4和方程5给出，分别为PRQ和PM

39、axQ。证明 通过使用x-形式（方程3），我们可以重写：对于PQR和PmaxQ，我们提出要求：利用方程15和方程16，方程14可写为。再加上方程12和方程3，我们可以看到，方程13是正确的。下面的草图是PRQ和PmaxQ的方程15和方程16的证明。PRQ ：首先，注意新的数据库包含每一个kx的唯一元组，存在概率是1，并且条件概率为0或1。 使用这个事实和方程4，我们能看到对每一个k 1，|X|，方程15是正确的。 对于方程16，观察是tik的和的某一函数（方程4），其中。如第3.2节所述的， PRQ中的值可以是或0。 因此和的这些值没有被在x-元组中的X通过任何清洗工作所改变，方程16适用k

40、= |X| + 1，m。PmaxQ:令新数据库的每一个元组的存在概率和条件概率分别为和。那么在清洗(k)后，在k中仅有一个元组可以在中存在。由于（方程5），我们有。此外，。因此，并且方程15的证明是完整的。要证明方程16，注意要使用方程5，可以被写成：接下来，我们提出为了直接计算，要求计算每一个向量。此外，计算包含在中的每一个可能世界。因此， 是查询D中所有PW-result概率的某一函数。 因此，方程18是正确的。最后，将方程18代入方程17，我们得到方程16。方程13揭示了三个重要的事实。 第一，质量改进，I(X,D,Q)，是非负(因为g(k,D,Q)是非正的)的。 这意味着期望的质量随着

41、清洗(k)操作单调递增。 第二，计算I(X,D,Q)的工作变得容易(与方程12比较)，因为g(k,D,Q)可以在多项时间中计算。如果这些g值被存放 (即，在查寻表里) 在了计算PWS-quality(方程3)的x-形式的过程中，则I(X,D,Q)可以由查询表评估。 第三，方程13可以被用于PRQ和PMaxQ，因为两种查询的g(k,D,Q) 在 4.2节已经得出. 我们看看这些结果怎么被用于开发有效的数据清洗算法。5.3 一个最优的、高效的数据清洗算法我们现在提出第二个问题:要找出x-元组的集合B，其引导了PWS-quality中最优的预期质量改进,它有可能避免在整个数据库中所有x-元组组合的列

42、举吗?要回答这个问题,我们首先提出下面的定理:定理4 对任一k B的x-元组，k必须满足的条件：存在k使得出现在Q的最终查询中，其中(0, 1)。证明 考虑一个x-元组j， 其元组的条件概率为0或1。 我们可以表示j不需要包括在B中。由矛盾假设j B.根据定理2，g(j, d,Q) = 0。通过使用定理3，我们能看到包括在B的j对质量改进I(B,D,Q)没有作用。因此，j包括在B中是多余的。实际上，通过排除j，我们需要为清洗考虑的剩余的x-元组中至少包含一个元组要有以下条件： (1) 出现于最终查询答案中，(2) (0，1)。例如，表1评估的最大查询，最优集合B可以从最大查询 (表2)中得出，

43、包含来自x-元组的a、b和c元组，而没有d。相应地，B是x-元组a，b，c的子集。 因此，定理4减少了在查询答案中出现的x-元组的查询空间。 同时也意味着，数据清洗算法的输入可以是包含在查询答案中的元组(如图1)。我们现在把注意力集中在满足定理4条件的x-元组。 令Z为这些x-元组的数量。 我们使用k (其中k = 1，Z)表示这些x-元组。优化问题。 我们现在给数据清洗问题的最佳方案提供一种有效的算法。 这种算法可以被用于基于实体的查询，包括PRQ和PMaxQ。 我们假设对于所有k = 1，Z的值，g(k,D,Q)的值已经得出。 为方便起见，我们也使用代表g (k，D，Q) (因为D和Q是恒

44、定的参量)。 然后， 定义6可以再被表示为最优问题P (C、M)的形式，其中M = 1，Z是将被考虑的候选集，C是分配给查询的预算：这里是长度为Z的位向量，编码从M中选择出来的要清洗的x-元组的IDs。特别的是，如果选择x-元组k， = 1，否则 = 0。 方程19是清洗x-元组集的总质量改进 (其中如果=1，k被选择)，方程13也是如此。 最优化限制在方程20中描述，要求清洗x-元组集的总成本不超过C。 注意，因为对于PRQ和PMaxQ方程19 (或方程13)是正确的，这个问题的解决方案可以被用于两种查询。我们进一步指出,P(C,M)本质上是一个0/1背包问题的变体,可以利用动态程序设计技术

45、解决。该算法的细节在附录B中提出。该方案的时间和空间复杂度分别和。5.4 数据清洗的启发式 为了进一步提高数据清洗的效率,我们开发了其他三个启发式:1. 随机：这是最简单的启发式，其中x-元组随机被选择，直到查询预算被用尽。2. MaxQP ： 使用方程2计算每个x-元组k的条件概率。 然后，选择在 (其中= 1)中按降序排序的x-元组，直到总成本超出C。 基本原理是选择比那些小概率值更高条件概率的x-元组对WS-quality的作用更有效。3. 贪心： 令。 选择具有最高值fk的x-元组，使得最大总成本比C少。直观上，是清洗(k) 每单位成本的质量改进。x-元组的选择决定于改进质量的数量和需

46、要的费用。MaxQP和贪心启发式可以被扩大到支持大的查询答案集。特别地，如果数据清洗算法考虑到x-元组的数量太大，以至于不能被存放在主存储器，基于磁盘的算法可以被用于x-元组的排序。然后，排列最高的x-元组可以被检索。在我们的实验中，因为主存储器是足够大将元组返回给用户，我们的数据清洗算法在主存储器上执行。作为旁注，在清洗执行之前，考虑一个查询评估数据库。在清洗数据库之后，重新启动这次查询不要求检查整个数据库。这是因为只有出现在预清洗数据库查询结果中的元组需要被处理。我们在附录C中解释这个“渐进性的处理技术”。6 研究结果我们现在讨论实验结果。在6.1节我们描述实验设置。我们在6.2节提出了我

47、们的研究结果。6.1 实验装置在我们的实验中我们使用了综合性数据集。 这个数据集包含10K对象(即，产品)，其中每一个对象有一个1D的属性y (从网页自动收集的价格)，在域0， 10，000。y的值遵循在9，35中描述的属性不确定性，其中y有两个成份： “不确定性区间” y.L和“不确定性 pdf” y.U。 y.L的中心一般分布在域中，并且y.L的范围一般分布在60，100范围内。不确定性pdf y.U是在y.L上定义的高斯分布，有y.L中心平均值，100单位方差。要在一个概率数据库中存放这些对象，我们通过获得它的直方图表示法离散y.U，其与y.L中 “直方图条”相等的概率10已经计算出。

48、然后每个对象看作是在10个元组下创造的x-元组，查询属性是直方图条的平均值，并且存在概率为计算直方图条的概率。因而我们的综合性数据库有10K 个x-元组或者100K个元组。我们也对实际数据集进行实验，其中包括对于不同电影观众评级中的一些不确定性。 表中有4999个x-元组，或者10037个元组。它有5个属性：， 其中是 x-元组的键，置信度记录元组的存在概率。要塑造数据清洗问题，我们为两个数据集附加一个归因于每个x-元组属性的“清洗成本”。 这个费用是一个整数，一致分布在1，10范围内。查询预算有30个单位的缺省值。我们实施了PRQ和PMaxQ的综合性数据集。对于PRQ，查询范围有20个单位的

49、宽度，并且它的位置均匀地分布在域中。对于实际数据集，PRQs使用作为一个2D的查询属性。我们也实施一个概率性的最近查询(PNNQ)，伴随着在上随机的4D查询点q。注意PNNQ本质上是PMaxQ通过排列q中每个数据点的欧式距离。 因而我们的算法也可被PNNQ使用。我们使用了基于代码的一棵R-树来标注查询属性，为了改进查询答案的有效性。用于评估的两个主要的度量标准是：(1) PWS-quality分数；(2)质量评估时间。注意到标准(2)不包括评估查询答案所需的时间。每个数据点是100次查询的平均值。除另有规定外，结果以综合性数据集为基础。我们的代码，实施在J2SE 1.5.0-09，在1.83G

50、Hz的英特尔T2400中央处理器和1GB内存的PC上运行。6.2 研究结果 第6.2.1节研究了PWS-quality的可表达性。第 6.2.2节检测了PWS-quality的x-形式，第6.2.3节提出数据清洗的结果。在第6.2.4节我们报告了实际数据集的结果。6.2.1 PWS-quality的可表达性我们首先研究PWS-quality如何量化查询结果的模糊性。我们用z表示查询答案的不同元组的数量，其条件概率是非零的。图3显示在z的一个大范围下PRQ (S)的质量分数。我们看到当z增加时质量分数减少(即，质量退化)。直观地，z的值越大，在查询答案中的元组越多，这意味着一个更加不确定的答案。

51、 因此，PWS-quality自然地反映了查询答案的模糊性。在同一张图中，我们在数据集中提出PWS-quality的两种不同的不确定性pdfs(y.U)的属性y。就象我们所看到的，统一的pdf证明比它的高斯副本质量分数低。这并不令人惊讶,因为统一的pdf比高斯pdf有更大的熵(即，更不确定性)。结果，查询答案变得更加模糊，就像由较低的质量分数说明的一样。其次，我们在5个不同的数据库中比较PRQ和PmaxQ的质量分数。为了公正，我们仅比较在同一个数据库中产生的，在他们的查询答案中有相同数量的元组(有1%的差异)。如图4所显示，PRQ分数低于在所有数据库样本的PmaxQ分数。 原因是PWS-qua

52、lity是PW-result概率(方程1)的熵函数。平均起来，PRQ (在指定范围找到具有查询属性（s）的元组（s）) 比PMaxQ (找到给出最大值的元组（s）)产出更多PW-results。因此，PRQ的答案也比PmaxQ的答案更加不确定，正如我们的结果所示。6.2.2 PWS-quality的评估健全检查。我们首先通过几次实验来验证x-形式的正确性。我们发现了x-形式和PWS-quality(方程1)的初始定义之间的相对差异大约在或更小。 对于PRQ，在z = 3.18时，相对差异为2.08e6。对于PMaxQ，在z = 77.46时，差异为3.99e 6。轻微的差异归结于计算小概率值的

53、精度损失。评估时间。图5比较了PRQ中计算x-形式和PWS-quality初始定义需要的时间。两种方法时间的数量随着z增加，因为要考虑更多结果的可能性。然而， x-形式比初始定义需要更短的时间评估。这是由x-形式 (方程4) 在多项式时间进行的事实而产生，而初始定义(方程1)并不要求指数的时间复杂度。图6显示了计算PRQ的x-形式需要的时间和查询评估时间。我们注意到前者仅仅需要比后者多10%的时间。PMaxQ的质量评估时间，没有显示在这里，平均需要0.16毫秒，或者查询评估时间的1.6%。一个查询的评估时间和它的质量的差异实际上可以很大，因为在这些实验中我们已经建立了索引来加速查询评估。因而计

54、算PWS-quality给查询评估程序增加了一点日常开支。复制元组的作用。 我们也研究“复制元组”对计算PMaxQ的PWS-quality的作用。这些是查询属性值相同的元组。我们通过将1范围之内的的属性值看作一个单一值来修改综合性数据库。结果，每个查询属性值平均与6.33个元组有关。我们发现用初始定义计算PWS-quality要用259.58毫秒来完成，而x-形式能在3.48毫秒完成。巨大的差异(98.6%的改善)归因于初始定义，要考虑由于复制元组而带来巨大数量的PW-results，但是x-形式仅需要遍历答案中的x-元组一次。我们也测试其他数据库；因为结果是相似的，他们没有在这儿报告。6.2

55、.3 数据清洗接下来，我们检查数据清洗的结果。我们假设已经获得了要测试的查询质量。 而且，在清洗之前，在x-形式评估时需要计算g(D, k,Q)的所有值，已经存放在查询表里。我们首先将在计算质量改进(方程13)中“改进”方法的绩效，与它的“初始”定义(即，定义5)比较。图7显示了这两种方法在给定x-元组的集合X的结果,|X| = 1, . . . , 5。初始定义需要的时间随|x|急剧增加。改进的方法总括k X的x-元组g(D, k,Q)的值，这些值可以从查询表中检索。所以，它的执行时间较少。因此，改进的方法将用于我们随后的实验。然后我们研究计算质量改进需要的时间，使用在5.3节和5.4节提出

56、的方法。 这里，基本的方法意味着检查所有x-元组的每一个幂集成员的质量改进，然后选择产生最高改进的x-元组。图8检查了在一个大范围的查询预算内，对于用不同方法使用PmaxQ的时间(在对数标度)的数量。我们看到基本执行最差。DP方法提供了在多项式时间中的一个最佳方案，因此它比基本方法快得多。然而，它的时间高于其他启发式(即，随机，MaxQP和贪心)。PRQ的结果是相似的，因此在这里跳过了。图9和图10检查了PRQ和PMaxQ各自的质量改进(I)。 因为基本和DP给出了最佳方案，我们只清晰显示了DP的结果。虽然DP执行最好，但值得注意的是，贪心和MaxQP已经接近它了。这是因为贪心根据清洗的费用和

57、收益来选择x-元组，而MaxQP优先考虑有更高条件概率的x-元组。这些因素对决定最佳方案是很重要的。此外，数据清洗问题是背包问题的变形，并且在15中已经显示了接近最优解决方案的一种贪心解决方法。随机根本不考虑这些因素中的任一个，因此它执行最差。观察MaxQP在PmaxQ中比在PRQ中好。在PmaxQ中，通过考虑具有最高条件概率的一个x-元组，在那个x-元组中的元组可能比其他元组有机会给出最高值，产生一种高质量的结果；因此预期的质量改进也可比PRQ情况更高。我们也对比PRQ和PMaxQ的质量改进(I)，相对于他们的初始质量(S)。我们假设DP算法用于获得x-元组。结果显示在图11上，显示在固定的查询预算和答案大小之下， PmaxQ的相对质量改进(I/|S|)也一致地比PRQ的要高。注意PMaxQ比PRQ (6.2.1节)有更少不同的PW-results。因而在PmaxQ的答案中有比在PRQ答案中更少的元组。清洗PMaxQ的一个x-元组有更多冲击。在多次查询同时执行的环境下，系统能选择在PmaxQ上放置比在PRQ