Automated storage management is critical for most dataintensive applications running on DBMSs. In large-scale storage subsystems, the workload is expected to vary with time. In order to ensure both QoS and efficient usage of storage resources, variation in the actual physical disks is allowed to support a single virtual disk. Such data migration generates extra IOs and consumes storage resources. Not only does data migration need to be scheduled ahead but it must also be scheduled in such a way that QoS violations do not occur because of the extra migration IOs. In this paper, we present a novel analytic framework, PULSTORE, for autonomically managing the storage to provide performance guarantee during migration.

The need for network storage has been increasing rapidly owing to the widespread use of the Internet in organizations and the shortage of local storage space due to the increasing size of applications and databases. Proliferation of network storage systems entails a significant increase in the number of storage objects (e.g., files) stored, the number of concurrent clients, and the size and number of storage objects transferred between the systems and their clients. Performance (e.g., client-perceived latency) of these systems becomes a major concern. Previous research has explored techniques for scaling up the number of storage servers involved to enhance the performance of network storage systems. However, adding servers to improve system performance is an expensive solution. Moreover, for a WAN-based network storage system, the bottleneck for its performance improvement typically is not caused by the load of storage servers, but by the network traffic between clients and storage servers. This paper introduces an Internet-based network storage system named NetShark and proposes a caching-based performance-enhancement solution for such a system. The proposed performance-enhancement solution is validated using a simulation.

The demands on storage systems are increasingly requiring expressiveness, fault-tolerance, security, distribution, etc. Such functionalities have been traditionally provided by DBMS. We propose a storage management system, SVL that leverages DBMS technology. The primary problem in block storage management is block virtualization, which is essentially an abstraction layer that separates the user view of storage from the implementation of storage. Storage virtualization standardizes storage management in a heterogeneous storage and/or host environment, and plays a crucial role in enhancing storage functionality and utilization. Currently specialized hardware or microcode-based solutions are popular for implementing block storage management systems, commonly referred to as disk controllers. We demonstrate how to take a general purpose commercial RDBMS, rather than a specialized solution, to support block storage management. We exploit the simple semantics of storage management systems to streamline database performance and thus attain acceptability from a storage point of view. This work promises to pave the way for diverse and innovative industrial applications of database management systems.

This paper proposes STORAGEDB; a paradigm for implementing storage virtualization using databases. It describes details for storing the logical-to-physical mapping information as tables within the database; handling the incoming I/O requests of the application as database queries; bookkeeping of the I/O operations as database transactions. In addition, STORAGEDB uses built-in DBMS features to support storage virtualization functionalities; as an example we describe how online table space migration can be used to support reallocation of logical disks. Finally, we describe our modifications to a traditional RDBMS implementation, in order to make it light-weight. Improving the performance of a traditional DBMS is critical for the acceptance of STORAGEDB since the performance overheads are considered a primary challenge in replacing existing storage virtualization engines. Our current lightweight RDBMS has a 19 times shorter invocation path length than the original. In comparison to the open-source virtualization software, namely LVM, the extra cost of STORAGEDB is within 20% of LVM in trace-driven tests, (unlike STORAGEDB, LVM did not have logging overhead). We consider these initial results as the "stepping stone" in the paradigm of applying databases for storage virtualization.

An important class of queries is the LIKE predicate in SQL. In the absence of an index, LIKE queries are subject to performance degradation. The notion of indexing on substrings (or q-grams) has been explored earlier without sufficient consideration of efficiency. q-grams are used to prune away rows that do not qualify for the query. The problem is to identify a finite number of grams subject to storage constraint that gives maximal pruning for a given query workload. Our contributions include: i) a formal problem definition, that produces results within a provable error bound, ii) performance evaluation of the application of the novel method to real data, and iii) parallelization of the algorithm, scaling considerations and a proposal to handle scaling issues.

