Title: Quantum Information-Theoretical Size Bounds for Conjunctive Queries with Functional Dependencies Show Chinese title

Title: 量子信息论关于带有函数依赖的连接查询的大小界限

Abstract: Deriving formulations for computing and estimating tight worst-case size increases for conjunctive queries with various constraints has been at the core of theoretical database research. If the problem has no constraints or only one constraint, such as functional dependencies or degree constraints, tight worst-case size bounds have been proven, and they are even practically computable. If the problem has more than one constraint, computing tight bounds can be difficult in practice and may even require an infinite number of linear inequalities in its optimization formulation. While these challenges have been addressed with varying methods, no prior research has employed quantum information theory to address this problem. In this work, we establish a connection between earlier work on estimating size bounds for conjunctive queries with classical information theory and the field of quantum information theory. We propose replacing the classical Shannon entropy formulation with the quantum R\'enyi entropy. Whereas classical Shannon entropy requires infinitely many inequalities to characterize the optimization space, R\'enyi entropy requires only one type of inequality, which is non-negativity. Although this is a promising modification, optimization with respect to the quantum states instead of classical distributions creates a new set of challenges that prevent us from finding a practically computable, tight worst-case size bound. In this line, we propose a quantum version to derive worst-case size bounds. The previous tight classical worst-case size bound can be viewed as a special limit of this quantum bound. We also provide a comprehensive background on prior research and discuss the future possibilities of quantum information theory in theoretical database research. Show Chinese abstract

Abstract: 研究各种约束条件下计算和估计合取查询的紧致最坏情况大小增加问题一直是理论数据库研究的核心。 如果该问题没有约束或只有一个约束（例如函数依赖或度约束），则已证明存在紧致的最坏情况大小界，并且它们实际上是可以计算的。 如果该问题有多个约束，则在实践中计算紧致界可能很困难，甚至可能需要优化公式中的无限数量的线性不等式。 尽管这些问题已经通过不同的方法得到了解决，但之前的研究尚未采用量子信息论来处理此问题。 在这项工作中，我们建立了早期关于使用经典信息论估计合取查询大小界限的工作与量子信息论领域之间的联系。 我们建议用量子Rényi熵代替经典的Shannon熵公式。 虽然经典Shannon熵需要无穷多的不等式来表征优化空间，但Rényi熵只需要一种类型的不等式，即非负性。 尽管这是一个有希望的修改，但相对于量子态而非经典分布进行优化会带来一组新的挑战，使我们无法找到一个实际可计算的紧致最坏情况大小界。 在此背景下，我们提出了一种量子版本的方法来推导最坏情况大小界。 之前的紧致经典最坏情况大小界可以看作是这个量子界的一个特殊极限。 我们还提供了关于先前研究的全面背景，并讨论了量子信息论在理论数据库研究中的未来可能性。