JCJC SIMI 2 - JCJC - SIMI 2 - Science informatique et applications

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

PAGODA

Ontology-based data access (OBDA) is a new paradigm in data management that seeks to exploit the semantic knowledge expressed in ontologies when querying data. In this project, our aim is to develop novel OBDA query answering algorithms with improved scalability and practical methods for handling inconsistent data. <br />

Challenges and Objectives

Before OBDA can be widely adopted in applications, some important foundational challenges need to be addressed. This project is centered on the following two challenges: <br /> <br />Scalability: Modern-day relational database management systems benefit from decades of research on querying algorithms and optimizations. By contrast, ontology-based data access is a young area of study, and despite important recent advances, including the identification of interesting tractable ontology languages, much work remains to be done in designing scalable OBDA query answering algorithms. <br /> <br />Handling data inconsistencies: In real-world applications involving large amounts of data or multiple data sources, it is very likely that the data will be inconsistent with the ontology, rendering standard querying algorithms useless (as everything is entailed from a contradiction). Appropriate mechanisms for dealing with inconsistent data are thus crucial to the successful use of OBDA in practice, yet have been little explored thus far. <br /> <br />The primary aim of this project is to help address these challenges by developing novel OBDA query answering algorithms and practical methods for handling inconsistent data.

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)

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.



Coordinateur du projet

Madame Meghyn BIENVENU (Université Paris Sud / Laboratoire de Recherche en Informatique) – meghyn.bienvenu@labri.fr

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

PSUD/LRI Université Paris Sud / Laboratoire de Recherche en Informatique

Aide de l'ANR 260 312 euros
Début et durée du projet scientifique : décembre 2012 - 48 Mois

Liens utiles