The chase procedure, originally introduced for checking implication of database constraints, and later on used for computing data exchange solutions, has recently become a central algorithmic tool in rule-based ontological reasoning. In this context, a key problem is non-uniform chase termination: does the chase of a database w.r.t. a rule-based ontology terminate? And if this is the case, what is the size of the result of the chase? We focus on guarded tuple-generating dependencies (TGDs), which form a robust rule-based ontology language, and study the above central questions for the semi-oblivious version of the chase. One of our main findings is that non-uniform semi-oblivious chase termination for guarded TGDs is feasible in polynomial time w.r.t.The database, and the size of the result of the chase (whenever is finite) is linear w.r.t.The database. Towards our results concerning non-uniform chase termination, we show that basic techniques such as simplification and linearization, originally introduced in the context of ontological query answering, can be safely applied to the chase termination problem.

Non-Uniformly Terminating Chase: Size and Complexity / M. Calautti, G. Gottlob, A. Pieris - In: PODS '22: Proceedings / [a cura di] L. Libkin, P. Barceló. - [s.l] : ACM, 2022. - ISBN 9781450392600. - pp. 369-378 (( Intervento presentato al 41. convegno Symposium on Principles of Database Systems, PODS tenutosi a Philadelphia nel 2022 [10.1145/3517804.3524146].

Non-Uniformly Terminating Chase: Size and Complexity

M. Calautti
Primo
;
2022

Abstract

The chase procedure, originally introduced for checking implication of database constraints, and later on used for computing data exchange solutions, has recently become a central algorithmic tool in rule-based ontological reasoning. In this context, a key problem is non-uniform chase termination: does the chase of a database w.r.t. a rule-based ontology terminate? And if this is the case, what is the size of the result of the chase? We focus on guarded tuple-generating dependencies (TGDs), which form a robust rule-based ontology language, and study the above central questions for the semi-oblivious version of the chase. One of our main findings is that non-uniform semi-oblivious chase termination for guarded TGDs is feasible in polynomial time w.r.t.The database, and the size of the result of the chase (whenever is finite) is linear w.r.t.The database. Towards our results concerning non-uniform chase termination, we show that basic techniques such as simplification and linearization, originally introduced in the context of ontological query answering, can be safely applied to the chase termination problem.
guardedness; non-uniform termination; semi-oblivious chase procedure; tuple-generating dependencies
Settore INF/01 - Informatica
ACM SIGACT
ACM SIGAI
ACM SIGMOD
Book Part (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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/2434/946595
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact