CS Paper Radar

Conjunctive Queries with Negation: Beyond Signed-Acyclicity

Simon Frisk, Paraschos Koutris

cs.DB cs.DS ·submitted 2026-10-02 19:46 UTC · v2

Abstract

We study constant-delay enumeration for conjunctive queries with negation ($\texttt{CQ}^{\neg}$). It is known that $\textit{signed-acyclic}$ queries can be enumerated with constant delay after linear preprocessing time, using linked lists with skip links. We use a hypergraph width measure for $\texttt{CQ}^{\neg}$, the $\textit{fractional signed hyperorder width}$ ($\textsf{sfhow}$), which requires a single variable order to simultaneously handle every subset of the negative atoms, which Capelli et al. introduced to characterize the preprocessing time of direct access. $\textsf{sfhow}$ strictly generalizes signed-acyclicity (recovered when $\textsf{sfhow} = 1$) and fractional hypertree width (recovered on queries without negation). Our main algorithmic result is a variable-elimination algorithm that achieves constant-delay enumeration on input $I$ for any full $\texttt{CQ}^{\neg}$ query with preprocessing time $O(|I|^{\textsf{sfhow}})$. Furthermore, we show that using multiple variable orders can improve this bound, exhibiting an $O(|I|^{3/2})$ algorithm for $k$-cycle queries with at least one negative edge.

Closest papers

Nearest neighbours by meaning across the whole index.

Containment of Conjunctive Queries with Negative Information over Semirings

cs.LO cs.DB ·2026-10-20 ·Guillermo Badia, Carles Noguera, Gaia Petreni, Alice Portone, Val Tannen
similarity 0.68
Abstract

We study the containment problem for (unions of) conjunctive queries ((U)CQs) with negative information on semiring-annotated databases. Our approach to negative information follows the treatment of negation proposed by Grädel and Tannen (2017, 2019, 2021 and 2024) for first-order logic and fixed point logic which applies productively to large classes of semirings, including bounded distributive lattices, as well as the important provenance semirings studied for positive CQ containment by Green (2009). Negation features in (U)CQs along two dimensions: negated equalities (disequations), and negated relational atoms. We study complexity for each of them separately, as well as jointly. For disequations, we extend a methodology that proves the same complexity bounds as the ones already known for the standard Boolean semiring (in the second level of the polynomial hierarchy) for most semirings of interest. Two prominent exceptions are $\mathbb{N}[X]$ and Trio(X) where the complexity bound for containment is in the second level of the counting hierarchy. For CQs with negated relational atoms we show that the complexity, surprisingly, is the same as that of the containment of CQs without negation when one considers model-defining and provenance-tracking interpretations (namely, nondeterministic polynomial time). Interestingly, among bounded distributive lattices, the Boolean two-element case is the only one where the complexity of the problem continues to be hard for the second level of the polynomial hierarchy for model-defining interpretations. Furthermore, we show that the complexity increases again for distributive lattices if we focus on other classes of interpretations. Finally, we consider queries that have both negated equalities and negated relational atoms and show that the complexity of containment continues to be that of the case with just negated equalities.

0.18

Size Bounds for CQs Under Acyclic Constraints

cs.DB cs.IT ·2026-08-27 ·Stefan Mengel, Andrei Romashchenko
similarity 0.64
Abstract

We study size bounds for conjunctive query (CQ) results which in recent years have played a crucial role in database theory. In particular, we compare the so-called entropic bound which is known to be asymptotically tight but not known to be computable, and its computable relaxation called the polymatroid bound, which is generally not tight. We focus here on conjunctive queries under acyclic functional dependencies. These queries are known to be well-behaved in the sense that, in the case without projections, both bounds coincide. We show that this picture changes when projections are allowed: in this case, even for acyclic functional dependencies, there is in general a polynomial gap between the two bounds. We complement this negative result by showing a special case for which the polymatroid bound is tight under acyclic functional dependencies and projections that is characterized by the position of the output variables in a topological order of the query variables.

0.20

Order-Dependent Complexity of Enumeration and Direct Access for Conjunctive Queries on Dynamic Data

