2013/01/28 by Meghyn Bienvenu, Bienvenu, Meghyn, Balder ten Cate +5 · 4 citations
Computer Science · #Semantic Web and Ontologies #Logic, Reasoning, and Knowledge #Advanced Database Systems and Queries
paper · pdf · doi:10.48550/arxiv.1301.6479
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