Probar la equivalencia de consultas SQL

Lo mejor que puede hacer es comparar las 2 salidas de consulta en función de un conjunto determinado de entradas en busca de diferencias. Decir que siempre devolverán los mismos resultados para todas las entradas realmente depende de los datos.

Para Oracle, uno de los mejores, si no los mejores enfoques (muy eficiente) está aquí (Ctrl +F Comparación del contenido de dos tablas):
http://www.oracle.com/technetwork/issue-archive/2005/05-jan/o15asktom-084959.html

Lo que se reduce a:

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);