There is a growing demand for systems that can detect complex patterns in high-speed streams of events or in large volumes of stored sequences. This demand is driven by so-called complex event processing (CEP) applications whose success depends on their ability to make real-time decisions, such as high-frequency trading, fraud detection, and online advertisement. As a result, several database vendors are providing new SQL extensions to support such applications.
In this talk, we show that these extensions suffer from expressivity limitations that severely impair their generality and effectiveness in practice. To overcome these problems, we present the K*SQL language that extends SQL with minimal, yet powerful constructs that can support a wide range of CEP applications. We show that the recently proposed Nested Word Automata (NWA) provide a natural underlying model for K*SQL, as they extend the power of regular expressions while remaining highly amenable to efficient implementation. Moreover, with its choice of NWA, K*SQL presents itself as a natural solution to the well-known quest of a unified framework for querying both relational and XML data. In the second part of this talk, we focus on some of the challenges and subtleties that are involved in turning a powerful query language such as K*SQL into an efficient CEP system. In particular, we introduce several optimization techniques for complex pattern detection and efficient execution of the underlying NWA, leading to significant performance gains over previous systems.