基于一阶逻辑的非一致性关系数据管理

摘要

对于给定的约束,数据库可能是非一致的.为了获得一致性结果,基于一阶逻辑,提出非一致性关系数据管理框架,研究多种合取查询类型对应的连接图及其连接的充分性,分析一致性查询应答的计算复杂度.在查询连接类型是键-键、非键-键或不充分的键-键,且查询对应的连接图是非环的情况下,一致性查询应答的计算在多项式时间内是可解的.针对大量实际的易处理合取查询,给出查询重写算法获得可重写的查询.算法首先判断初始查询是否为可重写,再基于连接图进行递归计算构造一致性识别语句,然后,与初始查询合取产生一个新的一阶重写查询,用于计算一致性结果.对于非环的自连接查询,由于递归重写算法不能剔除非一致性元组,因此,采用初始查询获取了用于剔除违反键约束的非一致性元组的语句.%In order to obtain consistent answers over databases that might be inconsistent with respect to a set of integrity constraints, a framework was proposed for inconsistent relational data management based on first-order logic. The join graphs was researched to conjunctive query types and the sufficiency of their join, the computational complexity for consistent query answering (CQA) was analyzed. If the join classes of queries are the key-key, nonkey-key or insufficient key-key, and the join graphs of these queries are acyclic, the computational complexity of CQA is PTIME (polynomial time). For a large and practical class of conjunctive queries, some query rewriting algorithms were proposed to obtain the rewritten query for computing the consistent answers. Firstly, the algorithms judge whether a initial query is rewritable, and the consistent identification statement is constructed based on the join graph by the recursive computation, and the statement combines with the initial query to construct a new first-order rewritten query for computing consistent answers. To acyclic self-join queries, the recursive rewriting algorithms can not eliminate inconsistent results, so the initial query combines with the statement that eliminates inconsistent results with respect to the key constraint.