Article contents
The Expressive Power of Higher-Order Datalog
Published online by Cambridge University Press: 20 September 2019
Abstract
A classical result in descriptive complexity theory states that Datalog expresses exactly the class of polynomially computable queries on ordered databases (Papadimitriou 1985; Grädel 1992; Vardi 1982; Immerman 1986; Leivant 1989). 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.
- Type
- Original Article
- Information
- Theory and Practice of Logic Programming , Volume 19 , Special Issue 5-6: 35th International Conference on Logic Programming , September 2019 , pp. 925 - 940
- Copyright
- © Cambridge University Press 2019
References
- 2
- Cited by