The parameterized complexity and kernelization of resilience for database queries

DOI10.1016/J.TCS.2020.08.018MaRDI QIDQ2202009zbMATH OpenOpenAlexFDO

Authors Dongjing Miao, Jianzhong Li, Zhipeng Cai

Publication date 17 September 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2020.08.018

zbMATH Keywords

conjunctive queryparameterized complexityresilience

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• On the complexity of resilience for aggregation queries
• The hardness of resilience for nested aggregation query
• scientific article; zbMATH DE number 1222098
• scientific article; zbMATH DE number 1424025
• On the complexity of database queries

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2243367 (Why is no real title available?)
• Complexity results for structure-based causality.
• On generating triangle-free graphs
• On the complexity of sampling query feedback restricted database repair of functional dependency violations
• On the correct translation of update operations on relational views
• Update semantics of relational views
• Updates of Relational Views

Cited in

(7)

• On the complexity of resilience for aggregation queries
• Parameterized resiliency problems
• Parameterized complexity of completeness reasoning for conjunctive queries
• The hardness of resilience for nested aggregation query
• Some aspects of the database resilience
• The resilience of conjunctive queries with inequalities
• Parameterized resiliency problems via integer linear programming

This page was built for publication: The parameterized complexity and kernelization of resilience for database queries

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