Papers for

database system designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Polynomial time check for Maltsev polymorphisms in finite structures

Complexity of Deciding Existence of Maltsev Polymorphisms of Finite Relational Structures

Abstract: In this article, we show that the problem of deciding whether a finite relational structure $\mathbf{A}$ admits a Maltsev polymorphism is a computational problem, which can be solved in polynomial time. We provide a proof of this result by reducing the problem to deciding whether a binary relational structure, associated with $\mathbf{A}$ admits such a polymorphism. In our construction of such an algorithm, we make an extensive use of a property of binary relations, which is implied by the existence of a Maltsev polymorphism, the so-called rectangularity property.

Tue 10 NovComputational Complexity
The gist
This paper tackles the question of whether certain mathematical structures, called finite relational structures, have a special kind of operation known as a Maltsev polymorphism. The authors show there is an efficient algorithm that can determine this quickly, even for large structures. Their approach works by transforming the problem to a simpler one involving only pairs of elements, using a property called rectangularity. This result means checking for these polymorphisms is easier than previously thought.
Open → 2611.14379v1

Complexity grows steeply in queries with multiple heads and transitivity

Answering Conjunctive Queries over Linear Existential Rules with Transitivity

Abstract: We study Conjunctive Query Entailment Problem over ontologies con- sisting of Linear Tuple Generating Dependencies and transitivity asser- tions. A special case of this problem has been shown to be decidable in [1]. In particular, it covers the case of linear single head TGDs with bi- nary signature. In This paper we show that The problem for linear multi head TGDs with binary signature is Ackermanian hard

Mon 9 NovDatabases
The gist
This paper looks at a type of logical question called conjunctive queries, which are used to get information from databases with certain rules. The authors study what happens when these rules include transitivity (like if A relates to B and B to C, then A relates to C) combined with linear rules that can have multiple outputs. While simpler versions of the problem are manageable, they found that adding multiple outputs makes the problem extremely hard to solve, even harder than some well-known tough problems. This means that building efficient systems for these queries with such rules will be challenging.
Open → 2611.13138v1

Semiring query interpretations cannot express SQL subtraction operation

Monus vs. Interpretations in Semiring Semantics

Abstract: Interpretations have been widely used in the study of provenance of queries on semiring-annotated databases. Here, we consider two different interpretation-based semantics for first-order formulas in negation normal form, namely, the canonical-interpretation semantics and the compatible-interpretation semantics. We show that the resulting query languages cannot express the monus operation on semiring-annotated relations, when the annotations come from the bag semiring or the tropical semiring or the fuzzy semiring. Consequently, the semantics of SQL cannot be captured using the interpretation-based semantics considered here.

Thu 5 NovDatabases
The gist
This paper looks at specific ways to understand how database queries work when the data includes extra information called semiring annotations. The authors find that two common interpretation methods for queries in such databases cannot perform the 'monus' operation, which is similar to subtraction. This means that these methods cannot fully capture how SQL handles certain operations. Their findings limit how these interpretation techniques can be used to represent database query semantics.
Open → 2611.08474v1

Monadically dependent graphs have nearly limited merge-width measures

Monadically Dependent Graph Classes Have Almost Bounded Merge-Width

