Data Mining: An Overview from a Database Perspective <s> Data cube approach <s> The topic of data warehousing encompasses architectures, algorithms, and tools for bringing together selected data from multiple databases or other information sources into a single repository, called a data warehouse, suitable for direct querying or analysis. In recent years data warehousing has become a prominent buzzword in the database industry, but attention from the database research community has been limited. In this paper we motivate the concept of a data warehouse, we outline a general data warehousing architecture, and we propose a number of technical issues arising from the architecture that we believe are suitable topics for exploratory research. <s> BIB001 </s> Data Mining: An Overview from a Database Perspective <s> Data cube approach <s> A warehouse is a repository of integrated information drawn from remote data sources. Since a warehouse effectively implements materialized views, we must maintain the views as the data sources are updated. This view maintenance problem differs from the traditional one in that the view definition and the base data are now decoupled. We show that this decoupling can result in anomalies if traditional algorithms are applied. We introduce a new algorithm, ECA (for "Eager Compensating Algorithm"), that eliminates the anomalies. ECA is based on previous incremental view maintenance algorithms, but extra "compensating" queries are used to eliminate anomalies. We also introduce two streamlined versions of ECA for special cases of views and updates, and we present an initial performance study that compares ECA to a view recomputation algorithm in terms of messages transmitted, data transferred, and I/O costs. <s> BIB002
The data cube approach has a few alternative names or a few variants, such as, \multidimensional databases," \materialized views," and \OLAP (On-Line Analytical Processing)." The general idea of the approach is to materialize certain expensive computations that are frequently inquired, es-pecially those involving aggregate functions, such as count, sum, average, max, etc., and to store such materialized views in a multi-dimensional database (called a \data cube") for decision support, knowledge discovery, and many other applications. Aggregate functions can be precomputed according to the grouping by di erent sets or subsets of attributes. Values in each attribute may also be grouped into a hierarchy or a lattice structure. For example, \date" can be grouped into \day," \month," \quarter," \year," or \week", which form a lattice structure. Generalization and specialization can be performed on a multiple dimensional data cube by \roll-up" or \drill-down" operations, where a roll-up operation reduces the number of dimensions in a data cube or generalizes attribute values to high-level concepts, whereas a drill-down operation does the reverse. Since many aggregate functions may often need to be computed repeatedly in data analysis, the storage of precomputed results in a multiple dimensional data cube may ensure fast response time and exible views of data from di erent angles and at di erent abstraction levels. For example, a relation with the schema \sales(part; supplier; customer; sale price)" can be materialized into a set of eight views as shown in Figure 4 There are commonly three choices in the implementation of data cubes: (1) physically materialize the whole data cube, (2) materialize nothing, and (3) materialize only part of the data cube. The problem of materialization of a selected subset of a very large number of views can be modeled as a lattice of views. A recent study 43] has shown that a greedy algorithm, which, given what views have already been materialized, selects for materializing those views that o er the most improvement in average response time, is able to lead to results within 63% of those generated by the optimal algorithm in all cases. As a matter of fact, in many realistic cases, the di erence between the greedy and optimal solutions is essentially negligible. Data cube approach is an interesting technique with many applications 83]. Techniques for indexing multiple dimensional data cubes and for incremental updating of data cubes at database updates have also been studied BIB001 BIB002 . Notice that data cubes could be quite sparse in many cases because not every cell in each dimension may have corresponding data in the database. Techniques should be developed to handle sparse cubes e ciently. Also, if a query contains constants at even lower levels than those provided in a data cube (e.g., a query refers time in the unit of \hour" whereas the lowest concept level on time in the cube is \day"), it is not clear how to make the best use of the precomputed results stored in the data cube.