zbMATH — the first resource for mathematics

Relational queries computable in polynomial time. (English) Zbl 0612.68086
We characterize the polynomial time computable queries as those expressible in relational calculus plus a least fixed point operator and a total ordering on the universe. We also show that even without the ordering one application of fixed point suffices to express any query expressible with several alternations of fixed point and negation. This proves that the fixed point query hierarchy suggested by Chandra and Harel collapses at the first fixed point level. It is also a general result showing that in finite model theory one application of fixed point suffices.

68P20 Information storage and retrieval of data
03C13 Model theory of finite structures
Full Text: DOI