You are not logged in |
All instances termination of chase is undecidable
- Speaker(s)
- Tomasz Gogacz
- Affiliation
- Uniwersytet Wrocławski
- Date
- May 21, 2014, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
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.
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.
