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 complexityfirst-order logicenumeration problems

Mathematics Subject Classification ID

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

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

(28)

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

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)