First-order queries on structures of bounded degree are computable with constant delay

DOI10.1145/1276920.1276923MaRDI QIDQ5277786zbMATH OpenOpenAlexFDO

Authors Arnaud Durand, Etienne Grandjean

Publication date 12 July 2017

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0507020

zbMATH Keywords

computational complexityenumeration problemsfirst-order logic

Mathematics Subject Classification ID

Logic in computer science (03B70) Quantifier elimination, model completeness, and related topics (03C10) Complexity of computation (including implicit computational complexity) (03D15) Database theory (68P15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Abstract: A bounded degree structure is either a relational structure all of whose relations are of bounded degree or a functional structure involving bijective functions only. In this paper, we revisit the complexity of the evaluation problem of not necessarily Boolean first-order queries over structures of bounded degree. Query evaluation is considered here as a dynamical process. We prove that any query on bounded degree structures is $constantdelaylin$, i.e., can be computed by an algorithm that has two separate parts: it has a precomputation step of linear time in the size of the structure and then, it outputs all tuples one by one with a constant (i.e. depending on the size of the formula only) delay between each. Seen as a global process, this implies that queries on bounded structures can be evaluated in total time $O(f(|phi|).(|calS|+|phi(calS)|))$ and space $O(f(|phi|).|calS|)$ where $calS$ is the structure, $phi$ is the formula, $phi(calS)$ is the result of the query and $f$ is some function. Among other things, our results generalize a result of cite{Seese-96} on the data complexity of the model-checking problem for bounded degree structures. Besides, the originality of our approach compared to that cite{Seese-96} and comparable results is that it does not rely on the Hanf's model-theoretic technic (see cite{Hanf-65}) and is completely effective.

Recommendations

• First-order queries on classes of structures with bounded expansion
• First-Order Queries on Finite Structures Over the Reals
• MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• First-order queries on databases embedded in an infinite structure
• Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
• Bounded queries, approximations, and the Boolean hierarchy
• The tractability frontier of graph-like first-order query sets
• The tractability frontier of graph-like first-order query sets
• On the Structure of Bounded Queries to Arbitrary NP Sets

Cited in

(31)

• Structural tractability of enumerating CSP solutions
• A logical approach to locality in pictures languages
• Answering FO+MOD queries under updates on bounded degree databases
• Constant delay enumeration for FO queries over databases with local bounded expansion
• Enumeration on trees under relabelings
• Efficient First-Order Model-Checking Using Short Labels
• Computing thejth solution of a first-order query
• On enumerating monomials and other combinatorial structures by polynomial interpolation
• An optimal construction of Hanf sentences
• First-order interpretations of bounded expansion classes
• Answering FO+MOD queries under updates on bounded degree databases
• Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width
• Enumerating answers to first-order queries over databases of low degree
• First-order queries on classes of structures with bounded expansion
• Enumeration for FO Queries over Nowhere Dense Graphs
• Faster Property Testers in a Variation of the Bounded Degree Model
• Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
• Compact labelings for efficient first-order model-checking
• Faster property testers in a variation of the bounded degree model
• Enumeration and updates for conjunctive linear algebra queries through expressibility
• Enumeration classes defined by circuits
• Ranked enumeration for MSO on trees via knowledge compilation
• Enumeration and updates for conjunctive linear algebra queries through expressibility
• Listing 4-cycles
• Conjunctive queries with free access patterns under updates
• Constant-delay enumeration for SLP-compressed documents
• Tractable conjunctive queries over static and dynamic relations
• FO-query enumeration over SLP-compressed structures of bounded degree
• From amortized to worst case delay in enumeration algorithms
• Tree inclusions in windows and slices
• Linear delay enumeration and monadic second-order logic

This page was built for publication: First-order queries on structures of bounded degree are computable with constant delay

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5277786)