Bag Query Containment and Information Theory
Bag Query Containment and Information Theory
复制标题
包查询遏制和信息论
DOI：
10.1145/3472391
复制
发表时间：
2021
影响因子：
1.8
通讯作者：
Suciu, Dan
中科院分区：
文献类型：
--
作者：
Khamis, Mahmoud Abo;Kolaitis, Phokion G.;Ngo, Hung Q.;Suciu, Dan
查询包含问题是数据管理中的一个基本算法问题。虽然这个问题在集合语义下很好理解，但在包语义下却很少被理解。特别是，包语义下的联合查询包含问题是否可判定是一个长期存在的悬而未决的问题。我们揭示了信息论和包语义下的联合查询包含之间的紧密联系。这些联系是利用信息不平等建立的，这被认为是信息论的定律。我们的第一个主要结果断言，决定信息不等式推广的有效性是多对等价于联合查询包含的限制情况，其中包含查询是非循环的；因此，这两个问题要么都是可判定的，要么都是不可判定的。我们的第二个主要结果确定了包语义下的联合查询包含问题的新的可判定情况。具体来说，我们给出了包语义下的联合查询包含的指数时间算法，前提是包含查询是弦式的并且允许简单的联合树。
The query containment problem is a fundamental algorithmic problem in data management. While this problem is well understood under set semantics, it is by far less understood under bag semantics. In particular, it is a long-standing open question whether or not the conjunctive query containment problem under bag semantics is decidable. We unveil tight connections between information theory and the conjunctive query containment under bag semantics. These connections are established using information inequalities, which are considered to be the laws of information theory. Our first main result asserts that deciding the validity of a generalization of information inequalities is many-one equivalent to the restricted case of conjunctive query containment in which the containing query is acyclic; thus, either both these problems are decidable or both are undecidable. Our second main result identifies a new decidable case of the conjunctive query containment problem under bag semantics. Specifically, we give an exponential-time algorithm for conjunctive query containment under bag semantics, provided the containing query is chordal and admits a simple junction tree.
登录
查看更多内容
关系数据和 XML 数据范式的信息论方法
DOI：
10.1145/1059513.1059519
发表时间：
2005
期刊：
J. ACM
影响因子：
--
作者：
M. Arenas;L. Libkin
通讯作者：
L. Libkin
影响因子：
32.8
作者：
Wainwright, Martin J.;Jordan, Michael I.
通讯作者：
Jordan, Michael I.
DOI：
10.1145/1142351.1142363
发表时间：
2006
期刊：
Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
影响因子：
--
作者：
T. S. Jayram;Phokion G. Kolaitis;Erik Vee
通讯作者：
Erik Vee
真实连接查询的优化
DOI：
10.1145/153850.153856
发表时间：
1993
期刊：
Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems
影响因子：
--
作者：
S. Chaudhuri;Moshe Y. Vardi
通讯作者：
Moshe Y. Vardi
bag 和 bag-set 语义下的查询包含
DOI：
10.1016/j.ipl.2010.02.017
发表时间：
2010
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
F. Afrati;M. Damigos;M. Gergatsoulis
通讯作者：
M. Gergatsoulis