1
$\begingroup$

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 d \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...

$\endgroup$
  • $\begingroup$ disclaimer: I don't know much about databases, so this may be a really trivial question $\endgroup$ – olinarr Jun 14 at 9:53
  • 2
    $\begingroup$ You'll have to provide a description of what operations $Q$ allows. $\endgroup$ – orlp Jun 14 at 10:00
  • $\begingroup$ @orlp Mmh. I don't know much about various versions of SQL and I don't know the differences between them, I have only used standard postgres SQL queries: what should I write in the question? Is "Postgres SQL 10.6 queries" detailed enough? $\endgroup$ – olinarr Jun 14 at 10:03
  • $\begingroup$ First, you need to find out whether your SQL is Turing-complete. If don't, yes, you have to study the whole language. Alternatively, you may choose the relational algebra or some its extension. $\endgroup$ – Bulat Jun 14 at 11:09
  • $\begingroup$ @Bulat is it enough as I specified? $\endgroup$ – olinarr Jun 14 at 11:27
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Really clever amswer, thank you very much. If I may ask, did you come up with this yourself or do you have a source I can see? $\endgroup$ – olinarr Jun 15 at 7:10
  • 2
    $\begingroup$ No particular source. I personally like Diophantine satisfiability problem, because it's probably the simplest undecidable problem. As a result, it can easily creep into the analysis of programming languages, even not-Turing complete ones (like above) $\endgroup$ – Curtis F Jun 15 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.