Доказательство эквивалентности SQL-запроса

Для меня это звучит как полная проблема NP. Я не уверен, что есть верный способ доказать такие вещи

Поставщики СУБД работали над этим очень и очень давно. Как сказал Рик, это наверное - неразрешимая проблема, но я не думаю, что был проведен какой-либо формальный анализ NP-полноты проблемного пространства.

Однако лучше всего использовать вашу СУБД в максимально возможной степени. Все системы СУБД преобразуют SQL в своего рода план запроса. Вы можете использовать этот план запроса, который представляет собой абстрактную версию запроса, в качестве хорошей отправной точки (СУБД будет делать ОЧЕНЬ МНОГО оптимизации, сводя запросы к более работоспособным моделям).

ПРИМЕЧАНИЕ: современные СУБД используют анализатор на основе затрат, который не является детерминированным при обновлении статистики, поэтому планировщик запросов со временем может изменить план запроса для идентичных запросов.

В Oracle (в зависимости от вашей версии) вы можете указать оптимизатору переключиться с анализатора на основе затрат на анализатор на основе детерминированных правил (это упростит анализ плана) с помощью подсказки SQL, например

SELECT /*+RULE*/ FROM yourtable

Оптимизатор, основанный на правилах, устарел с 8i, но он все еще существует даже через 10g (я не знаю насчет 11). Однако анализатор на основе правил гораздо менее сложен: потенциально вероятность ошибок намного выше.

Для дальнейшего чтения более общего характера IBM довольно плодотворно выдвинула свои патенты на оптимизацию запросов. Этот метод преобразования SQL в «абстрактный план» является хорошей отправной точкой: http://www.patentstorm.us/patents/7333981.html

Вы этого не сделаете.

Если вам нужен высокий уровень уверенности в том, что изменение производительности, например, не повлияло на вывод запроса, то проверьте его, черт возьми.

Если вам нужен действительно высокий уровень уверенности ... тогда эээ, проверьте его еще больше.

Огромный уровень тестирования не так уж и сложно собрать для SQL-запроса. Напишите процедуру, которая будет перебирать большой / полный набор возможных параметров, вызывать каждый запрос с каждым набором параметров и записывать выходные данные в соответствующие таблицы. Сравните две таблицы, и вот она.

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

Лучшее, что вы можете сделать, - это сравнить 2 вывода запроса на основе заданного набора входных данных, ища какие-либо различия. Сказать, что они всегда будут возвращать одинаковые результаты для всех входных данных, действительно зависит от данных.

For Oracle one of the better if not best approaches (very efficient) is here (Ctrl+F Comparing the Contents of Two Tables):
http://www.oracle.com/technetwork/issue-archive/2005/05-jan/o15asktom-084959.html

Что сводится к:

select c1,c2,c3, 
       count(src1) CNT1, 
       count(src2) CNT2
  from (select a.*, 
               1 src1, 
               to_number(null) src2 
          from a
        union all
        select b.*, 
               to_number(null) src1, 
               2 src2 
          from b
       )
group by c1,c2,c3
having count(src1) <> count(src2);

Возможно, вы могли бы нарисовать (вручную) свой запрос и результаты, используя Диаграммы Венна, и посмотреть, дают ли они одну и ту же диаграмму. Диаграммы Венна хороши для представления наборов данных, а запросы SQL работают с наборами данных. Составление диаграммы Венна может помочь вам визуализировать, если 2 запроса функционально эквивалентны.

Сделать это довольно просто.

Предположим, ваши запросы называются a и b

а минус б

должен дать вам пустой набор. Если это не так. затем запросы возвращают разные наборы, и в наборе результатов отображаются разные строки.

тогда делай

б минус а

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

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

select * from ((<query 1> MINUS <query 2>) UNION ALL (<query 2> MINUS <query 1>))

Вот удобный сценарий оболочки для этого:

#!/bin/sh

CONNSTR=
echo query 1, no semicolon, eof to end:; Q1=`cat` 
echo query 2, no semicolon, eof to end:; Q2=`cat`

T = "(($Q1 MINUS $Q2) UNION ALL ($Q2 MINUS $Q1));"

echo select 'count(*)' from $T | sqlplus -S -L $CONNSTR

ОСТОРОЖНЫЙ! Функциональная «эквивалентность» часто основана на данных, и вы можете «доказать» эквивалентность двух запросов, сравнивая результаты для многих случаев и все равно ошибаться, если данные изменятся определенным образом.

Например:

SQL> create table test_tabA
(
col1 number
)

Table created.

SQL> create table test_tabB
(
col1 number
)

Table created.

SQL> -- insert 1 row

SQL> insert into test_tabA values (1)

1 row created.

SQL> commit

Commit complete.

SQL> -- Not exists query:

SQL> select * from test_tabA a
where not exists
(select 'x' from test_tabB b
where b.col1 = a.col1)

      COL1

----------

         1

1 row selected.

SQL> -- Not IN query:

SQL> select * from test_tabA a
where col1 not in
(select col1
from test_tabB b)

      COL1

----------

         1

1 row selected.


-- THEY MUST BE THE SAME!!! (or maybe not...)


SQL> -- insert a NULL to test_tabB

SQL> insert into test_tabB values (null)

1 row created.

SQL> commit

Commit complete.

SQL> -- Not exists query:

SQL> select * from test_tabA a
where not exists
(select 'x' from test_tabB b
where b.col1 = a.col1)


      COL1

----------

         1

1 row selected.

SQL> -- Not IN query:

SQL> select * from test_tabA a
where col1 not in
(select col1
from test_tabB b)

**no rows selected.**

1) Доказательство реальной эквивалентности с Козеттой:
Cosette проверяет (с доказательством), эквивалентны ли 2 SQL-запроса, и встречает примеры, если они не эквивалентны. Это единственный способ быть абсолютно уверенным, ну почти;) Вы даже можете добавить 2 запроса на их веб-сайт и сразу проверить (формальную) эквивалентность.

Ссылка на Козетту: http://cosette.cs.washington.edu/

Ссылка на статью, которая дает хорошее объяснение того, как работает Cosette: https://medium.com/@uwdb/introduction-cosette-527898504bd6


2) Или, если вы просто ищете быстрое практическое решение:
Попробуйте этот ответ stackoverflow: [sql - проверьте, равны ли два элемента select]
Что сводится к:

(select * from query1 MINUS select * from query2) 
UNION ALL
(select * from query2 MINUS select * from query1)

Этот запрос дает вам все строки, возвращенные только одним из запросов.