一句话:为 guarded TGDs 本体/约束下的答案计数给出参数化复杂度分类,并研究结构测度有界性元问题。
本文研究本体中介查询与约束下查询中的答案计数复杂度。查询语言为合取查询及其并(UCQs),本体/约束语言为 guarded TGDs。作者在关系符号元数有界、本体中介查询采用 full data schema 的假设下,依据 treewidth、contract treewidth、starsize 与 linked matching number 等结构测度,将答案计数复杂度分类为 FPT、W[1]-等价、#W[1]-等价、#W[2]-难或 #A[2]-等价,推广了 Dell 等人关于无本体/约束 UCQs 的近期分类。论文还研究这些结构测度的元问题:判定给定本体中介查询或约束-查询规约是否等价于结构测度有界的规约。
We study the complexity of answer counting for ontology-mediated queries and for querying under constraints, considering conjunctive queries and unions thereof (UCQs) as the query language and guarded TGDs as the ontology and constraint language, respectively. Our main result is a classification according to whether answer counting is fixed-parameter tractable (FPT), W[1]-equivalent, #W[1]-equivalent, #W[2]-hard, or #A[2]-equivalent, lifting a recent classification for UCQs without ontologies and constraints due to Dell et al. The classification pertains to various structural measures, namely treewidth, contract treewidth, starsize, and linked matching number. Our results rest on the assumption that the arity of relation symbols is bounded by a constant and, in the case of ontology-mediated querying, that all symbols from the ontology and query can occur in the data (so-called full data schema). We also study the meta-problems for the mentioned structural measures, that is, to decide whether a given ontology-mediated query or constraint-query specification is equivalent to one for which the structural measure is bounded.