Non-linear prefixes in query languages

ABSTRACT

In first order logic there are two main extensions to quantification: generalized quantifiers and non-linear prefixes. While generalized quantifiers have been explored from a database perspective, non-linear prefixes have not-most likely because of complexity concerns. In this paper we first illustrate the usefulness of non-linear prefixes in query languages by means of example queries. We then introduce the subject formally, distinguishing between two forms of non-linearity: branching and cumulation. To escape complexity concerns, we focus on monadic quantifiers. In this context, we show that branching does not extend the expressive power of first order logic when it is interpreted over finite models, while cumulation does not extend the expressive power when it is interpreted over bounded models. Branching and cumulation do, however, allow us to formulate some queries in a succinct and elegant manner. When branching and cumulation are interpreted over infinite models, we show that the resulting language can be embedded in an infinitary logic proposed by Libkin. We also discuss non-linear prefixes from an algorithmic point of view.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Antonio Badia, A family of query languages with generalized quantifiers: its definition, properties and expressiveness, Indiana University, Indianapolis, IN, 1997
• 3: Antonio Badia, Safety, domain independence and generalized quantification, Data Engineering, v.38 n.2, p.147-172, 08/01/2001
• 4: Badia, A. and Cao, B. Processing and Optimization of Generalized Quantification Queries, under submission.
• 5: A. Blass and Y. Gurevich Henkin quantifiers and complete problems, Annals of Pure and Applied Logic, 32(1):1--16, 1986.
• 6: Barwise, J. On Branching Quantifiers in English, Journal of Philosophical Logic, v. 8, 1979, pages 47--80
• 7: Barwise, J. and R. Cooper, Generalized Quantifiers and Natural Language, Linguistic and Philosophy, volume 4, 1981.
• 8: Generalized Quantifiers in Natural Language, van Benthem, J. and ter Meulen, A., eds. Foris Publications, 1985.
• 9: Dawar, A. and Hella, L., The Expressive Power of Finitely Many Generalized Quantifiers, in Proceedings of the 9th IEEE Symposium on Logic In Computer Science, 1994.
• 10: Enderton, H. Finite Partially-Ordered Quantifiers, in Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik, vol. 16 (1970), pp. 393--397.
• 11: Enderton, H. A Mathematical Introduction to Logic, Academic Press, 1972.
• 12: Stéphane Grumbach , Christophe Tollu, Query Languages with Counters, Proceedings of the 4th International Conference on Database Theory, p.124-139, October 14-16, 1992
• 13: Gyssens, M., Van Gucht, D. and Badia, A., Query Languages with Generalized Quantifiers, in Application of Logic Databases, Ramakrishnan, Ragu ed., Kluwer Academic Publishers, 1995.
• 14: Hella, L., Definability Hierarchies of Generalized Quantifiers, Annals of Pure and Applied Logic, volume 43, 1989.
• 15: Hella, L., Luosto, K. and Vaananen, J. The Hierarchy Theorem for Generalized Quantifiers, J. Symbolic Logic, 61(3), p. 802--817, 1996.
• 16: Lauri Hella , Leonid Libkin , Juha Nurmonen , Limsoon Wong, Logics with aggregate operators, Journal of the ACM (JACM), v.48 n.4, p.880-907, July 2001 [doi>10.1145/502090.502100]
• 17: Leon Henkin, Some Remarks on Infinitely Long Formulas, in Infinitistic Methods, Warsaw, 1959, pp. 167--183.
• 18: Heinrich Herre , Michał Krynicki , Alexander Pinus , Jouko Väänänen, The Ha¨rtig quantifier: a survey, Journal of Symbolic Logic, v.56 n.4, p.1153-1183, Dec. 1991 [doi>10.2307/2275466]
• 19: Hintikka, J. Quantifiers vs. Quantification Theory, Linguistic Inquiry, 5(2), 1974, pages 153--177.
• 20: Ping-Yu Hsu , Douglas Stott Parker, Jr., Improving SQL with Generalized Quantifiers, Proceedings of the Eleventh International Conference on Data Engineering, p.298-305, March 06-10, 1995
• 21: Keenan, E. Beyond the Frege Boundary, Linguistics and Philosophy, v. 15, 1992.
• 22: Keenan, E. Natural Language, Sortal Reducibility and Generalized Quantifiers, Journal of Symbolic Logic, v. 58, n. 1, 1993, pages 314--325.
• 23: Keenan, E. and Moss, L., Generalized Quantifiers and the Expressive Power of Natural Language, in {8}.
• 24: Keenan, E. and Westerstahl, D., Generalized Quantifiers in Linguistics and Logic, in {8}.
• 25: Keisler, J. and Walkoe, W. The Diversity of Quantifier Prefixes, Journal of Symbolic Logic, v. 38, pages 79--85, 1973.
• 26: Kolaitis, P. and Väanänen, J., Generalized Quantifiers and Pebble Games on Finite Structures, Annals of Pure and Applied Logic, Elsevier, v. 74, 1995, pages 23--75.
• 27: Leonid Libkin, Expressive power of SQL, Theoretical Computer Science, v.296 n.3, p.379-404, 14 March 2003 [doi>10.1016/S0304-3975(02)00736-3]
• 28: Lindstrom, P., First Order Predicate Logic with Generalized Quantifiers, Theoria, volume 32, 1966.
• 29: Luosto, K. Hierarchies of Monadic Generalized Quantifiers, Journal of Symbolic Logic, 65(3), 2000, pages 1241--1263.
• 30: Mostowski, A., On a Generalization of Quantifiers, Fundamenta Mathematica, volume 44, 1957.
• 31: Pirotte, A., High Level Data Base Query Languages, in Logic and Databases, Gallaire and Minker, eds., Plenum Press, 1978, pages 409--436.
• 32: J. Joachim Quantz, How to fit generalized quantifiers into terminological logics, Proceedings of the 10th European conference on Artificial intelligence, p.543-547, August 1992, Vienna, Austria
• 33: Sudhir G. Rao , Antonio Badia , Dirk van Gucht, Providing better support for a class of decision support queries, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.217-227, June 04-06, 1996, Montreal, Quebec, Canada
• 34: Damianos Chatziantoniou , Kenneth A. Ross, Groupwise Processing of Relational Queries, Proceedings of the 23rd International Conference on Very Large Data Bases, p.476-485, August 25-29, 1997
• 35: Scha, R. Distributive, Collective and Cumulative Quantification, in Truth, Interpretation and Information; selected papers from the 3rd Amsterdam Colloquium, Dordrecht, Holland, 1984, pages 131--158.
• 36: M. Sevenster, Henkin Quantifiers: Logic, Games, and Computation, The bulletin of the EATCS no 89, pages 136--155, June 2006.
• 37: Sher, G. Ways of Branching Quantifiers, Linguistics and Philosophy, v. 13, 1990.
• 38: Spaan, M. Parallel Quantification, in J. van der Does and J. van Eyck (eds.) Generalized Quantifier Theory and Applications, CSLI Lecture Notes, 1993.
• 39: The TPC-H Benchmark, online at http:nnwww.tpc.org.
• 40: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 41: Jouko Väänänen, Unary Quantifiers on Finite Models, Journal of Logic, Language and Information, v.6 n.3, p.275-304, July 1997 [doi>10.1023/A:1008209019899 ]
• 42: Walkoe, W. Finite Partially-Ordered Quantification, Journal of Symbolic Logic, v. 35, n. 4, pages 535--555, 1970.
• 43: Westerstahl, D., Quantifiers in Formal and Natural Languages, in Handbook of Philosophical Logic, volume IV, Gabbay, D. and Guenther, F., eds., Reidel Publishing Company, 1989.
• 44: Westerstahl, D. Iterated Quantifiers, in Dynamics, Polarity and Quantification, Kanazawa and Pinon, eds., CSLI, Stanford University, 1994, pages 173--209.
• 45: Westerstahl, D. Branching Quantifiers and Natural Language, in Garderfons, P. (ed.) Generalized Quantifiers: Linguistic and Logical Approaches, Dordrecht, 1987.

INDEX TERMS

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

General Terms:
Languages, Theory

Keywords:
branching, cumulation, generalized quantifiers, non-linear prefixes