Proof of Real-Time Transfer (PoRT) consensus is a secure, highly scalable, decentralized data verification protocol that supports the exchange of data in any form factor (remaining content agnostic) with guarantees towards data privacy, data integrity and source authentication. It is built on a modular framework that serves core functionalities towards decentralized public key infrastructure (DPKI), message standardization and encryption, decentralized message verification a nd storage. PoRT's security guarantees stem from its adoption of cryptographic primitives and their nuanced derivatives that confer verifiability and further game theoretic constructs that prove pertinence in work. High scalability of PoRT can be attributed to network sharding and compute sharding that optimize resource usage and to parallel chains that confer instant finality. PoRT allows applications to define and implement purpose-built message-driven business solutions across industries like IoT, social media, instant messaging and gaming. Our analysis indicates that the proposed consensus protocol can achieve throughputs upto 976K messages per second on today's commodity hardware.

Many of the ETL products in the market today provide tools for design of ETL workflows, with very little or no support for opti-mization of such workflows. Optimization of ETL workflows pose several new challenges compared to traditional query optimization in database systems. There have been many attempts both in the industry and the research community to support cost-based opti-mization techniques for ETL Workflows, but with limited success. Non-availability of source statistics in ETL is one of the major chal-lenges that precludes the use of a cost based optimization strategy. However, the basic philosophy of ETL workflows of design once and execute repeatedly allows interesting possibilities for determin-ing the statistics of the input. In this paper, we propose a frame-work to determine various sets of statistics to collect for a given workflow, using which the optimizer can estimate the cost of any alternative plan for the workflow. The initial few runs of the work-flow are used to collect the statistics and future runs are optimized based on the learned statistics. Since there can be several alterna-tive sets of statistics that are sufficient, we propose an optimization framework to choose a set of statistics that can be measured with the least overhead. We experimentally demonstrate the effective-ness and efficiency of the proposed algorithms.

Data Integration engines increasingly need to provide sophisticated processing options for XML data. In the past, it was adequate for these engines to support basic shredding and XML generation capabilities. However, with the steady growth of XML in applications and databases, integration platforms need to provide more direct operations on XML as well as improve the scalability and efficiency of these operations. In this paper, we describe a robust and comprehensive framework for performing Extract-Transform-Load (ETL) of XML. This includes (i) full computational model and engine capabilities to perform these operations in an ETL flow, (ii) an approach to pushing down XML operations into a database engine capable of supporting XML processing, and (iii) methods to apply partitioning techniques to provide scalable, parallel processing for large XML documents. We describe experimental results showing the effectiveness of these techniques.

Increasingly large numbers of situational applications are being created by enterprise business users as a by-product of solving day-to-day problems. In efforts to address the demand for such applications, corporate IT is moving toward Web 2.0 architectures. In particular, the corporate intranet is evolving into a platform of readily accessible data and services where communities of business users can assemble and deploy situational applications. Damia is a web style data integration platform being developed to address the data problem presented by such applications, which often access and combine data from a variety of sources. Damia allows business users to quickly and easily create data mashups that combine data from desktop, web, and traditional IT sources into feeds that can be consumed by AJAX, and other types of web applications. This paper describes the key features and design of Damia's data integration engine, which has been packaged with Mashup Hub, an enterprise feed server currently available for download on IBM alphaWorks. Mashup Hub exposes Damia's data integration capabilities in the form of a service that allows users to create hosted data mashups.

Decision support (DSS) workloads generally contain multiple large concurrent scan operations. These are often executed as relational table scans which can take up a lot of I/O bandwidth. This is especially true for ad-hoc queries where the workload is not known in advance. Common database management systems have only limited ability to reuse memory buffer content across multiple running queries due to their treatment of queries in isolation. Previous attempts to coordinate scans for better buffer reuse were less than satisfactory due to drifting between scans and the required radical DBMS architecture changes. In this paper, we describe a new mechanism to keep similar table scans closer together during scanning. This is achieved via dynamic grouping and regrouping of scans based on their runtime behavior and via adaptive throttling of scan speeds based on scan group characteristics. The required memory footprint is very small and the effort required to extend existing database management systems is minimal, as shown in our DB2 UDB prototype. Our experiments show significant gains in end-to-end response times as well as average response times for TPC-H workloads.

