Relational database systems do not effectively support complex queries containing quantifiers (quantified queries) that are increasingly becoming important in decision support applications. Generalized quantifiers provide an effective way of expressing such queries naturally. In this paper, we consider the problem of processing quantified queries within the generalized quantifier framework. We demonstrate that current relational systems are ill-equipped, both at the language and at the query processing level, to deal with such queries. We also provide insights into the intrinsic difficulties associated with processing such queries. We then describe the implementation of a quantified query processor, Q²P, that is based on multidimensional and boolean matrix structures. We provide results of performance experiments run on Q²P that demonstrate superior performance on quantified queries. Our results indicate that it is feasible to augment relational systems with query subsystems like Q²P for significant performance benefits for quantified queries in decision support applications.

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BADIA, A., GYSSENS, M., AND VAN GUCHT, D. Query Languages with Generalized Quan~fiers. In Applications o/Logic Databases, R. Ramakrishnan, Ed. Kluwer Academic Publishers, 1995, pp. 235-258.
	2	BARWISE, J., AND COOPER, 1~. Generalized Quantifiers and Natural Language. In Linguistic and Philosophy (1981), pp. 159-219.
	3	BRAUNWALD, E., J.ISSELBACHER, K., G.PETERSDORF, R., WILSON, J. D., MARTIN, j. B., AND S.FAUCI, A., Eds. Harrison's Principles of internal Medicine, 11 ed. McGraw Hill Book Company, 1987.
	4	John V. Carlis, HAS, a Relational Algebra Operator or Divide is not Enough to Conquer, Proceedings of the Second International Conference on Data Engineering, p.254-261, February 05-07, 1986
	5	R. G. G. Cattell , Douglas K. Barry , Dirk Bartels , Mark Berler , Jeff Eastman , Sophie Gamerman , David Jordan , Adam Springer , Henry Strickland , Drew Wade, The object database standard: ODMG 2.0, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
	6	Surajit Chaudhuri , Kyuseok Shim, Including Group-By in Query Optimization, Proceedings of the 20th International Conference on Very Large Data Bases, p.354-366, September 12-15, 1994
	7	M. Dadashzadeh, An improved division operator for relational algebra, Information Systems, v.14 n.5, p.431-437, 1989  [doi>10.1016/0306-4379(89)90007-0]
	8	Umeshwar Dayal, Processing queries with quantifiers a horticultural approach, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia  [doi>10.1145/588058.588075]
	9	Umeshwar Dayal, Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers, Proceedings of the 13th International Conference on Very Large Data Bases, p.197-208, September 01-04, 1987
	10	David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	11	EXODUS. Using the EXODUS Storage Manager V3.0. unpublished'included in the EXODUS Storage Manager Software Release.
	12	Database Research: Achievements and Opportunities Into the 21st Century. Report of an NSF Workshop on the Future of Database Systems Research, May, 1995. Avi Silberschatz, Mike Stonebraker, Jeff Ullman, editors.
	13	Richard A. Ganski , Harry K. T. Wong, Optimization of nested SQL queries revisited, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.23-33, May 27-29, 1987, San Francisco, California, United States
	14	Goetz Graefe, Relational Division: Four Algorithms and Their Performance, Proceedings of the Fifth International Conference on Data Engineering, p.94-101, February 06-10, 1989
	15	Patrick O'Neil , Goetz Graefe, Multi-table joins through bitmapped join indices, ACM SIGMOD Record, v.24 n.3, p.8-11, Sept. 1995  [doi>10.1145/211990.212001]
	16	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
	17	INTERNATIONAL ORGANIZATION OF STANDARDIZATION (ISO). Database Language SQL. Document ISO/IEC 9075:1992.
	18	Hongjun Lu , Hock Chuan Chan , Kwok Kee Wei, A survey on usage of SQL, ACM SIGMOD Record, v.22 n.4, p.60-65, Dec. 1993  [doi>10.1145/166635.166656]
	19	J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984  [doi>10.1145/348.318586]
	20	Ekow J. Otoo, A multidimensional digital hashing scheme for files with composite keys, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.214-229, May 1985, Austin, Texas, United States
	21	G. Ozsoyoglu , H. Wang, A Relational Calculus with Set Operators, Its Safety, and Equivalent Graphical Languages, IEEE Transactions on Software Engineering, v.15 n.9, p.1038-1052, September 1989  [doi>10.1109/32.31363 ]
	22	Hamid Pirahesh , Joseph M. Hellerstein , Waqar Hasan, Extensible/rule based query rewrite optimization in Starburst, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.39-48, June 02-05, 1992, San Diego, California, United States
	23	RAMAKRISHNAN, R., SESHADRI, P., SRIVASTAVA, D., AND SUDARSHAN, S. The CORAL User Manual: A Tutorial Introduction to CORAL. Computer Science Department, University of Wisconsin-Madison, available via anonymous ftp from ftp. cs. wise. edu in the directory coral/doe., Software Release.
	24	I~AO, S. G., BADIA, A., AND VAN GUCHT, D. Processing Queries Containing Generalized Quantifiers. Technical Report 428, Indiana University, April 1995.
	25	RAO, S. G., BADIA, A., AND VAN GUCHT, D. Efficient Processing Support for Quantified Queries. Technical Report 452, Indiana University, February 1996.
	26	Arie Shoshani , Harry K. T. Wong, Statistical and scientific database issues, IEEE Transactions on Software Engineering, v.11 n.10, p.1040-1047, Oct. 1985  [doi>10.1109/TSE.1985.231851]
	27	SYBASE, INC. Interactive Query Accelerator- Too Much Data, Not Enough Information. Sybase White Papers, available on the web as of March 11, 1996 at ht tp: / /www. syb as e. corn / t o c. ht mI.
	28	TRANSACTION PROCESSING COUNCIL (TPC). TPC BenchmarkTM D (Decision Support) Standard Specification, May 1995. Revision 1.0.
	29	WESTERSTAHL, D. Quantifiers in Formal and Natural Languages. In Handbook of Philosophical Logic, D. Gabbay and F. Guenthner, Eds. D. Reidel Publishing Company, 1989, pp. 1-131.

• Constructing reality Proceedings of the 11th annual international conference on Systems documentation
  Douglas A. Powell ,  Norman R. Ball ,  Mansel W. Griffiths
  
  
• Data structures for quadtree approximation and compression Communications of the ACM   28, 9
  Hanan Samet
  
  
• A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
  Kim S. Lee ,  Huizhu Lu ,  D. D. Fisher
  
  
• An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
  Gwo-Dong Chen ,  Daniel D. Gajski
  
  
• The GemStone object database management system Communications of the ACM   34, 10
  Paul Butterworth ,  Allen Otis ,  Jacob Stein
  
  

• International Conference on Management of Data
  Proceedings of the 1996 ACM SIGMOD international conference on Management of data
  
  1996 , Montreal, Quebec, Canada