paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Answer Counting under Guarded TGDs

Guarded TGDs 下的答案计数
LMCS vol.Volume 19, Issue 32023匹配度 2/10 · 该论文属于数据库理论/本体查询与参数化复杂度,研究 guarded TGDs 下答案计数的分类与元问题,与用户关注的静态分析、LLM/Agent、浮点程序分析和贝叶斯程序分析均无直接交集;仅在形式化逻辑与约束理论上有边缘关联。引用 3 inbox
Cristina Feier, Carsten Lutz, Marcin Przybyłko
crossref: 2026-09-10

AI 速览

一句话:为 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 的近期分类。论文还研究这些结构测度的元问题:判定给定本体中介查询或约束-查询规约是否等价于结构测度有界的规约。

问题
在 UCQs 作为查询语言、guarded TGDs 作为本体或约束语言时,答案计数的参数化复杂度如何随查询与本体/约束的结构测度变化?同时,如何判定一个规约是否等价于某个结构测度有界的规约?
方法
作者扩展 Dell 等人的参数化计数复杂度分类框架,在元数有界与 full data schema 假设下,以 treewidth、contract treewidth、starsize、linked matching number 等结构测度对本体中介查询和约束查询进行复杂度分类,并分析相应结构测度的元问题。
评估
论文给出理论复杂度分类与元问题结论,而非实验评估;通过证明 FPT、W[1]-等价、#W[1]-等价、#W[2]-难与 #A[2]-等价等结果完成分类。
原文摘要(Abstract)

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.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot2194,
  title = {Answer Counting under Guarded TGDs},
  author = {Cristina Feier and Carsten Lutz and Marcin Przybyłko},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 19, Issue 3},
  year = {2023},
  doi = {10.46298/lmcs-19(3:16)2023}
}