Meghyn Bienvenu and her co-authors, Balder ten Cate, Carsten Lutz, and Frank Wolter, received the Albert O. Mendelzon Test of Time Award for their paper published 10 years ago at the PODS'13 conference. Mendelzon Test of Time Award for the impact of their paper published 10 years ago at the PODS'13 conference: "Ontology-based data access: A study through disjunctive datalog, CSP, and MMSNP".
Ontology-mediated data access is a recent paradigm in data management that aims at exploiting semantic knowledge described by an ontology to improve query answering. A central notion in this context is that of an ontology-mediated query (OMQ), which is a database query coupled with an ontology. In this paper, we study several classes of OMQs that combine conjunctive queries with ontologies formulated in description logics or other relevant fragments of first-order logic. The contributions of this paper are threefold. First, we characterise the expressive power of OMQs in terms of disjunctive datalog fragments. Second, we establish close connections between OMQs and constraint satisfaction problems (CSPs) and their logical generalization, MMSNP formulas. Third, we exploit these connections to obtain new results concerning (i) the existence of rewritings in first-order logic or datalog, (ii) P/NP dichotomies for the evaluation of OMQs, and (iii) the query inclusion problem for OMQs.
Read the article, here.