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)?