First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries
We focus on ontology-mediated queries (OMQs) based on (frontier-)guarded existential rules and (unions of) conjunctive queries, and we investigate the problem of FO-rewritability, i.e., whether an OMQ can be rewritten as a first-order query. We adopt two different approaches. The first approach employs standard two-way alternating parity tree automata. Although it does not lead to a tight complexity bound, it provides a transparent solution based on widely known tools. The second approach relies on a sophisticated automata model, known as cost automata. This allows us to show that our problem is 2ExpTime-complete. In both approaches, we provide semantic characterizations of FO-rewritability that are of independent interest.
Code (0)
등록된 구현이 없습니다.
Similar 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, …
NegationDichotomies in Ontology-Mediated Querying with the Guarded Fragment
We study the complexity of ontology-mediated querying when ontologies are formulated in the guarded fragment of first-order logic (GF). Our general aim is to classify the data complexity on the level of ontologies where …
A Complete Classification of the Complexity and Rewritability of Ontology-Mediated Queries based on the Description Logic EL
We provide an ultimately fine-grained analysis of the data complexity and rewritability of ontology-mediated queries (OMQs) based on an EL ontology and a conjunctive query (CQ). Our main results are that every such OMQ i…
General ClassificationFitting Ontologies and Constraints to Relational Structures
We study the problem of fitting ontologies and constraints to positive and negative examples that take the form of a finite relational structure. As ontology and constraint languages, we consider the description logics $…
Temporal Description Logic for Ontology-Based Data Access (Extended Version)
Our aim is to investigate ontology-based data access over temporal data with validity time and ontologies capable of temporal conceptual modelling. To this end, we design a temporal description logic, TQL, that extends t…