Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
From MaRDI portal
Publication:6135781
DOI10.46298/LMCS-19(3:11)2023arXiv1907.01988MaRDI QIDQ6135781FDOQ6135781
Authors: Ahmet Kara, Miloš Nikolić, Dan Olteanu, Haozhe Zhang 
Publication date: 26 August 2023
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Abstract: We investigate trade-offs in static and dynamic evaluation of hierarchical queries with arbitrary free variables. In the static setting, the trade-off is between the time to partially compute the query result and the delay needed to enumerate its tuples. In the dynamic setting, we additionally consider the time needed to update the query result under single-tuple inserts or deletes to the database. Our approach observes the degree of values in the database and uses different computation and maintenance strategies for high-degree (heavy) and low-degree (light) values. For the latter it partially computes the result, while for the former it computes enough information to allow for on-the-fly enumeration. We define the preprocessing time, the update time, and the enumeration delay as functions of the light/heavy threshold. By appropriately choosing this threshold, our approach recovers a number of prior results when restricted to hierarchical queries. We show that for a restricted class of hierarchical queries, our approach achieves worst-case optimal update time and enumeration delay conditioned on the Online Matrix-Vector Multiplication Conjecture.
Full work available at URL: https://arxiv.org/abs/1907.01988
Cites Work
- Size bounds and query plans for relational joins
- Approximating fractional hypertree width
- On Acyclic Conjunctive Queries and Constant Delay Enumeration
- Title not available (Why is that?)
- On the Desirability of Acyclic Database Schemes
- First-order queries on structures of bounded degree are computable with constant delay
- Probabilistic databases
- Enumeration complexity of logical query problems with second-order variables
- Enumeration on trees under relabelings
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Answering FO+MOD queries under updates on bounded degree databases
- Constant delay enumeration for FO queries over databases with local bounded expansion
- Enumeration complexity of conjunctive queries with functional dependencies
- Worst-case optimal join algorithms
- Enumeration of monadic second-order queries on trees
- MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay
- Enumerating answers to first-order queries over databases of low degree
- Title not available (Why is that?)
- The design of arbitrage-free data pricing schemes
- Size bounds for factorised representations of query results
- MSO queries on trees: enumerating answers under updates
- Title not available (Why is that?)
- A negative conjunctive query is easy if and only if it is beta-acyclic
- Database query processing using finite cursor machines
- Answering UCQs under updates and in the presence of integrity constraints
- Efficient enumeration for conjunctive queries over X-underbar structures
- Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
- Counting Triangles under Updates in Worst-Case Optimal Time
- Enumeration for FO Queries over Nowhere Dense Graphs
Cited In (4)
This page was built for publication: Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135781)
