Title 



Static analysis of schemamappings ensuring oblivious termination
 
Author 



 
Abstract 



A schemamapping is a high level specification of a dataexchange setting where a set of sourcetotarget 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 schemamappings that allow for additional constraints such as source dependencies on the source schema and targettosource dependencies from the target relations back to the source. Furthermore, strong schemamappings 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 schemamappings which is to determine whether a given constraint δ 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 Σ 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 schemamappings. 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 sourcetotarget constraints in a strong schemamapping are already implied by the embedded (standard) schemamapping. This problem is important if one wants to use targettosource constraints in standard dataexchange tools. Since no such constraints are logically implied by standard schemamappings (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 dataexchange tool. We consider three semantics based on universal solutions, cores and CWAsolutions, respectively. Decidability of the implication of general (resp. safe) targettosource constraints is shown for the CWAbased semantics (resp. coresemantics).   
Language 



English
 
Source (book) 



Proceedings of the 13th International Conference on Database Theory (ICDT 2010), Lausanne, Switzerland, March 2325, 2010 / Segoufin, Luc [edit.]  
Source (series) 



ACM international conference proceedings series  
Publication 



S.l. : ACM, 2010
 
ISBN 



9781605589473
 
Volume/pages 



p. 183195
 
Full text (Publishers DOI) 


  
