Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability

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 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 φ s and φ b , and a linear function F, the inequality F(φ s (D)) ≤ φ b (D) holds for each database instance D, is undecidable 1 .