III: Small: Durability Queries in Databases

真实数据往往有噪声，并且经常显示出瞬时模式。当使用数据进行决策时，必须避免根据一个特定的查询结果得出结论。在实践中，大多数数据集都是时态的，随着我们的经济、社会和科学活动越来越多地以数字化形式捕获，历史数据的丰富性将继续增长。因此，评估查询结果的“健壮性”的一个有用的方法是考虑它的持久性，或者它保持有效的时间。有很多现实生活中的例子，耐久性的概念可以帮助从数据中做出更有意义的决策，揭示数据中的瞬时模式，或者在数据中搜索同样健壮的有趣模式。该方案研究了数据库查询耐久性的概念、高效评估耐久性查询的技术及其实际应用，该项目将开发一个耐久性查询框架，该框架统一了常见的变体并引入了新的变体。该项目不是单独处理每个变体，而是确定耐久性查询的基本属性，这些属性导致基本理解和可重用的算法技术。该项目将采取原则性方法，为耐久性查询处理设计快速、可伸缩的算法和索引方法。这些方法结合了几何、统计和近似技术，在查询效率和结果质量之间取得了有意义的平衡。该项目超越了最坏情况分析，针对实际中出现的非对抗性案例，研究了查询和索引方法以及复杂性分析方法，并为开源数据库系统带来了对持久性查询的有效支持。该项目将耐久性查询应用于三个面向公众网站的真实领域，作为基于耐久性分析的有效性和耐久性查询处理技术效率的实用试验台。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.