New method speeds up queries with negation beyond previous limits
Conjunctive Queries with Negation: Beyond Signed-Acyclicity
DatabasesData Structures and Algorithms
Summary
The paper addresses how to quickly find answers to complicated database queries that include negative conditions, such as "not this" or "none of those." Previously, only certain simple cases were known to be fast to process. The authors introduce a new way to measure query complexity and develop an algorithm that can handle more complex queries efficiently. Their method improves on older approaches and shows faster performance for some examples that were previously difficult. This helps databases return results quickly even with tricky negative parts in queries.
What this means in practice
- •For database engineers: Improve query processing engines to handle queries with negation more efficiently, reducing wait times for complex conditions.
- •For data integration teams: Enable faster data retrieval when combining datasets with conditions that exclude certain records using negative filters.
Authors
Simon Frisk, Paraschos Koutris
Abstract
We study constant-delay enumeration for conjunctive queries with negation ($\texttt{CQ}^{\neg}$). Prior work defined \emph{signed-acyclicity}, which characterizes the class of queries where linear preprocessing time is achievable, but little has been known beyond this. We introduce a new hypergraph width measure for $\texttt{CQ}^{\neg}$, the \emph{signed fractional hypertree width} ($\textsf{sfhw}$), defined by requiring that a single variable order simultaneously handle every subset of the negative atoms. We show that $\textsf{sfhw}$ strictly generalizes signed-acyclicity (recovered when $\textsf{sfhw} = 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{sfhw}})$. We further 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.