The complexity of reverse engineering problems for conjunctive queries

DOI10.4230/LIPICS.ICDT.2017.7zbMATH Open1402.68040arXiv1606.01206MaRDI QIDQ3174895FDOQ3174895

Authors: Pablo Barceló, Miguel Romero 

Publication date: 18 July 2018

Full work available at URL: https://arxiv.org/abs/1606.01206

Recommendations

• The Complexity of Conjunctive Query Answering in Expressive Description Logics
• A more general theory of static approximations for conjunctive queries
• A trichotomy in the complexity of counting answers to conjunctive queries
• When is the evaluation of conjunctive queries tractable?
• A more general theory of static approximations for conjunctive queries

zbMATH Keywords

treewidthconjunctive queriesdefinabilityreverse engineeringcomplexity of pebble gamesquery by example

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)

Cited In (4)

• A logic-based framework for characterizing nexus of similarity within knowledge bases
• The complexity of acyclic conjunctive queries
• Regularizing conjunctive features for classification
• Logical separability of labeled data examples under ontologies

This page was built for publication: The complexity of reverse engineering problems for conjunctive queries

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