Reverse engineering complex join queries
Reverse engineering complex join queries
复制标题
逆向工程复杂的连接查询
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
D. Srivastava
中科院分区：
文献类型：
--
作者：
Meihui Zhang;Hazem Elmeleegy;Cecilia M. Procopiuc;D. Srivastava
我们研究以下问题：给定一个带有模式G和输出表Out的数据库D，计算一个连接查询Q，它从D生成OUT。一个更简单的变体允许Q返回Out的超集。这个问题有许多应用，无论是本身，并作为其他问题的构建块。相关的先前工作强加的条件上的结构的Q，这并不总是与应用程序一致，但简化计算。我们讨论了几个自然的SQL查询，不满足这些条件，不能发现以前的工作。
在本文中，我们提出了一个有效的算法，发现查询与任意连接图。一个关键的见解是，任何图都可以由一个简单结构（称为星星）和一系列在星星上的合并步骤的组合来表征。合并步骤在从同一星星导出的图上定义晶格。这使我们能够以原则性的方式探索候选解决方案集，并快速修剪出大量不可行的图。我们还设计了几个优化，显着减少运行时间。最后，我们在一个基准数据库上进行了广泛的实验研究，并表明我们的方法是可扩展的，准确地发现复杂的连接查询。
We study the following problem: Given a database D with schema G and an output table Out, compute a join query Q that generates OUT from D. A simpler variant allows Q to return a superset of Out. This problem has numerous applications, both by itself, and as a building block for other problems. Related prior work imposes conditions on the structure of Q which are not always consistent with the application, but simplify computation. We discuss several natural SQL queries that do not satisfy these conditions and cannot be discovered by prior work.
In this paper, we propose an efficient algorithm that discovers queries with arbitrary join graphs. A crucial insight is that any graph can be characterized by the combination of a simple structure, called a star, and a series of merge steps over the star. The merge steps define a lattice over graphs derived from the same star. This allows us to explore the set of candidate solutions in a principled way and quickly prune out a large number of infeasible graphs. We also design several optimizations that significantly reduce the running time. Finally, we conduct an extensive experimental study over a benchmark database and show that our approach is scalable and accurately discovers complex join queries.