Is "Query Equivalence" decidable?

Question

I have studied in my Computability course that it is impossible to design an algorithm $A(x,y)$ which decides, for every couple of programs ($P_1$, $P_2$), whether they are equivalent (e.g. $\forall x \in Data:P_1(x) = P_2(x)$). This is easily shown with Rice's theorem.

I was wondering if a similar problem with SQL queries is solvable:

Is it possible to design an algorithm $A_D(x,y)$ which, given a fixed database schema $D$, decides if, for every possible instance of $D$, $Q_1$ and $Q_2$ return the same table $T$?

---

Appendix

As suggested in the comments, I'll now specify the legal operations for $Q_i$. I am talking about simple queries such as:

• Simple queries with SELECT [DISTINCT] ... FROM ... WHERE
• Queries with subqueries
• Queries with aggregated operators
• Queries with GROUP BY and HAVING
• CREATE VIEW

Furthermore, let's assume our SQL is not turing complete, so no CTE or RECURSIVE are allowed. Lastly, I mean only SELECT-like queries, no UPDATEs, INSERT INTOs, etc...

Answer 1

Suppose the abstract SQL you're considering has support for infinite-precision "big" integers that can store any integer values, and that these support *, +, and = in WHERE clauses.

Fix the schema as $k$ such integer values columns called x_1, ..., x_k.

---

Query equivalence in this schema is undecidable by a reduction to the satisfiability of Diophantine equations (Hilbert's 10th problem):

A system of Diophantine equations can be described as a multivariate-polynomial with integer coefficients $p(x_1, \dots, x_n) = 0$. Determining whether or not there is any tuple $(x_1, \dots, x_n) \in \mathbb{Z}^n$ that satisfies the equation is known to be an undecidable problem.

This condition can be directly represented as the WHERE clause in the SQL described above: WHERE p(x_1, ..., x_k) = 0 (expanded using * and +).

Determining whether or not SELECT * FROM t WHERE p(x_1, ..., x_k) = 0 is equivalent to SELECT * FROM t WHERE false is determining whether or not p(x_1, ..., x_k) has some assignment of integers $x_1, \dots, x_k$ such that $p(x_1, \dots, p_k) = 0$; thus if we were able to determing the equivalence of SQL queries, we would be able to determine the satisfiability of Diophantine equations.

Because the satisfiability of Diophantine equations is undecidable, so must this query equivalence problem.

---

The above doesn't rely on any particularly interesting features of SQL -- it certainly doesn't rely on any tricky "Turing complete" features of many SQL implementations -- it relies solely on the embedded ability to evaluate expressions involving integers. That means this is unfortunately rather unenlightening, but it also makes it hard to pare down SQL to something that won't immediately have undecidability creep in.

Like any theoretical result on decidability would, this does require arbitrary precision integers are supported. While I don't know of any popular SQL implementation that truly supports unbounded integers, PostreSQL for one documents arbitrary-precision integers that support at least 1000 digits of precision, which is likely "large enough" to say an abstract model of SQL supports unbounded integers.

It might be worth analyzing a SQL without any support for arithmetic operators like + and *, though I think it might be possible to emulate both + and * using SUM and JOINs; even without SUM I think it may be possible.

Answer 2

The problem of query-equivalence, and the problem of query-containment (knowing if the result of some query Q1 is a subset of the result of some other query Q2, for any possible instance of the database) are undecidable in relational algebra [1].

Hence, the query-equivalence problem is undecidable in SQL (even without arithmetic operations, as already suggested).

[1] Abiteboul, Serge, Richard Hull, and Victor Vianu. Foundations of databases. Vol. 8. Reading: Addison-Wesley, 1995.