Computer Science – Databases
Scientific paper
2008-12-11
Computer Science
Databases
Correction of the previous version as described in the last sentence of the Abstract
Scientific paper
We consider the problem of finding equivalent minimal-size reformulations of SQL queries in presence of embedded dependencies [1]. Our focus is on select-project-join (SPJ) queries with equality comparisons, also known as safe conjunctive (CQ) queries, possibly with grouping and aggregation. For SPJ queries, the semantics of the SQL standard treat query answers as multisets (a.k.a. bags), whereas the stored relations may be treated either as sets, which is called bag-set semantics for query evaluation, or as bags, which is called bag semantics. (Under set semantics, both query answers and stored relations are treated as sets.) In the context of the above Query-Reformulation Problem, we develop a comprehensive framework for equivalence of CQ queries under bag and bag-set semantics in presence of embedded dependencies, and make a number of conceptual and technical contributions. Specifically, we develop equivalence tests for CQ queries in presence of arbitrary sets of embedded dependencies under bag and bag-set semantics, under the condition that chase [9] under set semantics (set-chase) on the inputs terminates. We also present equivalence tests for aggregate CQ queries in presence of embedded dependencies. We use our equivalence tests to develop sound and complete (whenever set-chase on the inputs terminates) algorithms for solving instances of the Query-Reformulation Problem with CQ queries under each of bag and bag-set semantics, as well as for instances of the problem with aggregate queries.
Chirkova Rada
Genesereth Michael
No associations
LandOfFree
Equivalence of SQL Queries in Presence of Embedded Dependencies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Equivalence of SQL Queries in Presence of Embedded Dependencies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Equivalence of SQL Queries in Presence of Embedded Dependencies will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-61077