The Expressive Power of Higher-Order Datalog. Issue 5 (September 2019) - CHARALAMBIDIS, ANGELOS; NOMIKOS, CHRISTOS; RONDOGIANNIS, PANOS
Abstract: A classical result in descriptive complexity theory states that Datalog expresses exactly the class of polynomially computable queries on ordered databases (Papadimitriou1985 ; Grädel1992 ; Vardi1982 ; Immerman1986 ; Leivant1989 ). In this paper we extend this result to the case of higher-order Datalog. In particular, we demonstrate that on ordered databases, for all k ≥ 2, k -order Datalog captures ( k − 1)-EXPTIME. This result suggests that higher-order extensions of Datalog possess superior expressive power and they are worthwhile of further investigation both in theory and in practice.