Many applications in commercial and scientific domains share the need for processing and analyzing of sequential or stream data. Examples include data from sensor networks, stock market data, telecommunications data, and earthquake data. Sometimes, the only feasible way to make sense of large volumes of data is to search for patterns of interest. This is especially difficult when the patterns of interest are complex. Traditional constructs available in SQL can’t express these rich patterns. Facilities like datablades have increased the expressive power of database query languages, but still there are applications that need a more expressive language for describing their patterns of interest. Another limitation of most of these applications is that data is processed on the fly and there is a limited buffer for keeping the history of the time-series; therefore, we are in need of an implementation of the pattern detection mechanism that isn’t bound to keeping the whole history of the sequence.

In this work, we investigate the design and optimization of constructs that enable SQL to express complex patterns. Our proposed algorithm exploits the inter-dependencies between the elements of a sequential pattern to minimize repeated passes over the same data. Currently, we are investigating how to employ our search mechanism to search in graphs and multimedia data.