New techniques for studying set languages, bag languages and aggregate functions

ABSTRACT

We provide new techniques for the analysis of the expressive power of query languages for nested collections. These languages may use set or bag semantics and may be further complicated by the presence of aggregate functions. We exhibit certain classes of graphs and prove that the properties of these graphs that can be tested in such languages are either finite or cofinite. This result settles the conjectures of Grumbach, Milo, and Paredaens that parity test, transitive closure, and balanced binary tree test are not expressible in bag languages like the PTIME fragment of BALG of Grumbach and Milo and BQL of Libkin and Wong. Moreover, it implies that many recursive queries, including simple ones like the test for a chain, cannot be expressed in a nested relational language even when aggregate functions are available. In an attempt to generalize the finite-cofiniteness result, we study the bounded degree property which says that the number of distinct in- and out-degrees in the output of a graph query does not depend on the size of the input if the input is “simple”. We show that such a property implies a number of inexpressibility results in a uniform fashion. We then prove the bounded degree property for the nested relational language.

REFERENCES

• AK90: Serge Abiteboul , Paris Kanellakis, Database theory column, ACM SIGACT News, v.21 n.3, p.9-18, Summer 1990 [doi>10.1145/101368.101370]
• BBW92: Val Tannen , Peter Buneman , Limsoon Wong, Naturally Embedded Query Languages, Proceedings of the 4th International Conference on Database Theory, p.140-154, October 14-16, 1992
• CH82: A. Chandra and D. Harel. Structure and complexity of relational queries. Journal of Computer and System Sciences, 25:99-128, 1982.
• Col90: Latha S. Colby, A recursive algebra for nested relations, Information Systems, v.15 n.5, p.567-582, 1990 [doi>10.1016/0306-4379(90)90029-O]
• CV93: Surajit Chaudhuri, Optimization of real conjunctive queries, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.59-70, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153856]
• CM93: Mariano P. Consens , Alberto O. Mendelzon, Low-complexity aggregation in GraphLog and Datalog, Theoretical Computer Science, v.116 n.1, p.95-116, Aug. 2, 1993
• Fag93: Ronald Fagin, Finite-model theory—a personal perspective, Theoretical Computer Science, v.116 n.1, p.3-31, Aug. 2, 1993
• FSV93: R. Fagin, L. Stockmeyer, and M. Vardi. On monadic NP vs monadic co-NP. In Proceedings of 8th IEEE Conference on Structure in Complexity Theory, pages 19-30, May 1993.
• FSS84: M. Furst, J. Saxe and M. Sipser, Parity, circuits and the polynomial time hierarchy, Math. Systems Theory, 17:13-27, 1984.
• Gai82: H. Gaifman. On local and non-local properties. In Proceedings of the Herbrand Symposium, Logic Colloquium '81, pages 105-135. North Holland, 1982.
• GM93: Stéphane Grumbach , Tova Milo, Towards tractable algebras for bags, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.49-58, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153855]
• Imm87: Neil Immerman, Languages that capture complexity classes, SIAM Journal on Computing, v.16 n.4, p.760-778, Aug. 1987 [doi>10.1137/0216051]
• IPS91: Neil Immerman , Sushant Patnaik , David Stemple, The expressiveness of a family of finite set languages, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.37-52, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113417]
• Joh90: David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• LW94a: Leonid Libkin , Limsoon Wong, Some Properties of Query Languages for Bags, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.97-114, August 30-September 01, 1993
• LW94b: Leonid Libkin , Limsoon Wong, Aggregate Functions, Conservative Extensions, and Linear Orders, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.282-294, August 30-September 01, 1993
• LW94c: Leonid Libkin , Limsoon Wong, Conservativity of nested relational calculi with internal generic functions, Information Processing Letters, v.49 n.6, p.273-280, March 22, 1994 [doi>10.1016/0020-0190(94)90099-X ]
• Par93: J. Paredaens, February 1993. Private communication at Bellcore Collection Types Workshop.
• PG92: Jan Paredaens , Dirk Van Gucht, Converting nested algebra expressions into flat algebra expressions, ACM Transactions on Database Systems (TODS), v.17 n.1, p.65-93, March 1992 [doi>10.1145/128765.128768]
• SS86: H J Schek , M H Scholl, The relational model with relation-valued attributes, Information Systems, v.11 n.2, p.137-147, 1986 [doi>10.1016/0306-4379(86)90003-7]
• ST94: Dan Suciu , Val Breazu-Tannen, A query language for NC, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.167-178, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182610]
• TF86: S. :I. Thomas and P. C. Fischer. Nested relational structures. In Advances in Computing Research: The Theory of Databases, pages 269-307, 1986. JAI Press.
• Won93: Limsoon Wong, Normal forms and conservative properties for query languages over collection types, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.26-36, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153853]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Languages, Theory, Verification