Cover Image

Parameterised Complexity of Consistent Query Answering via Graph Representations

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hankala, Teemu, Hannula, Miika, Mahmood, Yasir, Meier, Arne
Format:	Preprint
Published:	2024
Subjects:	Databases Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Logics with probabilistic team semantics and the Boolean negation
by: Hannula, Miika, et al.
Published: (2023)

Logic and Computation through the Lens of Semirings
by: Barlag, Timon, et al.
Published: (2025)

Diversity of Answers to Conjunctive Queries
by: Merkl, Timo Camillo, et al.
Published: (2023)

Lower Bounds for Conjunctive Query Evaluation
by: Mengel, Stefan
Published: (2025)

Towards Parameterized Hardness on Maintaining Conjunctive Queries
by: Wang, Qichen
Published: (2026)

Tight Fine-Grained Bounds for Direct Access on Join Queries
by: Bringmann, Karl, et al.
Published: (2022)

Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
by: Khamis, Mahmoud Abo, et al.
Published: (2026)

Aspects of Coherence in Dependence Logic
by: Barlag, Timon, et al.
Published: (2026)

The Complexity of Finding Missing Answer Repairs
by: Comer, Jesse, et al.
Published: (2026)

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
by: Focke, Jacob, et al.
Published: (2021)

Rejection in Abstract Argumentation: Harder Than Acceptance?
by: Fichte, Johannes K., et al.
Published: (2024)

Consistent Query Answering over SHACL Constraints
by: Ahmetaj, Shqiponja, et al.
Published: (2024)

Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
by: Aivasiliotis, Panagiotis, et al.
Published: (2025)

Dichotomy for Axiomatising Inclusion Dependencies on K-Databases
by: Hannula, Miika, et al.
Published: (2026)

Fine-Grained Complexity of Regular Path Queries
by: Casel, Katrin, et al.
Published: (2021)

Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases
by: Karmakar, Pratik, et al.
Published: (2024)

Parameterised Holant Problems
by: Aivasiliotis, Panagiotis, et al.
Published: (2024)

PFCS: Prime Factorization Cache System for Deterministic Data Relationship Discovery
by: Le, Duy
Published: (2025)

Circuits and Formulas for Datalog over Semirings
by: Fan, Austen Z., et al.
Published: (2025)

Logical Approaches to Non-deterministic Polynomial Time over Semirings
by: Barlag, Timon, et al.
Published: (2025)

The Complexity of Resilience for Digraph Queries
by: Bodirsky, Manuel, et al.
Published: (2026)

Fast Matrix Multiplication meets the Submodular Width
by: Abo-Khamis, Mahmoud, et al.
Published: (2024)

FPT Parameterisations of Fractional and Generalised Hypertree Width
by: Lanzinger, Matthias, et al.
Published: (2025)

Parameterised distance to local irregularity
by: Fioravantes, Foivos, et al.
Published: (2023)

Independence Under Incomplete Information
by: Hannula, Miika, et al.
Published: (2025)

Query Complexity with Unknowns
by: Mande, Nikhil S., et al.
Published: (2024)

A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
by: Pilipczuk, Michał, et al.
Published: (2025)

A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join
by: Padmanabha, Anantha, et al.
Published: (2023)

A SUBSET-SUM Characterisation of the A-Hierarchy
by: Gutleben, Jan, et al.
Published: (2024)

When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames
by: Krebs, Andreas, et al.
Published: (2025)

Sensitivity and Query Complexity under Uncertainty
by: Benson, Deepu, et al.
Published: (2025)

Space Efficient Algorithms for Parameterised Problems
by: Akhtar, Sheikh Shakil, et al.
Published: (2025)

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
by: MIT Hardness Group, et al.
Published: (2024)

Locally Consistent K-relations: Entailment and Axioms of Functional Dependence
by: Barlag, Timon, et al.
Published: (2025)

Learning Tree Pattern Transformations
by: Neider, Daniel, et al.
Published: (2024)

Matching walks that are minimal with respect to edge inclusion
by: Marsault, Victor
Published: (2024)

From Time to Space: The Impact of Linearity in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2026)

The Power of Negation in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2025)

A Simple Algorithm for Consistent Query Answering under Primary Keys
by: Figueira, Diego, et al.
Published: (2023)

The Query Complexity of Local Search in Rounds on General Graphs
by: Brânzei, Simina, et al.
Published: (2026)