SQL语句的模式识别

Question

我有一个文本模式匹配问题，希望能得到一些指导。由于我对模式识别不是很熟悉，所以我不知道这是属于那种“哦，只需要使用某某算法”还是一个非常困难的模式问题。

我想要做的通用陈述是识别一系列SQL语句之间的相似之处，以便让我将这些语句重构为更少的存储过程或其他动态生成的SQL片段。例如，

SELECT MIN(foo) FROM bar WHERE baz > 123;
SELECT MIN(footer) FROM bar;
SELECT MIN(foo), baz FROM bar;

这些语句都差不多，但我希望指出MIN()函数内的值应该是可以替换的，因为我可能会在SELECT列表中添加另一列，或者加入一个可选的WHERE子句。请注意，这个例子是高度虚构的，但我希望它能让您看到我的意图。

就范围而言，我有成千上万条SQL语句，希望将它们缩减为几十个通用语句。到目前为止，我已经了解了w-shingles和n-grams等方法，并且已经放弃了"词袋"之类的方法，因为顺序很重要。把这个问题从SQL领域拿出来，另一种陈述这个问题的方式可能是"给定一系列文本语句，有哪些最小的文本片段可以用来重新组合这些语句？"

- tomo

Answer 1

您真正想要的是在代码库中找到代码克隆。有很多方法可以做到这一点，但大多数方法似乎忽略了（SQL）语言所带来的结构。这种结构使得寻找在概念上有意义的代码元素变得“更容易”，而不是像N-grams（是的，“FROM x WHERE”是常见的，但是它是SQL中一个尴尬的块）。我的基于抽象语法树（AST）的克隆检测方案将源文本解析为AST，然后找到共享的树，可以通过使用语言语法作为指南对其进行参数化，从而产生合理的概括。请参阅我的技术论文Clone Detection Using Abstract Syntax Trees。关于OP的示例：

• 它将识别MIN()内部的值应该是可替换值
• SELECT单个列可以扩展为列表
• WHERE子句是可选的

它不会尝试提出那些建议，除非它找到两个候选克隆体，在这些概括解释的方式上有所不同。它基本上通过从（SQL）语法中提取它们来得到这些概括。OP的例子恰好有足够的变化来强制执行这些概括。

代码克隆检测技术调查（Comparison and Evaluation of Code Clone Detection Techniques and Tools: A Qualitative Approach）将此方法评为30种不同克隆检测方法中的最佳方法；请参见表14。

- Ira Baxter

---

这听起来非常符合我需要做的事情。您的论文和调查在指引方向方面非常有帮助。这还让我想要研究代码差异工具，看看它们背后的原理是什么。 - tomo

为了完整表达我的想法，我还发现这个SO主题很有帮助，https://dev59.com/MXRA5IYBdhLWcg3w1BuW，它又指向了这个C#实现：http://www.mathertel.de/Diff/。 - tomo

在我看来，最有趣的代码差异工具使用了某种基础技术，但作为克隆检测器的一种补充而存在：它们比较抽象语法树，并报告不同之处，而不是报告相同之处。请参见我的网站上的“智能差异分析器”；这个工具没有发表论文，但您应该能够在scholar.google.com上找到关于抽象语法树差异分析的技术论文。 - Ira Baxter

在语法和语义方面，我同意你的看法，艾拉。Diff方法对我目前需要做的事情非常有效，但是通过解析器运行SQL并更加智能地比较部分将会更有价值。知道一条SQL语句多了一个列或者WHERE子句中多了一个条件将会非常好。但是我需要将SQL输入到Microsoft的解析器中（假设我可以访问它），并消耗输出（假设我可以理解它）。 - tomo

但是通过解析器运行SQL并以某种更智能的方式比较部分会更有价值。请查看我的网站上的“智能差异分析器”。唉。 - Ira Baxter

Answer 2

问题有点太宽泛了，但我建议尝试以下方法：

这听起来像是一个文档聚类问题，其中你有一组文本片段（SQL语句），并且你想将它们聚类在一起以找出某些语句是否相互接近。现在，关键在于文本语句之间的距离度量。我会尝试使用编辑距离之类的东西。

因此，通常以下方法可能有效：

- 对你拥有的SQL语句进行一些预处理。分词、删除语句中的某些单词等。只要小心 - 你不仅仅是分析一些自然语言文本，而是SQL语句，所以你需要一些聪明的方法。 - 在此之后，尝试编写一个函数，该函数将计算两个SQL查询之间的距离。编辑距离应该适合你。 - 最后，尝试对所有SQL查询运行文档聚类，使用编辑距离作为聚类算法的距离度量。

希望这可以帮到你。

- Maksim Khaitovich

---

谢谢，这很有帮助。但我认为关于“代码克隆”的另一个答案更切题。 - tomo