Combined-semantics equivalence of conjunctive queries: Decidability and tractability results

Query containment and equivalence are fundamental problems in the context of query processing and optimization. In this paper, we consider combined-semantics equivalence of conjunctive (CQ) queries. The combined-semantics formalism [10] and [11] generalizes the well-known and practically useful notions of set, bag, and bag-set semantics for CQ queries. It also provides tools for studying practical SQL queries, specifically important types of queries arising in on-line analytical processing. In our study, we introduce a containment-based algorithm for deciding combined-semantics equivalence for pairs of CQ queries that belong to a large well-behaved class of “explicit-wave” queries. Our algorithm, as well as our general sufficient condition for containment of combined-semantics CQ queries, generalizes in a uniform way the tests reported in [3], [6] and [11]. Moreover, we single out a subclass of explicit-wave CQ queries for which it is tractable to determine combined-semantics equivalence.