We study adding aggregate operators, such as summing up elements of a column of a relation, to logics with counting mechanisms. The primary motivation comes from database applications, where aggregate operators are present in all real life query languages. Unlike other features of query languages, aggregates are not adequately captured by the existing logical formalisms. Consequently, all previous approaches to analyzing the expressive power of aggregation were only capable of producing partial results, depending on the allowed class of aggregate and arithmetic operations.We consider a powerful counting logic, and extend it with the set of all aggregate operators. We show that the resulting logic satisfies analogs of Hanf's and Gaifman's theorems, meaning that it can only express local properties. We consider a database query language that expresses all the standard aggregates found in commercial query languages, and show how it can be translated into the aggregate logic, thereby providing a number of expressivity bounds, that do not depend on a particular class of arithmetic functions, and that subsume all those previously known. We consider a restricted aggregate logic that gives us a tighter capture of database languages, and also use it to show that some questions on expressivity of aggregation cannot be answered without resolving some deep problems in complexity theory.

We study adding aggregate operators, such as summing up elements of a column of a relation, to logics with counting mechanisms. The primary motivation comes from database applications, where aggregate operators are present in all real life query languages. Unlike other features of query languages, aggregates are not adequately captured by the existing logical formalisms. Consequently, all previous approaches to analyzing the expressive power of aggregation were only capable of producing partial results, depending on the allowed class of aggregate and arithmetic operations. We consider a powerful counting logic, and extend it with the set of all aggregate operators. We show that the resulting logic satisfies analogs of Hanf's and Gaifman's theorems, meaning that it can only express local properties. We consider a database query language that expresses all the standard aggregates found in commercial query languages, and show how it can be translated into the aggregate logic, thereby providing a number of expressivity bounds, that do not depend on a particular class of arithmetic functions, and that subsume all those previously known. We consider a restricted aggregate logic that gives us a tighter capture of database languages, end also use it to show that some questions on expressivity of aggregation cannot be answered without resolving some deep problems in complexity theory.

Abstract Many known tools for proving expressibility bounds for first-ordér logic are based on one of several locality properties. In this paper we characterize the relationship between those notions of locality. We note that Gaifman's locality theorem gives rise to two notions: one deals with sentences and one with open formulae. We prove that the former implies Hanf's notion of locality, which in turn implies Gaifman's locality for open formulae. Each of these implies the bounded degree property, which is one of the easiest tools for proving expressibility bounds. These results apply beyond the first-order case. We use them to derive expressibility bounds for first-order logic with unary quantifiers and counting. We also characterize the notions of locality on structures of small degree.

We give a combinatorial method for proving elementary equivalence in first-order logic FO with counting module n quantifiers D/sub n/. Inexpressibility results for FO(D/sub n/) with built-in linear order are also considered. We show that certain divisibility properties of word models are not definable in FO(D/sub n/). We also show that the height of complete n-ary trees cannot be expressed in FO(D/sub n/) with linear order. Interpreting the predicate y=nx as a complete n-ary tree, we show that the predicate y=(n+1)x cannot be defined in FO(D/sub n/) with linear order. This proves the conjecture of Niwinski and Stolboushkin (1993). We also discuss connection between our results and the well-known open problem in circuit complexity theory, whether ACC=NC/sup 1/.

A combinatorial argument for two finite structures to agree on all sentences with bounded quantifier rank in first-order logic with any set of unary generalized quantifiers is given. It is known that connectivity of finite structures is neither in monadic Σ11 nor in ≲ww (Qu), where Qu is the set of all unary generalized quantifiers. Using this combinatorial argument and a combination of second-order Ehrenfeucht-Fraïssé games developed by Ajtai and Fagin, we prove that connectivity of finite structures is not in monadic σ11 with any set of unary quantifiers even if sentences are allowed to contain built-in relations of moderate degree. The combinatorial argument is also used to show that no class (if it is not in some sense trivial) of finite graphs defined by forbidden minors is in ≲ww(Qu). In particular, the class of planar graphs is not in ≲ww(Qu)