9
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Isn't this exactly the topic of Descriptive Complexity? they have language characterizations of queries for various complexity classes. $\endgroup$
    – Kaveh
    May 2, 2011 at 21:45
  • $\begingroup$ Descriptive complexity is definitely a huge part and guide for programming languages for efficient computation. But I don't think it's as simple as saying "descriptive complexity uses logic" and "queries to databases use logic". In particular, for DC it seems that the query size is fixed and the 'n' comes from the sizes of finite structures those queries accept. In databases, it is really the query size that is variable and the database is also variable or maybe a fixed parameter. $\endgroup$
    – Artem Kaznatcheev ♦
    May 3, 2011 at 4:40
  • 3
    $\begingroup$ there are also results for variable queries, they just aren't quite as astounding as the match between model-checking and well-known complexity classes. Also the wider field of finite model theory, of which descriptive complexity is a part, has a number of expressibility results directly related to databases. Databases are after all almost exactly finite model-theoretic structures. $\endgroup$
    – Marc Hamann
    May 3, 2011 at 14:04
  • 1
    $\begingroup$ I did not think about this correspondence. I added the finite model-theory tag. If you or @Kaveh want to elaborate on your comments and know of how to adopt specific results from descriptive complexity of finite model-theory in general to produce such query languages, then I would really like to see that answer! $\endgroup$
    – Artem Kaznatcheev ♦
    May 6, 2011 at 15:01

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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