The integration of data, especially from heterogeneous sources, is a hard and widely studied problem. One particularly challenging issue is the integration of sources that are semantically equivalent but schematically heterogeneous. While two such data sources may represent the same information, one may store the information inside tuples (data) while the other may store it in attribute or relation names (schema). The SchemaSQL query language is a recent solution to this problem powerful enough to restructure such sources into each other without the loss of information. We propose the first incremental view maintenance strategy for such schema-restructuring views. Our strategy, based on an algebraic representation of the view query, correctly transforms a data update or a schema change to a source into sequences of schema and data updates to be applied to the view. We also introduce an optimization of incremental maintenance using batching. We present a proof of correctness of the propagation approach. We also describe the implementation of our SchemaSQL Query Processor and View Maintainer. Last, our experimental results demonstrate that, in many cases, incremental SchemaSQL view maintenance is significantly faster than complete view recomputation.

Determining relationships such as functional or inclusion dependencies within and across databases is important for many applications in information integration. When such information is not available as explicit meta data, it is possible to discover potential dependencies from the source database extents. However, the complexity of such discovery problems is typically exponential in the number of attributes. We have developed an algorithm for the discovery of inclusion dependencies across high-dimensional relations in the order of 100 attributes. This algorithm is the first to efficiently solve the inclusion-dependency discovery problem. This is achieved by mapping it into a progressive series of clique-finding problems in k-uniform hypergraphs and solving those. Extensive experimental studies confirm the algorithm's efficiency on a variety of real-world data sets.

Query rewriting with relaxed semantics has been proposed as a means of retaining the validity of a data warehouse (i.e., materialized queries) in a changing environment. Attributes in the query interface can be classified as essential or dispensable (if it cannot be retained) according to the query definer's preferences. Similarly, preferences for query extent can be specified, for example, to indicate whether a subset of the original result is acceptable or not. The paper discusses the trade-off between quality and cost of query rewriting.

Supporting independent ISs and integrating them in distributed data warehouses (materialized views) is becoming more important with the growth of the WWW. However, views defined over autonomous ISs are susceptible to schema changes. In the EVE project we are developing techniques to support the maintenance of data warehouses defined over distributed dynamic ISs [5, 6, 7]. The EVE system is the first to allow views to survive schema changes of their underlying ISs while also adapting to changing data in those sources. EVE achieves this is two steps: applying view query rewriting algorithms that exploit information about alternative ISs and the information they contain, and incrementally adapting the view extent to the view definition changes. Those processes are referred to as view synchronization and view adaption, respectively. They increase the survivability of materialized views in changing environments and reduce the necessity of human interaction in system maintenance.

Material&d views (data warehouses) are becoming increasingly important in the context of distributed modem environments such as the World Wide Web.Information sources (I%) in such an environment may change their capabilities (schema), causing a data warehouse to become undefined.This process to evolve (rewrite) view queries after capability changes of ISs is referred to ss view synchronization.Current view synchronization algorithms generate a potentially large number of valid solutions for the rewriting of a view query and according to our analysis in this paper have high complexity (in O(n!)).We propose to reduce this complexity by representing the synchronization problem as a graph traversal problem.Once this mapping has been applied, the problem can be reduced to a single-source shortestpath problem in graphs, which can be solved with O(n3) complexity using the Bellman-Ford algorithm.