TESTING BAG-CONTAINMENT OF CONJUNCTIVE QUERIES

Under the bag-theoretic semantics relations are bags of tuples, that i s, a tuple may have any number of duplicates. Under this semantics, a conjunctive query Q is bag-contained in a conjunctive query Q(1), deno ted Q less than or equal to(b) Q', if for all databases D, Q(D), the r esult of applying Q to D, is a subbag of Q'(D). It is not known whethe r testing Q Ib Q' is decidable. In this paper we prove that Q less tha n or equal to(b) Q' can be tested on a finite set of canonical databas es built from the body of Q, Using that result we give a procedure tha t decides the bag-containment problem of conjunctive queries in a larg e number of cases.