Logics with aggregate operators

Abstract

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.

References

1. ABITEBOUL, S., HULL, R., AND VIANU, V. 1995. Foundations of Databases. Addison-Wesley, Reading, Mass.]]
2. ABITEBOUL, S., AND VIANU, V. 1995. Computing with first-order logic. J. Comput. Syst. Sci. 50, 309-335.]]
3. ALLENDER, E. 1996. Circuit complexity before the dawn of the new millennium. In Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS'96). Lecture Notes in Computer Science, vol. 1180. Springer-Verlag, New York, pp. 1-18.]]
4. BARRINGTON, D. M., IMMERMAN, N., AND STRAUBING, H. 1990. On uniformity within NC 1 .J. Comput. Syst. Sci. 41, 274-306.]]
5. BUNEMAN, P., NAQVI, S., TANNEN,V.,AND WONG, L. 1995. Principles of programming with complex objects and collection types. Theoret. Comput. Sci. 149, 1, (Sept.) 3-8.]]
6. CABIBBO, L., AND TORLONE, R. A framework for the investigation of aggregate functions in database queries. In International Conference on Data Base Theory 1999. Lecture Notes in Computer Science, vol. 1540. Springer-Verlag, New York, pp. 383-397.]]
7. CAI, J., FURER, M., AND IMMERMAN, N. 1992. On optimal lower bound on the number of variables for graph identification. Combinatorica 12, 389-410.]]
8. COHEN, S., NUTT,W.,AND SEREBRENIK, A. 1999. Rewriting aggregate queries using views. In Proceedings of the 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM, New York, pp. 155-166.]]
9. CONSENS, M., AND MENDELZON, A. 1993. Low complexity aggregation in GraphLog and Datalog, Theoret. Comput. Sci. 116, 95-116.]]
10. DONG, G., LIBKIN, L., AND WONG, L. 2000. Local properties of query languages. Theoret. Comput. Sci. 239, 277-308.]]
11. EBBINGHAUS, H.-D., AND FLUM, J. 1995. Finite Model Theory. Springer-Verlag, New York.]]
12. ETESSAMI, K. 1997. Counting quantifiers, successor relations, and logarithmic space. J. Comput. Syst. Sci. 54, 400-411.]]
13. FAGIN, R., STOCKMEYER, L., AND VARDI, M. 1995. On monadic NP vs monadic co-NP. Inf. Comput. 120, 78-92.]]
14. FEGARAS, L., AND MAIER, D. 1995. Towards an effective calculus for object query languages. In Proceedings of ACM SIGMOD'95 (San Jose, Calif., May 22-75). ACM, New York, pp. 47-58.]]
15. GAIFMAN, H. 1982. On local and non-local properties. In Proceedings of the Herbrand Symposium, Logic Colloquium '81. North-Holland, Amsterdam, The Netherlands.]]
16. GRADEL, E., AND GUREVICH, Y. 1998. Metafinite model theory. Inf. Comput. 140, 26-81.]]
17. GRUMBACH, S., RAFANELLI, M., AND TINININI, L. 1999. Querying aggregate data. In Proceedings of the 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM, New York, pp. 174-184.]]
18. HANF, W. 1965. Model-theoretic methods in the study of elementary logic. In The Theory of Models. J.W. Addison et al, Eds. North Holland, Amsterdam, The Netherlands, pp. 132-145.]]
19. HELLA, L. 1996. Logical hierarchies in PTIME. Inf. Comput. 129, 1-19.]]
20. HELLA, L., LIBKIN, L., AND NURMONEN, J. 1999. Notions of locality and their logical characterizations over finite models. J. Symb. Logic. 64, 1751-1773.]]
21. IMMERMAN, N. 1986. Relational queries computable in polynomial time. Inf. Contr. 68, 86-104.]]
22. IMMERMAN, N. 1999. Descriptive Complexity. Springer-Verlag, New York.]]
23. IMMERMAN, N. 1987. Languages that capture complexity classes. SIAM J. Comput. 16, 760-778.]]
24. IMMERMAN, N., AND LANDER, E. 1990. Describing graphs: A first-order approach to graph canonization. In Complexity Theory Retrospective. Springer-Verlag, Berlin, Germany.]]
25. KLUG, A. 1982. Equivalence of relational algebra and relational calculus query languages having aggregate functions. J. ACM 29, 699-717.]]
26. KOLAITIS,PH., VARDI, M. 1992. Infinitary logic and 0-1 laws. Inf. Comput. 98, 258-294.]]
27. LELLAHI, K., AND TANNEN, V. 1997. A calculus for collections and aggregates. In Proceedings of the Category Theory in Computer Science. Lecture Notes in Computer Science, vol. 1290. Springererlag, New York, pp. 261-280.]]
28. LIBKIN, L. 1997. On the forms of locality over finite models. In Proceedings of the 12th IEEE Symposium on Logic in Computer Science (LICS'97) (Warsaw, Poland, June-July). IEEE Computer Society Press, Los Alamitos, Calif., pp. 204-215.]]
29. LIBKIN, L. 2000. Logics with counting and local properties. ACM Trans. Comput. Logic 1, 33-59.]]
30. LIBKIN, L., AND WONG, L. 1994. Aggregate functions, conservative extensions, and linear orders. In Proceedings of the Database Programming Languages 1993. Springer-Verlag, New York, pp. 282-294.]]
31. LIBKIN, L., WONG, L. 1997a. Query languages for bags and aggregate functions. J. Comput. Syst. Sci. 55, 241-272.]]
32. LIBKIN, L., AND WONG, L. 1997b. On the power of aggregation in relational query languages. In Proceedings of Database Programming Languages 1997. Lecture Notes in Computer Science, vol. 1369. Springer-Verlag, New York, pp. 260-280.]]
33. MUMICK, I. S., PIRAHESH, H., AND RAMAKRISHNAN, R. 1990. Magic of duplicates and aggregates. In Proceedings of the Conference on Very Large Databases. 264-277.]]
34. MUMICK,I.S.,AND SHMUELI, O. 1995. How expressive is stratified aggregation? Ann. Math. AI 15, 407-435.]]
35. NURMONEN, J. 1996. On winning strategies with unary quantifiers. J. Logic Comput. 6, 779-798.]]
36. OTTO, M. 1997. Bounded Variable Logics and Counting: A Study in Finite Models. Springer- Verlag, New York.]]
37. ROSS, K., AND SAGIV, Y. 1992. Monotonic aggregation in deductive databases. In Proceedings of the 11th ACMSIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (San Diego, Calif., June 2-4). ACM, New York, pp. 114-126.]]
38. ROSS, K., SRIVASTAVA, D., STUCKEY,P.,AND SUDARSHAN, S. 1998. Foundations of aggregation constraints.Theoret. Comput. Sci. 193, 149-179.]]
39. ULLMAN, J. 1988. Principles of Database and Knowledge-Base Systems. Computer Science Press Rockville, Md.]]
40. VAN GELDER, A. 1992. The well-founded semantics of aggregation. In Proceedings of the 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (San Diego, Calif., June 2-4). ACM, New York, pp. 127-138.]]
41. VARDI, M. 1982. The complexity of relational query languages. In Proceedings of the 14th ACM Symposium on Theory of Computing. ACM, New York, pp. 137-146.]]
42. WONG, L. 1996. Normal forms and conservative properties for query languages over collection types. J. Comput. Syst. Sci. 52, 1 (June), 495-505.]]

Index Terms

• Information systems

  • Data management systems

    • Query languages

• Theory of computation

  • Logic

  • Models of computation

    • Computability

  • Theory and algorithms for application domains

    • Database theory

      • Database query languages (principles)