Français Anglais
Accueil Annuaire Plan du site
Home > Research results > Research highlights
Research results
Research highlight : ON THE COMPLEXITY OF CONSISTENT QUERY ANSWERING IN THE PRESENCE OF SIMPLE ONTOLOGIES
ON THE COMPLEXITY OF CONSISTENT QUERY ANSWERING IN THE PRESENCE OF SIMPLE ONTOLOGIES
2 April 2012

Meghyn Bienvenu, in Twenty-Sixth Conference on Artificial Intelligence (AAAI)
Consistent query answering is a standard approach for producing meaningful query answers when data is inconsistent.
Recent work on consistent query answering in the presence of ontologies has shown this problem to be intractable in data complexity even for ontologies expressed in lightweight description logics. In order to better understand the source of this intractability, we investigate the complexity of consistent query answering for simple ontologies consisting only of class subsumption and class disjointness axioms. We show that for conjunctive queries with at most one quantified variable,
the problem is first-order expressible; for queries with at most two quantified variables, the problem has polynomial data complexity but may not be first-order expressible; and for three quantified variables, the problem may become
coNP-hard in data complexity. For queries having at most two quantified variables, we further identify a necessary and sufficient condition for first-order expressibility. In order to be able to handle arbitary conjunctive queries, we propose a novel inconsistency-tolerant semantics and show that
under this semantics, first-order expressibility is always guaranteed. We conclude by extending our positive results to
DL-Lite ontologies without inverse.



Keyword
  ° Ontologies
  ° Logic
  ° Complexity
  ° Automated reasoning

Group
  ° Artificial Intelligence and Inference Systems

Contact
  [none]
Research highlights
BEST STUDENT PAPER AWARD (ML) AT ECML 2019
20 September 2019
Guillaume Doquet (A&O) received the Best Student Paper Award (category Machine Learning) at ECML 201

BEST PAPER AWARD - HPCS 2019 - ON SERVER-SIDE FILE ACCESS PATTERN MATCHING
17 July 2019
Francieli Zanon Boito¹ , Ramon Nou², Laércio Lima Pilla³, Jean Luca Bez⁴, Jean-François Méhaut¹, T

BEST FULL PAPER AWARD EDM 2019 - EDUCATIONAL DATA MINING
5 July 2019
DAS3H: Modeling Student Learning and Forgetting for Optimally Scheduling Distributed Practice of Ski

BEST PAPER AWARD - CODIT2019 - STOCHASTIC DUAL DYNAMIC INTEGER PROGRAMMING FOR A MULTI-ECHELON LOT-SIZING PROBLEM WITH REMANUFACTURING AND LOST SALES
14 May 2019
Franco Quezada, Céline Gicquel and Safia Kedad-Sidhoum

BEST PAPER AWARD ICONS 2019: RESONANCE THINKING AND INDUCTIVE MACHINE LEARNING
6 May 2019
Yves Kodratoff & Marta Franova