Answering FO+MOD queries under updates on bounded degree databases

DOI10.4230/LIPICS.ICDT.2017.8zbMATH Open1402.68041arXiv1702.08764MaRDI QIDQ3174897FDOQ3174897

Christoph Berkholz, Jens Keppeler, Nicole Schweikardt

Publication date: 18 July 2018

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

Recommendations

• Answering FO+MOD queries under updates on bounded degree databases
• Answering UCQs under updates and in the presence of integrity constraints
• First-order logic with counting: at least, \textit{weak} Hanf normal forms always exist and can be computed!
• First-order queries on structures of bounded degree are computable with constant delay
• Constant delay enumeration for FO queries over databases with local bounded expansion

zbMATH Keywords

counting problemdynamic databasesHanf localityfirst-order logic with modulo-counting quantifiersquery enumeration

Mathematics Subject Classification ID

Data structures (68P05) Database theory (68P15) Logic in computer science (03B70)

Cited In (11)

• Counting Triangles under Updates in Worst-Case Optimal Time
• Title not available (Why is that?)
• Title not available (Why is that?)
• Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
• Title not available (Why is that?)
• General space-time tradeoffs via relational queries
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• Enumeration complexity of conjunctive queries with functional dependencies
• Hardness self-amplification: simplified, optimized, and unified
• Range updates and range sum queries on multidimensional points with monoid weights
• Intersection joins under updates

This page was built for publication: Answering FO+MOD queries under updates on bounded degree databases

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