Français Anglais
Accueil Annuaire Plan du site
Accueil > Production scientifique > Résultat majeur
Production scientifique
Résultat majeur : 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
02 avril 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.



Activités de recherche
  ° Ontologies
  ° Logique
  ° Complexité
  ° Raisonnement automatique

Equipe
  ° Intelligence Artificielle et Systèmes d'Inférence

Contact
  [aucun]
Résultats majeurs
BEST PAPER AWARD - HPCS 2019 - ON SERVER-SIDE FILE ACCESS PATTERN MATCHING
17 juillet 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
05 juillet 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 mai 2019
Franco Quezada, Céline Gicquel and Safia Kedad-Sidhoum

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

COMPUTER‐AIDED BIOCHEMICAL PROGRAMMING OF SYNTHETIC MICROREACTORS AS DIAGNOSTIC DEVICES
27 avril 2018
Alexis Courbet, Patrick Amar, Francois Fages, Eric Renard, Franck Molina Mol Syst Biol. (2018) 14: