Query containment under bag and bag-set semantics
Foto N. Afrati, Matthew Damigos, and Manolis Gergatsoulis
Abstract: Conjunctive queries (CQs) are at the core of query
languages encountered in many logic-based research fields such as
AI, or database systems. The majority of existing work assumes set semantics but
often in real applications the manipulation
of duplicate tuples is required. One of the major problems that arises as part
of advanced features of query optimization,
data integration, query reformulation and many other research topics is testing
for containment of such queries.
In this work,
we investigate the complexity of query containment problem for CQs under bag
semantics (i.e. duplicate tuples are allowed
in both the database and the results of queries) and under bag-set semantics
(i.e. duplicates are allowed
in the result of the queries but not in the database). We derive complexity
results for these problems for five major subclasses of CQs; and we also find
necessary conditions for CQ query containment. The general case of these
problems remains open.