Математическое равенство двух операторов SQL

9

Есть ли способ получить проверку математического равенства двух операторов SQL?

У меня есть два оператора SQL:

  • SQL_STATEMENT_1
  • SQL_STATEMENT_2

Выполнение обоих операторов над данными и сравнение результатов не помогает вообще.

Математика, стоящая за утверждениями, должна оцениваться, как это делает решатель уравнений.

Вне моего вопроса находятся такие вещи, как:

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

В объеме:

  • Подвыбирает: ГДЕ other_id IN (ВЫБЕРИТЕ id ИЗ ДРУГОГО ГДЕ ...)
  • JOINS
database-theory guettli
источник
Частичным решением будет сравнение планов выполнения 2 запросов. Если планы выполнения одинаковы, то они равны. Однако отношения не работают в обоих направлениях. Может быть 2 логически эквивалентных запроса, которые имеют разные планы выполнения.
BuahahaXD
1
@BuahahaXD: это не правда. select * from foo where id = 4наверняка будет иметь тот же план выполнения, что иselect * from foo where id = 2
a_horse_with_no_name
@a_horse_with_no_name Я протестировал его на SQL Server и получил 2 разных файла XML. Параметры были включены как узел <ParameterList> в файл XML. Визуально эти планы были идентичны (сканирование таблицы + выбор). Но я верю, что вы, возможно, правы, сравнивая планы выполнения.
BuahahaXD
1
@a_horse_with_no_name правильно, когда дело доходит до уникальных ключей. Для всех остальных возможно select * from foo where id = 4и select * from foo where id = 2может быть два разных плана выполнения, если 1) статистика индекса не обновлена ​​и 2) даже если статистика индекса актуальна, распределение ключей по идентификатору является односторонним (предоставленный идентификатор не является уникальным ключом).
RolandoMySQLDBA

Ответы:

6

Каково математическое равенство двух операторов SQL? Для меня два запроса эквивалентны, если, когда им дано то же самое из любого набора данных, они возвращают один и тот же набор результатов.

Как вы указали, SQL-запросы, расширенный набор реляционной алгебры , могут быть очень сложными. Мы можем смешивать подзапросы, использовать хранимые процедуры и функции ( детерминированные или нет), которые сделают ваш запрос более похожим на реальный код . Если вы говорите об этих видах запросов, то это будет очень сложно. На самом деле это, вероятно, ничем не отличается от проблемы "эквивалент двух алгоритмов".

В этих условиях это, вероятно, невозможно.

Однако...

... это может быть осуществимо, если два запроса, которые вы хотите сравнить, являются строгими операциями над множествами. Если это так, вы можете преобразовать запросы в реляционную алгебру, а затем обработать ее, следуя правилам эквивалентности . Если у вас есть выбор / ограничение с нетривиальными логическими условиями, то вам может понадобиться доказать, что эти условия также эквивалентны. Затем вам нужно будет полагаться на булеву алгебру, и вы, вероятно, в конечном итоге составите таблицу истинности .

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

ForguesR
источник
Мой вопрос касается только операций над множествами. Я обновил вопрос. Это связано с «эквивалентностью двух алгоритмов». Но контекст ограничен, в моей области видимости только базовые операции множеств, объединений, подвыборов.
Геттли
3

Невозможно проверить семантическую эквивалентность за конечное время по определению, см . Теорему Райса :

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

user63455
источник
2
Это только просто не комментарий. Не могли бы вы подробнее рассказать о применимости Райс к этому контексту?
Майкл Грин,
Даже если бы это было теоретически возможно, нынешний стандартный синтаксис SQL настолько барокко, что на практике это было бы невозможно
Джеймс Андерсон,
1
С объяснением OP похоже, что вопрос скорее в логической эквивалентности, чем в семантической эквивалентности. Реальный вопрос: можем ли мы преобразовать операторы SQL в математическое выражение и затем оценить логическую эквивалентность?
ForguesR
2

Пользователь dba Lennart указал мне на этот проект:

http://cosette.cs.washington.edu/

Cosette является автоматическим средством проверки эквивалентности SQL-запросов. Он формализует существенный фрагмент SQL в Coq Proof Assistant и символической виртуальной машине Rosette. Он возвращает либо формальное доказательство эквивалентности, либо контрпример для пары заданных запросов.

guettli
источник
1

Один из способов сделать это - создать синтаксический анализатор или, лучше сказать, использовать существующий. Я считаю, что C # имеет класс TSQLParser и имеет метод Parse (). Парсер разбит ваш запрос на подклассы, которые вы сможете затем сравнить.

Матан Юнгман
источник
1

Если вы ищете тест эквивалентности, основанный на теории множеств, лучше всего конвертировать любые WHEREусловия, которые можно преобразовать в тип JOIN(внутренний или внешний), и реорганизовать утверждение. Это включает IN subselectи EXISTS subselectи любые другие условия в WHEREпредложении, которое содержит слово SELECT. Если вы выполните это для обоих операторов SQL, у вас будет новое FROMпредложение, представляющее интересующую вас логику / математику на основе множеств. Затем вы можете просто визуально сравнить два оператора. Если вы ищете автоматизированный способ сделать все это, я не знаю инструмента, который может сделать именно это.

Очередь Манн
источник