论文标题
恒定延迟枚举，并进行FPT预处理，以进行有界下宽度的连接性查询
Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width
论文作者
论文摘要
马克思（Stoc〜2010，J。〜ACM 2013）介绍了连接查询（CQ）的宽度宽度的概念，并表明，对于任何级别的限制性下宽度宽度的布尔cqs的$φ$φ$，所有有限型结构的$φ$的$φ$ cqs的所有有限结构都固定了 - 票房是固定的，是固定的 - 票房固定的（FPT）。请注意，对于非树状查询，查询结果的大小可能太大了，无法在FPT时间内完全计算。我们调查了子模块宽度的自由连续变体，并将马克思的结果概括为非树树的查询：对于每个类别的$φ$ CQ $ cqs的CQ $ cqs的cqs cqs的自由式supsodular宽度，在fpt-preprecorpercessing的时间内，我们可以构建一个数据结构，而无需延迟，所有的数据结构就可以构建一个数据结构。我们的证明是基于马克思分裂的常规，将查询结果分解为结果的结合；但是，我们必须解决其他技术困难，以确保可以有效地枚举这些困难。
Marx (STOC~2010, J.~ACM 2013) introduced the notion of submodular width of a conjunctive query (CQ) and showed that for any class $Φ$ of Boolean CQs of bounded submodular width, the model-checking problem for $Φ$ on the class of all finite structures is fixed-parameter tractable (FPT). Note that for non-Boolean queries, the size of the query result may be far too large to be computed entirely within FPT time. We investigate the free-connex variant of submodular width and generalise Marx's result to non-Boolean queries as follows: For every class $Φ$ of CQs of bounded free-connex submodular width, within FPT-preprocessing time we can build a data structure that allows to enumerate, without repetition and with constant delay, all tuples of the query result. Our proof builds upon Marx's splitting routine to decompose the query result into a union of results; but we have to tackle the additional technical difficulty to ensure that these can be enumerated efficiently.
