统一操作、一致的查询响应机制

《ACM Transactions on Database Systems》：Uniform Operational Consistent Query Answering

Operational consistent query answering (CQA)通过迭代应用事实删除等操作达成约束一致性数据库，提出基于操作概率的近似算法，并针对功能依赖和联合查询进行数据复杂度分析，突破传统主键限制的效率边界。

　　

摘要

操作一致性查询回答（CQA）是一种新兴的CQA框架，它基于对修复操作和一致性答案的重新定义，从而实现了具有明确误差保证的高效近似方法。其核心思想是从一个不一致的数据库开始，通过迭代应用各种操作（例如删除事实），直到达到满足给定约束条件的数据库状态。这种方式允许我们灵活地控制操作的执行概率，进而计算出操作修复的成功概率，以及由此产生的答案的一致性概率。为操作分配概率的一种自然方法是使用均匀概率分布，这种分布可以应用于合理的范围，例如操作修复集合、能够导致操作修复的操作序列集合，以及在修复过程中某个阶段可用的操作集合。这种方法通常被称为“均匀操作CQA”。本研究的目标是对精确和近似的均匀操作CQA进行数据复杂性分析，重点关注函数依赖关系（及其子类）和联合查询。我们的分析结果不仅包括一些积极发现，也揭示了一些局限性：均匀操作CQA通过确保在超出传统CQA方法适用范围（如主键情况）的场景中存在高效近似方案，进一步推动了效率的极限。