Nie jesteś zalogowany |
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.
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.
