This article presents a method for adaptively representing multidimensional data cubes using wavelet view elements in order to more efficiently support data analysis and querying involving aggregations. The proposed method decomposes the data cubes into an indexed hierarchy of wavelet view elements. The view elements differ from traditional data cube cells in that they correspond to partial and residual aggregations of the data cube. The view elements provide highly granular building blocks for synthesizing the aggregated and range-aggregated views of the data cubes. We propose a strategy for selectively materializing alternative sets of view elements based on the patterns of access of views. We present a fast and optimal algorithm for selecting a non-expansive set of wavelet view elements that minimizes the average processing cost for supporting a population of queries of data cube views. We also present a greedy algorithm for allowing the selective materialization of a redundant set of view element sets which, for measured increases in storage capacity, further reduces processing costs. Experiments and analytic results show that the wavelet view element framework performs better in terms of lower processing and storage cost than previous methods that materialize and store redundant views for online analytical processing (OLAP).

This paper describes Seeker, a platform for large-scale text analytics, and SemTag, an application written on the platform to perform automated semantic tagging of large corpora. We apply SemTag to a collection of approximately 264 million web pages, and generate approximately 434 million automatically disambiguated semantic tags, published to the web as a label bureau providing metadata regarding the 434 million annotations. To our knowledge, this is the largest scale semantic tagging effort to date.We describe the Seeker platform, discuss the architecture of the SemTag application, describe a new disambiguation algorithm specialized to support ontological disambiguation of large-scale data, evaluate the algorithm, and present our final results with information about acquiring and making use of the semantic tags. We argue that automated large scale semantic tagging of ambiguous content can bootstrap and accelerate the creation of the semantic web.

Database systems are not well-tuned to take advantage of modern superscalar processor architectures. In particular, the clocks per instruction (CPI) for rather simple database queries are quite poor compared to scientific kernels or SPEC benchmarks. The lack of performance of database systems has been attributed to poor utilization of caches and processor function units as well as higher branching penalties. In this paper, we argue that a block-oriented processing strategy for database operations can lead to better utilization of the processors and caches, generating significantly higher performance. We have implemented the block-oriented processing technique for aggregation expression evaluation and sorting operations as a feature in the DB2 Universal Database (UDB) system. We present results from representative queries on a 30-GB TPC-H (Transaction Processing Council Benchmark H) database to show the value of this technique.

Today's E-Commerce systems are a complex assembly of databases, web servers, home grown glue code, and networking services for security and scalability. The trend is towards larger pieces of these coming together in bundled offerings from leading software vendors, and the networking/hardware being offered through service delivery companies. In this paper we examine the bundle by looking in detail at IBM's WebSphere, Commerce Edition, and its deployment at a major customer site.

In this paper, we present a method for dynamically assembling views in multi-dimensional data cubes in order to more e#ciently support data analysis and querying involving aggregations. The proposed method decomposes the data cubes into an indexed hierarchy of view elements. The view elements di#er from traditional data cube cells in that they correspond to partial and residual aggregations of the data cube. The view elements provide highly granular building blocks for synthesizing the aggregated and rangeaggregated views of the data cubes. We propose a strategy for selecting and materializing the view elements based on the frequency of view access. This allows the dynamic adaptation of the view element sets to patterns of retrieval. We present a fast and optimal algorithm for selecting non-expansive view element sets that minimize the processing costs for generating a population of aggregated views. We also present a greedy algorithm for selecting redundant view element sets in order...

The use of parallel database systems to deliver high performance has become quite common. Although queries submitted to these database systems are executed in parallel, the interaction between applications and current parallel database systems is serial. As the complexity of the applications and the amount of data they access increases, the need to parallelize applications also increases. In this parallel application environment, a serial interface to the database could become the bottleneck in the performance of the application. Hence, parallel database systems should support interfaces that allow the applications to interact with the database system in parallel. We present a taxonomy of such parallel interfaces, namely the Single Coordinator, Multiple Coordinator, Hybrid Parallel, and Pure Parallel interfaces. Furthermore, we discuss how each of these interfaces can be realized and in the process introduce new constructs that enable the implementation of the interfaces. We also qualitatively evaluate each of the interfaces with respect to their restrictiveness and performance impact.

