From Conjunctive Queries to Instance Queries in Ontology-Mediated Querying
We consider ontology-mediated queries (OMQs) based on expressive description logics of the ALC family and (unions) of conjunctive queries, studying the rewritability into OMQs based on instance queries (IQs). Our results include exact characterizations of when such a rewriting is possible and tight complexity bounds for deciding rewritability. We also give a tight complexity bound for the related problem of deciding whether a given MMSNP sentence is equivalent to a CSP.
Code (0)
등록된 구현이 없습니다.
Tasks
SentenceSimilar Papers 제목 키워드 기반
Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP
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, …
NegationTowards Universal Languages for Tractable Ontology Mediated Query Answering
An ontology language for ontology mediated query answering (OMQA-language) is universal for a family of OMQA-languages if it is the most expressive one among this family. In this paper, we focus on three families of trac…
Computing FO-Rewritings in EL in Practice: from Atomic to Conjunctive Queries
A prominent approach to implementing ontology-mediated queries (OMQs) is to rewrite into a first-order query, which is then executed using a conventional SQL database system. We consider the case where the ontology is fo…
Tractable Responsibility Measures for Ontology-Mediated Query Answering
Recent work on quantitative approaches to explaining query answers employs responsibility measures to assign scores to facts in order to quantify their respective contributions to obtaining a given answer. In this paper,…
Ontology-Mediated Querying on Databases of Bounded Cliquewidth
We study the evaluation of ontology-mediated queries (OMQs) on databases of bounded cliquewidth from the viewpoint of parameterized complexity theory. As the ontology language, we consider the description logics $\mathca…