Распознавание образов операторов SQL

Question

У меня есть проблема с сопоставлением текстового шаблона, с которой я мог бы использовать некоторое направление. Не очень хорошо знакомый с распознаванием образов в целом, я не знаю, является ли это одним из тех, «о, просто используйте алгоритм blah-blah», или это очень трудная проблема с шаблоном.

Общая формулировка того, что я хочу сделать, это выявить сходства между рядом операторов SQL, чтобы позволить мне реорганизовать эти выражения на меньшее количество хранимых процедур или других динамически генерируемых фрагментов SQL. Например,

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

все вроде то же самое, но я хотел бы признать, что значение внутри MIN() должен быть сменным значение, что я, возможно, еще один столбец в списке выбора, или необязательное предложение WHERE. Обратите внимание, что этот пример очень хорошо подготовлен, но я надеюсь, что он позволит вам увидеть, что я за ним.

Что касается области видимости, у меня будет множество тысяч операторов SQL, которые я бы надеялся уменьшить до десятков (?) Общих операторов. В исследованиях до сих пор я сталкивался с w-shingles и n-граммами и отказался от таких подходов, как «мешок слов», потому что упорядочение важно. Принимая это из области SQL, другим способом постановки этой проблемы может быть «задана серия текстовых инструкций, каков самый маленький набор текстовых фрагментов, которые можно использовать для сборки этих операторов?»

Answer 1

Что вы действительно хотите найти: code clones через базу кода.

Существует много способов сделать это, но большинство из них, похоже, игнорируют структуру, которую приносит язык SQL. Эта структура упрощает поиск элементов кода, которые делают концептуальный смысл, в отличие от N-граммов (да, «FROM x WHERE» является обычным, но является неудобным куском SQL).

Схема определения клона на основе абстрактного синтаксического дерева (AST) анализирует исходный текст для АСТ, а затем находит общие деревья, которые могут быть параметризованы таким образом, чтобы создавать разумные обобщения, используя грамматику языка в качестве руководства. См. Мою техническую документацию Clone Detection Using Abstract Syntax Trees.

Что касается примера OP в:

• Он признает, что значение внутри MIN() должно быть сменным значение
• что ВЫБРАТЬ одноточечно колонка может быть расширена в список
• и что предложение WHERE является необязательным.

Он не будет пытаться делать эти предложения, если только он не найдет двух клонов-кандидатов, которые меняются, как объясняют эти обобщения. Он получает обобщения в основном путем извлечения их из (SQL) грамматики. Примеры OP имеют достаточно точные вариации, чтобы заставить эти обобщения.

Обзор методов обнаружения клонов (Comparison and Evaluation of Code Clone Detection Techniques and Tools: A Qualitative Approach) оценил этот подход в верхней части около 30 различных методов обнаружения клонов; см. таблицу 14.

Answer 2

Вопрос немного слишком широким, но я хотел бы предложить, чтобы дать выстрел следующий подход:

Это звучит как document clustering проблема, где у вас есть набор фрагментов текста (инструкции SQL), и вы хотите сгруппировать их вместе, чтобы найти, если некоторые из операторов близки друг к другу. Теперь трюк здесь находится в измерении расстояния между текстовыми операторами. Я хотел бы попробовать что-то вроде edit distance

Так что в целом следующий подход может работать:

• У некоторых предобработки SQL заявления у вас есть. Tokenization, удаление некоторых слов из инструкций и т. Д. Просто будьте осторожны: вы не анализируете только какой-то текст на естественном языке, его SQL-запросы, поэтому вам понадобится какой-то умный подход.
• После этого попробуйте написать функцию, которая будет считать расстояние между 2-мя запросами. Расстояние редактирования должно работать для вас.
• Наконец, попробуйте запустить документ кластеризацию на всех ваших запросов SQL, используя расстояние редактирования в качестве меры расстояния для кластеризации алгоритма

Надежда, что помогает.