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.
Our results of Sections -- build on the influential framework for data exchange @cite_2 by Fagin and colleagues. Our @math -induced dependencies of resemble target-to-source dependencies @math introduced into (peer) data exchange in @cite_35 . The difference is that @math are embedded dependencies defined at the schema level. In contrast, our disjunctive @math -induced dependencies embody the given set of view answers @math .
@cite_35 @cite_2
2107115563 2116661435 1991380207 2102729564
In this article, we introduce and study a framework, called peer data exchange, for sharing and exchanging data between peers. This framework is a special case of a full-fledged peer data management system and a generalization of data exchange between a source schema and a target schema. The motivation behind peer data exchange is to model authority relationships between peers, where a source peer may contribute data to a target peer, specified using source-to-target constraints, and a target peer may use target-to-source constraints to restrict the data it is willing to receive, but cannot modify the data of the source peer.A fundamental algorithmic problem in this framework is that of deciding the existence of a solution: given a source instance and a target instance for a fixed peer data exchange setting, can the target instance be augmented in such a way that the source instance and the augmented target instance satisfy all constraints of the settingq We investigate the computational complexity of the problem for peer data exchange settings in which the constraints are given by tuple generating dependencies. We show that this problem is always in NP, and that it can be NP-complete even for “acyclic” peer data exchange settings. We also show that the data complexity of the certain answers of target conjunctive queries is in coNP, and that it can be coNP-complete even for “acyclic” peer data exchange settings.After this, we explore the boundary between tractability and intractability for deciding the existence of a solution and for computing the certain answers of target conjunctive queries. To this effect, we identify broad syntactic conditions on the constraints between the peers under which the existence-of-solutions problem is solvable in polynomial time. We also identify syntactic conditions between peer data exchange settings and target conjunctive queries that yield polynomial-time algorithms for computing the certain answers. For both problems, these syntactic conditions turn out to be tight, in the sense that minimal relaxations of them lead to intractability. Finally, we introduce the concept of a universal basis of solutions in peer data exchange and explore its properties. A new coding problem is introduced for a correlated source (X sup n ,Y sup n ) sub n=1 sup spl infin . The observer of X sup n can transmit data depending on X sup n at a prescribed rate R. Based on these data the observer of Y sup n tries to identify whether for some distortion measure spl rho (like the Hamming distance) n sup -1 spl rho (X sup n ,Y sup n ) spl les d, a prescribed fidelity criterion. We investigate as functions of R and d the exponents of two error probabilities, the probabilities for misacceptance, and the probabilities for misrejection. In the case where X sup n and Y sup n are independent, we completely characterize the achievable region for the rate R and the exponents of two error probabilities; in the case where X sup n and Y sup n are correlated, we get some interesting partial results for the achievable region. During the process, we develop a new method for proving converses, which is called "the inherently typical subset lemma". This new method goes considerably beyond the "entropy characterization" the "image size characterization," and its extensions. It is conceivable that this new method has a strong impact on multiuser information theory. This paper investigates the data exchange problem among distributed independent sources. It is based on previous works of the authors [11, 12, 14] in which a declarative semantics for P2P systems has been presented and a mechanism to set different degrees of reliability for neighbor peers has been provided. The basic semantics for P2P systems defines the concept of Maximal Weak Models (in [11, 12, 14] these models have been called Preferred Weak Models. In this paper we rename them and use the term Preferred for the subclass of Weak Model defined here) that represent scenarios in which maximal sets of facts not violating integrity constraints are imported into the peers [11, 12]. Previous priority mechanism defined in [14] is rigid in the sense that the preference between conflicting sets of atoms that a peer can import only depends on the priorities associated to the source peers at design time. In this paper we present a different framework that allows to select among different scenarios looking at the properties of data provided by the peers. The framework presented here allows to model concepts like "in the case of conflicting information, it is preferable to import data from the neighbor peer that can provide the maximum number of tuples" or "in the case of conflicting information, it is preferable to import data from the neighbor peer such that the sum of the values of an attribute is minimum" without selecting a-priori preferred peers. To enforce this preference mechanism we enrich the previous P2P framework with aggregate functions and present significant examples showing the flexibility of the new framework. Data exchange is the problem of taking data structured under a source schema and creating an instance of a target schema that reflects the source data as accurately as possible. In this paper, we address foundational and algorithmic issues related to the semantics of data exchange and to the query answering problem in the context of data exchange. These issues arise because, given a source instance, there may be many target instances that satisfy the constraints of the data exchange problem.We give an algebraic specification that selects, among all solutions to the data exchange problem, a special class of solutions that we call universal. We show that a universal solution has no more and no less data than required for data exchange and that it represents the entire space of possible solutions. We then identify fairly general, yet practical, conditions that guarantee the existence of a universal solution and yield algorithms to compute a canonical universal solution efficiently. We adopt the notion of the "certain answers" in indefinite databases for the semantics for query answering in data exchange. We investigate the computational complexity of computing the certain answers in this context and also address other algorithmic issues that arise in data exchange. In particular, we study the problem of computing the certain answers of target queries by simply evaluating them on a canonical universal solution, and we explore the boundary of what queries can and cannot be answered this way, in a data exchange setting.