Ces dernières années ont vu un intérêt grandissant pour l'interrogation de données en présence d'ontologies ("ontology-mediated query answering", ou OMQA, en anglais), un nouveau 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. Les ontologies ont plusieurs avantages : elles permettent d'enrichir le vocabulaire d'interrogation des données, de relier les vocabulaires de différentes sources de données, et à pallier l'incomplétude des données en permettant l'inférence de nouveaux faits. Par contre, cette expressivité accrue complexifie la tâche de calculer les réponses aux requêtes. Dans ce contexte, la réécriture de requêtes, qui réduit OMQA à la réponse aux requêtes classique (sans ontologies), est une technique algorithmique particulièrement intéressante, car elle permet de bénéficier des bonnes performances et maturité des systèmes de gestion de bases de données.

Dans cet exposé, je commencerai par donner une courte introduction à OMQA, un sujet de recherche très actif à la croisée des domaines de l'intelligence artificielle et des bases de données. Ensuite, je considérerai deux questions naturelles en lien avec la réécriture de requêtes (concernant l'existence et la taille des réécritures) et présenterai des solutions obtenues grâce à des techniques issues de différents champs de l'informatique théorique (complexité de circuits, automates, problèmes de satisfaction de contraintes).