We explore a novel paradigm for data management in which a third party service provider hosts "database as a service", providing its customers with seamless mechanisms to create, store, and access their databases at the host site. Such a model alleviates the need for organizations to purchase expensive hardware and software, deal with software upgrades, and hire professionals for administrative and maintenance tasks which are taken over by the service provider. We have developed and deployed a database service on the Internet, called NetDB2, which is in constant use. In a sense, a data management model supported by NetDB2 provides an effective mechanism for organizations to purchase data management as a service, thereby freeing them to concentrate on their core businesses. Among the primary challenges introduced by "database as a service" are the additional overhead of remote access to data, an infrastructure to guarantee data privacy, and user interface design for such a service. These issues are investigated. We identify data privacy as a particularly vital problem and propose alternative solutions based on data encryption. The paper is meant as a challenge for the database community to explore a rich set of research issues that arise in developing such a service.

Rapid advances in networking and Internet technologies have fueled the emergence of the "software as a service" model for enterprise computing. Successful examples of commercially viable software services include rent-a-spreadsheet, electronic mail services, general storage services, disaster protection services. "Database as a Service" model provides users power to create, store, modify, and retrieve data from anywhere in the world, as long as they have access to the Internet. It introduces several challenges, an important issue being data privacy. It is in this context that we specifically address the issue of data privacy.There are two main privacy issues. First, the owner of the data needs to be assured that the data stored on the service-provider site is protected against data thefts from outsiders. Second, data needs to be protected even from the service providers, if the providers themselves cannot be trusted. In this paper, we focus on the second challenge. Specifically, we explore techniques to execute SQL queries over encrypted data. Our strategy is to process as much of the query as possible at the service providers' site, without having to decrypt the data. Decryption and the remainder of the query processing are performed at the client site. The paper explores an algebraic framework to split the query to minimize the computation at the client site. Results of experiments validating our approach are also presented.

With the tremendous growth of large scale data repositories, a need for integrating the exploratory techniques of data mining with the capabilities of relational systems to efficiently handle large volumes of data has now risen. We look at the performance of the most prevalent association rule mining algorithm-Apriori with IBM's DB2 Universal Database system. We show that a multi-column (MC) data model is preferable over the commonly used single column (SC) data model for association rule mining. We obtain factors of 4.8 to 6 improvement in performance for the MC data model over commercial implementations for the SC data model. We provide a new relational operator called Combinations, for efficient SQL implementation of Apriori in the database engine-this results in trivial parallelizability, reliability, and portability for the mining application.

Article Free Access Share on Data cube approximation and histograms via wavelets Authors: Jeffrey Scott Vitter Center for Geometric Computing and Department of Computer Science, Duke University, Durham, NC Center for Geometric Computing and Department of Computer Science, Duke University, Durham, NCView Profile , Min Wang Center for Geometric Computing and Department of Computer Science, Duke University, Durham, NC Center for Geometric Computing and Department of Computer Science, Duke University, Durham, NCView Profile , Bala Iyer Database Technology Institute, IBM Santa Teresa Laboratory, P.O. Box 49023, San Jose, CA Database Technology Institute, IBM Santa Teresa Laboratory, P.O. Box 49023, San Jose, CAView Profile Authors Info & Claims CIKM '98: Proceedings of the seventh international conference on Information and knowledge managementNovember 1998 Pages 96–104https://doi.org/10.1145/288627.288645Online:01 November 1998Publication History 169citation593DownloadsMetricsTotal Citations169Total Downloads593Last 12 Months34Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Classification is a key function of many business intelligence toolkits and a fundamental building block in data mining. Immense data may be needed to train a classifier for good accuracy. The state-of-art classifiers need an in-memory data structure of size O(N), where N is the size of the training data, to achieve efficiency. For large data sets, such a data structure will not fit in the internal memory. The best previously known classifier does a quadratic number of I/Os for large N. We propose a novel classification algorithm (classifier) called MIND (MINing in Databases). MIND can be phrased in such a way that its implementation is very easy using the extended relational calculus SQL, and this in turn allows the classifier to be built into a relational database system directly. MIND is truly scalable with respect to I/O efficiency, which is important since scalability is a key requirement for any data mining algorithm. We built a prototype of MIND in the relational database manager DB2 and benchmarked its performance. We describe the working prototype and report the measured performance with respect to the previous method of choice. MIND scales not only with the size of the datasets but also with the number of processors on an IBM SP2 computer system. Even on uniprocessors, MIND scales well beyond the dataset sizes previously published for classifiers. We also give some insights that may have an impact on the evolution of the extended relational calculus SQL.

