patternMinor
Mathematical equality of two SQL statements
Viewed 0 times
equalitysqlstatementstwomathematical
Problem
Is there a way to get check the mathematical equality of two SQL statements?
I have two SQL statements:
Running both statements on data and comparing the output does not help at all.
The set maths behind the statements needs to be evaluated, like a equation solver does.
Out of scope of my question are things like:
In the scope:
I have two SQL statements:
- SQL_STATEMENT_1
- SQL_STATEMENT_2
Running both statements on data and comparing the output does not help at all.
The set maths behind the statements needs to be evaluated, like a equation solver does.
Out of scope of my question are things like:
- comparisons other then equality (greater than, less than, LIKE, ...)
- stored procedures, or triggers
- Common Table Expressions (WITH)
In the scope:
- Subselects: WHERE other_id IN (SELECT id FROM other WHERE ...)
- JOINS
Solution
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:
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
Context
StackExchange Database Administrators Q#96865, answer score: 8
Revisions (0)
No revisions yet.