THE EXPRESSIVENESS OF A FAMILY OF FINITE-SET LANGUAGES

Authors
IMMERMAN N PATNAIK S STEMPLE D
Citation
N. Immerman et al., THE EXPRESSIVENESS OF A FAMILY OF FINITE-SET LANGUAGES, Theoretical computer science, 155(1), 1996, pp. 111-140
Citations number
37
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
155
Issue
1
Year of publication
1996
Pages
111 - 140
Database
ISI
SICI code
0304-3975(1996)155:1<111:TEOAFO>2.0.ZU;2-K
Abstract
In this paper we characterize exactly the complexity of a set-based da tabase language called SRL, which presents a unified framework for que ries and updates. By imposing simple syntactic restrictions on it, we are able to express exactly the classes, P and LOGSPACE. We also discu ss the role of ordering in database query languages and show that the horn operator of Machiavelli language in [Ohori et al. (1989)] does no t capture all the order-independent properties.