Testing bag-containment of conjunctive queries (Q1920218)

Among the bag-theoretic semantics relations are bags of tuples, that is, a tuple may have any number of duplicates. Among this semantics, a conjunctive query \(Q\) is bag-contained in a conjunctive query \(Q'\), denoted \(Q\leq_b Q'\), if for all databases \({\mathcal D}\), \(Q({\mathcal D})\), the result of applying \(Q\) to \({\mathcal D}\), is a subbag of \(Q' ({\mathcal D})\). It is not known whether testing \(Q\leq_b Q'\) is decidable. In this paper we prove that \(Q\leq_b Q'\) can be tested on a finite set of canonical databases built from the body of \(Q\). Using that result we give a procedure that decides the bag-containment problem of conjunctive queries in a large number of cases.