Polynomial rewritings from expressive description logics with closed predicates to variants of Datalog

DOI10.1016/J.ARTINT.2019.103220MaRDI QIDQ2302291zbMATH OpenOpenAlexWikidataFDO

Authors Shqiponja Ahmetaj, Magdalena Ortiz, Mantas Šimkus

Publication date 26 February 2020

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.07475

zbMATH Keywords

closed predicatesDatalogdescription logicsontology-mediated query answeringquery rewritingrelative expressivenesssuccinctness

Mathematics Subject Classification ID

Logic programming (68N17) Database theory (68P15) Logic in artificial intelligence (68T27) Knowledge representation (68T30)

Abstract: In many scenarios, complete and incomplete information coexist. For this reason, the knowledge representation and database communities have long shown interest in simultaneously supporting the closed- and the open-world views when reasoning about logic theories. Here we consider the setting of querying possibly incomplete data using logic theories, formalized as the evaluation of an ontology-mediated query (OMQ) that pairs a query with a theory, sometimes called an ontology, expressing background knowledge. This can be further enriched by specifying a set of closed predicates from the theory that are to be interpreted under the closed-world assumption, while the rest are interpreted with the open-world view. In this way we can retrieve more precise answers to queries by leveraging the partial completeness of the data. The central goal of this paper is to understand the relative expressiveness of OMQ languages in which the ontology is written in the expressive Description Logic (DL) ALCHOI and includes a set of closed predicates. We consider a restricted class of conjunctive queries. Our main result is to show that every query in this non-monotonic query language can be translated in polynomial time into Datalog with negation under the stable model semantics. To overcome the challenge that Datalog has no direct means to express the existential quantification present in ALCHOI, we define a two-player game that characterizes the satisfaction of the ontology, and design a Datalog query that can decide the existence of a winning strategy for the game. If there are no closed predicates, that is in the case of querying a plain ALCHOI knowledge base, our translation yields a positive disjunctive Datalog program of polynomial size. To the best of our knowledge, unlike previous translations for related fragments with expressive (non-Horn) DLs, these are the first polynomial time translations.

Recommendations

• Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
• On the relative expressiveness of description logics and predicate logics
• Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics (Invited Talk).
• scientific article; zbMATH DE number 2090542
• Tractable reasoning with DL-programs over Datalog-rewritable description logics
• Circumscribing DATALOG: expressive power and complexity
• Datalog rewritability of disjunctive Datalog programs and non-Horn ontologies
• Reasoning in description logics by a reduction to disjunctive datalog

Cites work

• Answering regular path queries in expressive description logics via alternating tree-automata
• Capturing missing tuples and missing values
• Combining answer set programming with description logics for the semantic web
• Combining decidability paradigms for existential rules
• Conjunctive query answering in the description logic \(\mathcal S \mathcal H\) using knots
• Data complexity of query answering in description logics
• Datalog rewritability of disjunctive Datalog programs and non-Horn ontologies
• scientific article; zbMATH DE number 67503 (Why is no real title available?)
• Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP
• Ontology-Mediated Query Answering with Data-Tractable Description Logics
• Polynomial rewritings from expressive description logics with closed predicates to variants of Datalog
• Query answering with DBoxes is hard
• Querying visible and invisible information
• Reasoning in description logics by a reduction to disjunctive datalog
• Reconciling description logics and rules
• Regular path queries in lightweight description logics: complexity and algorithms
• Rewriting guarded existential rules into small Datalog programs
• Rewriting Guarded Negation Queries
• The Complexity of Conjunctive Query Answering in Expressive Description Logics
• The data complexity of ontology-mediated queries with closed predicates
• The Description Logic Handbook
• The price of query rewriting in ontology-based data access
• Tractable query answering and rewriting under description logic constraints
• Tractable reasoning and efficient query answering in description logics: The DL-Lite family

Cited in

(8)

• Closed-world semantics for conjunctive queries with negation over \(\mathcal{ELH}_\bot\) ontologies
• Polynomial rewritings from expressive description logics with closed predicates to variants of Datalog
• Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics (Invited Talk).
• Fragments of Bag Relational Algebra: Expressiveness and Certain Answers
• The data complexity of ontology-mediated queries with closed predicates
• Temporal Minimal-World Query Answering over Sparse ABoxes
• Datalog rewritability and data complexity of \(\mathcal{ALCHOIQ}\) with closed predicates
• Query answering in circumscribed OWL2 profiles

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: Polynomial rewritings from expressive description logics with closed predicates to variants of Datalog

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2302291)