@inproceedings{a10f3eefaacb4080b3dcbb69116045f8,
title = "Parameterized Complexity of Resilience Decision for Database Debugging",
abstract = "Resilience decision problem plays a fundamental and important role in database debugging, query explanation and error tracing. Resilience decision problem is defined on a database d, given a boolean query q which is true initially, and a constant k>0, it is to decide if there is a fact set res of size no more than k such that query q becomes false after deleting all facts in res. Previous results showed it is NP-hard in many cases. However, we revisit this decision problem, in the light of the recent parametric refinement of complexity theory, provide some new results including negative and positive ones. We show that, there are still some cases intractable if only consider the query size or variable numbers as the parameter.",
keywords = "Database, Parameterized complexity, Resilience",
author = "Dongjing Miao and Zhipeng Cai",
note = "Publisher Copyright: {\textcopyright} 2017, Springer International Publishing AG.; 19th International Conference on Formal Engineering Methods, ICFEM 2017 ; Conference date: 13-11-2017 Through 17-11-2017",
year = "2017",
doi = "10.1007/978-3-319-68690-5\_20",
language = "英语",
isbn = "9783319686899",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "332--344",
editor = "Zhenhua Duan and Luke Ong",
booktitle = "Formal Methods and Software Engineering - 19th International Conference on Formal Engineering Methods, ICFEM 2017, Proceedings",
address = "德国",
}