Query optimization is an integral part of relational database management systems. One important task in query optimization is selectivity estimation, that is, given a query P, one needs to estimate the fraction of records in the database that satisfy P. Almost all previous work dealt with the estimation of numeric selectivity, i.e., the query contains only numeric variables. The general problem of estimating alphanumeric selectivity is much more difficult and has attracted attention only very recently, and the focus has been on the special case when only one column is involved. The authors consider the more general case when there are two correlated alphanumeric columns. They develop efficient algorithms to build storage structures that can fit in a database catalog. Results from extensive experiments to test the algorithms, on the basis of error analysis and space requirements, are given to guide DBMS implementors.

Removal of redundant outer joins is essential for the reassociation of outer joins with other binary operations. We present a set of comprehensive algorithms that employ the properties of strong predicates along with the properties of aggregation, intersection, union, and except operations to remove redundant outer joins from a query. For the purpose of query simplification, we generate additional projections by determining the keys. Our algorithm for generating keys is based on a novel concept of weak bindings that is essential for queries containing outer joins. Our algorithm for converting outer joins to joins is based on a novel concept of join-reducibility.

The strength of commercial query optimizers like DB2 comes from their ability to select an optimal order by generating all equivalent reorderings of binary operators. However, there are no known methods to generate all equivalent reorderings for a SQL query containing joins, outer joins, and groupby aggregations. Consequently, some of the reorderings with significantly lower cost may be missed. Using hypergraph model and a set of novel identities, we propose a method to reorder a SQL query containing joins, outer joins, and groupby aggregations. While these operators are sufficient to capture the SQL semantics, it is during their reordering that we identify a powerful primitive needed for a dbms. We report our findings of a simple, yet fundamental operator, generalized selection, and demonstrate its power to solve the problem of reordering of SQL queries containing joins, outer joins, and groupby aggregations.

Success of commercial query optimizers and database management systems (object-oriented or relational) depend on accurate cost estimation of various query reordering [BGI]. Estimating predicate selectivity, or the fraction of rows in a database that satisfy a selection predicate, is key to determining the optimal join order. Previous work has concentrated on estimating selectivity for numeric fields [ASW, HaSa, IoP, LNS, SAC, WVT]. With the popularity of textual data being stored in databases, it has become important to estimate selectivity accurately for alphanumeric fields. A particularly problematic predicate used against alphanumeric fields is the SQL like predicate [Dat]. Techniques used for estimating numeric selectivity are not suited for estimating alphanumeric selectivity.In this paper, we study for the first time the problem of estimating alphanumeric selectivity in the presence of wildcards. Based on the intuition that the model built by a data compressor on an input text encapsulates information about common substrings in the text, we develop a technique based on the suffix tree data structure to estimate alphanumeric selectivity. In a statistics generation pass over the database, we construct a compact suffix tree-based structure from the columns of the database. We then look at three families of methods that utilize this structure to estimate selectivity during query plan costing, when a query with predicates on alphanumeric attributes contains wildcards in the predicate.We evaluate our methods empirically in the context of the TPC-D benchmark. We study our methods experimentally against a variety of query patterns and identify five techniques that hold promise.

