{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T01:16:07Z","timestamp":1768698967792,"version":"3.49.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2004,6,1]],"date-time":"2004-06-01T00:00:00Z","timestamp":1086048000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2004,6]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1005566.1005568","type":"journal-article","created":{"date-parts":[[2004,7,20]],"date-time":"2004-07-20T16:39:33Z","timestamp":1090341573000},"page":"282-318","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":69,"title":["Expressing and optimizing sequence queries in database systems"],"prefix":"10.1145","volume":"29","author":[{"given":"Reza","family":"Sadri","sequence":"first","affiliation":[{"name":"Procom Technology Inc., Irvine, California, CA"}]},{"given":"Carlo","family":"Zaniolo","sequence":"additional","affiliation":[{"name":"UCLA Computer Science Department, Los Angeles, California, CA"}]},{"given":"Amir","family":"Zarkesh","sequence":"additional","affiliation":[{"name":"3Plus1 Technology, Inc., Saratoga, California, Saratoga, CA"}]},{"given":"Jafar","family":"Adibi","sequence":"additional","affiliation":[{"name":"Information Sciences Institute, USC, Marina del Rey, California, CA"}]}],"member":"320","published-online":{"date-parts":[[2004,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the International Conference on Data Engineering.]]","author":"Agrawal R."},{"key":"e_1_2_1_2_1","unstructured":"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.]]  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.]]"},{"key":"e_1_2_1_3_1","unstructured":"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.]]  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.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_2_1_5_1","unstructured":"Berry M. and Linoff M. 1996. Data Mining Techniques for Marketing Sales and Customer Support. Wiley New York.]]   Berry M. and Linoff M. 1996. Data Mining Techniques for Marketing Sales and Customer Support. Wiley New York.]]"},{"key":"e_1_2_1_6_1","volume-title":"(Eds.)","author":"Boag S.","year":"2003"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"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).]]   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).]]","DOI":"10.1016\/B978-155860869-6\/50027-5"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872857"},{"key":"e_1_2_1_10_1","unstructured":"Edwards R. and Magee J. 1997. Technical Analysis of Stock Trends. AMACOM.]]  Edwards R. and Magee J. 1997. Technical Analysis of Stock Trends. AMACOM.]]"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191925"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375610"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 1st International Conference on Rules in Database Systems.]]","author":"Gatziu S."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 18th International Conference on Very Large Data Bases.]]","author":"Gehani N. H."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.536253"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/232616.232692"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_1_18_1","unstructured":"Informix Software Inc. 1998. Managing time-series data in financial applications. White Paper.]]  Informix Software Inc. 1998. Managing time-series data in financial applications. White Paper.]]"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/42267.42273"},{"key":"e_1_2_1_21_1","first-page":"2","article-title":"Fast pattern matching in strings","volume":"6","author":"Knuth D. E.","year":"1997","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the IEEE Workshop on Visualization and Machine Vision.]]","author":"Mesrobian E."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253359"},{"key":"e_1_2_1_24_1","volume-title":"10th International Conference (DEXA '99)","volume":"1677","author":"Perng C.-S."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.877502"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.1998.688114"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 6th International Conference on Very Large Databases. 64--72","author":"Rosenkrantz D."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/273244.273251"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191926"},{"key":"e_1_2_1_31_1","volume-title":"SEQ: A model for sequence databases. In ICDE. 232--239.]]","author":"Seshadri P.","year":"1995"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.273033"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1989.559764"},{"key":"e_1_2_1_34_1","volume-title":"Principles of Database and Knowledge-Base Systems","author":"Ullman J. D."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 5th Pacific-Asic Conference on Knowledge Discovery and Data Mining (PAKDD)","author":"Wang H."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of 26th International Conference on Very Large Data Bases.]]","author":"Wang H."},{"key":"e_1_2_1_37_1","unstructured":"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\/&sim;cawright\/pattern_matching.html.]]  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\/&sim;cawright\/pattern_matching.html.]]"},{"key":"e_1_2_1_38_1","volume-title":"Tech. Rep. ANSI NCITS H2-99-155, ISO\/IEC JTC1\/SC32 WG3:YGJ-nnn","author":"Zemke F.","year":"1999"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1005566.1005568","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1005566.1005568","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:24:39Z","timestamp":1750263879000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1005566.1005568"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2004,6]]}},"alternative-id":["10.1145\/1005566.1005568"],"URL":"https:\/\/doi.org\/10.1145\/1005566.1005568","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,6]]},"assertion":[{"value":"2004-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}