Static Analysis of Schema-Mappings Ensuring Oblivious Termination

摘要

A schema-mapping is a high level specification of a data-exchange setting where a set of source-to-target dependencies is used to realize basic operations from source to target relations (such as copy, selection, join or union) while the target schema is subject to a set of target constraints (such as inclusion dependencies or key constraints). In this paper, we consider strong schema-mappings that allow for additional constraints such as source dependencies on the source schema and target-to-source dependencies from the target relations back to the source. Furthermore, strong schema-mappings may include disjunctive dependencies. We argue that this extension is desirable when the source instance is to provide both a lower and upper bound on the information that a target instance can have. We first focus on the implication problem for strong schema-mappings which is to determine whether a given constraint S is logically implied by the set ∑ of constraints (denoted by ∑ |= δ). After providing complete characterizations for this problem in terms of universal solutions (while supporting equality constraints), we introduce criteria of termination, denoted by TOC, DTOC and MTOC, that allow the efficient computation of universal solutions for standard constraints, disjunctive constraints, and when the source instance is assumed to be immutable (i.e., it is master data), respectively. We obtain decision procedures for the implication problem, provided that E satisfies these termination conditions, and give the corresponding complexity bounds. As an immediate application we revisit the problems of determinacy, relative information completeness and variations thereof, all for strong schema-mappings. Indeed, by viewing them as implication problems we obtain efficient decision procedures when the relevant termination conditions are satisfied. We then focus on the problem of deciding whether source-to-target constraints in a strong schema-mapping are already implied by the embedded (standard) schema-mapping. This problem is important if one wants to use target-to-source constraints in standard data-exchange tools. Since no such constraints are logically implied by standard schema-mappings (and hence the results established earlier are of no use), we provide an alternative semantics for implication. More specifically, we want the constraint to be satisfied by every solution corresponding to the output of a standard data-exchange tool. We consider three semantics based on universal solutions, cores and CWA-solutions, respectively. Decidability of the implication of general (resp. safe) target-to-source constraints is shown for the CWA-based semantics (resp. core-semantics).