Data warehouses collect large quantities of data from distributed sources into a single repository. A typical load to create or maintain a warehouse processes GBs of data, takes hours or even days to execute, and involves many complex and user-defined transformations of the data (e.g., find duplicates, resolve data inconsistencies, and add unique keys). If the load fails, a possible approach is to “redo” the entire load. A better approach is to resume the incomplete load from where it was interrupted. Unfortunately, traditional algorithms for resuming the load either impose unacceptable overhead during normal operation, or rely on the specifics of transformations. We develop a resumption algorithm called DR that imposes no overhead and relies only on the high-level properties of the transformations. We show that DR can lead to a ten-fold reduction in resumption time by performing experiments using commercial software.

On the Internet, the limited query processing capabilities of sources make answering even the simplest queries challenging. We present a scheme called GenCompact for generating capability-sensitive plans for queries on Internet sources. The query plans generated by GenCompact have the following advantages over those generated by existing query processing systems: the sources are guaranteed to support the query plans; the plans take advantage of the source capabilities; and the plans are more efficient since a larger space of plans is examined.

No abstract available.

No abstract available.

Data warehouses collect copies of information from remote sources into a single database. Since the remote data is cached at the warehouse, it appears as local relations to the users of the warehouse. To improve query response time, the warehouse administrator will often materialize views defined on the local relations to support common or complicated queries. Unfortunately, the requirement to keep the views consistent with the local relations creates additional overhead when the remote sources change. The warehouse is often kept only loosely consistent with the sources: it is periodically refreshed with changes sent from the source. When this happens, the warehouse is taken off-line until the local relations and materialized views can be updated. Clearly, the users would prefer as little down time as possible. Often the down time can be reduced by adding carefully selected materialized views or indexes to the physical schema. This paper studies how to select the sets of supporting views and of indexes to materialize to minimize the down time. We call this the view index selection (VIS) problem. We present an A* search based solution to the problem as well as rules of thumb. We also perform additional experiments to understand the space-time tradeoff as it applies to data warehouses.

Summary form only given. The goal of the Whips project (WareHousing Information Project at Stanford) is to develop algorithms and tools for the creation and maintenance of a data warehouse (J. Wiener et al., 1996). In particular, we have developed an architecture and implemented a prototype for identifying data changes at distributed heterogeneous sources, transforming them and summarizing them in accordance with warehouse specifications, and incrementally integrating them into the warehouse. In effect, the warehouse stores materialized views of the source data. The Whips architecture is designed specifically to fulfil several important and interrelated goals: sources and warehouse views can be added and removed dynamically; it is scalable by adding more internal modules; changes at the sources are detected automatically; the warehouse may be updated continuously as the sources change, without requiring down time; and the warehouse is always kept consistent with the source data by the integration algorithms. The Whips system is composed of many distinct modules that potentially reside on different machines. Each module is implemented as a CORBA object. They communicate with each other using ILU, a COBRA compliant object library developed by Xerox PARC.

A data warehouse is a repository of integrated information from distributed, autonomous, and possibly heterogeneous, sources. In effect, the warehouse stores one or more materialized views of the source data. The data is then readily available to user applications for querying and analysis. Figure 1 shows the basic architecture of a warehouse: data is collected from each source, integrated with data from other sources, and stored at the warehouse. Users then access the data directly from the warehouse.

In this paper, we study the area-balanced multiway partitioning problem of VLSI circuits based on a new dual netlist representation named the hybrid dual netlist (HDN), and propose a general paradigm for multiway circuit partitioning based on dual net transformation. Given a netlist, we first compute a K-way partitioning of nets based on the HDN representation, and then transform the K-way net partition into a K-way module partitioning solution. The main contribution of our paper is in the formulation and solution of the K-way module contention (KMC) problem, which determines the best assignment of the modules in contention to partitions while maintaining user-specified area requirements when we transform the net partition into a module partition. Under a natural definition of binding function between nets and modules, and preference function between partitions and modules, we show that the K-MC problem can be reduced to a min-cost max-flow problem. We present an efficient solution to the K-MC problem based on network flow computation. We apply our dual transformation paradigm to the well-known K-way Fiduccia-Mattheyses (FM) partitioning algorithm (K-FM) and show that the new algorithm, named K-DualFM, reduces the net cutsize by 20% to 31% compared with the K-FM algorithm. We also apply the same paradigm to the K-maximum fanout-free cone (MFFC)-FM algorithm, a K-FM algorithm based on MFFC clustering, and show that the resulting algorithm, K-DualMFFC-FM reduces the net cutsize by 15% to 26% compared with K-MFFC-FM. Furthermore, we compare the K-DualFM algorithm with EIG1 and Paraboli, two recently proposed spectral-based bipartitioning algorithms. We showed that K-DualFM reduces the net cutsize by 56% on average when compared with EIG1 and produces comparable results with Paraboli.