1
$\begingroup$

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 "query completeness" (I'm just going to assume my ill defined concept is totally understandable to everyone) so one can say stuff like "DB A is query level 4 but DB B is at query level 3, but of course much faster because of those limitations."

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.

$\endgroup$
4
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

For a query language to be "complete", in this sense of "being able to express all queries", it would have to be evaluated in its capacity to give a well-formed version of every question that can be posed, whose answer can be given as an instance of the data model that is being used to parameterize said language.

(I'm assuming your question is about what is definable, not computable, so to speak. The answer is trivial, otherwise.)

This is a heavy constraint on the kinds of questions that are considered legitimate. One would hope that a query language based on a powerful construct such as the logic/algebra of relations is good enough, at least for all practical purposes, especially because the data models that we use are always finitary. If that wasn't the case, all sorts of problems could emerge.

That said, being able to actually give a formal version to every possible (plausible) question is certainly an extremely tall order, technically speaking.

$\endgroup$

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.