Parameterised Complexity of Consistent Query Answering via Graph Representations
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909424648454144 |
|---|---|
| author | Hankala, Teemu Hannula, Miika Mahmood, Yasir Meier, Arne |
| author_facet | Hankala, Teemu Hannula, Miika Mahmood, Yasir Meier, Arne |
| contents | We study consistent query answering via different graph representations. First, we introduce solution-conflict hypergraphs in which nodes represent facts and edges represent either conflicts or query solutions. Considering a monotonic query and a set of antimonotonic constraints, we present an explicit algorithm for counting the number of repairs satisfying the query based on a tree decomposition of the solution-conflict hypergraph. The algorithm not only provides fixed-parameter tractability results for data complexity over expressive query and constraint classes, but also introduces a novel and potentially implementable approach to repair counting. Second, we consider the Gaifman graphs arising from MSO descriptions of consistent query answering. Using a generalization of Courcelle's theorem, we then present fixed-parameter tractability results for combined complexity over expressive query and constraint classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_08324 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parameterised Complexity of Consistent Query Answering via Graph Representations Hankala, Teemu Hannula, Miika Mahmood, Yasir Meier, Arne Databases Computational Complexity We study consistent query answering via different graph representations. First, we introduce solution-conflict hypergraphs in which nodes represent facts and edges represent either conflicts or query solutions. Considering a monotonic query and a set of antimonotonic constraints, we present an explicit algorithm for counting the number of repairs satisfying the query based on a tree decomposition of the solution-conflict hypergraph. The algorithm not only provides fixed-parameter tractability results for data complexity over expressive query and constraint classes, but also introduces a novel and potentially implementable approach to repair counting. Second, we consider the Gaifman graphs arising from MSO descriptions of consistent query answering. Using a generalization of Courcelle's theorem, we then present fixed-parameter tractability results for combined complexity over expressive query and constraint classes. |
| title | Parameterised Complexity of Consistent Query Answering via Graph Representations |
| topic | Databases Computational Complexity |
| url | https://arxiv.org/abs/2412.08324 |