Some Aspects of the Database Resilience

Authors :: Ana Teresa Martins
Luis Henrique Bustamante
Source :: Theoretical Aspects of Computing – ICTAC 2021 ISBN: 9783030853143, ICTAC
Publication Year :: 2021
Publisher :: Springer International Publishing, 2021.
Abstract: The resilience problem for a Boolean query in a database is the task of finding a minimum set of tuples that, when deleted from the database, turns the query evaluation false. We examine the parameterized complexity of a particular version of this problem for fixed queries. A natural parameter for this problem is the number of tuples needed to be deleted. For this, we use a formal characterization of the solution set that proves the W[1] membership for this parameter and a fixed-parameter tractable result when considering the database treewidth.

Subjects :: Database
Computer science
Solution set
InformationSystems_DATABASEMANAGEMENT
Parameterized complexity
computer.software_genre
Set (abstract data type)
Treewidth
Conjunctive query
Tuple
Resilience (network)
computer
Computer Science::Databases
Boolean conjunctive query

ISBN :: 978-3-030-85314-3
ISBNs :: 9783030853143
Database :: OpenAIRE
Journal :: Theoretical Aspects of Computing – ICTAC 2021 ISBN: 9783030853143, ICTAC
Accession number :: edsair.doi...........bc6d44d2b9af7e367a4deeca15439184
Full Text :: https://doi.org/10.1007/978-3-030-85315-0_3