论文标题
否定性查询的$β$ - 囊性超过$β$ - 囊肿
Tractability Beyond $β$-Acyclicity for Conjunctive Queries with Negation
论文作者
论文摘要
众所周知，许多基本数据库和推理问题通常是NP - hard，但在基础超图结构为$β$ -ACYCLIC的情况下可以进行处理。尽管许多此类问题的重要性很重要，但在将这些结果推广到超级状态之外，几乎没有成功。 在本文中，我们应对这一挑战并提出了巢式宽度，这是超图$β$ acyclicity的新型概括。我们证明巢式宽度具有理想的特性和算法意义。特别是，对于具有限制性巢穴宽度的类，对带否定的布尔结合查询的评估是可以处理的。此外，当通过巢穴宽度参数化时，命题可满足性是固定参数。
Numerous fundamental database and reasoning problems are known to be NP-hard in general but tractable on instances where the underlying hypergraph structure is $β$-acyclic. Despite the importance of many of these problems, there has been little success in generalizing these results beyond acyclicity. In this paper, we take on this challenge and propose nest-set width, a novel generalization of hypergraph $β$-acyclicity. We demonstrate that nest-set width has desirable properties and algorithmic significance. In particular, evaluation of boolean conjunctive queries with negation is tractable for classes with bounded nest-set width. Furthermore, propositional satisfiability is fixed-parameter tractable when parameterized by nest-set width.
