<p>One way of looking at database query languages is through the lens of <em>deductive databases</em>, where queries are represented as logic programs. In this setting, the most relevant work related to your question is McAllester's <a href="http://portal.acm.org/citation.cfm?id=581774">On the complexity analysis of static analyses</a>, 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.</p>

<p>In the functional programming world, this sort of thing is called a <em>cost semantics</em>: 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.</p>

<p>Some later work on implementations of McAllester's ideas include <a href="http://portal.acm.org/citation.cfm?id=1552311">From datalog rules to efficient programs with time and space guarantees</a> (Liu and Stoller) and <a href="http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-173.html">Dedalus: Datalog in Time and Space</a> (Alvaro, Marczak, Conway, Hellerstein, Maier, and Sears). I admit I haven't yet read the latter of those two papers, however.</p>

CC BY-SA 3.0
2011-05-02T13:19:58.537Z
2011-05-02T13:19:58.537Z
Rob Simmons
<p>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 <a href="https://stackoverflow.com/questions/4968077/are-there-way-to-controll-the-memory-usage-per-user-in-mysql-myisam/4968144#4968144">memory per query</a>, 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?</p>

<blockquote>
  <p>Are there query languages that can
  only implement efficient queries?</p>
</blockquote>

<p>If there are no such languages, is there a theoretical reason for this?</p>

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

<ul>
<li>we have programming languages that are specifically designed to only implement efficient computations (usually by having some restrictive logic in their type system) </li>
<li>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.</li>
<li>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. </li>
</ul>

<hr>

<p>This question is inspired by the intersection of two previous questions:</p>

<p><a href="https://cstheory.stackexchange.com/questions/5120/programming-languages-for-efficient-computation">Programming languages for efficient computation</a></p>

<p><a href="https://cstheory.stackexchange.com/questions/6255/why-do-relational-databases-work-at-all-given-the-theoretical-exponential-comple">Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?</a></p>

CC BY-SA 3.0
2011-05-02T21:45:06.287Z
Isn't this exactly the topic of Descriptive Complexity? they have language characterizations of queries for various complexity classes.
Kaveh
CC BY-SA 3.0
2011-05-03T04:40:54.833Z
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.
Artem Kaznatcheev
CC BY-SA 3.0
2011-05-03T14:04:59.223Z
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.
Marc Hamann
CC BY-SA 3.0
2011-05-06T15:01:07.673Z
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!
Artem Kaznatcheev
<cc.complexity-theory><pl.programming-languages><db.databases><finite-model-theory>
Database query languages for efficient queries
Artem Kaznatcheev
# Database query languages for efficient queries

(Asked by: username_0 on 2011-05-02)

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](https://stackoverflow.com/questions/4968077/are-there-way-to-controll-the-memory-usage-per-user-in-mysql-myisam/4968144#4968144), 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](https://cstheory.stackexchange.com/questions/5120/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)?](https://cstheory.stackexchange.com/questions/6255/why-do-relational-databases-work-at-all-given-the-theoretical-exponential-comple)

**Tags:** cc.complexity-theory, pl.programming-languages, db.databases, finite-model-theory
> **Comments:**
> **username_1**: Isn't this exactly the topic of Descriptive Complexity? they have language characterizations of queries for various complexity classes.  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: 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!  

---

## 1 answers

### Answer by username_3 on 2011-05-02. Score: 7 | Accepted answer

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](http://portal.acm.org/citation.cfm?id=581774), 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](http://portal.acm.org/citation.cfm?id=1552311) (Liu and Stoller) and [Dedalus: Datalog in Time and Space](http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-173.html) (Alvaro, Marczak, Conway, Hellerstein, Maier, and Sears). I admit I haven't yet read the latter of those two papers, however.


---