Complex queries containing outer joins are, for the most part, executed by commercial DBMS products in an "as written" manner. Only a very few reorderings of the operations are considered and the benefits of considering comprehensive reordering schemes are not exploited. This is largely due to the fact there are no readily usable results for reordering such operations for relations with duplicates and/or outer join predicates that are other than "simple." Most previous approaches have ignored duplicates and complex predicates; the very few that have considered these aspects have suggested approaches that lead to a possibly exponential number of, and redundant intermediate joins. Since traditional query graph models are inadequate for modeling outer join queries with complex predicates, we present the needed hypergraph abstraction and algorithms for reordering such queries with joins and outer joins. As a result, the query optimizer can explore a significantly larger space of execution plans, and choose one with a low cost. Further, these algorithms are easily incorporated into well known and widely used enumeration methods such as dynamic programming.

No abstract available.

The compression method is based on composing phrases from symbols. The authors extend the sort-order property to parsing models, i.e. to Variable-to-Fixed Length codes, or a static Ziv-Lempel algorithm, or alternatively a Tunstall algorithm for an adjoint source. The parsed phrases comprising the original storage data units have the same position in the sort ordering as the original units themselves. The VFL result may be further compressed by use of Variable-to-Variable Length techniques based on the relative frequencies of the parsed phrases. The sort-order property is facilitated by an 'end of record' symbol and requires a new zilch symbol.>

The dynamic programming algorithm for query optimization has exponential complexity. An alternative polynomial time algorithm, the IK-KBZ algorithm, is severely limited in the queries it can optimize. Other algorithms have been proposed, including the greedy algorithm, iterative improvement, and simulated annealing. The AB algorithm, which combines randomization and neighborhood search with the IK-KBZ algorithm, is presented. The AB algorithm is much more generally applicable than IK-KBZ, has polynomial time and space complexity, and produces near optimal plans in the space of outer linear join trees. On average, it does better than the other algorithms that do not do an exhaustive search like dynamic programming.>

The I/O performance of several concurrent external merge jobs sharing a parallel I/O system is studied. The placement of the runs is found to have a significant impact on performance. Placements leading to serialization among jobs were identified and analyzed, and solutions discussed. Contrary to the behavior of a single merge, increasing the buffer size in this situation may actually degrade performance.

A new join method, called hybrid join, is proposed which uses the join-index filtering and the skip sequential prefetch mechanism for efficient data access. With this method, the outer table is sorted on the join column. Then, the outer is joined with the index on the join column of the inner. The inner tuple is represented by its surrogate, equivalent of its physical disk address, which is carried in the index. The partial join result is sorted on the surrogate and then the inner table is accessed sequentially to complete the join result. Local predicate filtering can also be applied before the access of the inner relation through the index AND/ORing. Efficient methods for skip sequential access and prefetching of logically discontiguous leaf pages of B/sup +/-tree indexes are also presented.>

An efficient, exact algorithm is developed for optimizing the performance of nested block joins. The method uses both dynamic programming and branch-and-bound. In the process of deriving the algorithm, the class of resource allocation problems for which the greedy algorithm applies has been extended. Experiments with this algorithm on extremely large problems show that it is superior to all other known algorithms by a wide margin.>

An external parallel merge-sort and sort-merge join on tightly coupled processors is considered. The issue of whether significant speedup can be achieved with good CPU efficiency is addressed. A pure sort query and a five-relation join query using a sort-merge-join algorithm are examined. It is found that the external sort is readily parallelizable. In the absence of skew, a speedup, linear in the number of tightly coupled processors can be obtained. However, it is shown that skew can reduce the speedup significantly. An examination is made of how important types of skew can be handled to yield close to linear speedup. The effect on the speedup and CPU efficiency of the database size, memory constraints, CPU MIPS, query selectivity, I/O striping and skew is shown.>

A hybrid system structure comprised of distributed systems to take advantage of locality of reference and a central system to handle transactions that access non-local data is examined. Several transaction processing applications, such as reservation systems, insurance and banking have such regional locality of reference. A concurrency and coherency control protocol that maintains the integrity of the data and performs well for transactions that access local or non-local data is described. It is shown that the performance of the hybrid system is much less sensitive to the fraction of remote accesses than the distributed system and offers similar performance to the distributed system for local transactions.>

