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) Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Review text

In this paper, the authors examine the complexity of the resilience decision problem by means of parameterized complexity. It is observed that a triangle query is fixed parameter tractable if the data has the planarity property with respect to the triangle query.

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

• Complexity results for structure-based causality.
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2243367 (Why is no real title available?)
• 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)

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

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)