Meghyn Bienvenu et ses co-auteurs, Balder ten Cate, Carsten Lutz, et Frank Wolter, ont reçu le prix «Albert O. Mendelzon Test of Time Award» pour l'impact de leur article publié il y a 10 ans à la conférence PODS'13 : "Ontology-based data access: A study through disjunctive datalog, CSP, and MMSNP".
L'accès aux données médiatisé par des ontologies est un récent paradigme en gestion de données qui vise à exploiter des connaissances sémantiques décrites par une ontologie afin d'améliorer la réponse aux requêtes. Une notion centrale dans ce contexte est celle d'un "ontology-mediated query" (OMQ), qui est une requête de base de données couplée à une ontologie. Dans cet article, nous étudions plusieurs classes d'OMQs qui combinent les requêtes conjonctives avec les ontologies formulées dans des logiques de description ou d'autres fragments pertinents de la logique du premier ordre. Les contributions de cet article sont triples. Premièrement, nous caractérisons le pouvoir expressif des OMQs en termes de fragments de datalog disjonctif. Deuxièmement, nous établissons des liens étroits entre les OMQs et les problèmes de satisfaction de contraintes (CSP) et leur généralisation logique, les formules MMSNP. Troisièmement, nous exploitons ces connexions pour obtenir de nouveaux résultats concernant (i) l'existence de réécritures en logique du premier ordre ou datalog, (ii) les dichotomies P/NP pour l'évaluation d'OMQs, et (iii) le problème d'inclusion de requêtes pour des OMQs.
Consulter l’article, ici.