In a multinode data sharing environment, different buffer coherency control schemes based on various lock retention mechanisms can be designed to exploit the concept of deferring the propagation or writing of dirty pages to disk to improve normal performance. Two types of deferred write policies are considered. One policy only propagates dirty pages to disk at the times when dirty pages are flushed out of the buffer under LRU buffer replacement. The other policy also performs writes at the times when dirty pages are transferred across nodes. The dirty page propagation policy can have significant implications on the database recovery time. In this paper, we provide an analytical modeling framework for the analysis of the recovery times under the two deferred write policies. We demonstrate how these policies can be mapped onto a unified analytic modeling framework. The main challenge in the analysis is to obtain the pending update count distribution which can be used to determine the average numbers of log records and data I/Os needed to be applied during recovery. The analysis goes beyond previous work on modeling buffer hit probability in a data sharing system where only the average buffer composition, not the distribution, needs to be estimated, and recovery analysis in a single node environment where the complexities on tracking the propagation of dirty pages across nodes and the buffer invalidation effect do not appear.

In this paper, we describe the architecture and features of DB2 Parallel Edition (PE). DB2 PE belongs to the IBM family of open DB2 client/server database products including DB2/6000, DB2/2, DB2 for HP-UX, and DB2 for the Solaris Operating Environment. DB2 PE employs a shared nothing architecture in which the database system consists of a set of independent logical database nodes. Each logical node represents a collection of system resources including, processes, main memory, disk storage, and communications, managed by an independent database manager. The logical nodes use message passing to exchange data with each other. Tables are partitioned across nodes using a hash partitioning strategy. The cost-based parallel query optimizer takes table partitioning information into account when generating parallel plans for execution by the runtime system. A DB2 PE system can be configured to contain one or more logical nodes per physical processor. For example, the system can be configured to implement one node per processor in a shared-nothing, MPP system or multiple nodes in a symmetric multiprocessor (SMP) system. This paper provides an overview of the storage model, query optimization, runtime system, utilities, and performance of DB2 Parallel Edition.

Replication at the partition level is a promising approach for increasing availability in a Shared Nothing architecture. We propose an algorithm for maintaining replicas with little overhead during normal failure-free processing. Our mechanism updates the secondary replica in an asynchronous manner: entire dirty pages are sent to the secondary at some time before they are discarded from primary's buffer. A log server node (hardened against failures) maintains the log for each node. If a primary node fails, the secondary fetches the log from the log server, applied it to its replica, and brings itself to the primary's last transaction-consistent state. We study the performance of various policies for sending pages to secondary and the corresponding trade-offs between recovery time and overhead during failure-free processing.

In this paper we examine the recovery time in a database system using a Write-Ahead Log protocol, such as ARIES [9], under the assumption that the buffer replacement policy is strict LRU. In particular, analytical equations for log read time, data I/O, log application, and undo processing time are presented. Our initial model assumes a read/write ratio of one, and a uniform access pattern. This is later generalized to include different read/write ratios, as well as a “hot set” model (i.e. x% of the accesses go to y% of the data). We show that in the uniform access model, recovery is dominated by data I/O costs, but under extreme hot-set conditions, this may no longer be true. Furthermore, since we derive anaytical equations, recovery can be analyzed for any set of parameter conditions not discussed here.

Certain analytical results are established about precomputation in a complex object environment. The concept of 'intervals' is introduced and it is shown that object-identifier caching might be beneficial provided the frequency of updates to the set of subobjects associated with an object is not too high. However, in most cases, procedures with value caching outperformed other forms of representations. Certain performance characteristics of a knapsack-based algorithm are established which can be used to optimally decide which of the precomputed results to cache. Simulation results demonstrate how well this scheme performs. In particular, a binary search strategy seems ideally suited for caching.>

With database systems finding wider use in CAD, office information systems, and logic programming applications, the importance of efficiently representing and manipulating complex objects is growing. In this study a classification of the alternatives for representing complex objects is examined. Consideration is given to the performance aspects of one representation technique based on object identifiers. It is shown that clustering of subobjects with their referencing objects is rarely a good idea. In contrast, it is shown that caching the intermediate results of query processing can yield large benefits.>

This paper demonstrates that a simple rule system can be constructed that supports a more powerful view system than available in current commercial systems. Not only can views be specified by using rules but also special semantics for resolving ambiguous view updates are simply additional rules. Moreover, procedural data types as proposed in POSTGRES are also efficiently simulated by the same rules system. Lastly, caching of the action part of certain rules is a possible performance enhancement and can be applied to materialize views as well as to cache procedural data items. Hence, we conclude that a rule system is a fundamental concept in a next generation DBMS, and it subsumes both views and procedures as special cases.