一句话：将合取查询直接访问的可处理性结果推广到含负原子的情形，并用电路表示答案集。
给定合取查询 Q 与数据库 D，直接访问指按某答案序返回第 k 个答案。该问题组合复杂度下一般 #P-难，但许多查询结构可在多项式预处理后用多对数时间实现字典序直接访问；已有工作仅刻画了正查询的可处理类。本文将其推广到允许负原子的带符号合取查询。方法基于一类可表示关系数据的电路：先证明该电路支持可处理直接访问，再按查询结构给出表示答案集的电路规模上界。结合二者，恢复正合取查询已知可处理类，并推广统一负合取查询结果，证明 β-acyclic 负合取查询与有界 nest set width 负合取查询均可处理。
Given a conjunctive query $Q$ and a database $D$, a direct access to the answers of $Q$ over $D$ is the operation of returning, given an index $k$, the $k$-th answer for some order on its answers. While this problem is $\#\mathcal{P}$-hard in general with respect to combined complexity, many conjunctive queries have an underlying structure that allows for a direct access to their answers for some lexicographical ordering that takes polylogarithmic time in the size of the database after a polynomial time precomputation. Previous work has precisely characterised the tractable classes and given fine-grained lower bounds on the precomputation time needed depending on the structure of the query. In this paper, we generalise these tractability results to the case of signed conjunctive queries, that is, conjunctive queries that may contain negative atoms. Our technique is based on a class of circuits that can represent relational data. We first show that this class supports tractable direct access after a polynomial time preprocessing. We then give bounds on the size of the circuit needed to represent the answer set of signed conjunctive queries depending on their structure. Both results combined together allow us to prove the tractability of direct access for a large class of conjunctive queries. On the one hand, we recover the known tractable classes from the literature in the case of positive conjunctive queries. On the other hand, we generalise and unify known tractability results about negative conjunctive queries -- that is, queries having only negated atoms. In particular, we show that the class of $β$-acyclic negative conjunctive queries and the class of bounded nest set width negative conjunctive queries admit tractable direct access.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{CapelliI24,
title = {Direct Access for Conjunctive Queries with Negations},
author = {Florent Capelli and Nofar Carmeli and Oliver Irwin and Sylvain Salvati},
journal = {Logical Methods in Computer Science},
volume = {Volume 22, Issue 1},
year = {2026},
doi = {10.46298/lmcs-22(1:24)2026}
}