tailieunhanh - Expressing and Optimizing Sequence Queries in Database Systems

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 howto optimize the queries for this take the optimal text search algorithmof 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 | Expressing and Optimizing Sequence Queries in Database Systems REZA SADRI Procom Technology Inc. Irvine California CARLO ZANIOlO UCLA Computer Science Department Los Angeles California AMIRZARKESH 3Plus1 Technology Inc. Saratoga California and JAFAR ADIBI Information Sciences Institute USC Marina del Rey California 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. Categories and Subject Descriptors Database Management Languages query languages Database Management Systems query processing General Terms Algorithms Theory Languages Additional Key Words and Phrases Time series sequences query optimization searching 1. INTRODUCTION Many applications require processing and analyzing sequential data to detect pattern and trends of interest. Examples include the analysis of stock This work was partially supported by the National Science Foundation under grant IIS-0070135. Authors addresses R. Sadri Procom Technology Inc. 58 Discovery Irvine CA 92618 email sadri@ C. Zaniolo CSDept. UCLA Los Angeles CA 90095 email zaniolo@ A. Zarkesh 3Plus1 Technology Inc. 18809 Cox Avenue Suite 250 Saratoga CA 95070 email azarkesh@ J. Adibi ISI USC 4676 .