Mitch Cherniack - US grants

Database query optimizers are large, complex, and error-prone software systems. The goal of this project is to assist researchers and developers in building optimizers that are "provably correct". Specifically, this research group is building a framework which accepts specifications of optimizer components and their interactions, and generates optimizers that can be shown to satisfy the property that the plans they construct always return the data specified in a user queries. The group's approach separates the components of the optimizer into those that require correctness proofs (the safety critical components) from those that do not. Languages are under design for formally specifying those components, and tools are under construction that both generate these components according to the specifications, and generate proof obligations enabling their verification with an automated theorem prover. The experimental research is linked to the educational goal of training students in the application of formal methods in building large software systems. The results of this project will provide a sandbox for database researchers in both academia and industry, to introduce new optimizer techniques and products while providing tangible guarantees that they are free of errors.
{http://www.cs.brandeis.edu/~mfc/cokokola.html}

This research addresses the problem of adding data management facilities to inherently autonomous, distributed information sources such as those that occur in the web. Here, by data management, is meant the allocation and structuring of resources to provide more responsive access to data for applications. In this kind of environment, data management must be superimposed through an independently controlled service that exists between the data sources and the applications. This is facilitated through the introduction of architecture based on data centers, a collection of machines that prestage and distribute data for its clients. Client applications submit profiles describing their overall data needs, and the data center gathers data and organizes it on behalf of their clients in order to provide efficient data access. This research explores systems issues and techniques for the design and operation of data centers. This includes the management of large numbers of profiles, heuristics for balancing the needs of large numbers of users against the available resources of the data center, and the efficient processing of future client data needs against the data that is managed by the data center.

There is a host of existing and newly-emerging applications that require sophisticated and timely processing of fast, high-volume data streams. Examples of these applications include environmental monitoring, portfolio management, asset tracking, and traffic management. These applications, often referred to as monitoring applications, track data from numerous continuous data streams (coming from such sources as sensor networks and stock feeds), filtering them for signs of abnormal activity, and processing them in a timely fashion for purposes of aggregation, reduction, and correlation.

Currently, monitoring applications are commonly implemented using custom, application-specific code - there is no general-purpose software infrastructure that can efficiently and effectively meet the processing and performance requirements of these applications. The project will investigate the key issues related to the design and architecture of general-purpose data-stream processing systems by developing proper abstractions, mechanisms, policies, and protocols. In particular, the project will develop novel stream-oriented languages, query execution and optimization techniques, and resource allocation algorithms. The project will also address the challenges and opportunities that arise in distributed stream processing by addressing issues such as stream-oriented load sharing, dynamic operator placement, and high availability. In both cases, the algorithms will be driven by the Quality-of-Service expectations of the target applications.

Interactive systems are software systems that incorporate "human-in-the-loop" in achieving complex tasks. This proposal introduces Interaction History Management Systems (IHMSs): systems that capture and manage sequences of user interactions that determine the behavior of an interactive system. The interactions managed by an IHMS may be system- and domain-specific and can include SQL queries, search keywords, annotations of results and applied processing algorithms. By managing the histories of such interactions, it becomes possible to optimize and add additional functionality (e.g., versioning, time travel, use analysis) to the underlying interactive system.

This project explores the design and optimization of IHMSs to support the formulation of "systematic reviews": human-accumulated evidence that provide empirical data for the effectiveness of treatment strategies of a given patient's diagnosed disease or disorder. The project leverages research in several computer science areas such as query and workflow management, query recommendations and query provenance while it explores new interdisciplinary research domains. It also has high impacts in the domain of healthcare: it leads to the next generation of collaborative, streamlined systematic reviewing systems and therefore improves the effectiveness of evidence-based healthcare practice. Computer science students will be trained in healthcare applications and interdisciplinary research. Further information on the project can be found on the project web page: http://www.cs.brandeis.edu/~olga/IHMS.html

Novel hardware technologies and application requirements have recently triggered a flurry of research and development into new data management systems. These systems challenge the hegemony of ossified, legacy database systems which lack the agility to adapt to these new constraints. But features pioneered by legacy systems (e.g., declarative query processing) are still desirable, and therefore, much work is being devoted to designing components that provide these features in new systems.

The goal of this project is to support research and development of (query) optimizers in data management systems. Optimizers, which translate declarative descriptions of data (queries) into executable plans, are inherently complex but nonetheless, there are no software engineering tools dedicated to their development. Therefore this project aims to design and build DEVEL-OP: a dedicated DEVELopment Environment for OPtimizers consisting of the following suites of tools:

1) Component Generators, which use declarative specifications of components to produce executable code. Developers can use generators to rapidly prototype alternative versions of components encompassing different optimization approaches,

2) Profiling Tools, which help developers identify bugs or performance bottlenecks in generated components, and

3) Component Benchmarks, which enable the evaluation of optimization approaches (as manifested in generated components) in terms of their effectiveness and robustness in contributing to optimization as a whole.

DEVEL-OP provides a sandbox where optimizers can be quickly prototyped, refined and compared with minimal effort. Therefore, its impact will be in applying software engineering methodologies to the inherently difficult and complex development process for this key component of data management systems.