๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The complexity of evaluating relational queries

โœ Scribed by Stavros S. Cosmadakis

Book ID
114037678
Publisher
Elsevier Science
Year
1983
Weight
568 KB
Volume
58
Category
Article
ISSN
0019-9958

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

On the Complexity of Database Queries
On the Complexity of Database Queries
โœ Christos H. Papadimitriou; Mihalis Yannakakis ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 223 KB

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 queri

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