𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Complexity of Database Queries

✍ Scribed by Christos H. Papadimitriou; Mihalis Yannakakis

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
223 KB
Volume
58
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We revisit the issue of the complexity of database queries, in the light of the recent parametric refinement of complexity theory. We show that, if the query size (or the number of variables in the query) is considered as a parameter, then the relational calculus and its fragments (conjunctive queries, positive queries) are classified at appropriate levels of the so-called W hierarchy of Downey and Fellows. These results strongly suggest that the query size is inherently in the exponent of the data complexity of any query evaluation algorithm, with the implication becoming stronger as the expressibility of the query language increases. On the positive side, we show that this exponential dependence can be avoided for the extension of acyclic queries with { (but not < ) inequalities.

πŸ“œ SIMILAR VOLUMES

On database queries involving competitiv
On database queries involving competitive conditional preferences
✍ P. Bosc; A. Hadjali; O. Pivert πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 177 KB

This paper introduces a new type of database queries involving preferences. The idea is to consider competitive conditional preference clauses structured as a tree, of the type "preferably P 1 or β€’ β€’ β€’ or P n ; if P 1 then preferably P 1,1 or . . .; if P 2 then preferably P 2,1 or . . . ," where the

Inherent Complexity of Recursive Queries
Inherent Complexity of Recursive Queries
✍ Stavros Cosmadakis πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 223 KB

We give lower bounds on the complexity of certain Datalog queries. Our notion of complexity applies to compile-time optimization techniques for Datalog; thus, our results indicate limitations of these techniques. The main new tool is linear first-order formulas, whose depth (respectively, number of

On the Exact Worst Case Query Complexity
On the Exact Worst Case Query Complexity of Planar Point Location
✍ Raimund Seidel; Udo Adamy πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 241 KB

What is the smallest constant c so that the planar point location queries can be Ž . Ž . answered in c log n q o log n steps i.e., point᎐line comparisons in the worst 2 Ž case? M. T. Goodrich, M. Orletsky, and K. Ramaiyer 1997, in ''Proc 8th ACM-Ž . . SIAM Symp on Discrete Algorithms SODA ,'' pp. 75