基于标注的不一致数据库查询回答

吴爱华; 谈子敬; 汪卫

基于标注的不一致数据库查询回答

Annotation Based Query Answer over Inconsistent Database

摘要: 数据是对现实世界的描述，应该符合一定的语义规则和逻辑常识，但实际应用中，由于各种原因，有些数据违反了这样的规则，表现为数据不一致。不一致的数据库中存在不可信的数据，在这样的数据库上进行查询，得到的查询回答也可能不可信。
不一致数据库本质是一种不完整数据库，对应着多种可能的确定数据库，它上面的查询回答也一样。尽管用户都希望能得到唯一确定的查询回答，但不一致数据库的概率本质使得这样的查询回答不可能。有些相关工作试图为不一致数据库寻找一个强表示模型（比如CQA），这些模型都不可避免地存在信息丢失问题。另一方面，虽然数据清洗可以有效地发现并纠正某些关系数据库中的错误，但在这一问题上，也存在较大的信息丢失问题。上述两种方法存在信息丢失的根本原因在于他们都把记录作为信息不一致认定的最小对象。只要记录在一个属性上不一致，就整体被抛弃。
为此，本文提出一种基于标注的查询回答的研究方案，通过区分查询回答中的一致和不一致的部分，给用户可靠且信息量最大的查询回答。在本研究方案中，不一致性被看作是数据的一种属性，可以用标注加以描述, 更具体地说，关系中的每个单元值都可以附加0个或多个标注，有标注的单元值是不一致的，反之一致。且这些标注能随着查询计算从源数据库正确地迁徙到查询回答中。通过标注，原数据库和查询回答中的不一致信息都不会被过滤掉，因此本研究方案不存在信息丢失问题。而且，本方案从属性级别上检测并处理信息的不一致性，最大程度地区分了可信和不可信的数据。
基于标注的查询回答实际上不一致关系数据库及其查询的一个弱表示模型。本文详细介绍了这个模型，并解决了下面几个问题：1）对于任意给定关系数据库及其上完整性约束集（本文当前只考虑函数依赖），如何在属性级别上检测并标注其不一致数据；2）在标注过的数据库上，提交任何查询，系统应该如何查询估值，并返回标注过的查询回答，而且查询回答上的标注能正确地反映单元值的不一致性——单元值是否违反了查询回答上的所有函数依赖，以及如何求解查询结果上的所有合法函数依赖；3）证明了这些查询估值规则的正确性和完备性。

本文的主要贡献在于：
不一致关系数据库上的查询回答计算中存在的信息丢失的根本原因，那就是记录被当作不一致检测的最小单元。
提出了不一致关系数据库上的两类不一致标注及基于标注的查询回答的概念，把不一致检测和管理细化到了属性级别上，给出了查询回答上成立的所有函数依赖的求解规则，重新定义了标注过的数据库上的7种关系代数操作，任何查询只要转换为这7种查询或者他们的综合表达式，就能得到其基于标注的查询回答，并建议了一种可以实现本研究方案的系统框架。
证明了这些基于标注查询回答的估值规则的正确性和完备性。同时，在附录部分还探讨并证明了基于标注的查询回答和CQA之间的关系。.
进行了多项实验，测试并分析本文所提研究方案的在查询时间和信息保持两方面的性能

本文的主要创新点在于：
首次提出使用标注描述的方法来区分确定数据和不确定数据，使得能够在不丢失信息的前提下，给出有意义的查询回答。从而解决现在多数研究方法信息丢失的缺陷。
改变以记录为不确定衡量最小单位的现有做法，提出以属性值为不一致衡量的最小单位。从而在不确定定位的准确性和信息保留两方面都有较大提高。

目前，本文只解决了违反了函数依赖的不一致关系数据库上的基于标注的查询回答计算问题，没有涉及其他类型的完整性约束，如多值依赖，包含依赖等等。因此，未来还需要解决以下问题：
不一致关系数据的语义规则及其在查询结果上的演算。语义规则是不一致数据认定的依据，但已有研究都只涉及函数依赖，缺乏对他们的系统思考。不一致关系数据的语义规则到底有哪些类别，他们在不一致数据的测定方面有没有内在联系和矛盾冲突，对于给定查询，这些约束规则在查询结果上是否成立，是否还有其他蕴含约束也在查询结果上成立。
当有多种类型的完整性约束时，不一致标注是否也要调整。另外，应该如何正确地计算基于标注的查询回答，使得标注能正确地反映数据的不一致性。
采用哪种策略来实现不一致关系数据库上的基于标注的查询回答，并使得它能嵌入到已有数据库应用系统中。
如何存储和管理标记，最有利于基于标记的查询回答的计算。
在数据异地存放，遗留系统数据整合应用普遍的今天，不一致数据库上的查询回答问题的研究非常迫切，而且具有重大的意义。该问题的解决可以提高数据质量和信息价值。据调研，全美商业公司每年因为“脏”数据导致的各项耗费高达6000亿美元，其中仅零售业数据库中的错误价格信息一项，就使美国消费者每年损失25亿美元6。而基于标记的研究方案因为避免了信息丢失，又能准确地告知用户确定可信的信息，能大大地提高信息的利用价值。只要实现策略适合，该研究方案可以广泛应用到各类现有不一致数据库的查询处理中。

Abstract: In this paper, we introduce a concept of Annotation Based Query Answer, and a method for its computation, which can answer queries on relational databases that may violate a set of functional dependencies. In this approach, inconsistency is viewed as a property of data and described with annotations. To be more precise, every piece of data in a relation can have zero or more annotations with it and annotations are propagated along with queries from the source to the output. With annotations, inconsistent data in both input tables and query answers can be marked out but preserved, instead of being filtered in most previous work. Thus this approach can avoid information loss, a vital and common deficiency of most previous work in this area. To calculate query answers on an annotated database, we propose an algorithm to annotate the input tables, and redefine the five basic relational algebra operations (selection, projection, join, union and difference) so that annotations can be correctly propagated as the valid set of functional dependency changes during query processing. We also prove the soundness and completeness of the whole annotation computing system. Finally, we implement a prototype of our system, and give some performance experiments, which demonstrate that our approach is reasonable in running time, and excellent in information preserving.