Abstract: A graph class $\mathcal{C}$ is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from $\mathcal{C}$ using a fixed formula of first-order logic. We prove that every monadically dependent graph class has almost bounded merge-width, thereby confirming a conjecture of the first and the last author [STOC '25]. Our proof is algorithmic and the witnessing decompositions in the form of merge sequences can be computed in nearly-cubic time. This is a step towards the proof of fixed-parameter tractability of model checking first-order logic on monadically dependent graph classes, which is achieved in a companion paper.

Wed 4 NovDiscrete MathematicsData Structures and AlgorithmsLogic in Computer Science
The gist
The paper looks at special groups of graphs called monadically dependent graph classes, which avoid being too complex in a specific logical way. The authors prove these graphs can be described using a method called merge-width that is almost bounded, meaning it doesn’t grow too large. They also provide an algorithm to find these descriptions efficiently. This finding helps with understanding how to quickly check logical properties on such graphs in future work.
Open → 2611.06804v1

Maximum size of non-redundant independence sets found for databases

Non-redundant Independence Atoms

Abstract: Independence atom is a key concept in relational database theory. In the present paper, we prove that the maximum possible size of a non-redundant set of independence atoms on $n$ attributes is asymptotically $(1+o(1))\binom{n}{\floor{n/2}}$. It turns out that this problem is closely related to two extremal set theory problems, the Katona-Tarján question on ``V''-free families of subsets of $[n]$ for the lower bound, and Kleitman's bound on union-free families for the upper bound.

Tue 3 NovDatabases
The gist
In databases, independence atoms describe when some data attributes don't affect others. The authors show the largest possible set of these independent rules that don’t overlap too much grows like a special large combination number. They connect this problem to known questions in math about certain groups of sets without specific patterns. Their work gives a clearer sense of how complex these independence conditions can get as the number of attributes grows.
Open → 2611.05568v1

Complexity limits for queries with negation on semiring databases

Containment of Conjunctive Queries with Negative Information over Semirings

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.

Tue 20 OctLogic in Computer ScienceDatabases
The gist
This paper looks at how hard it is to check if one database question (query) that includes negative information can fit inside another, when the data has special labels called semirings. The researchers study two ways negativity shows up in queries, and find that the difficulty depends on what kinds of labels the data uses. They also show that some queries are surprisingly no harder than normal queries, while others get more complex. Their findings help understand the limits of working with negative information in complex database settings.
Open → 2610.27957v1

Deciding finite logic satisfiability with multiple successor relations

Finite Satisfiability of Two-Variable Logic with Arbitrarily Many Successors

Abstract: We study finite satisfiability of two-variable first-order logic over structures equipped with an arbitrary finite number of independent successor relations of linear orders. The number of successor relations is part of the input, and the vocabulary may contain further unrestricted unary and binary relations. We prove decidability in deterministic doubly exponential space together with a triply exponential bound on the size of a smallest finite model. This settles the unrestricted finite case beyond two successors.

Wed 14 OctLogic in Computer Science
The gist
Figuring out if some logical statements have a solution can be tough, especially when the logic allows only two variables but multiple ways to move from one item to the next. This paper looks at that problem when there are many successor types, meaning many ways to step forward independently. The authors show it is possible to decide if such statements can be satisfied in a finite setting, although it requires complex and large computations. They also provide precise bounds on how big the smallest solutions can be.
Open → 2610.19943v1

Tight bounds found for testing if two distributions match

Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples

Abstract: We study distribution testing with access to non-adaptive conditional samples. Specifically, we give tight bounds for equivalence testing, determining whether two unknown distributions are equal to or $\varepsilon$-far from each other in total variation distance. Our algorithm and lower bound show that $\tilde Θ\left(\frac{\log n}{\varepsilon^2}\right)$ queries are necessary and sufficient for this problem. These results demonstrate that the complexity of uniformity, identity, and equivalence testing with non-adaptive conditional samples are all $\tilde Θ(\log n)$.

Thu 8 OctData Structures and AlgorithmsInformation Theory
The gist
Checking if two unknown collections of things are the same or quite different is important for many applications. The authors studied how many questions you need to ask to decide this when you can only ask certain types of questions chosen in advance. They found the smallest number of questions needed and proved you cannot do better, showing this number grows roughly with the logarithm of the size involved. This clarifies how difficult these testing problems are under specific sampling restrictions.
Open → 2610.11145v1

Exponential size gap found between two logic query languages

An Exponential Succinctness Gap between Three-Variable Logic and the Calculus of Relations

Abstract: Three-variable first-order logic (FO3) and the calculus of relations (CoR) define the same binary queries, an equivalence going back to Tarski in the 1940s. While the classical translation $\text{FO3} \Rightarrow \text{CoR}$ is exponential, we prove that this blow-up is unavoidable, resolving a long-standing open question. We construct positive formulas $\varphi$ with a single quantifier whose equivalent terms require size $2^{Ω(|\varphi|)}$, even over finite structures and circuit representations with subterm sharing. Our proof uses a preservation argument over a single finite structure. This approach applies beyond our primary question, establishing the lower bound even for size-specific circuits and bounded-error randomized circuits, and yielding an analogous exponential gap for the matrix query language MATLANG.

Tue 22 SeptLogic in Computer ScienceComputational Complexity
The gist
Some ways of describing database queries use different logical languages. The authors show that when you switch from one language called three-variable logic to another called the calculus of relations, the descriptions can get exponentially larger. This means that certain logical expressions become much more complex and longer when translated between these languages. Their proof works even on small or finite data and applies to related query systems too.
Open → 2609.26778v1

Compressed subsequence checking is computationally hard even on two letters

Compressed Subsequence Checking is PSPACE-complete

Abstract: It is shown that the (scattered) subsequence problem for two words represented by straight-line programs is PSPACE-complete, even over a binary alphabet. The lower bound is obtained by a polynomial-time reduction from quantified subset sum.

Sun 13 SeptFormal Languages and Automata Theory
The gist
The problem of checking if one sequence appears scattered within another can be tricky when the sequences are stored in compressed forms. The authors show that deciding this is as tough as the hardest problems known in a complexity class called PSPACE, meaning it likely requires a lot of computational resources. This holds true even when the sequences only use two letters. They reached this conclusion by relating the problem to a well-known challenging problem called quantified subset sum.
Open → 2609.14490v1

Algorithm tests binary rank of matrices with fewer queries

Testing the Binary Rank with Polynomial Query Complexity

Abstract: We provide an adaptive two-sided error testing algorithm for the binary rank of a $0,1$ matrix $M$ with query complexity $O(d^3\log(d+1)/ε^2)$, where $d$ is the tested binary rank bound and $ε$ is the distance parameter. This answers an open question posed by Parnas, Ron and Shraibman~\cite{parnas2021property}, who asked whether the binary rank can be tested with query complexity polynomial in $d$ and $1/ε$. Furthermore, our testing algorithm can be used to find an approximate binary decomposition of $M$ with an additional $d(n+m)$ queries. That is, under the promise that the binary rank of $M$ is at most $d$, we show how to find, with probability at least $5/6$, two $0,1$ matrices $A',B'$ such that $M' = A' \cdot B'$ is a $0,1$ matrix which differs from $M$ on at most an $O(ε)$ fraction of its entries.

Wed 9 SeptData Structures and AlgorithmsDiscrete Mathematics
The gist
Figuring out the complexity of a matrix made of zeros and ones is a tricky problem. The authors created a new method that can quickly check if the matrix’s binary rank is below a certain limit. Their method works by only looking at a small part of the matrix, rather than the entire thing. If the matrix fits the limit, the method can also help build a close approximation of it.
Open → 2609.10496v1