Local properties of query languages

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.