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

Inherent Complexity of Recursive Queries

โœ Scribed by Stavros Cosmadakis

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

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 variables) matches the sequential (respectively, parallel) complexity of Datalog programs. We define a combinatorial game (a variant of Ehrenfeucht-Fraรฏssรฉ games) that can be used to prove nonexpressibility by linear formulas. We thus obtain lower bounds for the sequential and parallel complexity of Datalog queries. We prove syntactically tight versions of our results, by exploiting uniformity and invariance properties of Datalog queries.

๐Ÿ“œ 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

Recursive complexity of the Carnap first
Recursive complexity of the Carnap first order modal logic C
โœ Amรฉlie Gheerbrant; Marcin Mostowski ๐Ÿ“‚ Article ๐Ÿ“… 2006 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 134 KB

We consider first order modal logic C firstly defined by Carnap in "Meaning and Necessity" [1]. We prove elimination of nested modalities for this logic, which gives additionally the Skolem-Lรถwenheim theorem for C. We also evaluate the degree of unsolvability for C, by showing that it is exactly 0 .

Inherent Complexities of Trace Detection
Inherent Complexities of Trace Detection by Surface-Enhanced Raman Scattering
โœ Nicholas P. W. Pieczonka; Ricardo F. Aroca ๐Ÿ“‚ Article ๐Ÿ“… 2005 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 443 KB

## Abstract __Surfaceโ€enhanced Raman scattering (SERS) and surfaceโ€enhanced resonance Raman scattering (SERRS) are powerful optical scattering techniques used in such frontier areas of research as ultrasensitive chemical analysis, the characterization of nanostructures, and the detection of single

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