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.
As observed in , to the best of our knowledge, the formal problem that we address in this current paper has not been considered in the open literature. (Abiteboul and Duschka in @cite_9 consider the special case where the set of dependencies is empty, apply in their analysis a different type of complexity metric than we do in this paper, and do not provide algorithms alongside their complexity results.) The work @cite_26 addresses a problem that is similar to ours at the informal level; see for a detailed discussion of @cite_26 . Generally, the literature on privacy-preserving query answering and data publishing is represented by work on data anonymization and on differential privacy; @cite_3 is a recent survey. Most of that work focuses on probabilistic inference of private information, while in this paper we focus on the possibilistic situation, where an adversary can deterministically derive sensitive information. Further, our model of sensitive information goes beyond associations between individuals and their private sensitive attributes.
@cite_9 @cite_26 @cite_3
2160983447 2087154854
We study the complexity of the problem of answering queries using materialized views. This problem has attracted a lot of attention recently because of its relevance in data integration. Previous work considered only conjunctive view definitions. We examine the consequences of allowing more expressive view definition languages. The languages we consider for view definitions and user queries are: conjunctive queries with inequality, positive queries, datalog, and first-order logic. We show that the complexity of the problem depends on whether views are assumed to store all the tuples that satisfy the view definition, or only a subset of it. Finally, we apply the results to the view consistency and view self-maintainability problems which arise in data warehousing. We perform a theoretical study of the following query-view security problem: given a view V to be published, does V logically disclose information about a confidential query S? The problem is motivated by the need to manage the risk of unintended information disclosure in today's world of universal data exchange. We present a novel information-theoretic standard for query-view security. This criterion can be used to provide a precise analysis of information disclosure for a host of data exchange scenarios, including multi-party collusion and the use of outside knowledge by an adversary trying to learn privileged facts about the database. We prove a number of theoretical results for deciding security according to this standard. We also generalize our security criterion to account for prior knowledge a user or adversary may possess, and introduce techniques for measuring the magnitude of partial disclosures. We believe these results can be a foundation for practical efforts to secure data exchange frameworks, and also illuminate a nice interaction between logic and probability theory.