Database Seminar Series (2009-2010)

Web 2.0 applications regularly store and access data from a variety of Internet storage services. Such "cloud" storage services have reached remarkable scale in a short period of time: Amazon's S3 contained more than 52 billions objects as of April 2009. Authenticated directories have emerged as the preferred technique to verify the integrity and authenticity of dynamic data. However, existing implementations of authenticated directories employ data structures that exhibit performance problem at scale, making it infeasible to validate data retrieved from the cloud. This talk will describe our ongoing efforts to minimize the I/O required to insert and query an authenticated directory and improve the cache performance of the data structures. The optimizations include the use of incremental cryptography, the replication of authentication metadata, temporal organization of objects in the directory, and the adaptation of fractal trees and buffered repository trees to authenticated directories. When used together, these techniques have already improved the performance of authenticated directories by a factor of five.

For the next generation of data-management applications, such as sensor-based monitoring, data integration, and information extraction, data processing is the dominant cost. Often, the data driving these applications are uncertain, for example, due to missed, inconsistent, or imprecise sensor readings. Unfortunately, traditional data-management systems provide little or no support for managing uncertainty. To remedy this, I will discuss an approach for data management in which uncertainty is modeled using probabilities. The cost of modeling imprecision using probabilities is that basic data-management tasks, such as querying, become theoretically and practically more difficult. Thus, the key challenge in managing large-scale probabilistic data is efficiency.

In this talk, I will discuss the fundamental techniques that we used to build a probabilistic database capable of handling large, imprecise datasets: these techniques include top-k processing with probabilities, materialized views, approximate lineage, and extensional processing for complex analytic queries. This work resulted in two systems: Mystiq, the first system to support complex queries on gigabytes of probabilistic relational data, and Lahar, the first system to support rich event-style queries on large probabilistic streams.

The need to manage diverse information sources has triggered the rise of very loosely structured data models, known as "dataspace models." Such information management systems must allow querying in simple ways, mostly by a form of searching. Motivated by these developments, we propose a theory of search queries in a general model of dataspaces. In this model, a dataspace is a collection of data objects, where each data object is a collection of data items. Basic search queries are expressed using filters on data items, following the basic model of boolean search in information retrieval. We characterize semantically the class of queries that can be expressed by searching. We apply our theory to classical relational databases, where we connect search queries to the known class of fully generic queries, and to dataspaces where data items are formed by attribute-value pairs. We also extend our theory to a more powerful, associative form of searching where one can ask for objects that are similar to objects satisfying given search conditions. Such associative search queries are shown to correspond to a very limited kind of joins. Specifically, we show that the basic search language extended with associative search can done exactly like the queries definable in a restricted fragment of the semi-join algebra working on an explicit relational representation of the dataspace.

(This work was done in collaboration with George Fletcher, Jan Van den Bussche, and Stijn Vansummeren)

For many business intelligence applications, decision making depends critically on the information contained in all forms of “informal” text documents, such as emails, meeting summaries, attachments and web documents. For example, in a meeting, the topic of developing a new product was first raised. In subsequent follow-up emails, additional comments and discussions were added, which included links to web documents describing similar products in the market and user reviews on those products. A concise summary of this “conversation” is obviously valuable. However, existing technologies are inadequate in at least two fundamental ways. First, extracting “conversations” embedded in multi-genre documents is very challenging. Second, applying existing multi-document summarization techniques, where were designed mainly for formal documents, have proved to be highly ineffective when applied to informal documents like emails.

In this presentation, we give an overview of email summarization and meeting summarization methods. We give short demos on what we have developed so far. We conclude by presenting several open problems that need to be solved for multi-modal extraction and summarization of conversations to become a reality.

Many applications domains are faced with the need to store and manipulate uncertain or imprecise data. Examples include sensor databases, data cleansing, scientific data, and information retrieval systems. Probabilistic modeling of this uncertainty is an attractive option for these applications. In talk we will discuss challenges and some solutions for supporting probabilistic data in relational databases. We will use our experience in developing the Orion uncertain data management system as a concrete example of a potential solution. The challenges extend from the design of probabilistic relational models to performance, and user interfaces. Models are an essential first step with several design choices including the types of uncertainty handled (discrete, continuous, tuple, attribute, etc.) and semantics of the operators. Potential query processing and optimization issues will also be presented.

This talk presents a new compilation technique for turning complex aggregation queries into high-performance native code query processors for update streams. In contrast to today's mainly operator-centric query plan interpreters, DBToaster, our query compiler, aggressively compiles aggregate queries by recursively applying incremental view maintenance ideas, creating a network of data structures that support each other's maintenance under change through extremely simple local modifications. DBToaster is capable of generating incremental engines for a wide range of aggregate queries, including nested aggregate queries for which no incremental maintenance techniques were previously known. Our work is motivated by applications that require the continuous maintenance of aggregation queries on update streams, such as online data warehousing and low-latency algorithmic trading. As we show, our techniques are several orders of magnitude faster than state-of-the-art database and stream processing engines on such workloads. Code produced by DBToaster also admits a surprising form of massive parallelization, allowing for the automated generation of lightweight realtime data warehousing systems.

DBToaster is joint work with Yanif Ahmad and Oliver Kennedy.

As the amount of available data increases, the problem of information discovery, often referred to as finding the needle in the haystack problem, becomes more pressing. The most successful search applications today are the general purpose Web search engines and the well-structured database querying (e.g., SQL).

Directly applying these two search models to specific domains is ineffective since they ignore the domain semantics -meaning of object associations- and the needs of the domain users -a biologist wants to see different results from a physician for the same query on PubMed.

We present challenges and techniques to achieve effective information discovery on vertical domains by modeling the domain semantics and its users, and exploiting the knowledge of domain experts. Our focal domains are products marketplace, biological data, clinical data, and bibliographic data.

This project is being funded by NSF.