DB2 universal database allows database schema designers to specify generated columns. These generated columns are useful for maintaining rollup hierarchy variables in warehouses (e.g., date, month, quarter). In order for the generated columns to be useful for query processing, queries must automatically make use of such columns when applicable. In particular, query predicates on the original columns should be rewritten to make use of the generated columns. In this paper, we describe two main aspects of this predicate rewriting technique that allows usage of the generated columns for a variety of query predicate types. The first aspect, monotonicity detection, allows for rewrites in the case of range predicates. The second aspect, predicate derivation, is the technique for using generating expressions for query processing. We show the value of this technique for providing significant performance improvement when combined with indexing or multidimensional clustering in DB2.

XML documents are often represented as DOM structures or trees. In some instances, due to the complexity of queries, XPath queries are better evaluated by traversing these structures rather than using summarization indexes. A requirement for the optimization of document navigation, is to efficiently decrease the number of traversed nodes. The optimization task is more difficult when the query framework allows a syntax that enlarges the search space, such as wildcards and descendant queries. To reduce the overhead of query processing, many database systems supporting XML rely on indexes. Such indexes are typically not able to adapt to memory restrictions or workload changes. A secondary data structure that uses little storage space and tunes itself to address hot spots in processing, can therefore be beneficial. In this paper, we propose a first method for creating, using, and maintaining selective signatures called hints to aid in the navigation of XML documents. Hints form a flexible data structure for pruning the search space, that can be used on its own or it can complement existing indexes. The amount of hints used is variable, and it depends on the storage limitation set a priori, and on the efficiency of the hints. Our experiments show that hints can improve the efficiency of navigational XML query processing by a large margin while using only little extra memory.

As XML becomes an increasingly popular format for information exchange, the efficient processing of broadcast XML data on a constrained device (for example, a cell phone or a PDA) becomes a critical task. In this paper we present the EXPedite system: a new model of data processing in an information exchange environment, which "migrates" the power of the data-sending server to receivers for efficient processing. It consists of a simple and general encoding scheme for servers, and streaming query processing algorithms on encoded XML stream for data receivers with constrained computing abilities. Experiments show the impressive performance of EXPedite.

Semantic caches, originally proposed for client-server database systems, are being recently deployed to accelerate the serving of dynamic Web content by transparently caching data on edge servers. Such caches require fast query containment tests to determine if a new query is contained in the results of cached queries. Query containment checking algorithms have been studied in the context of query optimization and materialized view selection, but their scalability remains a serious limitation. We argue that application queries are usually instantiations of a smaller number of base templates and show how this can be exploited to scale up containment checking. Our contributions include (i) algorithms to detect similarity between query predicates; (ii) efficient algorithms for proving containment among similar query predicates; (iii) a technique to dynamically aggregate similar queries in the cache to support efficient search; and (iv) integration of these schemes into a two-level containment checker. We describe our approach, report on its implementation in a dynamic Web data cache, and show that it can reduce query containment cost by an order of magnitude for Web workloads.

The majority of web pages served today are generated dynamically, usually by an application server querying a back-end database. To enhance the scalability of dynamic content serving in large sites, application servers are offloaded to front-end nodes, called edge servers. The improvement from such application offloading is marginal, however, if data is still fetched from the origin database system. To further improve scalability and cut response times, data must be effectively cached on such edge servers. The scale of deployment of edge servers and the rising costs of their administration demand that such caches be self-managing and adaptive. In this paper, we describe DBProxy, an edge-of-network semantic data cache for web applications. DBProxy is designed to adapt to changes in the workload in a transparent and graceful fashion by caching a large number of overlapping and dynamically changing "materialized views". New "views" are added automatically while others may be discarded to save space. In this paper, we discuss the challenges of designing and implementing such a dynamic edge data cache, and describe our proposed solutions.

As the amount of data available online and the number of pervasive applications that take advantage of it increase, systems that support selective dissemination of information are becoming more popular. At the same time, XML is becoming the standard for document exchange over the Internet. A key capability of emerging information dissemination systems is therefore the effective filtering of a continuous stream of XML data items according to user preferences. Here we propose a model for information dissemination that integrates profile inference with data dissemination and takes advantage of the structured content in XML documents. Starting from the assumption that explicitly stating one's information interests is an inconvenient and error-prone process, we aim to automatically construct user profiles. We do this by clustering items previously deemed valuable by the user according to a novel similarity measure that takes advantage of the semantic content of XML. Furthermore, we index the profiles from all users into a multilevel index structure whose nodes naturally will be a close match to subject areas present in the document collection. Such an approach is both intuitive and efficient since the indexing structure is not primarily affected by an increasing number of users. To support our claims we experimentally validate our method and report on its effectiveness and efficiency.

