Search Results

Bag-semantics allows for atomic relations and query answers to contain multiple copies of the same data tuple, reflecting real-world database systems more accurately. Deciding containment under bag-semantics (or simply, bag-containment) for two conjunctive queries (CQs) requires determining whether the answer of the first query, taking multiplicities into account, is contained within the answer of the second query, across all databases. Despite numerous attempts in the last thirty years, this problem of determining decidability and complexity of this task remains open as one of the prominent challenges in database theory, given its relevance in important applications. Previous works have established the decidability of the problem for specific classes of queries, among which is the the bag-containment of projection-free queries (PFQs), i.e., queries without existentially quantified variables, into general CQs. In this work, we push the boundaries further by addressing a broader, yet natural, fragment of CQs, called join-on-free queries (JoFQ), which allows existential variables, while prohibiting joins involving them. We prove decidability of bag-containment of a JoFQ within a general CQ, placing the complexity of the problem in the first non-deterministic layer of the exponential hierarchy. The approach involves a homomorphism-counting reduction to the solution of a system of Diophantine inequalities with a specific structure (an undecidable problem in its general form) and an algorithm designed to address this category of inequalities.