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

Question

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

---

Поскольку я имел в виду конкретный запрос, когда делал это, я закончил тем, что выполнил, как предложил @dougman, около 10% строк соответствующих таблиц и сравнил результаты, убедившись, что не было неуместных результатов. 1004 *

Answer 1

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

Для 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);

Answer 2

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

Answer 3

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

Ссылка на Cosette: http://cosette.cs.washington.edu/

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

Если все, что вам нужно, это просто быстрое практическое исправление, вы также можете проверить ответ на этот стек: [sql - проверить, равны ли два выбора]

Answer 4

Это довольно легко сделать.

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

а минус б

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

затем сделайте

б минус а

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

Answer 5

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

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

Answer 6

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

Answer 7

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

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

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

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

SELECT /*+RULE*/ FROM yourtable

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

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

Answer 8

ОСТОРОЖНО! Функциональная «эквивалентность» часто основывается на данных, и вы можете «доказать» эквивалентность 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.**

Answer 9

Вы не.

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

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

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

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