We describe the design and implementation of a new data layout scheme, called multi-dimensional clustering, in DB2 Universal Database Version 8. Many applications, e.g., OLAP and data warehousing, process a table or tables in a database using a multi-dimensional access paradigm. Currently, most database systems can only support organization of a table using a primary clustering index. Secondary indexes are created to access the tables when the primary key index is not applicable. Unfortunately, secondary indexes perform many random I/O accesses against the table for a simple operation such as a range query. Our work in multi-dimensional clustering addresses this important deficiency in database systems. Multi-Dimensional Clustering is based on the definition of one or more orthogonal clustering attributes (or expressions) of a table. The table is organized physically by associating records with similar values for the dimension attributes in a cluster. We describe novel techniques for maintaining this physical layout efficiently and methods of processing database operations that provide significant performance improvements. We show results from experiments using a star-schema database to validate our claims of performance with minimal overhead.

Recent work on incremental crawling has enabled the indexed document collection of a search engine to be more synchronized with the changing World Wide Web. However, this synchronized collection is not immediately searchable, because the keyword index is rebuilt from scratch less frequently than the collection can be refreshed. An inverted index is usually used to index documents crawled from the web. Complete index rebuild at high frequency is expensive. Previous work on incremental inverted index updates have been restricted to adding and removing documents. Updating the inverted index for previously indexed documents that have changed has not been addressed.In this paper, we propose an efficient method to update the inverted index for previously indexed documents whose contents have changed. Our method uses the idea of landmarks together with the diff algorithm to significantly reduce the number of postings in the inverted index that need to be updated. Our experiments verify that our landmark-diff method results in significant savings in the number of update operations on the inverted index.

This paper discusses an index-based subsequence matching that supports time warping in large sequence databases. Time warping enables finding sequences with similar patterns even when they are of different lengths. In our earlier work, we suggested an efficient method for whole matching under time warping. This method constructs a multi-dimensional index on a set of feature vectors, which are invariant to time warping, from data sequences. For filtering at feature space, it also applies a lower-bound function, which consistently underestimates the time warping distance as well as satisfies the triangular inequality.In this paper, we incorporate the prefix-querying approach based on sliding windows into the earlier approach. For indexing, we extract a feature vector from every subsequence inside a sliding window and construct a multi-dimensional index using a feature vector as indexing attributes. For query processing, we perform a series of index searches using the feature vectors of qualifying query prefixes. Our approach provides effective and scalable subsequence matching even with a large volume of a database. We also prove that our approach does not incur false dismissal. To verify the superiority of our method, we perform extensive experiments. The results reveal that our method achieves significant speedup with real-world S&P 500 stock data and with very large synthetic data.

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.

XML is emerging as an important format for describing the schema of documents and data to facilitate integration of applications in a variety of industry domains. An important issue that naturally arises is the requirement to generate, store and access XML documents. It is important to reuse existing data management systems and repositories for this purpose. We describe the XML Access Server (XAS), a general purpose XML based storage and retrieval system which provides the appearance of a large set of XML documents while retaining the data in underlying federated data sources that could be relational, object-oriented, or semi-structured. XAS automatically maps the underlying data into virtual XML components when mappings between DTDs and underlying schemas are established. The components can be presented as XML documents or assembled into larger components. XAS manages the relationship between XML components and the mapping in the form of document composition logic. The versatility in its ways to generate XML documents enables XAS to serve a large number of XML components and documents efficiently and expediently.

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 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.

An important aspect of database processing in parallel computer systems is the use of data parallel algorithms. Several parallel algorithms for the relational database join operation in a hypercube multicomputer system are given. The join algorithms are classified as cycling or global partitioning based on the tuple distribution method employed. The various algorithms are compared under a common framework, using time complexity analysis as well as an implementation on a 64-node NCUBE hypercube system. In general, the global partitioning algorithms demonstrate better speedup. However, the cycling algorithm can perform better than the global algorithms in specific situations, viz., when the difference in input relation cardinalities is large and the hypercube dimension is small. The usefulness of the data redistribution operation in improving the performance of the join algorithms, in the presence of uneven data partitions, is examined. The results indicate that redistribution significantly decreases the join algorithm execution times for unbalanced partitions.>