Доказательство эквивалентности SQL-запросов
Как бы вы могли доказать, что два запроса функционально эквивалентны, например, они всегда будут возвращать один и тот же набор результатов.
Поскольку я имел в виду конкретный запрос, когда я делал это, я закончил тем, что сделал, как предложил @dougman, около 10% строк соответствующих таблиц и сравнил результаты, гарантируя, что не было неуместных результатов.
9 ответов
Лучшее, что вы можете сделать, - это сравнить результаты двух запросов на основе заданного набора входных данных, чтобы найти различия. Сказать, что они всегда будут возвращать одинаковые результаты для всех входных данных, действительно зависит от данных.
Для Oracle один из лучших, если не лучших подходов (очень эффективный) здесь (Ctrl + F Сравнение содержимого двух таблиц):
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);
Вы должны действительно проверить Cosette: он проверяет (с доказательством), являются ли 2 SQL-запроса эквивалентными и встречными примерами, когда не эквивалентны. Это единственный способ быть абсолютно уверенным, ну почти;) Вы даже можете добавить 2 запроса на их веб-сайте и сразу же проверить (формальную) эквивалентность.
Ссылка на Cosette: http://cosette.cs.washington.edu/
Ссылка на статью, которая дает хорошее объяснение того, как работает Cosette: https://medium.com/@uwdb/introducing-cosette-527898504bd6
Если все, что вам нужно, это просто быстрое практическое исправление, вы также можете проверить этот ответ stackru: [sql - проверить, равны ли два выбора]
Это звучит для меня как полная проблема NP. Я не уверен, что есть надежный способ доказать такую вещь
Это довольно легко сделать.
Предположим, что ваши запросы называются a и b
минус б
должен дать вам пустой набор. Если это не так. затем запросы возвращают разные наборы, а результирующий набор показывает разные строки.
тогда делай
б минус
это должно дать вам пустой набор. Если это так, то запросы возвращают одинаковые наборы. если он не пустой, то запросы в некотором отношении различны, и результирующий набор показывает разные строки.
Это сделает свое дело. Если этот запрос возвращает ноль строк, два запроса возвращают одинаковые результаты. В качестве бонуса он выполняется как один запрос, поэтому вам не нужно беспокоиться об установке уровня изоляции, чтобы данные не менялись между двумя запросами.
select * from ((<query 1> MINUS <query 2>) UNION ALL (<query 2> MINUS <query 1>))
Вот удобный скрипт оболочки для этого:
#!/bin/sh
CONNSTR=$1
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
ОСТОРОЖНЫЙ! Функциональная "эквивалентность" часто основана на данных, и вы можете "доказать" эквивалентность 2 запросов, сравнивая результаты для многих случаев и все еще ошибаться, когда данные изменяются определенным образом.
Например:
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.**
Возможно, вы могли бы нарисовать (вручную) свой запрос и результаты с помощью диаграмм Венна и посмотреть, дают ли они одну и ту же диаграмму. Диаграммы Венна хороши для представления наборов данных, а запросы SQL работают с наборами данных. Составление диаграммы Венна может помочь вам визуализировать, если 2 запроса функционально эквивалентны.
Вендоры СУБД работают над этим очень и очень долго. Как сказал Рик, это, вероятно, неразрешимая проблема, но я не думаю, что был проведен какой-либо формальный анализ NP-полноты пространства задач.
Тем не менее, ваш лучший выбор - максимально использовать вашу СУБД. Все системы СУБД переводят SQL в какой-то план запроса. Вы можете использовать этот план запроса, который является абстрагированной версией запроса, в качестве хорошей отправной точки (СУБД будет выполнять МНОЖЕСТВО оптимизации, объединяя запросы в более работоспособные модели).
ПРИМЕЧАНИЕ: современные СУБД используют анализатор на основе затрат, который является недетерминированным при обновлении статистики, поэтому планировщик запросов со временем может изменить план запроса для идентичных запросов.
В Oracle (в зависимости от вашей версии) вы можете сказать оптимизатору переключиться с анализатора на основе затрат на анализатор на основе детерминированных правил (это упростит анализ плана) с помощью подсказки SQL, например:
SELECT /*+RULE*/ FROM yourtable
Оптимизатор, основанный на правилах, устарел с 8i, но до сих пор стоит около 10 г (я не знаю, как насчет 11). Однако анализатор, основанный на правилах, гораздо менее сложен: частота ошибок потенциально намного выше.
Для дальнейшего прочтения более общего характера, IBM была довольно плодовитой с их патентами оптимизации запросов. Вот этот метод преобразования SQL в "абстрактный план" - хорошая отправная точка: http://www.patentstorm.us/patents/7333981.html
Вы не
Если вам нужен высокий уровень уверенности в том, что, например, изменение производительности не изменило вывод запроса, проверьте его.
Если вам нужен действительно высокий уровень уверенности... тогда ошибайтесь, протестируйте его еще больше.
Массовый уровень тестирования не так уж сложно объединить для SQL-запроса. Напишите процедуру, которая будет перебирать большой / полный набор возможных параметров, и вызывать каждый запрос с каждым набором параметров, а также записывать выходные данные в соответствующие таблицы. Сравните две таблицы, и вот оно.
Это не совсем научно, что, как мне кажется, было вопросом ОП, но я не знаю формального метода доказательства эквивалентности.