Database query languages for efficient queries It seems that in popular query languages for relational databases, it is possible to create queries that will require a lot of resources to answer. In practice, database admins manage this by limiting the amount of memory per query, and checking for any long-running queries if there is a slowdown in the database. This seems rather ad-hoc, is there a TCS solution to this?


  Are there query languages that can
  only implement efficient queries?


If there are no such languages, is there a theoretical reason for this?

Some reasons why I might expect these sort of things to exist or atleast make sense:


we have programming languages that are specifically designed to only implement efficient computations (usually by having some restrictive logic in their type system) 
popular query languages (such as SQL) are already inspired by logic, so it does not seem as a stretch for database users to consider more restrictive logics.
a non-malicious database user already tries to prepare queries that execute quickly, so we should expect these more restrictive query languages to only hamper malicious users. 




This question is inspired by the intersection of two previous questions:

Programming languages for efficient computation

Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?
One way of looking at database query languages is through the lens of deductive databases, where queries are represented as logic programs. In this setting, the most relevant work related to your question is McAllester's On the complexity analysis of static analyses, which observed that you can reason about the running time of a query by reasoning about the number of "prefix firings" in the rules of your program. What a "prefix firing" is isn't terribly complicated, but I'll refer you to the paper for that.

In the functional programming world, this sort of thing is called a cost semantics: it doesn't mean you can only implement efficient queries (programs), but it means that you can reason about the asymptotic complexity of your declarative program in a reasonable way.

Some later work on implementations of McAllester's ideas include From datalog rules to efficient programs with time and space guarantees (Liu and Stoller) and Dedalus: Datalog in Time and Space (Alvaro, Marczak, Conway, Hellerstein, Maier, and Sears). I admit I haven't yet read the latter of those two papers, however.