Query rewriting: Limits and possibilities
Meghyn Bienvenu, CNRS (French National Center for Scientific Research)
Abstract: Recent years have seen an increasing interest in ontology-mediated query answering (OMQA), in which the semantic knowledge provided by an ontology is exploited when querying data. Adding an ontology has several advantages (e.g. simplifying query formulation, integrating data from different sources, providing more complete answers to queries), but it also makes the query answering task more difficult. Query rewriting, which reduces OMQA to the evaluation of database queries, allows OMQA to be implemented on top of existing database systems, thereby benefitting from the maturity and performance of such systems.
In this talk, I will first introduce the OMQA problem, focusing on ontologies formulated using description logics (DLs). The rest of the talk will give a brief overview of two recent lines of work aimed at understanding the limits and possibilities of query rewriting in OMQA. The first line of work arose out of the observation that while first-order rewritings always exist for ontologies formulated in DL-Lite (a popular lightweight DL), the rewritings generated by implemented rewriting engines were often prohibitively large. This motivated the study of the following succinctness problem: under what circumstances can polynomial-size rewritings be achieved? If we move to richer ontology languages, it is no longer guaranteed that all ontology-querypairs possess a first-order rewriting, but it may nonetheless be the case that rewritings exist for many of the ontologies and queries encountered in practice. Thus, the second topic that I will discuss is how to devise methods for identifying those ontology-query pairs which admit rewritings.
Biography: Meghyn Bienvenu is a full-time tenured researcher at the CNRS (French National Center for Scientific Research) and a member of the LIRMM computer science laboratory in Montpellier. She carried out her undergraduate studies at the University of Toronto and received her Master's and PhD degrees at Universit? Paul Sabatier (Toulouse, France). She obtained her PhD in 2009 and was awarded the 2010 AFIA Prize for best French dissertation in artificial intelligence. Prior to joining the CNRS, she held a postdoctoral research and teaching position at University Bremen (Germany). Her main topic of interest is knowledge representation and reasoning (KRR), with a current focus on description logic (DL) ontologies and their use in querying data. She is an active member of the DL and KRR research communities and publishes her work in top international conferences and journals in AI and database theory (IJCAI, AAAI, KR, PODS, AIJ, JAIR, TODS). She has served as PC co-chair and general co-chair of the International Workshop on Description Logics (2014, 2016), doctoral consortium co-chair of the KR conference (2016), and tutorial co-chair of IJCAI'18, and is a regular member of the program committees of top international conferences. In 2016, she gave an invited Early Career Spotlight talk at IJCAI and was awarded the CNRS Bronze Medal in the area of Computer Science.