cs.DB ·2026-11-03 ·Antoine Amarilli, Nofar Carmeli, Clémence Dumoulin
theory similarity 0.63
Abstract · Preliminary version

This note studies the fine-grained complexity of ranked enumeration and ranked direct access of conjunctive query answers over a dynamic database. We focus on lexicographically sorted answers, defined by an ordering on the query's free variables. From the literature, when no particular order is required, we know that when the query is self-join-free and q-hierarchical, we can build a data structure for enumeration (resp. direct access) with linear (resp. linearithmic) preprocessing and constant (resp. logarithmic) update time in the size of the database. For enumeration (resp. direct access), this data structure yields an algorithm that enumerates all query answers (resp. that returns the $k$-th query answer) with constant delay (resp. logarithmic access time). Our goal is to extend these results to ranked enumeration and ranked direct access, with the ranking function defined by a lexicographic order. We define a property on the order over the variables of $Q$, which we call being hierarchy-consistent. Given a user-specified query and hierarchy-consistent order, we first propose, for ranked enumeration under updates, an algorithm with linear preprocessing and logarithmic update time that enumerates all the query answers according to the user-specified order with constant delay. Moreover, for ranked direct access under updates, we propose an algorithm with linear preprocessing and logarithmic update time that returns the $k$-th tuple according to the user-specified order with logarithmic access time. In contrast, given a user-specified query and non-hierarchy-consistent order, we show a lower bound for ranked direct access under updates.

0.36

Guanaco: A Global-Uniformity Algorithm for Near-Submodular-Width Conjunctive Query Evaluation

cs.DB cs.DS ·2026-10-04 ·Mahmoud Abo Khamis, Hubie Chen
similarity 0.63
Abstract

We present Guanaco, an algorithm for performing conjunctive query evaluation where, for each Boolean conjunctive query, and positive epsilon, the algorithm achieves polynomial time with exponent equal to the submodular width plus epsilon. The algorithm and its running time generalize smoothly to general conjunctive queries. We believe the algorithm and its analysis to be notably simple, indeed, together we believe they form a highly simple argument that conjunctive query evaluation can be performed in essentially submodular width time. In the case of Boolean conjunctive queries, the algorithm is based on interleaving three simple primitives: a subroutine for establishing a form of consistency; a subroutine for establishing global uniformity, which, briefly speaking, partitions relations as needed to control discrepancies between average degree and maximum degree; and, a simple step that joins pairs of existing relations to form new relations.

0.22

A Fine-Grained Dichotomy for Bounded-Variable Query Evaluation: The Calculus of Relations, a Boolean Modal Logic, and One-Variable Counting Logic

cs.DB cs.CCcs.LO ·2026-10-03 ·Yoshiki Nakamura, Yuya Uezato
publishedtheory similarity 0.62
Abstract · Long version of PODS'27 paper

We study the fine-grained complexity of evaluating Boolean bounded-variable first-order queries over sparse relational structures. For every fixed $k \ge 2$, every relational signature, and every fragment between $k$-variable primitive positive ($\mathrm{PP}^{k}$) and first-order ($\mathrm{FO}^{k}$) logic, we prove, assuming the Sparse MAX-$3$-SAT hypothesis, a dichotomy theorem for evaluation in $O(m^{k-\varepsilon})$ time, where $m$ is the number of tuples in the input structure. The only tractable cases fall into three families: (1) three-variable fragments, (2) two-variable fragments, and (3) fragments over unary signatures. On the hard side, for every fixed $k \ge 4$ and every $\varepsilon > 0$, there is a fixed sentence $\varphi_\varepsilon$ in $\mathrm{PP}^{k}$ over a single binary relation symbol, depending on $\varepsilon$ but not on the input structure, whose evaluation cannot be performed in $O(m^{k-\varepsilon})$ time. For the tractable cases, we show that the evaluation problem can be solved in $2^{O(|\varphi|)} \cdot m^{k-\varepsilon}$ time for some $\varepsilon > 0$. Moreover, every tractable fragment reduces, with a $2^{O(|\varphi|)}$ blowup in formula size under DAG representations, to one of the following query languages: (1) Tarski's calculus of relations, (2) a new Boolean modal logic for sparse model checking, and (3) one-variable counting logic.

