We provide a rewriting technique of Warded Datalog+/− settings to sustain decidability and data tractability of reasoning tasks in the presence of existential quantification and recursion. To achieve this behaviour in practice, reasoners implement specialized strategies which exploit the theoretical bases of the language to control the effects of recursion, ensuring reasoning termination with small memory footprint. However, as a necessary condition for such exploitation, the setting is required to be in a “normalized form”, essentially without joins on variables affected by existential quantification. We present the Harmful Join Elimination, a normalization algorithm of Warded Datalog+/− that removes such “harmful” joins, supporting the tractability of the reasoning task as well as the full expressive power of the language. The algorithm is integrated in the Vadalog system, a Warded Datalog+/− -based reasoner that performs ontological reasoning in complex scenarios.

Baldazzi, T., Bellomarini, L., Sallinger, E., Atzeni, P. (2021). Eliminating Harmful Joins in Warded Datalog+/−. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.267-275). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-91167-6_18].

Eliminating Harmful Joins in Warded Datalog+/−

Baldazzi T.;Bellomarini L.;Atzeni P.
2021-01-01

Abstract

We provide a rewriting technique of Warded Datalog+/− settings to sustain decidability and data tractability of reasoning tasks in the presence of existential quantification and recursion. To achieve this behaviour in practice, reasoners implement specialized strategies which exploit the theoretical bases of the language to control the effects of recursion, ensuring reasoning termination with small memory footprint. However, as a necessary condition for such exploitation, the setting is required to be in a “normalized form”, essentially without joins on variables affected by existential quantification. We present the Harmful Join Elimination, a normalization algorithm of Warded Datalog+/− that removes such “harmful” joins, supporting the tractability of the reasoning task as well as the full expressive power of the language. The algorithm is integrated in the Vadalog system, a Warded Datalog+/− -based reasoner that performs ontological reasoning in complex scenarios.
2021
978-3-030-91166-9
Baldazzi, T., Bellomarini, L., Sallinger, E., Atzeni, P. (2021). Eliminating Harmful Joins in Warded Datalog+/−. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.267-275). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-91167-6_18].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/404520
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 2
social impact