Is there a query language variant of Turing Completeness? By this I mean a theory where you can say Language X is Query Complete so that you know that language is able to do any sort of query? I'm guessing not because some queries would run into things that a language would have to be Turing complete to work?
Why do I wonder - well you might have a relational database and a graph database and someone might say anything that can be done in the relational database can be done in the graph database (albeit at different speeds) so I would like if there were some terms DB A and DB B are both Query Complete - or if not that if there was a way to categorize levels of &quot;query completeness&quot; (I'm just going to assume my ill defined concept is totally understandable to everyone) so one can say stuff like &quot;DB A is query level 4 but DB B is at query level 3, but of course much faster because of those limitations.&quot;
I sure hope (so as to not feel like a bigger idiot than normal) that the answer to this question isn't just a flat No.
The most you could expect out of a query language would be Turing completeness. In other words, the most powerful you could make a (physically realizable) query language would be to allow operations equivalent to treating the entire database as a single string and running an arbitrary program with that string as input.
Any real-world database query language that includes WHILE loops in the query language (e.g. PL/SQL) is probably Turing-complete in this sense. With such a language, you can go all the way down to reading and writing single rows at a time as necessary to read arbitrary data out of the database and interpret a Turing machine with the data as input. Of course, this is horrifically inefficient, but that's beside the point!