寻找联结查询的最小证据（即满足查询条件的最小数据集）

《ACM Transactions on Database Systems》：Finding Smallest Witnesses for Conjunctive Queries

最小见证问题在并发式查询中的应用研究，建立了头聚类属性与P=NP的关联性，提出了头支配属性下的近似算法，并关联到有向Steiner森林问题，当前存在近似比上下界的差距。

　　

摘要人工智能摘要

要查看此由人工智能生成的摘要，您必须具有高级访问权限。

了解更多登录

摘要

摘要

“见证者”（Witness）是一个子数据库，它保存了原始数据库的查询结果，但体积要小得多。它在查询重写和调试、查询解释、物联网分析、多层网络路由等领域有广泛的应用。在本文中，我们研究了不含自连接（self-joins）的联结查询（Conjunctive Queries，CQs）类中最小的“见证者”问题（简称SWP）。

我们首先确立了这样一个二分法：对于一个联结查询（CQ），当且仅当它具有“头部簇属性”（head-cluster property）时，SWP问题可以在多项式时间内求解；否则，$\text{P}=\text{NP}$。此外，我们还发现：如果一个联结查询具有头部簇属性，并且满足某些众所周知的猜想，那么SWP问题也可以在线性时间内求解。接下来，我们研究了将“见证者”的大小从最小值放宽后的近似版本。令人惊讶的是，我们在[40]中发现的“头部支配属性”（head-domination property）也能够准确反映近似最小“见证者”问题的难度。对于具有头部支配属性的任何联结查询，SWP问题可以在多项式时间内被近似到某个常数因子以内；而对于没有这种属性的任何联结查询，则无法在对数因子以内进行近似，除非$\text{P}=\text{NP}$。

我们进一步研究了没有头部支配属性的联结查询（CQs）的高效近似算法：（1）我们展示了一个简单的算法，可以对一般联结查询实现多项式级别的近似；（2）对于只有一个非输出属性的联结查询（例如星形联结查询，Star CQs），我们展示了一个具有对数级近似比的贪心算法；（3）对于至少包含两个非输出属性的线性联结查询（Line CQs），我们将SWP问题与有向斯坦纳森林问题（Directed Steiner Forest Problem）联系起来，后者的相关算法可以直接应用于线性联结查询。同时，我们得出了一个比上述结果更严格的下界。目前，如何缩小没有头部支配属性的联结查询的SWP问题的近似下界和上界之间的差距仍然是一个未解决的问题。

人工智能摘要

要查看此由人工智能生成的通俗语言摘要，您必须具有高级访问权限。