Parameterized complexity of completeness reasoning for conjunctive queries

DOI10.1016/J.TCS.2021.02.005MaRDI QIDQ2661762zbMATH OpenOpenAlexFDO

Authors Xianmin Liu, Jianzhong Li, Yingshu Li, Yuqiang Feng

Publication date 8 April 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.02.005

zbMATH Keywords

completeness reasoningconjunctive queriesparameterized complexity

Mathematics Subject Classification ID

Database theory (68P15) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• scientific article; zbMATH DE number 1222098
• A remark on the complexity of consistent conjunctive query answering under primary key violations
• The Complexity of Counting Problems Over Incomplete Databases
• When is the evaluation of conjunctive queries tractable?
• A trichotomy in the complexity of counting answers to conjunctive queries

Cites work

• Algorithms and complexity results for labeled correlation clustering problem
• Equivalences among Relational Expressions
• Fixed-parameter tractability, definability, and model-checking
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• On the complexity of sampling query feedback restricted database repair of functional dependency violations
• On the hardness of labeled correlation clustering problem: a parameterized complexity view
• Parametrized complexity theory.
• The hardness of resilience for nested aggregation query
• The parameterized complexity and kernelization of resilience for database queries
• Tree size reduction with keeping distinguishability

Cited in

(11)

• Complexity of the \(r\)-query tautologies in the presence of a generic oracle
• How hard is completeness reasoning for conjunctive queries?
• Completeness guarantees for incomplete ontology reasoners: theory and practice
• The complexity of acyclic conjunctive queries
• On the convergence of query-bounded computations and logical closure properties of c.e. sets
• Three‐query PCPs with perfect completeness over non‐Boolean domains
• Theory and Applications of Satisfiability Testing
• The resilience of conjunctive queries with inequalities
• How to tell easy from hard: complexities of conjunctive query entailment in extensions of \(\mathcal{ALC}\)
• Enumeration complexity of conjunctive queries with functional dependencies
• Combined-semantics equivalence of conjunctive queries: decidability and tractability results

This page was built for publication: Parameterized complexity of completeness reasoning for conjunctive queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2661762)