All-Instances Termination of Chase is Undecidable

Tomasz Gogacz, Jerzy Marcinkowski

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

The arity we need for our undecidability proof is three. We also show that the problem is EXPSPACE-hard for binary signatures, but decidability for this case is left open.

Both the proofs – for ternary and binary signatures – are easy. Once you know them.
Original languageEnglish
Title of host publicationAutomata, Languages, and Programming
Subtitle of host publication41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II
PublisherSpringer Berlin Heidelberg
Pages293-304
Number of pages12
ISBN (Electronic)978-3-662-43951-7
ISBN (Print)978-3-662-43950-0
DOIs
Publication statusPublished - 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume8573
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'All-Instances Termination of Chase is Undecidable'. Together they form a unique fingerprint.

Cite this