Mapping analysis in ontology-based data access: Algorithms and complexity (Discussion paper)

We study the formal analysis of mappings in ontology-based data access (OBDA). Specifically, we focus on the problem of identifying mapping inconsistency and redundancy, two of the most important anomalies for mappings in OBDA. We consider a wide range of ontology languages that comprises OWL 2 and all its profiles, and examine mapping languages of different expressiveness over relational databases. We establish tight complexity bounds for the decision problems associated with mapping inconsistency and redundancy