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 proving 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.''
Every 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 proving
inexpressibility results, which are often easier to apply than
Ehrenfeucht-Fraisse games. We also show that some
generalizations of the bounded degree property that were conjectured
to hold, fail for relational calculus.
We then prove that the language obtained from relational calculus
by adding grouping and aggregates, which is essentially plain SQL,
has the bounded degree property, thus answering
a question that has been open for several years. Consequently,
first-order queries with H\"{a}rtig or Rescher quantifiers also
have the bounded degree property. Finally,
we apply our results to incremental maintenance of views,
and show that SQL and relational calculus are incapable of
maintaining the transitive closure view even in the presence of
auxiliary relations of moderate degree.