III: Small: Durability Queries in Databases

Duke University, Durham NC

Investigators

Abstract

Real data tends to be noisy and often exhibits transient patterns. When using data to make decisions, one must avoid jumping to conclusions based on one particular query result. In practice, most datasets are temporal, and the abundance of historical data will continue to grow as our economic, social, and scientific activities are increasingly captured in digitized forms. Therefore, a useful way of assessing the "robustness" of a query result is to consider its durability, or how long it has remained valid. There is an abundance of real-life examples where the notion of durability can help make more meaningful decisions from data, reveal transient patterns in data, or search for interesting patterns in data that are also robust. This proposal studies the notion of durability for database queries, techniques for efficiently evaluating durability queries, and their practical applications. This project will develop a framework for durability queries, which unifies common variants and introduces novel ones. Instead of tackling each variant separately, the project identifies underlying properties of durability queries that lead to fundamental understanding and reusable algorithmic techniques. The project will take principled approaches to designing fast, scalable algorithms and indexing methods for durability query processing. These approaches combine geometric, statistical, and approximation techniques for a meaningful balance between query efficiency and result quality. Going beyond worst-case analysis, the project researches query and indexing methods as well as complexity analysis methods aimed at non-adversarial cases that arise in practice.In addition, the project brings efficient support for durability queries to an open-source database system. The project will apply durability queries to three real-world domains with public-facing websites, as a practical test bed for the effectiveness of durability-based analysis and the efficiency of durability query processing techniques. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.