The Complexity of Datalog on Linear Orders

DOI10.2168/LMCS-5(1:4)2009zbMATH Open1164.68008arXiv0902.1179OpenAlexW3102391036MaRDI QIDQ3623016

Publication date: 29 April 2009

Published in: (Search for Journal in Brave)

Abstract: We study the program complexity of datalog on both finite and infinite linear orders. Our main result states that on all linear orders with at least two elements, the nonemptiness problem for datalog is EXPTIME-complete. While containment of the nonemptiness problem in EXPTIME is known for finite linear orders and actually for arbitrary finite structures, it is not obvious for infinite linear orders. It sharply contrasts the situation on other infinite structures; for example, the datalog nonemptiness problem on an infinite successor structure is undecidable. We extend our upper bound results to infinite linear orders with constants. As an application, we show that the datalog nonemptiness problem on Allen's interval algebra is EXPTIME-complete.

Full work available at URL: https://arxiv.org/abs/0902.1179

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic programming (68N17)