Providing better support for a class of decision support queries

ABSTRACT

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.

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.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Theory