Ontology-based Data Access: A Study through Disjunctive Datalog, CSP,\n and MMSNP

Abstract

Ontology-based data access is concerned with querying incomplete data sources\nin the presence of domain-specific knowledge provided by an ontology. A central\nnotion in this setting is that of an ontology-mediated query, which is a\ndatabase query coupled with an ontology. In this paper, we study several\nclasses of ontology-mediated queries, where the database queries are given as\nsome form of conjunctive query and the ontologies are formulated in description\nlogics or other relevant fragments of first-order logic, such as the guarded\nfragment and the unary-negation fragment. The contributions of the paper are\nthree-fold. First, we characterize the expressive power of ontology-mediated\nqueries in terms of fragments of disjunctive datalog. Second, we establish\nintimate connections between ontology-mediated queries and constraint\nsatisfaction problems (CSPs) and their logical generalization, MMSNP formulas.\nThird, we exploit these connections to obtain new results regarding (i)\nfirst-order rewritability and datalog-rewritability of ontology-mediated\nqueries, (ii) P/NP dichotomies for ontology-mediated queries, and (iii) the\nquery containment problem for ontology-mediated queries.\n