SQL 语句的模式识别

Question

我有一个文本模式匹配问题，我可以使用一些指导。总体上对模式识别不是很熟悉，我不知道这是其中之一 "oh, just use blah-blah algorithm"，还是这是一个非常难的模式问题。

我想做的一般说明是识别一系列 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-gram，并且放弃了 "bag of words" 之类的方法，因为排序很重要。将其从 SQL 领域中取出，另一种说明此问题的方式可能是 "given a series of text statements, what is the smallest set of text fragments that can be used to reassemble those statements?"

Answer 1

问题有点太宽泛了，不过我建议试试下面的方法：

这听起来像 document clustering problem, where you have a set of pieces of text (SQL statements) and you want to cluster them together to find if some of the statements are close to each other. Now, the trick here is in the distance measure between text statements. I would try something like edit distance

所以一般来说，以下方法可行：

对您拥有的 sql 语句进行一些预处理。标记化，从语句中删除一些单词等。这里要小心 - 你不只是分析一些自然语言文本，它是一个 SQL 语句，所以你需要一些聪明的方法。
之后，尝试编写一个函数来计算 2 sql 查询之间的距离。编辑距离应该适合您。
最后，尝试运行记录所有 SQL 查询的聚类，使用编辑距离作为聚类算法的距离度量

希望对您有所帮助。

Answer 2

您真正想要的是在整个代码库中找到代码克隆。

有很多方法可以做到这一点，但大多数方法似乎都忽略了 (SQL) 语言带来的结构。这种结构使得 "easier" 可以找到具有概念意义的代码元素，而不是说 N-gram（是的，"FROM x WHERE" 很常见，但它是 SQL 的笨拙块）。

我的基于抽象语法树 (AST) 的克隆检测方案将源文本解析为 AST，然后找到可以通过使用语言语法作为指南以产生合理概括的方式进行参数化的共享树。看我的技术论文Clone Detection Using Abstract Syntax Trees.

关于OP的例子：

它将识别 MIN() 中的值应该是可替换值
SELECT 单例列可以扩展到列表
并且 WHERE 子句是可选的

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

克隆检测技术综述（代码克隆检测技术的比较与评估 and Tools: A Qualitative Approach) 将这种方法评为大约 30 种不同克隆检测方法中的佼佼者；参见 table 14.

SQL 语句的模式识别

Pattern recognition of SQL statements

algorithm

pattern-recognition

machine-learning

pattern-matching