Deciding bag query containment using controlled Diophantine equations
Attacking Diophantus: Special Cases of Bag Containment
Databases
Summary
Checking if one database query always gives answers contained within another is a key problem in databases. When counting duplicate answers (bag semantics), deciding this containment can be very hard or impossible for complex queries. The authors create a new way to handle certain queries, called join-uniform queries, by translating the problem into a special kind of math problem with equations. They prove that for these queries, deciding containment is indeed doable, improving on earlier restricted cases. This work links tricky database questions to classic math problems about numbers.
What this means in practice
- •For database system developers: Enable database engines to decide containment for join-uniform queries under bag semantics, improving query optimization and correctness checks.
- •For data integration teams: Provide tools to verify equivalence and containment of complex queries when combining multiple data sources using bag semantics.
A theory result. No direct application yet.
Authors
George Konstantinidis, Xinzhuo Li, Fabio Mogavero
Abstract
Query containment is a fundamental decision problem in database theory: given two queries, determine whether, over all database instances, every answer produced by the first is also produced by the second. For conjunctive queries under set semantics, the problem is understood through the classical homomorphism-based characterisation. Under bag semantics, the interpretation underlying real relational databases, containment becomes a quantitative comparison of answer multiplicities. Despite decades of work, the decidability of bag containment for conjunctive queries remains open. This frontier is fragile: for slightly more expressive classes, bag containment is undecidable, with negative results relying on reductions from variants of Hilbert's 10th problem. This work develops a unified framework for bag containment of conjunctive queries that subsumes two previously studied decidable cases: projection-free and join-on-free containee queries. The framework yields decidability for a broader class, called join-uniform queries, while leaving the containing query arbitrary. This contrasts with techniques that impose restrictions on the containing query. The approach identifies tractable classes based on the internal unification structure of the query whose multiplicities must be bounded. Specifically, it reduces containment to a controlled Diophantine problem. Starting from the containee query, one builds a canonical model generated by all its possible unifications, over which multiplicities admit a finite arithmetic characterisation. Containment is proved equivalent to the non-existence of solutions of a corresponding Diophantine inequality system. Although these problems are undecidable in general, we show that the systems arising from join-uniform containment form a decidable subclass. Thus, the standard source of undecidability for bag containment becomes the core of the decision procedure.