Publikationsdatum:
2014-05-01
Beschreibung:
The problems of query containment, equivalence and minimization are fundamental problems in the context of query processing and optimization. In their classic work published in 1977 [Chandra, A. and Merlin, P. (1977) Optimal Implementation of Conjunctive Queries in Relational Data Bases. Proc. ACM STOC , Boulder, CO, USA, May 4–6, pp. 77–90, ACM, USA], Chandra and Merlin solved the three problems for the language of conjunctive queries (CQ queries) on relational data, under the ‘set-semantics’ assumption for query evaluation. While the results of Chandra and Merlin ((1977) Optimal Implementation of Conjunctive Queries in Relational Data Bases. Proc. ACM STOC , Boulder, CO, USA, May 4–6, pp. 77–90, ACM, USA] have been very influential in database research, it was recognized long ago that the set semantics does not correspond to the semantics of the standard commercial query language structured query language (SQL). Alternative semantics, called bag and bag-set semantics , have been studied since 1993; Chaudhuri and Vardi [(1993) Optimization of Real Conjunctive Queries (Extended Abstract). Proc. PODS , Washington, DC, USA, May 25–28, pp. 59–70. ACM Press, USA] outlined necessary and sufficient conditions for the equivalence of CQ queries under these semantics. (The problems of containment of CQ bag and bag-set queries remain open to this day.) More recently, Cohen [(2006) Equivalence of Queries Combining Set and Bag-Set Semantics. Proc. PODS , Chicago, IL, USA, 26–28 June, pp. 70–79. ACM, USA; (2009) Equivalence of queries that are sensitive to multiplicities. VLDB J. , 18, 765–785] introduced a formalism for treating (generalizations of) CQ queries evaluated under each of set, bag and bag-set semantics uniformly as special cases of the more general combined semantics . This formalism provides tools for studying broader classes of practical SQL queries, specifically important types of queries that arise in on-line analytical processing. Cohen [(2009) Equivalence of queries that are sensitive to multiplicities. VLDB J. , 18, 765–785] provides a sufficient condition for the equivalence of (generalizations of) combined-semantics CQ queries, as well as sufficient and necessary equivalence conditions for several proper sublanguages of the query language of Cohen ((2009) Equivalence of queries that are sensitive to multiplicities. VLDB J. , 18, 765–785]. To the best of our knowledge, no results on minimization of CQ queries beyond set-semantics queries have been reported in the literature. Our goal in this paper is to continue the study of equivalence and minimization of CQ queries. We focus on the practically important problem of finding minimized versions of combined-semantics CQ queries. The main contribution of this paper is the extension of the minimization result of Chandra and Merlin ((1977) Optimal Implementation of Conjunctive Queries in Relational Data Bases. Proc. ACM STOC , Boulder, CO, USA, May 4–6, pp. 77–90, ACM, USA] to all combined-semantics CQ queries; we develop this result using our sufficient condition for containment of combined-semantics CQ queries [Chirkova, R. (2012) Combined-semantics equivalence is decidable for a practical class of conjunctive queries. Submitted for publication]. We also present an extension to all combined-semantics CQ queries of the well-known equivalence condition of Chandra and Merlin ((1977) Optimal Implementation of Conjunctive Queries in Relational Data Bases. Proc. ACM STOC , Boulder, CO, USA, May 4–6, pp. 77–90. ACM, USA] of CQ set-semantics queries. Similarly to the condition of Chandra and Merlin ((1977) Optimal Implementation of Conjunctive Queries in Relational Data Bases. Proc. ACM STOC , Boulder, CO, USA, May 4–6, pp. 77–90. ACM, USA], our extension is given in terms of the relationship between the minimized versions of the queries.
Print ISSN:
0010-4620
Digitale ISSN:
1460-2067
Thema:
Informatik
Permalink