All instances termination of chase is undecidable

Prelegent(ci)

Tomasz Gogacz

Afiliacja

Uniwersytet Wrocławski

Termin

21 maja 2014 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

We show that all instances termination of chase is undecidable.
More precisely, there is no algorithm deciding, for a given set T
consisting of Tuple Generating Dependencies (a.k.a. Datalog+/- program), whether the T-chase on D will terminate for every finite database instance D. Our method applies to Oblivious Chase, Semi-Oblivious Chase and after a slight modification also for Standard Chase. This means that we give a (negative) solution to the all  instances termination problem for all version of chase that are usually considered.

---