论文标题
关于查询遏制的复杂性并计算ACS存在的某些答案
On the complexity of query containment and computing certain answers in the presence of ACs
论文作者
论文摘要
我们经常添加算术来扩展查询语言的表现力，并研究问题的复杂性，例如测试查询遏制并在使用视图回答查询的框架中找到某些答案。当添加算术比较时，此类问题的复杂性高于没有它们的同行的复杂性。已经观察到，如果我们限制了包含查询中的某些比较以封闭或开放的半间隔比较，则可以达到较低的复杂性。在这里，将a）集中在算术比较（简称CQAC查询）的结合查询问题上，我们证明了其计算复杂性上的上限和b）在计算某些答案的问题上，我们发现了大量的CQAC查询，并且在此问题的地方观看了这个问题。
We often add arithmetic to extend the expressiveness of query languages and study the complexity of problems such as testing query containment and finding certain answers in the framework of answering queries using views. When adding arithmetic comparisons, the complexity of such problems is higher than the complexity of their counterparts without them. It has been observed that we can achieve lower complexity if we restrict some of the comparisons in the containing query to be closed or open semi-interval comparisons. Here, focusing a) on the problem of containment for conjunctive queries with arithmetic comparisons (CQAC queries, for short), we prove upper bounds on its computational complexity and b) on the problem of computing certain answers, we find large classes of CQAC queries and views where this problem is polynomial.
