The expressiveness of a family of finite set languages
Neil Immerman, Sushant Patnaik, David W. Stemple · 1991
In this paper we characterise exactly the complexity of a set based database language called SRL, which presents a unified framework for queries and updates.By imposing simple synt act ic restrictions on it, we are able to express exactly the classes, P and L OGSPA CE.We also discuss the role of ordering in database query languages and show that the hom operator of Machiavelli language in [OBB89]does not capture all the order-independent properties.Complexity