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.

This work addresses the problem of efficient processing of queries in very large numerical databases. Previous focus has been on the design of index structures for the efficient access of data. Recently more and more statistical methods have been used in query optimization. Those methods approximate the distribution of the attribute values to estimate the selectivity of query results. A methodology that uses regression techniques to approximate the actual attribute values is introduced. Through analysis of the data, one derives a set of characteristic functions to form a "regression database", a compressed image of the original database. Based on these functions, approximate answers to queries may be provided within a pre-specified tolerable error, but without the expensive search overhead usually inherent with the use of indexing techniques. A framework to build regression databases is proposed. An experimental prototype is implemented to evaluate the technique in terms of realizability, efficiency and practicality. This technique is complementary to conventional approaches and to statistical methods.

A class of order-preserving dynamic hashing structures is introduced and analyzed. The access method is referred to as the dynamic random-sequential access method (DRSAM) and is derived from linear hashing. A new logical to physical mapping that is based on sequential bucket allocations in hash order is proposed. With respect to previous methods, this allocation technique has the following characteristics: (1) the structure captures the hashed order in consecutive storage areas so that order preserving (OPH) schemes should result in performance improvements for range queries and sequential processing; and (2) it adapts elastic buckets for the control of file growth. Under specific conditions, this approach outperforms the partial expansion method previously proposed by P.-A. Larson (1982).>

A novel class of order-preserving dynamic hashing structures is introduced and analyzed. The access method is referred to as dynamic random-sequential access method (DRSAM) and is derived from linear hashing. With respect to previous methods DRSAM presents the following characteristics: (1) the structure captures the hashed order in consecutive storage areas so that order-preserving schemes result in performance improvements for range queries and sequential processing; and (2) it adapts elastic buckets for the control of file growth. This approach outperforms the partial expansion method. The file structure is also extended with proper control mechanisms to cope with nonuniform distributions. The outcome is a multilevel trie stored as a two-level sequentially allocated file.>