0.29

Tight Width Minimisation of Self-Join-Free Quantified Conjunctive Queries

cs.DB cs.LO ·2026-11-16 ·Hubie Chen, Fabio Mogavero, Sam M. Thompson
top venue similarity 0.62
Abstract · To appear at PODS 2027

Query minimisation is a classical problem in database theory and the width of a formula, defined as the maximum number of free variables over all subformulae, is a central measure for query evaluation. We study width minimisation for a subclass of quantified conjunctive queries (QCQs), namely self-join-free QCQs. For this subclass, we show that rewriting optimality coincides with semantic optimality: given a query $φ$, the minimum-width query obtainable from $φ$ by applying natural and established rewriting rules has minimum width among all first-order formulae logically equivalent to $φ$. As a consequence, the width of a self-join-free QCQ can be optimised by a logical-equivalence-preserving rewriting algorithm.

0.28

Counting on Nowhere Dense Classes

cs.LO ·2026-09-16 ·Steffen van Bergerem, Nicole Schweikardt
similarity 0.61
Abstract · 22 pages

For every effectively nowhere dense class $\mathcal{C}$ of relational structures, we present an algorithm that runs an almost-linear-time preprocessing step on a given structure $\mathcal{A} \in \mathcal{C}$ and a first-order formula $φ(x_1, \dots, x_k, y_1, \dots, y_\ell)$. After the preprocessing, whenever given a tuple $\bar{v} \in A^k$, the algorithm computes the number of tuples $\bar{w} \in A^\ell$ that satisfy $\mathcal{A} \models φ(\bar{v}, \bar{w})$ in constant time. Building on this, we provide an algorithm for constant-time query answering and constant-delay enumeration after almost-linear-time preprocessing for the recently introduced logic clique-guarded first-order logic with counting (cgFOC) on effectively nowhere dense classes. This generalises the testing and enumeration results for first-order logic [Schweikardt, Segoufin, and Vigny, JACM 2022] and the evaluation result for the first-order logic with counting FOC1 [Grohe and Schweikardt, PODS 2018] on nowhere dense classes.

0.32

The Power of Bidegeneracy for Hypergraph Data Structures

cs.DS cs.DBcs.DM ·2026-11-03 ·Marco Bressan, Stefano Clemente, Giacomo Fumagalli, Daniel Paul-Pena, C. Seshadhri
similarity 0.59
Abstract

A hypergraph $H = (V,E)$ describes a set system over a vertex universe $V$. Hypergraphs are increasingly popular in network science, as they represent interactions between subsets of vertices. A natural challenge is to design a data structure for $H$ to quickly answer basic questions about it, e.g. how many neighbors a vertex $v$ has or whether a hyperedge contains a vertex subset $S$. Such questions are trivial for graphs, for which we simply inspect the adjacency list. The gold standard, from a data structures perspective, would be near-linear time preprocessing and query answering in (poly)logarithmic time. Since this is unlikely for arbitrary $H$, we ask for well-motivated hypergraph properties that can make such a goal possible. We introduce bidegeneracy, a measure of hypergraph sparsity that strictly generalizes many other measures, including bounded degree, bounded rank, and bounded $\infty$-degeneracy. We show that bounded bidegeneracy yields fast hypergraph data structures. For a large set of fundamental queries, including their listing and sampling versions, we obtain near-linear preprocessing and (poly)logarithmic query time. Moreover, direct reductions from assumptions like the Orthogonal Vectors Conjecture suggest that, without assumptions on the input, these structures require almost-quadratic preprocessing or almost-linear query time. We use bidegeneracy to compute a compressed representation of $H$ and perform careful reductions to stabbing and searching problems in $\mathbb{R}^d$. Our framework significantly extends the well-studied "partial matching" problem of finding database entries through wildcard search. It also uncovers an intriguing connection between hypergraph sparsity, compression, and the complexity of hypergraph primitives. We also find remarkably low bidegeneracy in hypergraph datasets from the literature, suggesting practical consequences.

0.25