| This dissertation investigates how constraints can be used to check the consistency of data being exchanged between different sources. Data exchange involves transformations of data, and therefore the "transformed" data can be seen as a view of its source. Thus, the problem we investigate is how constraints are propagated to views, when the data involved is not restricted to relational tables, but may be hierarchically structured in several levels of nesting. The ability to determine constraint propagation relies on the ability to determine constraint implication. This is because the validity of a constraint on the view may not result directly from constraints defined on the source data, but from their consequences. Therefore, the dissertation starts by investigating two forms of constraints: nested functional dependencies and keys for XML, and their implication problems. More specifically, we present a definition of functional dependencies for a nested relational model, and a sound and complete set of inference rules for determining logical implication for the case when no empty sets are present. Motivated by the popularity of XML as a data exchange format, we present a definition of keys for XML that are independent of any type specification. We study two notions of keys: strong keys, and weak keys, and for each of them we derive a sound and complete set of inference rules, as well as algorithms for determining their implication. Capitalizing on the results of XML key implication, we investigate the problem of propagating XML keys to relational views. That is, the problem of determining what are the functional dependencies that are guaranteed to hold in a relational representation of XML data, given that a set of XML keys hold on the XML document. We provide two algorithms: one is to check whether a functional dependency is propagated from XML keys, and the other is to compute a minimum cover for all functional dependencies on a universal relation given certain XML keys. The ability to compute XML key propagation is a first step toward establishing a connection between XML data and its relational representation at the semantic level. |
