# Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability

arXiv: https://arxiv.org/abs/2503.18003 · HTML: https://mlsanity.com/paper/2503.18003/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Mar 2025.

## Built on by (most cited first, 1 of 1)

- [EXPO-SQL: Execution-based Clause-level Policy Optimization for Text-to-SQL](https://mlsanity.com/paper/2606.23693/) (2026)

## Abstract (arXiv)

Query Containment Problem (QCP) is one of the most fundamental decision problems in database query processing and optimization. Complexity of QCP for conjunctive queries (QCP-CQ) has been fully understood since 1970s. But, as Chaudhuri and Vardi noticed in their classical 1993 paper [1], this understanding is based on the assumption that query answers are sets of tuples, and it does not transfer to the situation when multi-set (bag) semantics is considered. Now, 30 years after [1] was written, decidability of QCP-CQ for bag semantics remains an open question, one of the most intriguing open questions in database theory. In this paper we show a series of undecidability results for some generalizations of bag-semantics QCP-CQ. We show, for example, that the problem whether, for given two boolean conjunctive queries Q and Q' , and a linear function F, the inequality F(Q(D)) =< Q'(D) holds for each database instance D, is undecidable