Mathematical equality of two SQL statements
What is the mathematical equality of two SQL statements? For me two queries are equivalent if, when given both the same of any dataset, they return the same result set.

As you pointed out, SQL queries, a superset of relational algebra, can be very complex.  We can mix subqueries, use stored procedures and functions (deterministic or not) which will make you query looks more like real code.  If you are talking about these kinds of queries then it is going to be really hard.  In fact it is probably no different than the "are two algorithms equivalent" problem.

Under those conditions it is probably impossible.

However...

...it might be feasible if the two queries you want to compare are strict set operations.  If so, you can convert the queries to relational algebra and then work it out following equivalence rules.  If you have a selection/restriction with nontrivial boolean conditions then you might end up needing to prove than thoses conditions are also equivalent.  You'll then need to rely on boolean algebra and you'll probably end up doing a truth table.

As you can see this is going to be a lot of work and, as far as I know, nothing exists to compute all of that automatically.  Nevertheless, I found some tools that you might found useful if you want to tackle the task:


RelaX a relational algebra calculator
Truth table generator