We consider the problems of finding and determining certain query answers and of determining containment between queries; each problem is formulated in presence of materialized views and dependencies under the closed-world assumption. We show a tight
relationship between the problems in this setting. Further, we introduce algorithms for solving each problem for those inputs where all the queries and views are conjunctive, and the dependencies are embedded weakly acyclic. We also determine the complexity of each problem under the security-relevant complexity measure introduced by Zhang and Mendelzon in 2005. The problems studied in this paper are fundamental in ensuring correct specification of database access-control policies, in particular in case of fine-grained access control. Our approaches can also be applied in the areas of inference control, secure data publishing, and database auditing.
In this paper, we focus on the problem of determining whether two conjunctive (CQ) queries posed on relational data are combined-semantics equivalent [9]. We continue the tradition of [2,5,9] of studying this problem using the tool of containment bet
ween queries. We introduce a syntactic necessary and sufficient condition for equivalence of queries belonging to a large natural language of explicit-wave combined-semantics CQ queries; this language encompasses (but is not limited to) all set, bag, and bag-set queries, and appears to cover all combined-semantics CQ queries that are expressible in SQL. Our result solves in the positive the decidability problem of determining combined-semantics equivalence for pairs of explicit-wave CQ queries. That is, for an arbitrary pair of combined-semantics CQ queries, it is decidable (i) to determine whether each of the queries is explicit wave, and (ii) to determine, in case both queries are explicit wave, whether or not they are combined-semantics equivalent, by using our syntactic criterion. (The problem of determining equivalence for general combined-semantics CQ queries remains open. Even so, our syntactic sufficient containment condition could still be used to determine that two general CQ queries are combined-semantics equivalent.) Our equivalence test, as well as our general sufficient condition for containment of combined-semantics CQ queries, reduce correctly to the special cases reported in [2,5] for set, bag, and bag-set semantics. Our containment and equivalence conditions also properly generalize the results of [9], provided that the latter are restricted to the language of (combined-semantics) CQ queries.
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) querie
s, 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.
