Expressing and optimizing sequence queries in database systems

ABSTRACT

The need to search for complex and recurring patterns in database sequences is shared by many applications. In this paper, we investigate the design and optimization of a query language capable of expressing and supporting efficiently the search for complex sequential patterns in database systems. Thus, we first introduce SQL-TS, an extension of SQL to express these patterns, and then we study how to optimize the queries for this language. We take the optimal text search algorithm of Knuth, Morris and Pratt, and generalize it to handle complex queries on sequences. Our algorithm exploits the interdependencies between the elements of a pattern to minimize repeated passes over the same data. Experimental results on typical sequence queries, such as double bottom queries, confirm that substantial speedups are achieved by our new optimization techniques.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 2: Alur, N., Haas, P., Momiroska, D., Read, P., Summers, N., Totanes, V., and Zuzarte, C. 2002. Db2 UDBS high-function business intelligence in e-business. IBM redbooks, IBM, http://www.redbooks.ibm.com/redbooks/pdfs/sg246546.pdf.
• 3: Arasu, A., Babu, S., and Widom, J. 2002. An abstract semantics and concrete language for continuous queries over streams and relations. Tech. rep., Stanford Univ., Stanford, Calif.
• 4: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 5: Michael J. Berry , Gordon Linoff, Data Mining Techniques: For Marketing, Sales, and Customer Support, John Wiley & Sons, Inc., New York, NY, 1997
• 6: Boag, S., Chamberlin, D., Fernandez, M. F., Florescu, D., Robie, J., and Simeon, J. (Eds.). 2003. Xquery 1.0: An XML query language--working draft 22 august 2003. Working Draft 22 August 2003, W3C, http://www.w3.org/tr/xquery/.
• 7: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 8: Carney, D., Cetintemel, U., Cherniack, M., Convey, C., Lee, S., Seidman, G., Stonebraker, M., Tatbul, N., and Zdonik, S. 2002. Monitoring streams---A new class of data management applications. In VLDB (Hong Kong, China).
• 9: Sirish Chandrasekaran , Owen Cooper , Amol Deshpande , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong , Sailesh Krishnamurthy , Samuel R. Madden , Fred Reiss , Mehul A. Shah, TelegraphCQ: continuous dataflow processing, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872857]
• 10: Edwards, R. and Magee, J. 1997. Technical Analysis of Stock Trends. AMACOM.
• 11: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 12: Paolo Ferragina , Nick Koudas , Divesh Srivastava , S. Muthukrishnan, Two-dimensional substring indexing, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.282-288, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375610]
• 13: Gatziu, S. and Dittrich, K. R. 1993. Events in an object-oriented database system. In Proceedings of the 1st International Conference on Rules in Database Systems.
• 14: Narain H. Gehani , H. V. Jagadish , Oded Shmueli, Composite Event Specification in Active Databases: Model & Implementation, Proceedings of the 18th International Conference on Very Large Data Bases, p.327-338, August 23-27, 1992
• 15: Sha Guo , Wei Sun , Mark A. Weiss, On Satisfiability, Equivalence, and Implication Problems Involving Conjunctive Queries in Database Systems, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.604-616, August 1996 [doi>10.1109/69.536253]
• 16: Sha Guo , Wei Sun , Mark A. Weiss, Solving satisfiability and implication problems in database systems, ACM Transactions on Database Systems (TODS), v.21 n.2, p.270-293, June 1996 [doi>10.1145/232616.232692]
• 17: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 18: Informix Software, Inc. 1998. Managing time-series data in financial applications. White Paper.
• 19: Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
• 20: Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
• 21: Knuth, D. E., Morris, J. H., and Pratt, V. R. 1997. Fast pattern matching in strings. SIAM J. Comput. 6, 2 (June), 323--350.
• 22: Mesrobian, E., Muntz, R., Santos, J., Shek, E., Mechoso, C., Farrara, J., and Stolorz, P. 1994. Extracting spatio-temporal patterns from geoscience datasets. In Proceedings of the IEEE Workshop on Visualization and Machine Vision.
• 23: Iakovos Motakis , Carlo Zaniolo, Temporal aggregation in active database rules, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.440-451, May 11-15, 1997, Tucson, Arizona, United States
• 24: Chang-Shing Perng , Douglas Stott Parker, Jr., SQL/LPP: A Time Series Extension of SQL Based on Limited Patience Patterns, Proceedings of the 10th International Conference on Database and Expert Systems Applications, p.218-227, August 30-September 03, 1999
• 25: Davood Rafiei , Alberto O. Mendelzon, Querying Time Series Data Based on Similarity, IEEE Transactions on Knowledge and Data Engineering, v.12 n.5, p.675-693, September 2000 [doi>10.1109/69.877502]
• 26: Raghu Ramakrishnan , Donko Donjerkovic , Arvind Ranganathan , Kevin S. Beyer , Muralidhar Krishnaprasad, SRQL: Sorted Relational Query Language, Proceedings of the 10th International Conference on Scientific and Statistical Database Management, p.84-95, July 01-03, 1998 [doi>10.1109/SSDM.1998.688114]
• 27: Rosenkrantz, D. and Hunt III, H. B. 1970. Processing conjunctive predicates and queries. In Proceedings of the 6th International Conference on Very Large Databases. 64--72.
• 28: Mohammad Reza Sadri , Carlo Zaniolo, Optimization of sequence queries in database systems, 2001
• 29: Praveen Seshadri, PREDATOR: a resource for database research, ACM SIGMOD Record, v.27 n.1, p.16-20, March 1998 [doi>10.1145/273244.273251]
• 30: Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, Sequence query processing, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.430-441, May 24-27, 1994, Minneapolis, Minnesota, United States
• 31: Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, SEQ: A Model for Sequence Databases, Proceedings of the Eleventh International Conference on Data Engineering, p.232-239, March 06-10, 1995
• 32: W. Sun , C. Yu, Semantic Query Optimization for Tree and Chain Queries, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.136-151, February 1994 [doi>10.1109/69.273033]
• 33: Xian-He Sun , Nabil N. Kamel, Processing Implication on Queries, IEEE Transactions on Software Engineering, v.15 n.10, p.1168-1175, October 1989 [doi>10.1109/TSE.1989.559764]
• 34: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 35: Haixun Wang , Chang-Shing Perng, The S2-Tree: An Index Structure for Subsequence Matching of Spatial Objects, Proceedings of the 5th Pacific-Asia Conference on Knowledge Discovery and Data Mining, p.312-323, April 16-18, 2001
• 36: Haixun Wang , Carlo Zaniolo, Using SQL to Build New Aggregates and Extenders for Object- Relational Systems, Proceedings of the 26th International Conference on Very Large Data Bases, p.166-175, September 10-14, 2000
• 37: Wright, C. A., Cumberland, L., and Feng, Y. 1998. A performance comparison between five string pattern matching algorithms. Technical Report. http://ocean.st.usm.edu/∼cawright/pattern_matching.html.
• 38: Zemke, F., Kulkarni, K., Witkowski, A., and Lyle, B. 1999. Proposal for OLAP functions. Tech. Rep. ANSI NCITS H2-99-155, ISO/IEC JTC1/SC32 WG3:YGJ-nnn, http://ganga.iiml.ac.in/∼bhasker/dmds/99-154.pdf.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Time series analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Languages, Theory

Keywords:
Time series, query optimization, searching, sequences