The authors propose an integrated control mechanism and analyze the performance gain due to its use. An extension to the data sharing system structure is examined in which a shared intermediate memory is used for buffering and for early commit processing. Read-write-synchronization and write-serialization problems arise. The authors show how the integrated concurrency protocol can be used to overcome both problems. A queueing model is used to quantify the performance improvement. Although using intermediate memory as a buffering device produces a moderate performance benefit, the analysis shows that more substantial gains can be realized when this technique is combined with the use of an integrated concurrency-coherency control protocol.>

A hybrid architecture is proposed that combines the approaches of a multisystem partitioned database system and a data-sharing multisystem approach offering the advantages of each. With this architecture some databases are shared between systems, while others are retained private by specific systems. The authors examine how to determine which databases to share, which to retain private, and how to route transactions and partition the private databases among systems so as to minimize response time or overheads while balancing the load among systems. A simulated annealing heuristic is used to solve this optimizing problem. Trace data from large mainframe systems running IBM's Information Management System database management system are used to illustrate the methodology and to demonstrate the advantages of the hybrid approach.>

Proposes and evaluates a hybrid architecture that combines the approaches, and offers the advantages of both data sharing and data partitioning. Some databases are shared between systems, while others are retained private by specific systems. The issue is to determine which databases to share, which to retain private, and how to route transactions and partition the private databases among systems so as to minimize response time or overheads, while balancing the load among systems. A simulated annealing heuristic is used to solve this optimization problem. Trace data from large mainframe systems running IBM's IMS database management system are used to illustrate the methodology and to demonstrate the advantage of the hybrid approach.>

A methodology is developed to determine the number of processors needed to satisfy transaction throughput and response time requirements for processors of different MIPS (sizes). The minimum MIPS per processor required to satisfy response time and throughput constraints in a transaction processing complex of N coupled systems is also determined. For realistic overhead assumptions, despite large assumed cost advantages on a per-MIPS basis, it is found that very small systems may not match up to the cost/performance of some larger systems, when required to meet the same throughput and response-time constraints. If transactions running on smaller systems were allowed a larger response-time constraint, then it may be possible to construct a lower-cost system from smaller and less expensive processors, generally with lower supportable maximum throughput. Besides the coupling degradation between multiprocessor systems, there is a small systems effect. The cost criterion indicates that there is an optimum processor size below which total system costs would increase appreciably.>

Today's concomitant needs for higher computing power and reliability has increased the relevance of multiple-processor fault-tolerant systems. Multiple functional units improve the raw performance (throughput, response time, etc.) of the system, and, as units fail, the system may continue to function albeit with degraded performance. Such systems and other fault-tolerant systems are not adequately characterized by separate performance and reliability measures. A composite measure for the performance and reliability of a fault-tolerant system observed over a finite mission time is analyzed. A Markov chain model is used for system state-space representation, and transient analysis is performed to obtain closed-form solutions for the density and moments of the composite measure. Only failures that cannot be repaired until the end of the mission are modeled. The time spent in a specific system configuration is assumed to be large enough to permit the use of a hierarchical model and static measures to quantify the performance of the system in individual configurations. For a multiple-processor system, where performance measures are usually associated with and aggregated over many jobs, this is tantamount to assuming that the time to process a job is much smaller than the time between failures. An extension of the results to general acyclic Markov chain models is included.

