[Zurück]

S. Ahmetaj, M. Ortiz de la Fuente, M. Simkus:
"Polynomial rewritings from expressive Description Logics with closed predicates to variants of Datalog";
Artificial Intelligence, 280 (2020), 103220; S. 1 - 27.

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 pos-sibly 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 en-
riched 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 ontology-mediated query languages in which the ontology part 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 as failure 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-in the case of querying an 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.

http://dx.doi.org/10.1016/j.artint.2019.103220

https://doi.org/10.1016/j.artint.2019.103220

Projektleitung Mantas Simkus:
KtoAPP

Projektleitung Mantas Simkus:
OMEGA