19
$\begingroup$

It seems to be known that to find an answer to a query $Q$ over a relational database $D$, one needs time $|D|^{|Q|}$, and one cannot get rid of the exponent $|Q|$.

As $D$ can be very large, we wonder why databases work at all in practice.

Is it just a matter of the usual queries not being large at all in the real-world applications? (Then it is interesting to know what the usual size of the queries posed to relational database systems is, and what the "maximal" size of the queries that are expected to be effectively answerable by a DB system in practice is.)

Notes on the exponent $|Q|$ not `removable'

To show that the exponent $|Q|$ is not removable, one can use a query asking whether there exists a clique of size $n$ in the graph given by the database. To check whether a graph has an $n$-clique is an NP-complete problem. Moreover, it is not fixed-parameter tractable, with parameter $n$. Details can be found in, e.g.,
Libkin, L.: Elements Of Finite Model Theory. Springer (2004)
or
Papadimitriou, C.H., Yannakakis, M.: On the complexity of database queries. J. Comput. Syst. Sci. 58(3), 407–427 (1999)

Improve this question
$\endgroup$
10
  • 7
    $\begingroup$ Ordinary queries (like SELECT * FROM users WHERE username="abc" AND passwrod="xyz") are simple searches, which take O(|D|) to run. If there's an index on relevant database fields, it will take O(log |D|). I'm not into databases, but I don't think more complicated queries would take exponential time. $\endgroup$
    – Sadeq Dousti
    Apr 26, 2011 at 9:08
  • 7
    $\begingroup$ @imz: In your example, the complexity is $O(|D|^2)$, which is still polynomial. It seems that, if there are k joins in the query, the complexity is $O(|D|^{k+1})$. This is a polynomial for fixed k, but I think for large k, running the query will be very slow in practice. Hence one must avoid too many joins at all costs. $\endgroup$
    – Sadeq Dousti
    Apr 26, 2011 at 10:53
  • 7
    $\begingroup$ The time complexity is exponential in the length of a query in the worst case. This does not contradict that some long queries are fast. Database practitioners know which queries run fast in typical database engines, and they do not rely on the worst-case bound in terms of the length of the query anyway. $\endgroup$
    – Tsuyoshi Ito
    Apr 26, 2011 at 14:32
  • 2
    $\begingroup$ @Kaveh: "Immerman's Descriptive Complexity book had a small discussion at the last chapter": Very good suggestion. Nitpicking: It is discussed in the penultimate chapter. @imz: You may find the paper Expressive Power of SQL useful, as well. $\endgroup$
    – Sadeq Dousti
    Apr 26, 2011 at 15:16
  • 5
    $\begingroup$ @imz: "Does this graph have an n-clique" is not that common a query in practice. Most queries are more like the ones @Sadeq suggests, and have a strongly tree-like structure. Moreover, for really large databases even a completely linear query is too expensive, and one has to work with a sketch of the database. $\endgroup$
    – András Salamon
    May 1, 2011 at 17:51

5 Answers 5

Reset to default
16
$\begingroup$

There are large classes of queries which are "easy", even in the worst case. In particular, if the class of queries contains conjunctive queries only and each query has bounded width (for instance treewidth, treewidth of its incidence graph, fractional hypertree width, or submodular width) then the query can be answered by using something like a join tree, together with brute force enumeration for the local parts of the query that deviate from the tree. This requires polynomial time, with the degree of the polynomial determined by the width parameter.

It seems that many queries encountered in practice are both conjunctive and have small width. So the polynomial runtime has low degree in this case.

Dániel Marx presented a paper at STOC 2010 on submodular width recently, the full version of which includes a nice summary of the various notions of width and how the CSP formulation relates to the database formalism (the conference version lacks this).

  • Dániel Marx, Tractable hypergraph properties for constraint satisfaction and conjunctive queries, 2010. arxiv:0911.0801

This is not a complete answer, since it does not deal with the "typical" complexity of database queries, but even with worst-case analysis there are easy queries.

Improve this answer
$\endgroup$
0
6
$\begingroup$

One can use queries Q_n to check whether a graph, represented as a database, contains a clique with n elements. To check whether a graph has a clique is an NP-complete problem. Moreover, it is not fixed-parameter tractable, with parameter n (which means D^n).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Please post additional explanations concerning the background of the question either as a "comment" (not an "answer")--with the "Add Comment" button below the question, or as an edit suggestion--with the "edit" link below the question. "Answers" are not for any discussions and additions to the question. (Participating here should be more convenient if you register as a non-anonymous user; then it's easier to track who said what in the discussions.) $\endgroup$
    – imz -- Ivan Zakharyaschev
    Apr 26, 2011 at 17:56
  • $\begingroup$ @imz: He put it as an answer because he doesn't have a privilege to comment. One need to have at least 50 rep. to be able to comment everywhere. $\endgroup$
    – Tomek Tarczynski
    Apr 26, 2011 at 18:36
  • $\begingroup$ @Tomek, @imz, well, it is being discussed on the meta at the moment if we should allow commenting using answers or not. $\endgroup$
    – Kaveh
    May 1, 2011 at 19:19
5
$\begingroup$

Another way of answering this question is, "they don't!"

If you give a typical DBMS implementation a query containing a very large number of joins, it won't even make it past the planning/optimization phase (let alone evaluation), even if the query is acyclic or otherwise has very simple structure such as András alludes to above.

But, for "typical" DBMS workloads, such queries seem not to arise.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ For complex queries the result of optimization phase is randomly chosen plan. This is not as bad as it sounds, because the execution path might still be "good enough", and there are many more reasons why optimization is hard beyond combinatorics of the number of joins. $\endgroup$
    – Tegiri Nenashi
    Feb 6, 2012 at 19:55
4
$\begingroup$

Here's a more reality-concerned version of tigreen's answer from the point of a person who actually makes heavy use of (relational) databases: The whole point and complexity of their application is to structure them in a way they'd require as little amount of joins for each and every ever-needed query as possible and that's why they actually Do Work. In other words do not expect databases to solve complex problems for you on their own - they wouldn't, but if used wisely they are a really handy and applicable instrument.

Improve this answer
$\endgroup$
0
$\begingroup$

Joins are only quadratic over many-to-many relationships. These are relatively rare: in practice, most relationships and joins are 1-to-many, so they will take linear time if indexes/keys are defined. Queries with several many-to-many joins are a serious problem.

Improve this answer
$\endgroup$

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.