The demand for larger transaction rates and the inability of single-system-based transaction processors to keep up with demand have resulted in the growth of multi-processor-based database systems. The focus here is on coupling in a locally distributed system through multi-system data sharing in which all systems have direct access to the data. This paper addresses the following questions; i) How does a workload running on a single system today perform if migrated to a multi-system? ii) What are the multi-system locking design issues that limit multi-system performance and what is the maximum number of systems that may be effectively coupled? iii) Can alternative locking designs increase the number of systems that may be effectively coupled? Our analysis is based on traces from large mainframe systems running IBM's IMS database management system. We have developed a hierarchical modeling methodology that starts by synthesizing a multi-system IMS lock trace and a reference trace from single-system traces. The multisystem traces are used in trace-driven simulations to predict lock contention and database I/O increase in multi-system environment and to generate workload parameters. These parameters are used in event-driven simulation models to examine the overall performance under different system structures. Performance results are presented for realistic system parameters to determine the performance impact of various design parameters. Lock contention is found to be the critical factor in determining the coupling effectiveness and the effect of alternative locking design to reduce lock contention is studied. The limit on coupling is explored and the analysis indicates that, for this workload, on the order of 6 to 12 systems may be effectively coupled through data sharing, depending on system structure and locking design.

The demand for on-line transaction processing has grown rapidly in recent years. To meet the transaction demand, several DB (database management) and DC (data communication management) subsystems can be coupled together to form a distributed DB/DC system. A key problem is to provide these distributed systems with effective means to recover transactions upon failure while paying little performance penalty during normal processing. Also, there should be minimal interference of fault-free components, during the recovery of failed component. By decentralizing recovery management, and using transaction level structural information to eliminate costly lower level handshaking protocols, proposed progressive transaction recovery protocols seek to solve the problem. A queueing model for evaluating the transaction response time during normal processing for the progressive and pessimistic protocols is developed and solved, via simulation. The progressive recovery protocols are shown to reduce normal processing overhead and lead to performance improvement over the pessimistic protocol.

The prospect of coupling a large number of small inexpensive microprocessor based systems to deliver the performance of a large transaction processing system at lower cost has not been realized, to date. Inter-system interference, multi-system coupling protocol overhead and the increased processing time for smaller systems can cause considerable degradation. A methodology is developed to determine the number of processors needed to satisfy transaction throughput and response time requirements for processors of different MIPS (sizes). The minimum MIPS per processor required to satisfy response time, throughput and utilization constraints in a transaction processing complex of N coupled systems is also determined, by using an approximate analytical model driven by measured workload parameters. Despite large assumed cost advantages on a per MIPS basis we find that small systems do not match up to the cost/performance of some larger systems. Besides multi-system's coupling degradation, there is a small system effect. Because of the increased transaction execution time in smaller systems, transaction hold on to resources longer, thereby causing increased inter-system interference. Our cost criterion indicates that there is an optimum processor size below which total system costs would increase appreciably. Ways to reduce the inter-system interference and coupling protocol overheads are investigated and shown to shift this optimum.

Performability, a composite measure for the performance and reliability, may be interpreted as the probability density function of the aggregate reward obtained from a system during its mission time. For large mission times we show that known limit theorems lead to an asymptotic normal distribution for the aggregate reward. For finite mission times and Markovian models we obtain the expressions for all moments of performability and give recursions to compute coefficients involved in the expressions. We illustrate the use of the results through an example of a multiple processor computer system.

The performance of multiple systems sharing a common data base is analyzed for an architecture with concurrency control using a centralized lock engine. The workload is based on traces from large mainframe systems running IBM's IMS database management system. Based on IMS lock traces the lock contention probability and data base buffer invalidation effect in a multi-system environment is predicted. Workload parameters are generated for use in event-driven simulation models that examine the overall performance of multi-system data sharing, and to determine the performance impact of various system parameters and design alternatives. While performance results are presented for realistic system parameters, the emphasis is on the methodology, approximate analysis technique and on examining the factors that affect multi-system performance.

In this correspondence we consider a model for dynamic memories that are characterized by small cell fan-out and a small number of I/O ports. Many schemes have been proposed in the literature to interconnect dynamic memory cells. These usually exhibit a tradeoff between random and block access times. We propose a scheme that combines the interconnection scheme of a previous work with the idea of interleaving. With this we show that both random and block access times can be optimized. We analyze access times for our scheme and compare them to those for other schemes in the literature. We define delay between two block accesses and compare the dynamic memory organization schemes on the basis of delay.