Quantitative reasoning about database queries

传统的数据库概念和系统在查询应答中坚持逻辑正确性的整体性。然而，如今以数据为中心的应用程序经常分析不可靠和嘈杂的数据集，或者只是太大而无法准确回答复杂的查询。因此，现代数据的管理应该通过在数据建模中引入不确定性和不精确性，在数据访问建模中引入采样，在查询语义中引入近似，以及在查询公式化中引入机器学习来实现。然而，尽管这些概念在现代数据分析实践中无处不在，但它们在数据库理论中的基础却稀疏而分散。我们在本提案中的目标是着手对这些条款下的数据库管理进行系统和综合的研究。为此，一个关键的和中心的子目标是建立近似查询回答的理论基础的方式，是动态的（数据驱动）和定量的。动态将实现更好的近似，因为我们可以利用手头数据的属性。量化将允许近似保证，无论是绝对的还是统计的，并将提供灵活性，以换取性能的准确性。我们将通过追求几个目标来开展拟议的研究。我们计划建立和探索数据库距离的理论基础和相应的近似查询回答的概念，包括查询样本和数据的有损压缩的关系。我们还将研究该理论在更具体的任务中的应用，例如文本分析和复杂查询和函数的描述。

Traditional database concepts and systems have insisted on the totality of logical correctness in query answering. However, nowadays data-centric applications often analyze datasets that are unreliable and noisy or simply too large to allow answering complex queries exactly. Hence the management of modern data should be pursued by incorporating uncertainty and imprecision in data modeling, sampling in data-access modeling, approximation in query semantics, and machine learning in query formulation. Yet, while these concepts are ubiquitous in modern practice of data analytics, their underlying foundational basis in database theory is sparse andfragmented. Our goal in this proposal is to embark on a systematic and integrated study of database management under these terms. Towards that, a crucial and central subgoal is to establish the theoretical foundations of approximate query answering in a manner that is dynamic (data driven) and quantitative. Being dynamic will enable better approximations, since we can leverage properties of the data at hand. Being quantitative will allow for approximation guarantees, either absolute or statistical, and will provide the flexibility to trade accuracy for performance. We will carry out the proposed research by pursuing several objectives. We plan to establish and explore the theoretical foundations of database distances and corresponding notions of approximate query answering, including the relationship to querying samples and lossy compressions of data. We will also investigate the application of the theory to more specific tasks such as text analytics and description of complex queries and functions.