Logo des Repositoriums
 
Zeitschriftenartikel

All-Instances Restricted Chase Termination for Linear TGDs

Vorschaubild nicht verfügbar

Volltext URI

Dokumententyp

Text/Journal Article

Zusatzinformation

Datum

2020

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Verlag

Springer

Zusammenfassung

The chase procedure is a fundamental algorithmic tool in database theory with a variety of applications. A key problem concerning the chase procedure is all-instances chase termination: for a given set of tuple-generating dependencies (TGDs), is it the case that the chase terminates for every input database? In view of the fact that this problem is, in general, undecidable, it is natural to ask whether well-behaved classes of TGDs, introduced in different contexts, ensure decidability. It has been recently shown that the problem is decidable for the restricted (a.k.a. standard) version of the chase, and linear TGDs, a prominent class of TGDs that has been introduced in the context of ontological query answering, under the assumption that only one atom appears in TGD-heads. We provide an alternative proof for this result based on Monadic Second-Order Logic, which we believe is simpler that the ones obtained from the literature.

Beschreibung

Gogacz, Tomasz; Marcinkowski, Jerzy; Pieris, Andreas (2020): All-Instances Restricted Chase Termination for Linear TGDs. KI - Künstliche Intelligenz: Vol. 34, No. 4. DOI: 10.1007/s13218-020-00690-7. Springer. PISSN: 1610-1987. pp. 465-473

Schlagwörter

Zitierform

Tags