00000cab a22000003a 4500 UP-99796217608727512 Buklod 20231007234724.0 m |o d | ta 090226s xx d | ||r ||||| || (iLib)UPD-00077096424 DENGII eng Hella, Lauri Logics with aggregate operators. pp. 880-907 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. Theory of computation. Mathematical logic and formal languages. Mathematical logic. Information systems. Database management. Languages. Theory. Journal of the ACM 48, 4 (2001). FO UPD DENG-II Article