Algorithmique robuste pour l’interrogation de données en présence d’ontologie – PAGODA

To address the first challenge (scalability), we will study how different alternative query answering approaches may be fruitfully combined in order to obtain novel querying algorithms with better properties. In particular, we will explore approaches which incorporate both query rewriting (backward-chaining) and saturation (forward-chaining). A detailed complexity analysis will help determine for a given setting, which (combination of) algorithms are most appropriate, subject to the constraints of the application. Finally, we will investigate different possible optimizations of OBDA query answering algorithms.

With regards to the second challenge, two complementary approaches to inconsistency-handling will be explored. The first consists in repairing the data in order to restore coherence, while the second adopts an alternative semantics for query answering which allows meaningful answers to be obtained despite the inconsistencies. For the first approach, our aim is to provide appropriate tools for helping the user identify the correct repair. For the second approach, the main difficulty is to find querying algorithms for the alternative semantics with good computational behavior, either by identifying tractable sub-cases, or by proposing generic algorithms which perform well on typical instances.

The expected results of our foundational research will be essentially of two types:

-- novel algorithms and optimizations for OBDA query answering and for handling inconsistencies in an OBDA setting

-- fine-grained complexity results which provide a clearer understanding of what makes OBDA reasoning problems easy or hard and which algorithms are most appropriate for a given problem

The dissemination of our results will mainly take the form of publications in first-rank conferences. We target the main artificial intelligence conferences (IJCAI, AAAI, ECAI) and the top specialized conference KR. When appropriate, we may also publish our work in prestigious conferences in related fields, like database theory (PODS, ICDT) or semantic web (ISWC), in order to communicate our results to a larger scientific public.

The applied component of the project will produce:

-- an implementation and experimentation of a toolkit for the query answering algorithms designed in the project;

-- a case study which will examine the utility of OBDA techniques in an anatomy application.

Ontology-based data access is widely acknowledged as an important topic, and there will undoubtedly be many interesting ways of continuing PAGODA beyond the project's four-year duration. However, it is impossible at this early stage to predict which avenues of research will be the most promising, as this will depend not only on the progress made within the project, but also on the development of ontology-based data access at an international level.

Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter:
Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP.
Proceedings of the 32nd International Conference on the Principles of Database Systems (PODS'13).

Meghyn Bienvenu, Carsten Lutz, and Frank Wolter:
First Order-Rewritability of Atomic Queries in Horn Description Logics
To appear in Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13).

Meghyn Bienvenu, Magdalena Ortiz, and Mantas Simkus:
Conjunctive Regular Path Queries in Lightweight Description Logics
To appear in Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13).

Meghyn Bienvenu, Magdalena Ortiz, Mantas Simkus, and Guohui Xiao:
Tractable Queries for Lightweight Description Logics
To appear in Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13).

Meghyn Bienvenu and Riccardo Rosati:
Tractable Approximations of Consistent Query Answering for Robust Ontology-based Data Access
To appear in Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13).

Michaël Thomazo:
Compact Rewritings for Existential Rules
To appear in Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13).

Mélanie König, Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo:
On the Exploration of the Query Rewriting Space with Existential Rules
To appear in Proceedings of the 7th International Conference on Web Reasoning and Rule Systems (RR'13).

L’interrogation de données en présence d’ontologie (“ontology-based data access” en anglais) est un nouveau paradigme dans la gestion de données qui vise à exploiter des connaissances sémantiques décrites par une ontologie afin d’améliorer les réponses aux requêtes. Cette approche a de nombreuses applications potentielles. Par exemple, elle pourrait révolutionner la gestion des données dans le secteur de la santé en permettant l'interrogation sémantique des données des patients ; elle est aussi susceptible d’avoir un impact majeur dans les sciences de la vie en facilitant l'échange de données expérimentales entre chercheurs. Plus généralement, cette approche est pertinente pour quasiment toutes les applications qui reposent actuellement sur des bases de données relationnelles, comme par exemple les systèmes d'information d'entreprise. Cependant, d’importants défis fondamentaux doivent être surmontés avant que ces techniques puissent être largement adoptées dans les applications.

Ce projet cible les deux verrous scientifiques suivants :

1. Passage à l’échelle des algorithmes de réponse aux requêtes

L’efficacité des systèmes de bases de données relationnelles repose sur
des décennies de travaux sur l’algorithmique et l'optimisation des mécanismes de réponse aux requêtes. En revanche, l’interrogation de données en présence d’ontologie est un sujet tout jeune, et malgré des avancées importantes, concernant notamment l’identification de langages d’ontologie intéressants de faible complexité, d'importants travaux restent à accomplir avant de disposer d’algorithmes qui passent à l’échelle.

2. Gestion raisonnée des données incohérentes

Dans les applications traitant de grands volumes de données ou ayant des données issues de plusieurs sources, il y a une forte probabilité pour que l’ensemble de données soit incohérent avec l’ontologie, rendant impuissants les algorithmes d'interrogation classiques (car tout est conséquence d’une contradiction). Des mécanismes de gestion raisonnée des données incohérentes (soit par réparation de la base pour restaurer la cohérence, soit par l’adoption d’une sémantique alternative robuste aux incohérences) sont donc indispensables.

L’objectif principal de ce projet est de répondre à ces défis majeurs en développant de nouveaux algorithmes d'interrogation en présence d'ontologie qui passent à l'échelle ainsi que de nouvelles méthodes pragmatiques pour gérer de façon raisonnée les données incohérentes.

Pour réussir cet objectif ambitieux, le coordinateur a réuni une équipe qui comprend les cinq chercheurs français ayant la plus grande expérience sur l’interrogation de données en présence d’ontologie. Trois contribuent avec leur expérience en logiques de description, qui sous-tendent la plupart des langages d’ontologie (y compris les normes W3C OWL et RDFS), tandis que les deux autres apportent leur expertise sur des langages d’ontologie fondés sur des règles existentielles. Tous jouissent d'une excellente réputation académique. Pour faire le lien avec des applications, l’équipe comprend également un professeur d'anatomie qui développe un logiciel à base d’ontologie pour accéder et visualiser les données des patients, qui servira de cas d’étude. Enfin, l’équipe compte aussi une doctorante dont le sujet de thèse est directement en phase avec les objectifs du projet. Au total, la composition de l'équipe assure un excellent niveau d’implication de jeunes chercheurs et de personnel permanent.

Il mérite d’être souligné que si l’interrogation de données en présence d’ontologie est actuellement un sujet de recherche très actif au niveau international, cette question n'a pas encore attiré beaucoup d'attention en France. En réunissant les meilleurs chercheurs français sur le sujet, ce projet contribue à la formation d'une communauté française autour de ce thème.