Fine-grained Data Provenance for Very Expressive Queries

数据来源揭示了数据库查询如何转换、过滤、合并和聚合输入数据以获得最终输出。随着当今数据量和查询复杂性的急剧增长，查询的内部工作很快变得难以评估和验证：这段输出来自输入的哪里？为什么查询发出了这一项而忽略了另一项？查询是如何产生这个结果值的，究竟是哪些查询构造参与了计算？数据来源可以回答这些问题和进一步的问题，这些回答解释了查询的内部（和错误），有助于数据质量评估，并有助于建立对查询结果的信任——这是对依赖数据的科学和社会的关键服务。有了来源，我们将查询的重点从值及其转换转移到输出和输入数据之间的依赖关系。本研究计划建立在一个中心假设上，即抽象解释提供了一个理想的框架来思考和推理，并实现了这种焦点的转移。在抽象解释中，在20世纪70年代首次建立的程序分析学科中，除了程序评估的一个（或几个）选定方面之外，所有方面都被忽略了。本项目将采用这些思想来开发查询和程序的视图，其中输入/输出依赖关系（而不是值）承担主要角色。数据来源的好处随着它能够解释的查询逻辑的复杂性而增加。我们开始推导高级查询语言结构和习惯用法的起源，如深度嵌套、滑动窗口、用户定义和内置函数，或递归。它的核心目标是采用与实际相关的复杂语言，比如SQL的现代变体，在这些语言中，以前的工作受到了很大的限制。我们将充分利用抽象解释的灵活性，并设计抽象域，在不同的数据粒度级别上解释起源，直至单个原子值（例如表单元格）。对抽象域和查询解释规则的进一步调整将允许探索新的和非常困难的数据来源类型（例如，输出中缺少的值）。抽象解释既是一种强大的理论工具，也是一种实践工具。在后者的基础上，我们将研究大数据量查询的并行来源派生，以及将数据来源无缝集成到现有现代数据库系统的查询编译器中。

Data provenance uncovers how database queries transform, filter, merge, and aggregate input data to arrive at the final output. With today's characteristic steep growth in data volume as well as query complexity, the inner workings of a query quickly become hard to assess and validate: where in the input did this piece of output originate? Why did the query emit this item but omit another? How did the query produce this result value and exactly which query constructs participated in the evaluation? Data provenance has answers to these and further questions and the responses explain query internals (and bugs), aid in data quality assessments, and help to build trust in query results—a critical service to data-dependent science and society.With provenance, we shift a query's focus from values and their transformation to the dependencies between output and input data. This research proposal is built on the central hypothesis that abstract interpretation provides an ideal framework to think and reason about as well as to implement this shift of focus. In abstract interpretation, a program analysis discipline first established in the 1970s, all but one (or few) selected aspect(s) of a program's evaluation are ignored. This project will adapt these ideas to develop a view of queries and programs in which input/output dependencies—not: values—assume the primary role.The benefits of data provenance grow with the complexity of the query logic it is able to explain. We set out to derive provenance for advanced query language constructs and idioms like deep nesting, sliding windows, user-defined and built-in functions, or recursion. It is a core goal to embrace practically relevant and complex languages, like modern variants of SQL, where prior work exhibited significant restrictions. We will capitalize on the flexibility of abstract interpretation and design abstract domains that explain provenance at various levels of data granularity, down to individual atomic values (table cells, say). Further adaptations of the abstract domain and query interpretation rules will allow the exploration of new and notoriously difficult types of data provenance (e.g., those of values absent in the output). Abstract interpretation is both, a powerful theoretical but also a practical tool. Building on the latter, we will study parallel provenance derivation for queries over large data volumes and the seamless integration of data provenance into query compilers of existing modern database systems.