Ontology-Based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP

Bienvenu, M, ten Cate, B, Lutz, C and Wolter, F (2014) Ontology-Based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP. ACM Transactions on Database Systems, 39 (4). pp. 1-44.

Text subpods12.pdf - Author Accepted Manuscript Download (643kB)

Abstract

Ontology-based data access is concerned with querying incomplete data sources in the presence of domain-specific knowledge provided by an ontology. A central notion in this setting is that of an ontology-mediated query, which is a database query coupled with an ontology. In this article, we study several classes of ontology-mediated queries, where the database queries are given as some form of conjunctive query and the ontologies are formulated in description logics or other relevant fragments of first-order logic, such as the guarded fragment and the unary negation fragment. The contributions of the article are threefold. First, we show that popular ontology-mediated query languages have the same expressive power as natural fragments of disjunctive datalog, and we study the relative succinctness of ontology-mediated queries and disjunctive datalog queries. Second, we establish intimate connections between ontology-mediated queries and constraint satisfaction problems (CSPs) and their logical generalization, MMSNP formulas. Third, we exploit these connections to obtain new results regarding: (i) first-order rewritability and datalog rewritability of ontology-mediated queries; (ii) P/NP dichotomies for ontology-mediated queries; and (iii) the query containment problem for ontology-mediated queries.

Item Type:	Article
Uncontrolled Keywords:	ontology-based data access, query answering, query rewriting
Depositing User:	Symplectic Admin
Date Deposited:	08 Jul 2016 07:58
Last Modified:	19 Jan 2023 07:34
DOI:	10.1145/2661643
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3002146