In this paper we study the expressiveness of local queries. By locality we
mean - informally - that in order to check if a tuple belongs to the result
of a query, one only has to look at a certain predetermined portion of the
input. Examples include all relational calculus queries. We start by provi
ng a general result describing outputs of local queries. This result leads
to many easy inexpressibility proofs for local queries. We then consider a
closely related property, namely, the bounded degree property. It describes
the outputs of local queries on structures that locally look "simple." Eve
ry query that is local is shown to have the bounded degree property. Since
every relational calculus (first-order) query is local, the general results
proved for local queries can be viewed as "off-the-shelf" strategies for p
roving inexpressibility results, which are often easier to apply than Ehren
feucht-Fraisse games. We also show that some generalizations of the bounded
degree property that were conjectured to hold, fail for relational calculu
s. We then prove that the language obtained from relational calculus by add
ing grouping and aggregates, which is essentially plain SQL, has the bounde
d degree property, thus answering a question that has been open for several
years. Consequently, first-order queries with Hartig or Rescher quantifier
s also have the bounded degree property. Finally, we apply our results to i
ncremental maintenance of views, and show that SQL and relational calculus
are incapable of maintaining the transitive closure view even in the presen
ce of auxiliary relations of moderate degree. (C) 2000 Published by Elsevie
r Science B.V. All rights reserved.