<p>How would you go about proving that two queries are functionally equivalent, eg they will always both return the same result set.</p>

<hr>

<p>As I had a specific query in mind when I was doing this, I ended up doing as @dougman suggested, over about 10% of rows the tables concerned and comparing the results, ensuring there was no out of place results.</p>

[{'answer_id': 56931, 'author': 'Rik', 'author_id': 5409, 'author_profile': 'https://Stackoverflow.com/users/5409', 'pm_score': 3, 'selected': False, 'text': "<p>This sounds to me like a an NP complete problem. I'm not sure there is a sure fire way to prove this kind of thing</p>\n"}, {'answer_id': 57313, 'author': 'Matt Rogish', 'author_id': 2590, 'author_profile': 'https://Stackoverflow.com/users/2590', 'pm_score': 1, 'selected': False, 'text': '<p>The DBMS vendors have been working on this for a very, very long time. As Rik said, it\'s <em>probably</em> an intractable problem, but I don\'t think any formal analysis on the NP-completeness of the problem space has been done.</p>\n\n<p>However, your best bet is to leverage your DBMS as much as possible. All DBMS systems translate SQL into some sort of query plan. You can use this query plan, which is an abstracted version of the query, as a good starting point (the DBMS will do LOTS of optimization, flattening queries into more workable models). </p>\n\n<p><em>NOTE: modern DBMS use a "cost-based" analyzer which is non-deterministic across statistics updates, so the query planner, over time, may change the query plan for identical queries.</em></p>\n\n<p>In Oracle (depending on your version), you can tell the optimizer to switch from the cost based analyzer to the deterministic rule based analyzer (this will simplify plan analysis) with a SQL hint, e.g.</p>\n\n<pre><code>SELECT /*+RULE*/ FROM yourtable\n</code></pre>\n\n<p>The rule-based optimizer has been deprecated since 8i but it still hangs around even thru 10g (I don\'t know \'bout 11). However, the rule-based analyzer is much less sophisticated: the error rate potentially is much higher.</p>\n\n<p>For further reading of a more generic nature, IBM has been fairly prolific with their query-optimization patents. This one here on a method for converting SQL to an "abstract plan" is a good starting point:\n<a href="http://www.patentstorm.us/patents/7333981.html" rel="nofollow noreferrer">http://www.patentstorm.us/patents/7333981.html</a></p>\n'}, {'answer_id': 75328, 'author': 'Michael OShea', 'author_id': 13178, 'author_profile': 'https://Stackoverflow.com/users/13178', 'pm_score': 0, 'selected': False, 'text': "<p>You don't.</p>\n\n<p>If you need a high level of confidence that a performance change, for example, hasn't changed the output of a query then test the hell out it.</p>\n\n<p>If you need a really high level of confidence .. then errrm, test it even more.</p>\n\n<p>Massive level's of testing aren't that hard to cobble together for a SQL query. Write a proc which will iterate around a large/complete set of possible paramenters, and call each query with each set of params, and write the outputs to respective tables. Compare the two tables and there you have it.</p>\n\n<p>It's not exactly scientific, which I guess was the OP's question, but I'm not aware of a formal method to prove equivalency.</p>\n"}, {'answer_id': 93489, 'author': 'Doug Porter', 'author_id': 4311, 'author_profile': 'https://Stackoverflow.com/users/4311', 'pm_score': 5, 'selected': True, 'text': '<p>The best you can do is compare the 2 query outputs based on a given set of inputs looking for any differences.  To say that they will always return the same results for all inputs really depends on the data.</p>\n\n<p>For Oracle one of the better if not best approaches (very efficient) is here (<kbd>Ctrl</kbd>+<kbd>F</kbd> Comparing the Contents of Two Tables):<br>\n<a href="http://www.oracle.com/technetwork/issue-archive/2005/05-jan/o15asktom-084959.html" rel="noreferrer"><a href="http://www.oracle.com/technetwork/issue-archive/2005/05-jan/o15asktom-084959.html" rel="noreferrer">http://www.oracle.com/technetwork/issue-archive/2005/05-jan/o15asktom-084959.html</a></a></p>\n\n<p>Which boils down to:</p>\n\n<pre><code>select c1,c2,c3, \n       count(src1) CNT1, \n       count(src2) CNT2\n  from (select a.*, \n               1 src1, \n               to_number(null) src2 \n          from a\n        union all\n        select b.*, \n               to_number(null) src1, \n               2 src2 \n          from b\n       )\ngroup by c1,c2,c3\nhaving count(src1) &lt;&gt; count(src2);\n</code></pre>\n'}, {'answer_id': 93527, 'author': 'Kibbee', 'author_id': 1862, 'author_profile': 'https://Stackoverflow.com/users/1862', 'pm_score': 1, 'selected': False, 'text': '<p>Perhaps you could draw (by hand) out your query and the results using <a href="http://en.wikipedia.org/wiki/Venn_diagram" rel="nofollow noreferrer">Venn Diagrams</a>, and see if they produce the same diagram.  Venn diagrams are good for representing sets of data, and SQL queries work on sets of data.  Drawing out a Venn Diagram might help you to visualize if 2 queries are functionally equivalent.</p>\n'}, {'answer_id': 98609, 'author': 'EvilTeach', 'author_id': 7734, 'author_profile': 'https://Stackoverflow.com/users/7734', 'pm_score': 2, 'selected': False, 'text': '<p>This is pretty easy to do.</p>\n\n<p>Lets assume your queries are named a and b</p>\n\n<p><strong>a\nminus \nb</strong></p>\n\n<p>should give you an empty set.  If it does not. then the queries return different sets, and the result set shows you the rows that are different.</p>\n\n<p>then do</p>\n\n<p><strong>b \nminus \na</strong></p>\n\n<p>that should give you an empty set.  If it does, then the queries do return the same sets.\nif it is not empty, then the queries are different in some respect, and the result set shows you the rows that are different.</p>\n'}, {'answer_id': 2122095, 'author': 'Mark Harrison', 'author_id': 116, 'author_profile': 'https://Stackoverflow.com/users/116', 'pm_score': 1, 'selected': False, 'text': '<p>This will do the trick.  If this query returns zero rows the two queries are returning the same results.  As a bonus, it runs as a single query, so you don\'t have to worry about setting the isolation level so that the data doesn\'t change between two queries.</p>\n\n<pre><code>select * from ((&lt;query 1&gt; MINUS &lt;query 2&gt;) UNION ALL (&lt;query 2&gt; MINUS &lt;query 1&gt;))\n</code></pre>\n\n<p>Here\'s a handy shell script to do this:</p>\n\n<pre><code>#!/bin/sh\n\nCONNSTR=$1\necho query 1, no semicolon, eof to end:; Q1=`cat` \necho query 2, no semicolon, eof to end:; Q2=`cat`\n\nT="(($Q1 MINUS $Q2) UNION ALL ($Q2 MINUS $Q1));"\n\necho select \'count(*)\' from $T | sqlplus -S -L $CONNSTR\n</code></pre>\n'}, {'answer_id': 5730066, 'author': 'tbone', 'author_id': 534120, 'author_profile': 'https://Stackoverflow.com/users/534120', 'pm_score': 1, 'selected': False, 'text': '<p>CAREFUL!   Functional "equivalence" is often based on the data, and you may "prove" equivalence of 2 queries by comparing results for many cases <strong><em>and still be wrong once the data changes in a certain way</em></strong>.</p>\n\n<p>For example:</p>\n\n<pre><code>SQL&gt; create table test_tabA\n(\ncol1 number\n)\n\nTable created.\n\nSQL&gt; create table test_tabB\n(\ncol1 number\n)\n\nTable created.\n\nSQL&gt; -- insert 1 row\n\nSQL&gt; insert into test_tabA values (1)\n\n1 row created.\n\nSQL&gt; commit\n\nCommit complete.\n\nSQL&gt; -- Not exists query:\n\nSQL&gt; select * from test_tabA a\nwhere not exists\n(select \'x\' from test_tabB b\nwhere b.col1 = a.col1)\n\n      COL1\n\n----------\n\n         1\n\n1 row selected.\n\nSQL&gt; -- Not IN query:\n\nSQL&gt; select * from test_tabA a\nwhere col1 not in\n(select col1\nfrom test_tabB b)\n\n      COL1\n\n----------\n\n         1\n\n1 row selected.\n\n\n-- THEY MUST BE THE SAME!!! (or maybe not...)\n\n\nSQL&gt; -- insert a NULL to test_tabB\n\nSQL&gt; insert into test_tabB values (null)\n\n1 row created.\n\nSQL&gt; commit\n\nCommit complete.\n\nSQL&gt; -- Not exists query:\n\nSQL&gt; select * from test_tabA a\nwhere not exists\n(select \'x\' from test_tabB b\nwhere b.col1 = a.col1)\n\n\n      COL1\n\n----------\n\n         1\n\n1 row selected.\n\nSQL&gt; -- Not IN query:\n\nSQL&gt; select * from test_tabA a\nwhere col1 not in\n(select col1\nfrom test_tabB b)\n\n**no rows selected.**\n</code></pre>\n'}, {'answer_id': 45584198, 'author': 'Sander van den Oord', 'author_id': 3489155, 'author_profile': 'https://Stackoverflow.com/users/3489155', 'pm_score': 4, 'selected': False, 'text': '<p><strong>1) Real equivalency proof with Cosette:</strong><br>\nCosette checks (with a proof) if 2 SQL query\'s are equivalent and counter examples when not equivalent. It\'s the only way to be absolutely sure, well almost ;) You can even throw in 2 query\'s on their website and check (formal) equivalence right away.</p>\n<p>Link to Cosette:\n<a href="https://cosette.cs.washington.edu/" rel="nofollow noreferrer">https://cosette.cs.washington.edu/</a></p>\n<p>Link to article that gives a good explanation of how Cosette works: <a href="https://medium.com/@uwdb/introducing-cosette-527898504bd6" rel="nofollow noreferrer">https://medium.com/@uwdb/introducing-cosette-527898504bd6</a><br>\n<br>\n<br>\n<strong>2) Or if you\'re just looking for a quick practical fix:</strong><br>\nTry this stackoverflow answer: <a href="https://stackoverflow.com/questions/5727882/check-if-two-selects-are-equivalent">[sql - check if two select\'s are equal]</a><br>\nWhich comes down to:</p>\n<pre><code>(select * from query1 MINUS select * from query2) \nUNION ALL\n(select * from query2 MINUS select * from query1)\n</code></pre>\n<p>This query gives you all rows that are returned by only one of the queries.</p>\n'}]
['https://Stackoverflow.com/questions/56895', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/3839/']