Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
From MaRDI portal
Publication:6135781
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.
Cites work
- scientific article; zbMATH DE number 1222814 (Why is no real title available?)
- scientific article; zbMATH DE number 7561482 (Why is no real title available?)
- scientific article; zbMATH DE number 7204563 (Why is no real title available?)
- A negative conjunctive query is easy if and only if it is beta-acyclic
- Answering FO+MOD queries under updates on bounded degree databases
- Answering UCQs under updates and in the presence of integrity constraints
- Approximating fractional hypertree width
- Constant delay enumeration for FO queries over databases with local bounded expansion
- Counting Triangles under Updates in Worst-Case Optimal Time
- Database query processing using finite cursor machines
- Efficient enumeration for conjunctive queries over X-underbar structures
- Enumerating answers to first-order queries over databases of low degree
- Enumeration complexity of conjunctive queries with functional dependencies
- Enumeration complexity of logical query problems with second-order variables
- Enumeration for FO Queries over Nowhere Dense Graphs
- Enumeration of monadic second-order queries on trees
- Enumeration on trees under relabelings
- First-order queries on structures of bounded degree are computable with constant delay
- MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay
- MSO queries on trees: enumerating answers under updates
- On Acyclic Conjunctive Queries and Constant Delay Enumeration
- On the Desirability of Acyclic Database Schemes
- Probabilistic databases
- Size bounds and query plans for relational joins
- Size bounds for factorised representations of query results
- The design of arbitrage-free data pricing schemes
- Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Worst-case optimal join algorithms
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)
